Русская Википедия:Алгоритм Гровера

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Grovers algorithm.svg
Алгоритм Гровера

Алгоритм Гровера (также GSA от Шаблон:Lang-en) — квантовый алгоритм решения задачи перебора, то есть нахождения решения уравнения

<math>(1)\qquad f(x)=1,</math>

где <math>f</math> есть булева функция от n переменных.[1] Был предложен американским математиком Ловом Гровером в 1996 году.

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

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

Смысл алгоритма Гровера состоит в «Шаблон:Iw» целевого состояния за счёт убывания амплитуды всех других состояний. Геометрически алгоритм Гровера заключается во вращении текущего вектора состояния квантового компьютера по направлению точно к целевому состоянию (движение по наикратчайшему пути обеспечивает оптимальность алгоритма Гровера). Каждый шаг дает вращение на угол <math>2\alpha</math>, где угол между <math>I_{\tilde 0}</math> и <math>I_{x_{tar}}</math> составляет <math>\pi/2 -\alpha</math>. Дальнейшее продолжение итераций оператора G даст продолжение обхода окружности в вещественной плоскости, порождённой данными векторами.

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

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

Описание

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

Алгоритм Гровера состоит в применении оператора <math>G=-I_{\tilde 0}I_{x_{tar}}</math> к состоянию <math>|\tilde 0\rangle</math> число раз, равное целой части <math>\pi\sqrt{N}/4</math>. Результат будет почти совпадать с состоянием <math>|x_{tar}\rangle</math>. Измерив полученное состояние, получаем ответ с вероятностью, близкой к единице.

Замечания

Предположим, уравнение (1) имеет <math>l</math> корней. Классический алгоритм решения такой задачи (линейный поиск), очевидно, требует <math>O(\tfrac{N}{l})</math> обращений к <math>f</math> для того, чтобы решить задачу с вероятностью <math>\tfrac12</math>. Алгоритм Гровера позволяет решить задачу поиска за время <math>O(\sqrt{\tfrac{N}{l}})</math>, то есть порядка квадратного корня из классического, что является огромным ускорением. Доказано, что Алгоритм Гровера является оптимальным в следующих отношениях:

  • Константу <math>\tfrac{\pi}{4}</math> нельзя улучшить[3].
  • Большего квантового ускорения, чем квадратичное, нельзя получить[4].

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

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

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

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

Вариации и обобщения

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

Примечания

Шаблон:Примечания

Ссылки

Шаблон:Квантовые алгоритмы Шаблон:Квантовая информатика

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

  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]
Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Гровера&oldid=8940030