Квантовые вычисления - Стин Э.
Скачать (прямая ссылка):
эффективную имитацию любой физической системы. Однако можно показать, что
квантовый компьютер эффективен при имитации большого класса квантовых
систем, для многих из которых, например для систем многих тел с
локальными взаимодействиями, не существует эффективного классического
алгоритма решения (Lloyd 1996, Zalka 1996, Wiesner 1996, Meyer 1996,
Lidar и Biam 1996, Abrams and Lloyd 1997, Boghosian and Taylor 1997).
7.2. Алгоритм поиска периода функции. Алгоритм Шора по разложению на
множители
До настоящего момента в обзоре рассматривалась лишь имитация процессов
Природы, что является довольно ограниченным типом вычисления. Хотелось
бы, чтобы квантовый компьютер использовался и для решения более общих
задач; хотя и было доказано, что поиск тех задач, в которых квантовый
компьютер был бы эффективнее классического, затруднителен. Однако факт,
что подобные задачи, в принципе, существуют, является значительным
открытием в физике. Он также в большой степени способствовал поискам в
данной области.
На сегодняшний день алгоритм поиска периода функции является одним из
самых важных. Предположим, что функция f(x) - периодическая с периодом г,
т.е. f(x) = f(x + г). Предположим далее, что функция f(x) может быть
легко найдена при данном х, кроме того, изначально известно, что N/2 < г
< N для какого-либо N. Предполагая, что не существует аналитического
способа определения периода функции f(x), единственным выходом остается
определение с помощью классического компьютера значений f(x) для порядка
N/2 значений х, и нахождение того значения х, после которого значения
функции начинают повторяться (для регулярных функций необходимо в среднем
лишь 0('/N) значений). Данный метод является неэффективным, по-
70
Глава 7
Ю>т-(c)-*
х~(c)- Э*>
Ю>7
О f(x)
Рис. 10. Квантовая сеть для алгоритма Шора по нахождению периода функции.
Здесь каждая горизонтальная линия обозначает квантовый регистр, а не
кубит. Окружности слева представляют создание входного состояния |0).
Символ FT в кружочке представляет преобразование Фурье (см. текст), а
блок, связывающий два регистра, представляет сеть, соответствующую
оператору U/. Действие алгоритма завершается после измерения регистра х
скольку число операций экспоненциально зависит от величины log TV
(информации, необходимой для определения N).
Вышеуказанная задача может быть решена на квантовом компьютере
посредством строгого метода (см. рис. 10), предложенного Шором
(1994) и опирающегося на метод Симона (1994). Для решения задачи
квантовому компьютеру необходимо 2п кубитов, а также 0{п) кубитов - для
создания рабочего пространства, где п - [2 log TV] (выражение [п]
обозначает ближайшее большее целое к х число). Все кубиты делятся на два
"регистра", каждый из которых содержит по п кубитов. Ниже будем
обращаться к ним, как к "регистру х" и "регистру уъ. Каждый из регистров
изначально задан в состоянии |0) (т. е. все п кубитов находятся в
состоянии |0)). Далее, к каждому из кубитов регистра х применим операцию
Н, определяя итоговое состояние
где ш = 2". По причинам, которые вскоре станут очевидными, данное
действие рассматривается как преобразование Фурье (см. рис. 10).
Выражение |ж) обозначает, например, состояние (0011010), где 0011010 -
двоичная запись целого числа х. В связи с этим базис {|0), |1)} может
рассматриваться как "вычислительный базис". При описании компьютера
удобно (хотя, разумеется, не обязательно) пользоваться данным базисом.
Затем, для выполнения преобразования Uf\x)\0) = |ж)/|а;), к регистрам хну
применяется сеть логических гейтов. Следует от-
(34)
7.2. Алгоритм поиска периода функции. Алгоритм Шора
71
метить, что данное преобразование может быть единичным, поскольку входное
состояние |ж)|0) полностью соответствует входному состоянию \x)\f(x)), и,
следовательно, процессы являются обратимыми. Теперь, применяя
преобразование С/у к состоянию, описываемому уравнением (34), получим
Данное состояние продемонстрировано на рис. 11а. Здесь необходимо
отметить следующую уникальную особенность: за один шаг были найдены
значения функции f(x) для и> = 2П значений х. Эта особенность называется
квантовым параллелизмом и, вследствие экспоненциальной зависимости от п,
представляет мощнейший параллелизм. (Вообразите существование 2100, т. е.
в миллион раз больше числа Авогадро, классических процессоров).
Хотя 2" значений функции /(ж) в каком-то смысле "присутствуют" в
квантовом состоянии, определяемом уравнением (35), прямой доступ к ним, к
сожалению, невозможен. Это связано с тем, что в соответствии со следующим
шагом алгоритма, вследствие измерения (по вычислительному базису)
регистра у можно получить лишь одно значение /(ж).1 Предположим, что при
этом получаем значение функции /(ж) = и. Состояние регистра у
перебрасывается в состояние |и), а общее состояние будет определяться как
где du+jr - все значения ж, для которых f(x)=u, j = 0,1,2, ... , М-1.
Другими словами, периодичность функции /(ж) означает, что регистр ж
