М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 81
Текст из файла (страница 81)
Ускорение решения ХР-полных задач 329 Рассмотрим пример. Предположим, мы выбрали гп = [и/2] + 1, е = 1/6. Тогда получим 1 = [и/2] + 3, поэтому алгоритм требует 9(;/М) итераций Гровера, а следовательно, и 9(~/Ф) обращений к оракулу. Согласно оценке (6.33), точность определяется неравенством [ЬМ[ < /М/2+ 1/4 = 0(~/М). Сравните эту оценку с упражнением 6.14, в котором утверждается, что на классическом компьютере для получения подобной точности потребовалось бы 0(Л) обращений к оракулу. Только что описанный пример несет двойную нагрузку.
Во-первых, этот алгоритм определяет, есть ли вообще решение у задачи поиска, т. е. выполняется лн условие М = О или М ф О. Если М = О, то получим, что [ЬМ[ < 1/4, поэтому алгоритм должен дать ответ «нуль» с вероятностью не менее 5/6. Напротив, если М ф О, то легко проверить, что ответ для М будет отличен от нуля с вероятностью по крайней мере 5/6.
Во-вторых, квантовое перечисление применяется для нахождения решения задачи поиска, когда число решений М неизвестно. Трудность в применении квантового алгоритма поиска заключается в том, что число повторений итерации Гровера (определяемое уравнением (6.15)) зависит от знания количества решений М (см. рэзд. 6.1). Эта проблема может быть решена с использованием квантового алгоритма перечисления (для оценки 9 и М с высокой точностью используется процедура нахождения собственного числа) с последующим применением квантового алгоритма поиска (аналогично рэзд.
6.1), при этом итерации Гровера будут повторяться Я раз (где В определяется уравнением (6.15), а оценки для 8 и М получены с помощью процедуры нахождения собственного числа). Ошибка в определении угла в этом случае не превосходит (я/4)(1 + [ЬО[/д), поэтому если выбрать, как н раньше, т = [и/2[+ 1, то ошибка по углу будет не больше, чем я/4 3/2 = Зя/8, что соответствует вероятности успешного завершения алгоритма поиска не менее соя~(Зя/8) = 1/2 — 1/(2~/2) ш 0.15.
Если вероятность получения оценки для д с такой точностью равна 5/6, как в нашем предыдущем примере, тогда окончательная вероятность нахождения решения задачи поиска составит 5/6 сов~(Зя/8) ш 0.12, и она может быть приближена к единице, если несколько рэз повторить комбинированную процедуру перечисления-поиска. 6.4 'Ускорение решения МР-полных задач Квантовый поиск можно использовать для ускорения решения задач в классе сложности ХР (см.
подразд. 3.2.2). Выше было показано (см. подраздел 6.1.1), как можно ускорить поиск простых делителей, теперь рассмотрим, как можно применить квантовый поиск к задаче о гамильтоновом цикле (НС). Напомним, что гамильтоновым циклом для данного графа называют цикл, обходящий все вершины графа «ровно» по одному разу. Задача НС заключается в определении, содержит ли данный граф гамильтонов цикл.
Она относится к классу г1Р-полных задач, для которых неизвестны быстрые алгоритмы решения для классического компьютера (однэко не доказано, что таких алгоритмов вообще не существует) . 330 Глава 6. Квантовые алгоритмы поиска Простой алгоритм решения НС состоит в поиске по всем возможным спискам вершин длины гп 1. задать все возможные списки (им..., е„) вершин графа; повторы вершин разрешаются, поскольку они упрощают анализ, не влияя на содзржательный результат; 2. для каждого списка проверить, задает ли он гамильтонов цикл в графе; если нет, продолжить перебор.
Поскольку существуют пэ = 2""Я" возможных списков вершин, которые надо перебрать, этот алгоритм требует в худшем случае 2" "Я" проверок, являегся ли цикл гамильтоновым. Любая задача в классе ХР может быть решена аналогичным образом: если задача размера п имеет решения, которые могут быть записаны с использованием и(п) бит, где ю(п) — некоторый многочлен от и, то поиск среди 2 00 гипотетических решений даст настоящее решение задачи, если оно существует. Квантовый алгоритм поиска может быть использован для ускорения этого алгоритма за счет более быстрого выполнения поиска. Мы используем описанный в равд.
6.3 алгоритм для определения того, существует ли решение задачи поиска. Пусть тп ш (!ойп). Пространство поиска будет представлено строкой из тпп кубит, где каждый блок из т кубит используется для хранения номера отдельной вершины. Таким образом, можно записать состояния вычислительного базиса слевующим образом: ~см..., е„), где каждый из элементов ~га) отображается подходящей строкой из тп кубит, т. е. общее количество кубитов равно тп.
Оракул для квантового алгоритма поиска должен применить преобразование ! ~с~,..., е„), если щ,..., о„не гамильтонов цикл, .!.1,...,са) = (6.34 1-~ем...,о„), если щ,...,с„гамильтонов цикл. Такой оракул легко построить по описанию графа. Следует взять классическую схему полиномиального размера, распознающую гамильтоновы циклы, и превратить ее в обратимую схему (имеюшую также полиномиальный размер), выполняющую преобразование (ом...,о„,д) -+ (ом...,е„,д ® Дом...,с„)), где ~(иы..., са) = 1, когда ом..., е„— гамильтонов цикл, и Дом..., са) = 0 в противном случае.
Реализация соответствующей схемы на квантовом компьютере с последним кубитом, устанавливаемым в начальный момент в состояние (!О) — ~1))/~/2, дает требуемое преобразование. Мы не будем здесь ука зывать в явном виде детали, отметим лишь ключевой момент: оракул требует полиномиального по и количества элементов (это является прямым следствием того факта, что гамильтоновы циклы можно распознать классическим образом с помощью полиномиального числа элементов). Применяя вариант алгоритма поиска, который определяет, существует ли решение задачи поиска (см. равд.
6.3), мы видим, что для выяснения того, существует ли гамильтонов цикл, потребуется 0(2~а"~т) = 0(2""'Я")~з!) обращений к оракулу. Если цикл существует, легко применить комбинированный алгоритм перечисления-поиска, с 6.5. Квантовый поиск в неструктурированной базе данных 331 помощью которого и станет возможным найти такой цикл. Последний и будет являться решением задачи. Таким образом, можно сделать следующие выводы. ° В классическом алгоритме перебора требуется 0(р(п)2"3»к "~) операций, чтобы определить, существует ли гамильтонов цикл, где полиномиальный множитель р(п) — накладные расходы, связанные в основном с реализацией оракула, т. е.
элементов, проверяющих, является ли пробный путь гамильтоновым или нет. Определяющим фактором, задающим необходимые ресурсы, является показатель степени в выражении 2"й»к "1. Классический алгоритм является детерминированным, т. е. завершается с вероятностью 1. ° Чтобы получить квантовый алгоритм, необходимо произвести 0(р(п)2"3»к"1?з) операций для определения того, существует ли гамильтонов цикл, где полиномиальный множитель р(п) — накладпые расходы, связанные в основном с реализацией оракула. Определяющим фактором, задающим требуемые ресурсы, является показатель степени в выражении 2"3'к"~?з.
Существует конечная вероятность (например, 1~6) ошибки в данном алгоритме; она может быть уменьшена до 1/6" за счет г-кратного повторения алгоритма. ° Для реализации асимптотически квантового алгоритма требуется число операций, которое является кеадратнэ«м корнем из числа операций, необходимых для выполнения классического алгоритма. 6.5 Квантовый поиск в неструктурированной базе данных Представьте себе, что некто дает вам список, содержащий тысячу названий цветов, а затем спрашивает, в каком месте списка появляегся название «пертская роза». Если каждое название появляется в списке лишь один раз и никакого очевидного упорядочения нет, вам в среднем придется просмотреть 500 названий, прежде чем вы отыщете «пертскую розу».
Можно ли ускорить поиск по базе данных такого сорта, используя квантовый алгоритм поиска? Квантовый алгоритм поиска иногда упоминают как алгоритм поиска по базе данных, однако его полезность для этого применения ограничена и основывается на определенных предположениях. В этом разделе мы покажем, как квантовый алгоритм поиска может е нрющнпе быть использован для поиска в неструктурированной базе данных в исполнении, аналогичном примененному в обычном компьютере.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
