Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
является суперпозицией М ~ ш/г состояний при значениях ж, взятых с
периодом г. Следует отметить, что смещение du множества значений х
зависит от величины и, полученной при изменении регистра у.
Теперь необходимо определить периодичность состояния в регистре ж. Для
этого необходимо последовательно осуществить преобразова-
(35)
М-1
(36)
1Нет необходимости в обязательном измерении регистра у. Однако данное
действие упрощает описание.
72
Глава 7
У
148) -132) -116>- . . . lo>-t_L;
Рис. 11. Эволюция квантового состояния, соответствующая алгоритму Шора.
Схематично квантовое состояние показано посредством определения ненулевых
требований к суперпозиции. Таким образом, общее состояние '^cXty\x)\y)
изображается закрашенным квадратом в тех точках с координатами (х, у),
для которых сХ)У ф 0. Рис. а) соответствует уравнению (35), Ь) -
уравнению (38)
ние Фурье и измерение состояния. Используемое дискретное преобразование
Фурье описывается следующей единичной процедурой
0) 116) 132) 148) 164) 180) 196) 1112) *
У ' 148) -
Ь)
132) -
116)
|0>
|0> 116) 132) 148) 164) 180) 196) j 112) х
(37)
Отметим, что уравнение (34) является примером данной процедуры,
примененной к начальному состоянию |0). Основой для квантовой сети,
необходимой для реализации преобразования Г/у#, служит алгоритм
7.2. Алгоритм поиска периода функции. Алгоритм Шора
73
быстрого преобразования Фурье (Fast Fourie Transform, см., например,
Knuth 1981). Вариант данного алгоритма, применимый к квантовым
вычислениям, был независимо разработан Копперсмитом (Coppersmith 1994) и
Дойчем (Deutsch 1994). Его точное изложение можно также найти у Екерта и
Джозса (1996), Баренцо (1996)2. Для перехода от уравнения (36) к
преобразованию Ugg- необходимо сделать упрощающее задачу предположение о
том, что оз делится на г без остатка, т. е. М = = оз jr. Данное
ограничение не искажает сути, однако при отказе от него необходимо
учитывать некоторые дополнительные детали (Shor 1994, 1995, Ekert and
Jozsa 1996).
Поскольку больше нет необходимости обращаться к регистру у, будем
учитывать только состояние регистра х, определяемое уравнением (36).
Данное состояние проиллюстрировано на рис. lib. Заключительное состояние
регистра х теперь измерено и можно заметить, что полученное значение
кратно оз/r. Остается лишь определить величину периода г. Имеем х = Л
оз/r, где Л - неизвестная величина. Если Лиг не имеют общего множителя,
то нужно привести х/оз к несократимой дроби и, таким образом, определить
Лиг. Если же Л и г имеют общий множитель, что маловероятно при больших
значениях г, то необходимо еще раз повторить все шаги алгоритма. Можно
показать, что вероятность успешного решения задачи после числа
повторений, не больше (а, как правило, гораздо меньше) log г, как угодно
близка к 1 (Ekert and Jozsa 1996).
2 Для осуществления точного квантового преобразования Фурье могут
потребоваться операторы вращения соответственно экспоненциально точно
зависящие от п. Их использование позволяет достичь эффективности решения,
совпадающей с эффективностью алгоритма Шора. Однако использование
приближенного варианта преобразования Фурье будет достаточным (Вагепсо
et. al. 1996).
U> / 7* - 1
(38)
где
1, если к кратно оз/г
О, во всех остальных случаях.
(39)
74
Глава 7
Квантовый алгоритм нахождения периода функции, описанный выше, может
считаться эффективным, если преобразование Uf, при котором определяются
значения функции f(x), не является сложным. Общее количество необходимых
логических гейтов полиномиально, а не экспоненциально зависит от п. Как
подчеркивалось в разделе 3.2, в этом состоит главное отличие, при
достаточно больших п, между разрешимыми и неразрешимыми задачами.
Для полноты описания необходимо отметить, что имеющая большое значение
задача разложения на множители, которая была отмечена в разделе 3.2,
может быть сведена к задаче нахождения периода простой функции. Эти и
вышеуказанные сведения были впервые объединены Шором (1994). Таким
образом, он показал, что задача разложения на множители может быть
разрешена с помощью идеального квантового компьютера. В данном случае
определяемая функция имеет вид f(x) = ах mod N, где N - число, которое
требуется разложить на множители. Значение а берется произвольно, причем
а < N. Опираясь на элементарную теорию чисел, можно показать, что при
любом а период г является четным числом, а величина аг/2±1 имеет общий
множитель с N. Теперь данный общий множитель (который, разумеется, есть
множитель N) может быть легко найден посредством классического алгоритма
Евклида (около 300 лет до н.э., см., например, Харди и Райт (Hardy and
Wright 1965)).
Для эффектного вычисления функции f(x) используется повторяющееся
возведение в квадрат (по модулю N): ((а2)2)2 • • • Затем данные степени,
соответствующие двоичному разложению величины а, перемножаются. Полная
сеть гейтов, необходимая для реализации алгоритма Шора, описана Микуэлем
