Квантовый алгоритм Шора

Квантовый алгоритм Шора — это квантовый алгоритм, предназначенный для разложения целого числа на простые множители (факторизации) за полиномиальное время. Разработанный в 1994 году американским математиком Питером Шором, алгоритм решает задачу, которая считается вычислительно сложной для классических компьютеров, и представляет собой один из наиболее значимых примеров демонстрации превосходства квантовых вычислений над классическими. Ключевая особенность алгоритма — его способность эффективно находить период некоторой периодической функции с помощью квантового преобразования Фурье, что и позволяет факторизовать большие числа.

История создания

Предпосылки и контекст

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

В 1994 году Питер Шор, работавший тогда в Bell Labs, опубликовал статью «Algorithms for quantum computation: discrete logarithms and factoring» (Алгоритмы для квантовых вычислений: дискретные логарифмы и факторизация). В этой работе он впервые представил квантовый алгоритм, который мог бы факторизовать число за время, полиномиально зависящее от его длины. Это открытие стало одним из ключевых стимулов для развития квантовых вычислений, так как показало их практическую применимость для взлома широко используемых криптографических систем.

Развитие и реализация

Первые экспериментальные реализации алгоритма Шора были выполнены на небольших квантовых компьютерах. В 2001 году группа учёных из IBM и Стэнфордского университета под руководством Айзека Чуанга реализовала алгоритм на 7-кубитном ядерном магнитном резонансе (ЯМР) квантовом компьютере, успешно разложив число 15 на множители 3 и 5. С тех пор алгоритм был реализован на различных квантовых платформах, включая сверхпроводящие кубиты, ионные ловушки и фотонные системы, с постепенным увеличением размера факторизуемых чисел (например, 21, 35, 143).

Принцип работы

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

Сведение к задаче поиска периода

Для данного числа \( N \), которое требуется разложить на множители, выбирается случайное число \( a \), такое что \( 1 < a < N \) и \( \gcd(a, N) = 1 \). Рассматривается функция: \[ f(x) = a^x \mod N \] Эта функция является периодической. Её период \( r \) — это наименьшее положительное целое число, такое что \( a^r \equiv 1 \pmod{N} \). Если период \( r \) найден, то с высокой вероятностью можно получить нетривиальные делители \( N \):

• Если \( r \) чётное, то \( a^{r/2} - 1 \) и \( a^{r/2} + 1 \) имеют общие делители с \( N \).
• Вычисляя \( \gcd(a^{r/2} - 1, N) \) и \( \gcd(a^{r/2} + 1, N) \), можно получить простые множители \( N \).

Нахождение периода \( r \) на классическом компьютере требует экспоненциального времени. Квантовый алгоритм Шора позволяет найти его за полиномиальное время.

Квантовая часть: поиск периода

Квантовая часть алгоритма использует два регистра кубитов:

1. Первый регистр (счётный) содержит \( n \) кубитов, где \( n \approx \log_2 N \). Он используется для представления суперпозиции всех возможных значений \( x \) от 0 до \( 2^n - 1 \).
2. Второй регистр (функциональный) содержит \( m \) кубитов, достаточных для хранения значений \( f(x) \).

Основные шаги квантовой части:

1. Инициализация: Первый регистр приводится в состояние равномерной суперпозиции всех \( 2^n \) состояний с помощью преобразования Адамара.
2. Вычисление функции: Вычисляется значение \( f(x) = a^x \mod N \) для каждого \( x \) в суперпозиции, и результат записывается во второй регистр. После этого состояния первого и второго регистров становятся запутанными.
3. Квантовое преобразование Фурье (QFT): Применяется к первому регистру. Это преобразование переводит амплитуды состояний в частотное представление. В результате, состояния с одинаковой частотой (соответствующей периоду \( r \)) интерферируют конструктивно, а остальные — деструктивно.
4. Измерение: Измеряется первый регистр. С высокой вероятностью результатом будет число, близкое к \( \frac{k \cdot 2^n}{r} \) для некоторого целого \( k \). Из этого результата с помощью цепной дроби восстанавливается период \( r \).

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

