|
Алгоритм ГровераАлгоритм Гровера GSA (Grover search algorithm), быстрый квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения где f есть булева функция от n переменных. (Иногда GSA неточно называют поиском в базе данных). Предполагается, что функция f задана в виде черного ящика, или оракула, то есть в ходе решения мы можем только задавать оракулу вопрос типа: «чему равна f на данном x», и после получения ответа использовать его в дальнейших вычислениях). То есть задача решения уравнения (1) является общей формой задачи перебора; здесь требуется отыскать «пароль к устройству f», что классически требует прямого перебора всех N = 2n вариантов. GSA находит какой-нибудь корень уравнения, используя обращений к функции f, с использованием O(n) кубитов. (Сложность работы алгоритма, для задачи с оракулом называемая еще временем его работы, определяется числом обращений к оракулу). Алгоритм был открыт американским математиков Ловом Гровером в 1996 году. Если уравнение (1) имеет l корней, по схеме Гровера можно найти один из них на квантовом компьютере за время (даже если l не известно заранее), то есть снова квантовая сложность является квадратным корнем из классической. Классический алгоритм решения такой задачи (линейный поиск), очевидно требует обращений к f. Алгоритм Гровера позволяет решить задачу поиска за время порядка квадратного корня из классического, что является огромным ускорением. Доказано, что GSA является оптимальным в следующих отношениях. 1). Константу нельзя улучшить более чем на 3 % [1]. 2). Большего квантового ускорения, чем квадратичное, нельзя получить для неисчезающей доли всех возможных черных ящиков f [2]. GSA есть пример массовой задачи, зависящей от оракула. Для более частных задач удается получить большее квантовое ускорение. Например, алгоритм факторизации Шора дает экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами. То, что f задана в виде черного ящика, никак не влияет в общем случае на сложность как квантовых, так и классических алгоритмов. Знание «устройства» функции f (например, знание задающей ее схемы из функциональных элементов) в общем случае никак не может помочь в решении уравнения (1). Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных. Пусть Ia есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору a, — состояние, соответствующее корню уравнения (1), — равномерная суперпозиция всех состояний. Тогда GSA состоит в применении оператора к состоянию число раз, равное целой части . Результат будет почти совпадать с состоянием . Алгоритмы, использующие схему Гровера: 1) Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции . Квантовый алгоритм находит максимум за обращений к f. 2) Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии g(x1) = 1 где x = x1x2 разбиение строки x на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени. 3) Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов на которых функция принимает одно и то же значение. Алгоритм требует O(N3 / 4) обращений к f. Непрерывные версии А.Г.: 1) Пусть гамильтониан квантовой системы имеет вид H = H1 + H2 где exp(iH1) и exp(iH2) соответственно представляют собой операторы и соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом H, стартуя с , естественно приводит к . Сложность такого непрерывного аналога GSA точно та же, что и для дискретного случая. 2) Адиабатический вариант GSA. Медленная эволюция основного состояния типа под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка ведет к состоянию . Смысл GSA состоит в «подскоке амплитуды» (amplitude amplification) целевого состояния за счет убывания амплитуды всех других состояний. Геометрически GSA заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность GSA). Каждый шаг дает вращение на угол 2α где угол между и составляет π / 2 − α. Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порожденной данными векторами. Гроверовский «подскок амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учет необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему GSA, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести ее до реально наблюдаемых величин. А.Г. также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путем исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде. |
Loading
|