Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
*Q Г Г Г
• • •
N/r N/r N/r N/r %
• • •
(*)
(О
Рис. 4.7. Графическое представление периодических амплитуд (а) состояния |\|/), и его преобразования Фурье. После применения Э к |vj/) период г превратился в N/r, а случайный сдвиг х0 исчез.
Если мы теперь измерим квантовое состояние | у/), то получим вектор под номером с, который обязательно будет кратен N/r, то есть, c = XN!г. Тогда можно записать
?=-• (416)
N г
где с и N - известные нам числа, а значения 0<Я<г-1с равной вероятностью могли быть случайно выбраны в эксперименте (поскольку все амплитуды в состоянии ^vy) одинаковы по величине). Теперь, если случайно выбранное число Я оказалось взаимно простым с г, (то есть', у них нет общих множителей) то мы можем найти г, сократив дробь c/N до несократимой. Какова вероятность, что случайно выбранное Я окажется взаимно простым с г? Согласно теореме о простом числе (см. [142, 143] и Приложение А в [144]), количество простых чисел, не превышающих г, растет как r/logr при больших г. Таким образом, вероятность того, что наше случайно выбранное число Я окажется взаимно простым с г, равна, по меньшей мере, 1/log г, что больше, чем 1/logTV. Следовательно, если мы повторим описанную выше процедуру 0(log N) раз, то сможем определить г с любой наперед заданной точностью (1-г), насколько угодно близкой единице.
Как было отмечено выше, мы хотим, чтобы нашему квантовому алгоритму для определения г требовалось для работы poly (log N)
154 Концепция квантовых вычислений
шагов - то есть, число шагов, полиномиальное по log N, а не по самому N. Тогда он будет экспоненциально быстрее, чем любой известный классический алгоритм для определения периодичности. Выше мы показали, что для определения г достаточно 0(log N) повторений, но в наших доводах все еще остается большой пробел: преобразование Фурье !7, которое мы использовали, - это большая унитарная операция, размера NxN, и мы не можем изначально предполагать, что ее можно осуществить всего лишь за poly (log N) базовых вычислительных шагов. Можно показать, что любую унитарную операцию размера dxd можно осуществить на квантовом компьютере за 0(d2) шагов [124, 144]. Это также и число шагов, необходимое классическому компьютеру для умножения матрицы размера dxd на d-мерный вектор. В нашем случае вычисления ?7, эта граница 0(N2) неудовлетворительна. К счастью, у преобразования Фурье есть некоторые специфические дополнительные свойства, которые позволяют осуществить его за 0((log N)2) шагов. Эти свойства вытекают из классической теории быстрого преобразования Фурье (БПФ) [145], которая показывает, как уменьшить число в 0(N2) шагов, нужных для матричного умножения, до 0(N log N) шагов. Если применить те же самые идеи в квантовом случае, то можно увидеть [134,144], как принцип локальных операций позволяет свести число шагов к 0((log N)2), что нам и было необходимо. Отметив этот важный момент, мы опустим многочисленные технические детали конструкции БПФ и его применения в квантовом случае. Эти детали разработаны в работе [134], к которой мы отсылаем заинтересованного читателя. Отметим также, что, согласно (4.14),
так что, имея эффективную реализацию U-, мы сможем эффективно создать большое равномерное распределение, чтобы получить |/) в
Итак, квантовый алгоритм для определения периода функции /, с N кубитами на входе, начинается с применения квантового параллельного вычисления, чтобы вычислить все значения/ в равной суперпозиции за 0(log N) шагов. Затем применяется преобразование Фурье, чтобы в получившемся в результате состоянии проявилась периодическая структура. Принцип локальных операций, примененный к квантовой версии алгоритма БПФ, гарантирует, что можно проделать преобразование Фурье за poly(log./V) шагов. Аналогичному классическому вычислению потребовалось бы 0(N) раз вызвать функцию / для вычисления таблицы ее значений, а затем еще 0(N log TV) шагов для
(4.17)
(4.12).
Квантовые алгоритмы 155
выполнения БПФ. Таким образом, квантовый алгоритм создает экспоненциальное ускорение.
Интересно отметить, что понятие периодичности и построение преобразования Фурье можно обобщить на случай произвольной конечной группы G. Наше предыдущее обсуждение относится к одному частному случаю аддитивной группы целых чисел по модулю N. Обобщенная точка зрения помогает лучше понять работу преобразования Фурье. Далее мы кратко опишем некоторые важные используемые при этом идеи, ограничив наше внимание случаем абелевых групп. (Оставшуюся часть этого раздела можно, при желании, пропустить. Связь с изложением последующих разделов при этом не будет потеряна.)
Пусть G - произвольная абелева группа. Пусть /: G —» X - функция на группе (принимающая значения из некоторого множества А"), и рассмотрим
К = {? е G : f{k + g) = f(g) для всех geG} . (4.18)
(Отметим, что мы записали групповую операцию с помощью аддитивного обозначения). К - это подгруппа G, называемая стабилизатором, или группой симметрии /. Она характеризует симметрию / по отношению к групповой операции G. В нашем предыдущем примере группа G являлась ZA„ а К была циклической подгруппой всех чисел, кратных г. Пусть существует аппарат, вычисляющий/. Наша цель