Если полученный период \( r \) является чётным и \( a^{r/2} \not\equiv -1 \pmod{N} \), то вычисляются \( \gcd(a^{r/2} - 1, N) \) и \( \gcd(a^{r/2} + 1, N) \), которые и дают нетривиальные делители \( N \). Если \( r \) нечётное или \( a^{r/2} \equiv -1 \pmod{N} \), алгоритм повторяется с другим случайным \( a \).

Вычислительная сложность

Классические алгоритмы факторизации, такие как общий метод решета числового поля (GNFS), имеют субэкспоненциальную сложность, которая для числа \( N \) оценивается как \( O\left( \exp\left( ( \sqrt[3]{\frac{64}{9}} + o(1) ) (\ln N)^{1/3} (\ln \ln N)^{2/3} \right) \right) \). Это делает факторизацию чисел длиной 2048 бит практически невозможной на современных классических компьютерах.

Квантовый алгоритм Шора имеет полиномиальную сложность: \( O((\log N)^2 (\log \log N) (\log \log \log N)) \) для числа кубитов и \( O((\log N)^3) \) для времени выполнения. Это означает, что с ростом размера числа \( N \) время, требуемое для его факторизации, растёт значительно медленнее, чем для классических алгоритмов.

Применение и значение

Криптография

Наиболее известное применение алгоритма Шора — взлом криптосистем с открытым ключом, основанных на сложности факторизации и дискретного логарифмирования. К ним относятся:

• RSA: Безопасность RSA основана на сложности факторизации. Алгоритм Шора позволяет эффективно разложить модуль RSA, тем самым восстановив закрытый ключ.
• Криптосистема Эль-Гамаля и DSA: Безопасность этих схем основана на сложности задачи дискретного логарифмирования. Алгоритм Шора может быть адаптирован для решения и этой задачи, что делает эти системы уязвимыми.
• Криптография на эллиптических кривых (ECC): Хотя ECC не основана на факторизации, существуют квантовые алгоритмы (например, алгоритм Шора для дискретного логарифмирования на эллиптических кривых), которые также могут её взломать.

Постквантовая криптография

Угроза, которую представляет алгоритм Шора, стимулировала активное развитие постквантовой криптографии — области, занимающейся созданием криптографических систем, устойчивых к атакам с использованием квантовых компьютеров. Национальный институт стандартов и технологий США (NIST) проводит конкурс по стандартизации постквантовых криптоалгоритмов, в котором уже отобраны несколько кандидатов, основанных на решётках, кодах, хэш-функциях и многомерных квадратичных уравнениях.

Научное значение

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

Текущее состояние и ограничения

Несмотря на теоретическую эффективность, практическая реализация алгоритма Шора для чисел, используемых в современной криптографии (например, 2048-битных), сталкивается с серьёзными техническими ограничениями:

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

На данный момент (2024 год) самый большой экспериментально факторизованный с помощью алгоритма Шора (с использованием квантового компьютера) является число 21 (3×7) на сверхпроводящем процессоре в 2012 году. Факторизация числа 143 (11×13) была выполнена с использованием гибридного подхода, где часть вычислений выполнялась классически. Факторизация чисел, представляющих реальную криптографическую угрозу, остаётся задачей будущего.

Интересные факты

• Алгоритм Шора решает не только задачу факторизации, но и задачу дискретного логарифмирования, что делает его универсальным инструментом для взлома многих криптосистем.
• Открытие алгоритма Шора привело к созданию Национального института стандартов и технологий США (NIST) программы по постквантовой криптографии.
• В 2019 году Google заявила о достижении «квантового превосходства» с помощью процессора Sycamore, решив задачу, которая считается сложной для классических компьютеров. Однако эта задача не была факторизацией, а была специально подобранной задачей для демонстрации возможностей квантового компьютера.

Источники

• Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. Proceedings 35th Annual Symposium on Foundations of Computer Science.
• Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.
• Vandersypen, L. M. K., et al. (2001). Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature, 414(6866), 883–887.
• Monz, T., et al. (2016). Realization of a scalable Shor algorithm. Science, 351(6277), 1068–1070.
• NIST. (2016). Post-Quantum Cryptography Standardization.