Физика квантовой информации - Бауместер Д.
ISBN 5-94057-017-8
Скачать (прямая ссылка):
kt) = atZlx) + Ako) ’ (4-35)
х*х0
где, также, ак и /Зк - действительные числа. Используя выражения для матричных элементов D и I можно вывести рекуррентные соотношения:
a° = /?0 = VF ’
ам=(\-1)ак~&, (4.36)
Ры=<\-^Ж+0*-\)^ак.
Нормировка дает
Pl+(N-\)al=\, (4.37)
Квантовые алгоритмы 163
из чего следует, что было бы удобно ввести обозначения
1 о
а, =-------cos в,
И fik=sinek.
Тогда можно убедиться [151], что рекуррентные соотношения (4.36) выполняются при
ак =-j====cos(2k+ 1)в , /Зк = sm(2k+ 1)в , (4.38)
где угол допределен равенством sin в = 1 / л/N.
Таким образом, при изменении к, (Зк меняется по синусоидальному закону. У нас получится (ik = 1 , например, если (2к + \)в = я/2 - то есть, при к = (л - 26) /4в. Для больших N можно считать sin#= 1/ л/N & в, и тогда к = п!4 W"- 1/2, что порядка Vn. Значит, если мы проделаем итерации такое число раз, которое будет равно целому числу, ближайшему к этому значению к, то сможем с высокой (и не зависящей от N) вероятностью найти х произведя считывание конечного состояния в стандартном базисе (см. [151] для дальнейшего анализа рассматриваемых вероятностей). На этом алгоритм завершен.
Со времени появления первой работы Гровера основные идеи, использованные в описанном выше алгоритме, были далее развиты в большом количестве других приложений - таких, как оценка среднего и медианы в базе данных из N чисел [152], или анализ случая более чем одной помеченной записи в базе данных [151, 153]. Использовав оригинальную комбинацию алгоритмов Гровера и Шора, Брассар, Хойе и Тапп показали [153], что возможно также узнать количество помеченных записей (не определяя их положение). Не вдаваясь в детали, идея, лежащая в основе их подхода, состоит в том, что амплитуды ак и (Зк, описанные выше, изменяются периодически с периодом, зависящим от числа помеченных записей. Эта периодичность оценивается с помощью квантового преобразования Фурье, как это было отмечено в предыдущих разделах. Также было показано [151, 153, 154], что, хоть это и удивительно на первый взгляд, если заменить в определении D унитарную операцию Н на почти унитарную операцию U, то алгоритм с измененным определением D все равно сможет находить х0 за o(VJv) шагов.
Алгоритм Гровера дает нам возможность проводить поиск в экспоненциально большом пространстве данных. Проблема экспоненциального поиска очень важна для многих областей математики и программирования. С практической точки зрения, интересна ситуация, когда можно проверить, выполняется ли для данной записи желаемое
164 Концепция квантовых вычислений
свойство (то, по которому проводится поиск) за полиномиальное время
- проще говоря, когда, «вычислительно легко» проверить, выполняется ли это свойство для одного кандидата, но поиск надо вести среди экспоненциально большого их числа. Например, предположим, что нам дан граф, который состоит из набора вершин, а также ребер, соединяющих между собой некоторые вершины. Граф с п вершинами можно записать в виде матрицы п х п, состоящей из нулей и единиц, в которой элемент ij равен 1 тогда и только тогда, когда в графе есть ребро, соединяющее вершину / с вершиной j. Мы хотим узнать, существует ли замкнутый путь, по которому можно обойти все вершины, побывав на каждой ровно один раз. У этой, так называемой, задачи о гамильтоновой цепи, есть много важных приложений. В общем случае, если дан граф, то на нем существует экспоненциально много возможных цепей (то есть, экспоненциально много, как функция от размера матрицы, описывающей граф). Но если дана цепь, то легко за полиномиальное время проверить, удовлетворяет она требуемому условию, или нет (надо просто обойти эту цепь и посмотреть, побывает ли она на каждой вершине ровно один раз). В теории вычислительной сложности класс задач такого типа называется NP (см. более глубокое обсуждение в [131, 132]). С интуитивных позиций, в задачах класса NP «трудно» найти элемент, удовлетворяющий условиям, но «легко» проверить, удовлетворяется условие или нет.
Многие очень интересные с точки зрения как математики, так и практики вычислительные задачи принадлежат классу NP (см. длинный и разнообразный перечень примеров в [132]). Пожалуй, самая знаменитая нерешенная проблема в классической теории вычислительной сложности - это проблема Р * NP , которая состоит в вопросе, возможно ли решить за полиномиальное время любую задачу из NP. Мотивирующая идея здесь состоит в том, что если выполнение свойства можно «вычислительно легко» проверить, то, может быть, на вопрос, содержится ли оно в данной структуре, также можно ответить за полиномиальное время. Заметим, что мы здесь думаем не о полном просмотре экспоненциально большого числа кандидатов (что гарантированно потребовало бы экспоненциального времени), но о некоем хитром анализе самой структуры, породившей экспоненциально большое число возможностей. Например, для задачи о гамильтоновой цепи - существует ли способ как-то проверить описание самого графа, чтобы увидеть, содержит ли он гамильтонову цепь, вместо того, чтобы примитивно проверять все цепи по очереди.
