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


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

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

(1)\qquad f(x)=1,

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

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

GSA находит какой-нибудь корень уравнения, используя \frac{\pi}{4}\sqrt{N} обращений к функции f, с использованием O(n) кубитов.[2] Алгоритм был открыт американским математиком Ловом Гровером в 1996 году.

Содержание

Свойства

Если уравнение (1) имеет l корней, по схеме Гровера можно найти один из них на квантовом компьютере за время O(\sqrt{\frac{N}{l}}) (даже если l не известно заранее), то есть снова квантовая сложность является квадратным корнем из классической.

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

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

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

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

Пусть I_a есть унитарный оператор, зеркально отражающий гильбертово пространство относительно гиперплоскости, перпендикулярной вектору a, |x_{tar}\rangle — состояние, соответствующее корню уравнения (1), |\tilde 0\rangle=\frac{1}{\sqrt{N}}\sum\limits_j|j\rangle — равномерная суперпозиция всех состояний. Тогда GSA состоит в применении оператора G=-I_{\tilde 0}I_{x_{tar}} к состоянию |\tilde 0\rangle число раз, равное целой части \pi\sqrt{N}/4. Результат будет почти совпадать с состоянием |x_{tar}\rangle.

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

  • Алгоритм поиска экстремума целочисленной функции (P. Hoyer и др.). Ищется наибольшее значение функции f:\ \{ 0,1\}^n\rightarrow\{ 0,1\}^n. Квантовый алгоритм находит максимум за O(\sqrt{N}) обращений к f.
  • Алгоритм структурного поиска (Farhi, Gutman). Ищется решение уравнения (1) при дополнительном условии g(x_1)=1 где x=x_1x_2 разбиение строки x на две строки одинаковой длины. Алгоритм имеет сложность порядка квадратного корня из классического времени.
  • Алгоритм поиска совпадающих строк в базе данных (Амбайнис). Ищется пара разных аргументов x_1\neq x_2 на которых функция f:\ \{ 0,1\}^n\rightarrow\{ 0,1\}^n принимает одно и то же значение. Алгоритм требует  O(N^{3/4}) обращений к f.

Непрерывные версии алгоритма Гровера

  • Пусть гамильтониан квантовой системы имеет вид H=H_1+H_2, где \exp(iH_1) и \exp(iH_2) представляют собой операторы I_{\tilde 0} и I_{x_{tar}} соответственно. Тогда непрерывная унитарная эволюция с гамильтонианом H, стартуя с |\tilde 0\rangle, естественно приводит к |x_{tar}\rangle. Сложность такого непрерывного аналога GSA точно та же, что и для дискретного случая.
  • Адиабатический вариант GSA. Медленная эволюция основного состояния типа |\tilde 0\rangle под действием гамильтониана, зависящего от f, согласно адиабатической теореме, за время порядка \sqrt{N} ведет к состоянию |x_{tar}\rangle.

Применение

Смысл GSA состоит в «подскоке амплитуды» (amplitude amplification) целевого состояния за счет убывания амплитуды всех других состояний. Геометрически GSA заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность GSA). Каждый шаг дает вращение на угол 2\alpha, где угол между I_{\tilde 0} и I_{x_{tar}} составляет \pi/2 -\alpha. Дальнейшее продолжение итераций оператора 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]

Ссылки



Wikimedia Foundation. 2010.

Смотреть что такое "Алгоритм Гровера" в других словарях:

  • Алгоритм гровера — …   Википедия

  • Алгоритм Шора — это квантовый алгоритм факторизации (разложения числа на простые множители), позволяющий разложить число N за время , используя O(log N) логических кубитов. Значимость алгоритма заключается в том, что при использовании квантового компьютера с… …   Википедия

  • Алгоритм Дойча — Джоза — это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря использованию явления квантовой… …   Википедия

  • Алгоритм Дойча — Алгоритм Дойча  Джоза  это квантовый алгоритм, предложенный Давидом Дойчем и Ричардом Джозой в 1992 году. Он стал одним из первых примеров алгоритмов, предназначенных для выполнения на квантовых компьютерах. Эти алгоритмы благодаря …   Википедия

  • Квантовый алгоритм — Квантовый алгоритм  это алгоритм, предназначенный для выполнения на квантовом компьютере. Квантовый алгоритм представляет собой классический алгоритм, который задает последовательность унитарных операций (гейтов, или вентилей) с указанием,… …   Википедия

  • Квантовый компьютер — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер вычислительное устройство, работающее на основе квантовой механики. Квантовый компьютер принципиально отличается от классических компьютеров, работающих на основе …   Википедия

  • Квантовые вычисления — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

  • Квантовые компьютеры — 3 кубита квантового регистра против 3 битов обычного Квантовый компьютер  гипотетическое[1] вычислительное устройство, которое путем выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как… …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Программируемые алгоритмы —       Служебный список статей, созданный для координации работ по развитию темы.   Данное предупреждение не устанавл …   Википедия

Книги