Алгоритм Гровера

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Алгоритм Гровера

Алгоритм Гровера (англ. Grover search algorithm, GSA) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения

где есть булева функция от n переменных.[1]

Предполагается, что функция задана в виде чёрного ящика, или оракула, то есть в ходе решения мы можем только задавать оракулу вопрос типа: «чему равна на данном », и после получения ответа использовать его в дальнейших вычислениях. То есть задача решения уравнения (1) является общей формой задачи перебора; здесь требуется отыскать «пароль к устройству », что классически требует прямого перебора всех вариантов.

GSA находит какой-нибудь корень уравнения, используя обращений к функции , с использованием кубитов.[2] Алгоритм был открыт американским математиком Ловом Гровером в 1996 году.

Свойства[править | править вики-текст]

Если уравнение (1) имеет корней, по схеме Гровера можно найти один из них на квантовом компьютере за время (даже если не известно заранее), то есть основная квантовая сложность является квадратным корнем из классической.

Классический алгоритм решения такой задачи (линейный поиск), очевидно, требует обращений к . Алгоритм Гровера позволяет решить задачу поиска за время порядка квадратного корня из классического, что является огромным ускорением. Доказано, что GSA является оптимальным в следующих отношениях:

  • Константу нельзя улучшить [3].
  • Большего квантового ускорения, чем квадратичное, нельзя получить для неисчезающей доли всех возможных черных ящиков [4].

GSA есть пример массовой задачи, зависящей от оракула. Для более частных задач удается получить большее квантовое ускорение. Например, алгоритм факторизации Шора дает экспоненциальный выигрыш по сравнению с соответствующими классическими алгоритмами.

То, что f задана в виде черного ящика, никак не влияет в общем случае на сложность как квантовых, так и классических алгоритмов. Знание «устройства» функции f (например, знание задающей её схемы из функциональных элементов) в общем случае никак не может помочь в решении уравнения (1). Поиск в базе данных соотносится с обращением функции, которая принимает определенное значение, если аргумент x соответствует искомой записи в базе данных.

Пусть есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору ,  — состояние, соответствующее корню уравнения (1),  — равномерная суперпозиция всех состояний. Тогда GSA состоит в применении оператора к состоянию число раз, равное целой части . Результат будет почти совпадать с состоянием .

Алгоритмы, использующие схему Гровера[править | править вики-текст]

  • Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции . Квантовый алгоритм находит максимум за обращений к f.
  • Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии , где разбиение строки на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени.
  • Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов , на которых функция принимает одно и то же значение. Алгоритм требует обращений к f.

Непрерывные версии алгоритма Гровера[править | править вики-текст]

  • Пусть гамильтониан квантовой системы имеет вид , где и представляют собой операторы и соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом , стартуя с , естественно приводит к . Сложность такого непрерывного аналога GSA точно та же, что и для дискретного случая.
  • Адиабатический вариант GSA. Медленная эволюция основного состояния типа под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка ведет к состоянию .

Применение[править | править вики-текст]

Смысл GSA состоит в «подскоке амплитуды» (amplitude amplification) целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически GSA заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность GSA). Каждый шаг дает вращение на угол , где угол между и составляет . Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.

Гроверовский «подскок амплитуды» является, по-видимому, фундаментальным физическим феноменом в квантовой теории многих тел. Например, его учёт необходим для оценки вероятностей событий, которые кажутся «редкими». Процесс, реализующий схему GSA, приводит к взрывному росту первоначально пренебрежимо малой амплитуды, что способно быстро довести её до реально наблюдаемых величин.

Алгоритм Гровера также может быть использован для нахождения медианы и среднего арифметического числового ряда. Кроме того, он может применяться для решения NP-полных задач путём исчерпывающего поиска среди множества возможных решений. Это может повлечь значительный прирост скорости по сравнению с классическими алгоритмами, хотя и не предоставляя «полиномиального решения» в общем виде.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. Иногда GSA неточно называют поиском в базе данных.
  2. Сложность работы алгоритма, для задачи с оракулом называемая еще временем его работы, определяется числом обращений к оракулу.
  3. Christof Zalka, Grover’s quantum searching algorithm is optimal, Phys.Rev. A60 (1999) 2746—2751 [1]
  4. Yuri Ozhigov, Lower Bounds of Quantum Search for Extreme Point, Proc.Roy.Soc.Lond. A455 (1999) 2165—2172 [2]

Ссылки[править | править вики-текст]