Алгоритм Саймона¶

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

¶Постановка задачи

Задача, решаемая алгоритмом Саймона, формулируется следующим образом. Дана функция \( f: \{0,1\}^n \to \{0,1\}^n \), которая является оракулом (то есть доступна для вычисления, но её внутреннее устройство неизвестно). Известно, что функция обладает свойством: существует строка \( s \in \{0,1\}^n \), такая что для любых различных \( x, y \in \{0,1\}^n \) выполняется: \[ f(x) = f(y) \iff x \oplus y \in \{0, s\}, \] где \( \oplus \) обозначает побитовое сложение по модулю 2 (XOR). Иными словами, функция является двух-к-одной (за исключением случая \( s = 0 \), когда она становится однозначной) и имеет скрытый период \( s \). Цель алгоритма — найти \( s \) с минимальным числом обращений к оракулу.

Классическое решение этой задачи требует \( \Omega(2^{n/2}) \) запросов к функции, так как необходимо найти коллизию — пару различных входов, дающих одинаковый выход. Алгоритм Саймона решает её за \( O(n) \) запросов, что экспоненциально быстрее.

¶История

Алгоритм был предложен Дэниелом Саймоном в 1994 году в работе «On the Power of Quantum Computation» (опубликована в 1997 году в журнале SIAM Journal on Computing). Саймон исследовал возможности квантовых вычислений в контексте задач, связанных с поиском скрытых подгрупп. Его работа стала важным шагом в развитии квантовой теории сложности, показав, что существуют задачи, для которых квантовые алгоритмы дают экспоненциальное ускорение. В том же году Питер Шор представил свой знаменитый алгоритм факторизации, который использует аналогичные идеи, но для более сложной группы — целых чисел по модулю.

¶Описание алгоритма

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

¶Квантовая часть

1. Подготовка начального состояния. Имеется два регистра по \( n \) кубитов каждый. Начальное состояние:

\[ |0\rangle^{\otimes n} |0\rangle^{\otimes n}. \]

1. Применение преобразования Адамара. К первому регистру применяется преобразование Адамара \( H^{\otimes n} \), что переводит его в равномерную суперпозицию всех \( 2^n \) возможных состояний:

\[ \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle |0\rangle. \]

1. Запрос к оракулу. Оракул \( U_f \) вычисляет значение функции \( f(x) \) и записывает его во второй регистр:

\[ \frac{1}{\sqrt{2^n}} \sum_{x \in \{0,1\}^n} |x\rangle |f(x)\rangle. \]

1. Измерение второго регистра. После измерения второго регистра получается некоторое значение \( f(x_0) \). Первый регистр коллапсирует в суперпозицию двух состояний, которые дают это значение: \( |x_0\rangle \) и \( |x_0 \oplus s\rangle \):

\[ \frac{1}{\sqrt{2}} (|x_0\rangle + |x_0 \oplus s\rangle). \]

1. Применение преобразования Адамара. К первому регистру снова применяется \( H^{\otimes n} \). В результате получается состояние:

\[ \frac{1}{\sqrt{2^{n+1}}} \sum_{y \in \{0,1\}^n} \left[ (-1)^{x_0 \cdot y} + (-1)^{(x_0 \oplus s) \cdot y} \right] |y\rangle, \] где \( \cdot \) обозначает скалярное произведение по модулю 2. Амплитуда для \( y \) равна нулю, если \( s \cdot y = 1 \), и отлична от нуля, если \( s \cdot y = 0 \).

1. Измерение первого регистра. Измерение даёт случайный вектор \( y \), такой что \( s \cdot y = 0 \). Этот вектор является линейным уравнением относительно \( s \).

¶Классическая часть

