Первый пример квантового алгоритма, взламывающего криптографию
Квантовые вычисления стали известны, когда Питер Шор представил свой алгоритм, способный эффективно разлагать числа на множители.
Это вызвало бурю негодования в сфере ИТ-безопасности, потому что современная асимметричная криптография предполагает, что факторизация больших чисел практически невозможна. Таким образом, этот алгоритм угрожает шифрованию, которое мы используем сегодня, и делает уязвимыми все наши секреты.
Однако алгоритм Шора не был первым, кто взломал шифрование. Это был алгоритм Бернштейна-Вазирани. Более того, это жизненно важный предшественник и строительный блок для понимания алгоритма Шора.
Алгоритм Бернштейна-Вазирани идентифицирует секретную двоичную строку за один проход (см. этот пост). Для этой задачи классическому алгоритму потребуется n шагов, где n — количество цифр в строке (см. этот пост).
Алгоритм Бернштейна-Вазирани состоит из пяти частей, как показано на следующем рисунке:
- набор кубитов в суперпозиции в состоянии |+⟩, где каждый кубит представляет цифру.
- вспомогательный кубит в состоянии |−⟩.
- квантовый оракул, представляющий секретный ключ
- вывод кубитов из суперпозиции
- измерение кубитов
Если вы новичок в квантовых вычислениях, первая часть уже может быть вам сложна для понимания: ряд кубитов в суперпозиции. Но это основная концепция, которую вам необходимо понять, чтобы освоить любую квантовую схему.
Кубит — это двумерная система, как показано на следующем рисунке. Полюса визуализации представляют базовые состояния |0⟩ и |1⟩. Стрелка — вектор квантового состояния. Близости к полюсам (базовым состояниям) обозначают амплитуды, квадраты которых представляют собой вероятности измерения кубита как 0 или 1. Проще говоря, чем ближе вектор квантового состояния к базовому состоянию |1⟩, тем выше вероятность измерения кубита как единицы.
Эта линейная комбинация приближений векторов базисного состояния кубита к |0⟩ и |1⟩ обозначает квантовую суперпозицию.
В случае алгоритма Бернштейна-Вазирани мы помещаем кубит в определенное состояние: |+⟩. В этом состоянии близости к обоим базовым состояниям равны. Таким образом, вероятность измерения одного из двух исходов равна 0,5.
Мы достигаем этого состояния, применяя вентиль Адамара к кубиту в состоянии |0⟩.
Вторая часть — это вспомогательный кубит в состоянии |−⟩. Это состояние почти равно состоянию |+⟩, потому что здесь также равны близости к обоим базовым состояниям. Таким образом, вероятность измерения одного из двух исходов также равна 0,5.
Но если мы посмотрим на состояние кубита графически, то увидим, что оно указывает в направлении, противоположном вектору состояния |+⟩.
Мы достигаем состояния |−⟩, применяя вентиль Адамара к кубиту в состоянии |1⟩.
Между прочим, мы определили важные эффекты ворот Адамара на кубиты. Он превращает состояние |0⟩ в |+⟩ и |1⟩ в |−⟩. Кроме того, и это станет важным на шаге 4, все меняется на противоположное. Таким образом, если применить вентиль Адамара к кубиту в состоянии |+⟩, он вернется в состояние |0⟩. Наконец, применение его к кубиту в состоянии |−⟩ переводит его в состояние |1⟩.
Если мы пока пропустим шаг 3 и сразу посмотрим на шаг 4, мы увидим, что мы снова применяем вентили Адамара ко всем кубитам. Поэтому мы перемещаем их из их состояний |+⟩ и |−⟩ и возвращаем в базовые состояния |0⟩ и |1⟩. Если мы измерим их на шаге 5, пока они находятся в таком базовом состоянии, случайность больше не будет задействована. Если мы измеряем кубит в состоянии |0⟩, мы всегда получаем 0. Если мы измеряем кубит в состоянии |1⟩, мы всегда получаем 1.
Теперь вернемся к шагу 3. Здесь мы используем квантовый оракул, реализующий секретную строку, которую мы хотим идентифицировать. Например, предположим, что наша секретная двоичная строка равна 101 (читается справа налево).
Мы ничего не делаем с кубитом, представляющим 0 в двоичной строке. Вместо этого мы добавляем вентиль «управляемое НЕ» для каждой единицы в двоичной строке. Здесь мы используем кубит в позиции, представляющей цифру, как управляющий кубит, а вспомогательный кубит — как кубит назначения.
Ворота управляемого НЕ имеют два эффекта. Во-первых, он инвертирует амплитуды вектора состояния целевого кубита. Поскольку в состоянии |−⟩ вспомогательного бита амплитуды обоих базовых состояний равны, этим эффектом можно пренебречь.
Во-вторых, он копирует фазу целевого кубита в контрольный кубит. Это называется фазовой отдачей. Фаза отличает состояние |+⟩ от состояния |−⟩. Несмотря на то, что эти состояния имеют одинаковые амплитуды состояний, тем не менее они различны.
И мы уже узнали выше, как проявляется эта разница. Ворота Адамара превращают |+⟩ в |0⟩ и |−⟩ в |1⟩.
Таким образом, поскольку вспомогательный бит, который служит целевым битом, находится в состоянии |−⟩, логический элемент «управляемое НЕ» переключает управляющий бит с |+⟩ на |−⟩.
Таким образом, вентили Адамара на шаге 4 переворачивают управляющие кубиты с |−⟩ на |1⟩. Но они ничего не делают с этими кубитами, оставшимися в |+⟩. Они снова становятся |0⟩.
Когда мы, наконец, измерим кубиты, они откроют секретную двоичную строку.
Алгоритм Бернштейна-Вазирани не получил такого признания, как алгоритм Шора. Тем не менее, он был первым, кто показал, как квантовый компьютер может ускорить обнаружение секретной строки, например, используемой для шифрования.
Не пропустите следующий выпуск и подпишитесь на мой Substack channel.
Хотите начать работу с квантовым машинным обучением? Взгляните на Практическое обучение квантовому машинному обучению с помощью Python.
Получите первые три главы бесплатно здесь.
