М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 76
Текст из файла (страница 76)
Шор [354] сделал важное открытие: для некоторых специальных значений го на квантовых компьютерах можно эффективно выполнить преобразование Фурье на группе Е . Вдохновленные этим результатом, Копперсмит [100], Дойч (не опубликовано) и Клин (не опубликовано) построили простые квантовые схемы для вычисления квантового преобразования Фурье на Ез, которыми мы воспользовались в этой главе. Клин, Экерт, Макиавелло и Моска [80], также Гриффитс и Ниу [163] независимо открыли формулу произведения (5.4); следует отметить, что этот результат был гораздо раньше известен Даниэльсону и Ланцошу. Упрощенное доказательство, начинающееся с формулы (5.5), было предложено Зоу. Гриффитсу и Ниу [163] принадлежит измеряемое преобразование Фурье из задачи 5.2.
Преобразование Фурье на Ез было обобщено до преобразования Фурье на произвольной конечной абелевой группе Китаевым [211]; он также предложил процедуру определения собственного числа в виде, изложенном в задаче 5.3. Клин, Экерт, Макиавелло и Моска [80] объединили некоторые элементы техники Шора и Китаева в изящную картину, на которой основан равд. 5.2. Подробное описание процедуры определения собственного числа можно найти в диссертации Моски [294].
Шор предложил квантовый алгоритм нахождения порядка в основополагающей работе 1994 г. [354] и заметил, что задачи факторизации и дискретного логарифмирования можно свести к нахождению порядка. Заключительная статья, содержащая подробное обсуждение и библиографию, была опубликована в 1997 г.
[357]. В этой статье содержится также обсуждение остроумных алгоритмов умножения, с помощью которых алгоритм Шора можно сделать более быстрым, чем в нашем изложении, где умножение проводилось довольно простыми методами. При использовании этих ускоренных методов умножения трудоемкость разложения и-битового числа равна 0(из !ой п(об1обп), как и было отмечено во введении к главе. В 1995 г. Китаев [211] разработал алгоритм для нахождения стабилизатора общей абелевой группы и показал, что его частными случаями являются задачи о дискретном логарифме и факторизации. Кроме того, алгоритм Китаева содержал ряд идей, отсутствовавших у Шора.
Описание алгоритма факторизации сделли Экерт и Йожа [139]; см. также Ди Винченцо [123]. Обсуждение цепных дробей основано на гл. 10 книги Харди и Райта [195]. Во время работы над книгой наиболее эффективным клас- 310 Глава 5. Квантовое преобразование Фурье и его приложения сическим алгоритмом факторизации был метод теоретико-числового решета. Он описан в сборнике под редакцией А. К.Ленстры и Х. У. Ленстры (мл.) [250]. Обобщение квантовых алгоритмов для решения задачи о скрытой подгруппе рассматривалось многими авторами. Исторически Саймон был первым, кто заметил, что квантовый компьютер может найти скрытый период функции, удовлетворяющей условию 7" [х Ю з) = 7" [я) [359, 360].
В действительности Шор сделал свое открытие, обобщив результат Саймона и применив преобразование Фурье на Ен вместо использовавшихся Саймоном преобразований Адамара (преобразования Фурье на 2~~). Затем Боне и Липтон обнаружили связь с за дачей о скрытой подгруппе и описали квантовый алгоритм, решающий задачу о скрытой линейной функции [6Ц. Йожа был первым, кто дал унифицированное описание алгоритмов Дейча — Йожи, Саймона и Шорк в терминах задачи о скрытой подгруппе. Работа Экерта и Йожи пояснила роль абелева и неабелева быстрых преобразований Фурье в ускорении квантовых алгоритмов [140].
Наше описание задачи о скрытой подгруппе в равд. 5.4 соответствует работе Моски и Экерта [279, 294]. Клив показал, что задача нахождения порядка перестановки нуждается в зкспоненциальном количестве запросов при ее решении на классическом вероятностном компьютере с ограниченными ошибками [91]. Попытки обобщить метод решения задачи о скрытой подгруппе за пределы абелевых групп были предприняты Эттингером и Хейером [136], Ретелером и Бетом [337], Пюшелем, Регелером и Бетом [326], Билзом, который также описал конструкцию квантового преобразования Фурье на симметрической группе [25], а также Эттингером, Хейером и Книллом [137].
На данный момент эти результаты показывают, что существует квантовый алгоритм, решающий неабелеву задачу о скрытой подгруппе с использованием 0(1оя [С]) обращений к оракулу, но неизвестно, можно ли его реализовать за полиномиальное время. Глава 6 КВАНТОВЫЕ АЛГОРИТМЫ ПОИСКА Представьте, что у вас есть карта с большим количеством городов, а вы хотите найти кратчайший маршрут, проходящий через все эти города. Простой алгоритм заключается и переборе всех возможных путей, проходящих через все города, и сравнении каждого из них с кратчайшим из уже рассмотренных путей.
Если имеется Ф возможных маршрутов, то с помощью классического компьютера, очевидно, кратчайший можно найти таким методом за 0(И) операций. В высшей степени удивительно, что существует квантовый алгоритм поиска, называемый иногда алгоритмом Гроеера, который позволяет существенно ускорить этот метод поиска — до 0(~/Ф) операций. Более того, квантовый алгоритм поиска является общим в том смысле, что может быть применен не только для поиска кратчайшего пути, но и для ускорения многих (хотя и не всех) классических алгоритмов, использующих перебор.
В этой главе рассматривается квантовый алгоритм поиска. Основной алгоритм изложен в разд. 6.1. В рэзд. 6.2 мы выведем алгоритм другим способом — с использованием алгоритма моделирования квантовой системы, описанного в рэзд. 4.7. Также будут описаны три важных применения этого алгоритма: квантовое перечисление (рэзд. 6.3), ускорение решения ХР-полных задач (равд. 6.4) и поиск по неструктурированной базе данных (рэзд. 6.5). Априори можно было бы надеяться на дальнейшее улучшение квантового алгоритма поиска, чтобы он работал быстрее, чем за 0(~/У) операций, но, как мы покажем в разд. 6.6, это невозможно. В равд. 6.7 будет доказано, что данный предел быстродействия относится к большинству неструктурированных задач. 6.1 Квантовый алгоритм поиска Начнем с формулирования схемы алгоритма поиска в терминах оракула — по аналогии с подразд.
3.1.1. Это позволит провести общее описание процедуры поиска и геометрического способа визуализации ее действия, а также увидеть, как она выполняется. 6.1.1 Оракул Допустим, мы хотим провести поиск в пространстве поиска из М элементов. Вместо того чтобы искать непосредственно среди элементов, сосредоточимся на номерах этих элементов, т. е. числах в диапазоне от 0 до (Ф вЂ” 1).
Для удобства будем считать, что Ф = 2", поэтому номер можно хранить в ячейке 312 Глава 6. Квантовые алгоритмы поиска из и бит, и что задача поиска имеет ровно М решений, где 1 < М < И. Задачу поиска удобно представлять функцией /, аргументом которой является целое число х в диапазоне от 0 до (>У вЂ” 1). По определению, /(х) = 1, если х является решением задачи поиска, /(х) = 0 в противном случае. Будем считать, что имеется квантовый оракул — черный ящик, внутреннее устройство которого мы обсудим позже (впрочем, на данной стадии зто нас не интересует),— он может распознавать решения задачи поиска.
Сигнал распознавания подаегся с помощью крбпша оракула Точнее говоря, оракул представляет собой унитарный оператор О, определенный действием на вычислительный базис следующим образом: (6.1) )х))д) -+ )х)(д ® /(х)), где ~х) — индексный регистр, символом «®» обозначено сложение по модулю 2, а кубит оракула ~6) меняет значение, если /(х) = 1, и сохраняет его в противном случае.
Можно проверить, является ли х решением нашей задачи поиска, приготовив состояние ~х) ~0), подействовав на него оракулом и проверив, перешел ли кубит оракула в состояние )1). В квантовом алгоритме поиска полезно применять оракул к кубиту оре куль, находящемуся изначально в состоянии (~0) — ~1))/~/2, как это сделано в алгоритме Дейча-Йожа (см. подразд. 1.4.4).
Если х не является решением задачи поиска, действие оракула на состояние >х)()0) — (1))/~/2 не изменит последнее. В то же время, если х — решение задачи поиска, то состояния ~0) и ~1) в результате применения оракула перейдут друг в друга, и конечное состояние будет иметь вид — )х)((0) — (1))/~/2.
Таким образом, действие оракула можно представить следующим выражением: (~0) — !1)~ о, 1Д., (~0) — Р) (6.2) Обратите внимание на то, что состояние кубита оракула не меняется. Оказывается, оно остается равным (~0) — >1))/~/2 на протяжении всей работы квантового алгоритма поиска, следовательно, в дальнейшем обсуждении алгоритма его можно не учитывать, что несколько упростит наше описание.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