Квантовая процедура повторяется \( O(n) \) раз (обычно \( n-1 \) раз достаточно). В результате накапливается система линейных уравнений: \[ s \cdot y_1 = 0, \quad s \cdot y_2 = 0, \quad \dots, \quad s \cdot y_k = 0. \] Классический компьютер решает эту систему методом Гаусса над полем \( GF(2) \). Если полученные уравнения линейно независимы, то из них находится \( s \). Если \( s = 0 \) (функция однозначна), то все уравнения тривиальны, и алгоритм выдаёт нулевой вектор.

¶Сложность и эффективность

Квантовая часть алгоритма требует \( O(n) \) запросов к оракулу. Классическая часть требует \( O(n^3) \) операций для решения системы уравнений (или \( O(n^2) \) при использовании эффективных методов). Таким образом, общая временная сложность составляет \( O(n^3) \), что экспоненциально меньше классического \( \Omega(2^{n/2}) \).

Важно отметить, что алгоритм является вероятностным: существует вероятность получить линейно зависимые уравнения, что потребует дополнительных итераций. Однако вероятность успеха после \( n-1 \) итераций составляет не менее \( 1/4 \), и её можно увеличить повторением.

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

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

• Теоретическая основа. Алгоритм является частным случаем задачи о скрытой подгруппе (Hidden Subgroup Problem, HSP) для группы \( \mathbb{Z}_2^n \). Он демонстрирует, как квантовые компьютеры могут эффективно решать задачи, связанные с поиском скрытых структур.
• Вдохновение для алгоритма Шора. Алгоритм Шора для факторизации чисел и дискретного логарифмирования использует аналогичные методы, но для группы \( \mathbb{Z}_N \) (целые числа по модулю). Без алгоритма Саймона разработка алгоритма Шора была бы менее вероятной.
• Демонстрация квантового превосходства. Алгоритм Саймона стал одним из первых доказательств того, что квантовые вычисления могут давать экспоненциальное ускорение для определённых задач, что стимулировало дальнейшие исследования в этой области.
• Образовательная ценность. Алгоритм часто используется в учебных курсах по квантовым вычислениям как простой и наглядный пример работы квантовых алгоритмов.

¶Критика и ограничения

Несмотря на теоретическую значимость, алгоритм Саймона имеет ряд ограничений:

• Зависимость от оракула. Алгоритм предполагает, что функция \( f \) задана в виде оракула, то есть доступна для квантового запроса. В реальных задачах такая функция может быть неизвестна или сложна для реализации.
• Ограниченная применимость. Задача нахождения периода для произвольной функции редко встречается на практике. Алгоритм не решает более общие задачи, такие как поиск коллизий в криптографических хеш-функциях.
• Требования к квантовому компьютеру. Для реализации алгоритма требуется квантовый компьютер с \( 2n \) кубитами и возможностью выполнения многокубитных гейтов. На современных квантовых устройствах (с ограниченным числом кубитов и высоким уровнем шума) алгоритм может быть реализован только для малых \( n \).

¶Экспериментальная реализация

Алгоритм Саймона был экспериментально реализован на различных квантовых платформах, включая ионные ловушки, сверхпроводящие кубиты и фотонные системы. Первая реализация была выполнена в 2003 году группой исследователей из Массачусетского технологического института (MIT) на ядерном магнитном резонансе (ЯМР) для \( n=2 \). В последующие годы алгоритм был реализован для \( n=3 \) и \( n=4 \), демонстрируя принципиальную работоспособность квантовых вычислений.

¶Источники

• Simon, D. R. (1997). On the Power of Quantum Computation. SIAM Journal on Computing, 26(5), 1474–1483.
• Nielsen, M. A., & Chuang, I. L. (2010). Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press.
• Childs, A. M., & van Dam, W. (2010). Quantum algorithms for algebraic problems. Reviews of Modern Physics, 82(1), 1–52.
• Brassard, G., & Høyer, P. (1997). An exact quantum polynomial-time algorithm for Simon's problem. Proceedings of the Fifth Israeli Symposium on Theory of Computing and Systems, 12–23.