Почему квантовые вычисления превосходят классические

Классическая криптография

Криптография как наука способна обеспечить конфиденциальность передачи данных, проверку целостности аутентификации пользователей. В качестве развлекательного примера ученый предложил рассмотреть протокол аутентификации.

Он задал аудитории вопрос, какой выбрать способ, чтобы узнать легален ли пользователь, ведь в мире компьютеров пароль можно вводить многократно. Даже при ограниченном числе попыток, пользователь может прийти повторно с другого IP-адреса или представиться иным именем, попытаться взломать пароль путем многократных подборов.

Когда сервисы говорят, что пароль ненадежен, это неслучайно. Короткий шифр легко набирается путем перебора, поэтому рекомендуется создавать длинные пароли и использовать символы.

Насколько устойчив ваш пароль?

Выделяют две группы протоколов. Первая — протоколы симметричной криптографии, когда у двух участников есть секретный ключ и с его помощью они могут шифровать или дешифровать передаваемые сообщения. Это надежная техника. Единственная проблема: ключ надо распределить каким-то образом, то есть обеспечить секретность ключа у участников обмена, говорит Александр Васильев.

В асимметричной криптографии используют открытый и закрытый ключ. В этом случае в основе протоколов часто лежат задачи односторонней функции. Например, перемножить два простых числа легко, а вот обратная задача считается сложной, поскольку тяжело разложить произведение двух простых чисел на множители, которые заранее неизвестны. Александр Васильев объясняет:

— Функции, лежащие в основе асимметричной криптографии, — это односторонние функции, которые легко вычислить и сложно обратить. Строго доказать существование односторонних функций пока не удается. Мы предполагаем, что они сложные, так как неизвестны эффективные способы их вычисления. Стойкость таких протоколов становится условной. Либо мы верим, что такие алгоритмы не существуют, либо понимаем, что у атакующего не хватает вычислительных ресурсов, чтобы взломать протокол. Здесь уместно перейти к квантовой криптографии и квантовым вычислениям. Именно они могут взломать подобные протоколы.

Квантовый параллелизм

Переходя к разговору о квантовой криптографии ученый отметил, что единицу квантовой информации называют кубит. Если классический бит информации может находится в двух состояниях: 0 и 1, то в противоположность ему квантовые биты одновременно находятся в суперпозиции своих состояний. Они могут одновременно быть и 0, и 1 с некоторыми амплитудами альфа и бета. Они могут задаваться в произвольной точке, которая интерпретирует состояние квантового бита, и находится на сфере Блоха.

Александр Васильев сравнил кубит с летящей в воздухе монетой:

— Монета летит в воздухе и крутится, и вы не знаете, как она упадет — орлом или решкой. Но как только вы поймаете ее, она окажется в одном из двух состояний.

Похожая ситуация и с квантовым битом. Пока кубит участвует в процессе преобразований, вычислениях, он находится в произвольной позиции, точнее, одновременно в одном из базовых своих состояний: 0 или 1. Как только его измерят, то спроецируют на одно из базовых состояний. Такова особенность квантовой формации.

Благодаря тому, что квантовый бит может быть и 0, и 1, появляется понятие квантового параллелизма. Вычисляя некоторую функцию, аргумент которой задается квантовыми битами, аргументы одновременно принимают все свои возможные значения. И вычисляя эту функцию на аргументах, вычисляются все аргументы сразу. Это и есть квантовый параллелизм, который во многих случаях обеспечивает преимущества квантовых вычислений.

Квантовый компьютер за 15 млн долларов

Классический пример и простая иллюстрация квантовых вычислений — это алгоритм Дойча-Йожи. Интерпретировать этот алгоритм Александр Васильев предлагает следующим образом:

— Как узнать, фальшивая монета или настоящая? Как это можно проверить? Мы смотрим на монету с одной стороны, переворачиваем на другую и видим, что она фальшивая или настоящая. В квантовом случае мы можем создать суперпозицию состояния монеты, посмотреть на нее один раз и сразу узнать, фальшивая она или нет.

Настоящий значимый пример превосходства квантовых вычислений перед классическими обнаружили в 1994 году. В этот год Питер Шор предложил эффективный алгоритм разложения числа на множители. Это стало бы возможным, если бы был создан квантовый компьютер и тогда можно было бы взламывать соответствующие протоколы.

По словам Александра Васильева, все не так плохо, поскольку квантовых компьютеров еще нет, а как только появился алгоритм Питера Шора, криптография шагнула еще дальше и возникла постквантовая криптография. Подобная криптография работает в предположении, что квантовые компьютеры уже есть. Строятся протоколы устойчивые к квантовым компьютерам. Область квантовой криптографии сама представляет протоколы о защите информации.

Впрочем, не стоит лукавить, квантовые компьютеры есть. Правда, стоят они 15 млн долларов, покупают такие машины для исследовательских целей Google, NASA. И все же это не самый универсальный квантовый компьютер, на котором можно рассчитать алгоритм Шора. По словам Александра Васильева, компьютер настроен на вычисление оптимизационных задач и работает по принципу имитации квантового отжига.

В квантовой информации есть ряд особенностей, которые вызывают большой интерес у ученых. Их интересует процесс измерения квантовой информации. Считывание классической информации не составляет труда.

— Если же квантовый бит находится в суперпозиции квантовых состояний, то процесс детектирования измерений схлопывает его в одно из базовых состояний с соответствующими вероятностями. Самое главное то, что суперпозиция разрушается при воздействии измерения. Как только мы пытаемся читать информацию, она пропадает. И важно правильно ее считать. Квантовая информация может быть телепортирована, но не может быть клонирована, — утверждает Александр Васильев.

Квантовую информацию нельзя клонировать

Протокол квантовой телепортации существует, когда при помощи некоторых дополнительных преобразований обеспечивается появление состояния на другой стороне без передачи физического носителя. Между тем, клонировать квантовую информацию в отличие от классической нельзя.

— Если у вас есть квантовый бит в неизвестном состоянии, то нет возможности создать копию этого неизвестного квантового состояния. Если вы его не знаете, то не сможете клонировать, — замечает ученый.

Такие особенности подходят для создания криптографических протоколов. Например, известный протокол распределения ключа появился еще в 1984 году и с тех пор неоднократно модифицировался и совершенствовался. Протокол обеспечивает появление секретного ключа у двух получателей. В процессе его формирования один из участников передает квантовые состояния, переворачивая их различным образом. От того, в каком базисе будет производиться измерение будет зависеть, что будет получать второй участник.

Хакер, решивший перехватить передающиеся квантовые состояния, то есть попытавшийся их измерить, выдаст себя. Он разрушит состояние, которое ему передавали. И появится возможность детектировать его вмешательство в канал. Есть еще ряд криптографических протоколов, которые появлялись в этой области. Они демонстрируются экспериментально. В 2016 году на базе Казанского квантового центра запустили четырехузловую сеть для распределения ключа. Такие сети запускают по всему миру, а протокол внедряется в практику.

Стойкость квантовой криптографии

Александр Васильев рассказал о таком протоколе, как квантовая цифровая подпись, являющимся аналогом рукописной подписи. Квантовый аналог использует квантовые биты вместо классических и протокол также демонстрируется экспериментально. Запускать его в массовое использование или в широкое применение пока не приходится.

Следы квантовых вычислений — тоже интересный протокол, который также демонстрируется экспериментально. На базе крупной лаборатории квантового вычислителя простейшие клиенты могут создавать кубиты и отправлять их на сервер. Протокол обеспечивает неосведомленность сервера о том, что он делал, с какими данными и что получил на выходе. Для него это становится шумом, что обеспечивается средствами квантовых вычислений.

— Я намерено не вдаюсь в подробности, потому что протоколы квантовых вычислений и квантовой криптографии содержат много математики, и абстрактной алгебры, и теории вероятности, и математическую статистику. Многие разделы математики привлекаются для обоснования протоколов. Я уже говорил вначале, когда мы говорим о стойкости протокола в классической криптографии, то предполагаем, что вычислительные возможности злоумышленника или атакующего ограничены. Это является необходимым условием стойкости наших протоколов. Если они не ограниченны, то протокол взламывается. Стойкость квантовой криптографии обеспечивает постулат: законы природы выполняются.