Как работает диффузионный оператор Гровера и почему он оптимален?

В этом ответе объясняется алгоритм Гровера. Объяснение указывает, что алгоритм в значительной степени опирается на оператор диффузии Гровера , но не дает подробных сведений о внутренней работе этого оператора.

Вкратце, оператор диффузии Гровера создает «инверсию относительно среднего», чтобы итеративно сделать крошечные различия на ранних этапах достаточно большими, чтобы их можно было измерить.

Вопросы сейчас:

1. Как диффузионный оператор Гровера достигает этого?
2. Почему в результате $O(\sqrt{n})$в общем времени поиска неупорядоченной базы данных оптимально?

$\newcommand{\bra}[1]{\left<#1\right|}\newcommand{\ket}[1]{\left|#1\right>}\newcommand{\braket}[2]{\left<#1\middle|#2\right>}\newcommand{\bke}[3]{\left<#1\middle|#2\middle|#3\right>}\newcommand{\proj}[1]{\left|#1\right>\left<#1\right|}$ Так как исходный вопрос касался описания непрофессионала, я предлагаю немного другое решение, которое, возможно, легче понять (зависит от фона), основываясь на непрерывном времени эволюция. (Однако я не претендую на то, что он подходит для непрофессионала.)

Мы начнем с начального состояния, которое является равномерной суперпозицией всех состояний, и мы стремимся найти состояние которое можно распознать как правильный ответ (при условии, что существует только одно такое состояние, хотя это можно обобщить). Для этого мы эволюционируем во времени под действием гамильтониана Действительно прекрасная особенность поиска Гровера заключается в том, что на этом этапе мы можем свести математику к подпространству всего из двух состояний , вместо того, чтобы требовать все . Проще описать, если мы сделаем ортонормированный базис из этих состояний, где | х⟩H=| х⟩⟨х| +| г |⟩⟨г || , {| х⟩,| г |⟩}2п{| х⟩,| г |⊥⟩}| г |⊥⟩=

$$\ket{\psi}=\frac{1}{\sqrt{2^n}}\sum_{y\in\{0,1\}^n}\ket{y}$$ $\ket{x}$ $$H=\proj{x}+\proj{\psi}.$$ $\{\ket{x},\ket{\psi}\}$$2^n$$\{\ket{x},\ket{\psi^\perp}\}$е-яхт| г |⟩е-ят(I+2-пZ+ $$\ket{\psi^{\perp}}=\frac{1}{\sqrt{2^n-1}}\sum_{y\in\{0,1\}^n:y\neq x}\ket{y}.$$ Используя эту основу, эволюция времени может быть записана как где и - стандартные матрицы Паули. Это можно переписать как Таким образом, если мы будем развиваться в течение времени$e^{-iHt}\ket{\psi}$XZe-it(Icos( $$e^{-it\left(\mathbb{I}+2^{-n}Z+\frac{\sqrt{2^n-1}}{2^{n}}X\right)}\cdot\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right),$$ $X$$Z$т= $$e^{-it}\left(\mathbb{I}\cos\left(\frac{t}{2^{n/2}}\right)-i\frac{1}{2^{n/2}}\sin\left(\frac{t}{2^{n/2}}\right)\left(Z+X\sqrt{2^n-1}\right)\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right).$$ $t=\frac{\pi}{2}2^{n/2}$и игнорируя глобальные фазы, конечное состояние равно Другими словами, с вероятностью 1 мы получаем состояние которое мы искали. Обычное основанное на схемах описание поиска Гровера - это просто непрерывная эволюция во времени, разбитая на отдельные этапы, с небольшим недостатком, который вы обычно не можете получить точно с вероятностью 1 для вашего результата, просто очень близко к ней.| х $$\frac{1}{2^{n/2}}\left(Z+X\sqrt{2^n-1}\right)\left(\begin{array}{c}\frac{1}{\sqrt{2^n}} \\ \sqrt{1-\frac{1}{2^n}} \end{array}\right)=\left(\begin{array}{c}\frac{1}{2^n} \\ -\frac{\sqrt{2^n-1}}{2^n} \end{array}\right)+\left(\begin{array}{c} 1-\frac{1}{2^n} \\ \frac{\sqrt{2^n-1}}{2^n}\end{array}\right)=\left(\begin{array}{c} 1 \\ 0 \end{array}\right).$$ $\ket{x}$

Одно предостережение заключается в следующем: вы можете переопределить и развиваться, используя и время эволюции будет в 5 раз короче. Если вы хотите быть действительно радикальным, замените 5 на , и поиск Гровера будет выполняться в постоянное время! Но вы не можете делать это произвольно. Любой данный эксперимент будет иметь фиксированную максимальную силу сцепления (то есть фиксированный множитель). Итак, разные эксперименты имеют разное время выполнения, но их масштабирование одинаково, . Это все равно, что сказать, что стоимость затвора в модели схемы постоянна, а не предполагать, что если мы используем схему глубины каждый затвор может быть запущен за время .$\tilde H=5H$$\tilde H$$2^{n/2}$$2^{n/2}$$k$$1/k$

Доказательство оптимальности по существу включает в себя показ того, что если вы сделаете обнаружение одного возможного отмеченного состояния быстрее, это сделает обнаружение другого отмеченного состояния, , более медленным. Поскольку алгоритм должен работать одинаково хорошо независимо от состояния, это решение является лучшим.$\ket{x}$$\ket{y}$

Один из способов определения оператора диффузии: ¹ , где - фазовый оракул$D = -H^{\otimes n}U_0H^{\otimes n}$$U_0$

$$U_0\left|0^{\otimes n}\right> = -\left|0^{\otimes n}\right>,\,U_0\left|x\right> = \left|x\right>\,\text{for} \left|x\right>\neq\left|0^{\otimes n}\right>.$$

Это показывает, что также можно записать как, давая где .$U_0$$U_0 = I-2\left|0^{\otimes n}\rangle\langle0^{\otimes n}\right|$

$$D= 2\left|+\rangle\langle+\right| - I,$$ $\left|+\right> = 2^{-n/2}\left(\left|0\right> + \left|1\right>\right)^{\otimes n}$

Запись состояния где ортогонально (то есть дает то, что .$\left|\psi\right> = \alpha\left|+\right> + \beta\left|+^\perp\right>$$\left|+^\perp\right>$$\left|+\right>$$\left<+^\perp\mid+\right> =0)$$D\left|\psi\right> = \alpha\left|+\right> - \beta\left|+^\perp\right>$

Это дает ^2, что диффузионный оператор является отражением о$\left|+\right>$

Поскольку другая часть алгоритма Гровера также является отражением, они объединяются для поворота текущего состояния ближе к значению . Этот угол уменьшается линейно с числом оборотов (пока он не выходит за пределы искомого значения), давая, что вероятность правильного измерения правильного значения увеличивается квадратично.$x_0$

Беннет и др. и др. показал, что это оптимально. Принимая классическое решение NP-проблемы, алгоритм Гровера может быть использован для квадратичного ускорения этого процесса. Однако, взяв язык для сохраняющей длину функции (здесь - оракул), любой ограниченный Квантовая машина Тьюринга, основанная на ошибке оракула, не может принять этот язык за время .$\mathcal L_A = \left\lbrace y:\exists x\, A\left(x\right) = y\right\rbrace$$A$$T\left(n\right)=\mathcal o\left(2^{n/2}\right)$

Это достигается с помощью набора оракулов, где не имеет обратного (поэтому не содержится в языке). Тем не менее, это содержится в некотором новом языке по определению. Разница в вероятностях того, что машина принимает а другая машина принимает за время , тогда меньше и поэтому ни один язык не принят, и алгоритм Гровера действительно асимптотически оптимально. ³$\left|1\right>^{\otimes n}$$\mathcal L_{A_y}$$\mathcal L_A$$\mathcal L_{A_y}$$T\left(n\right)$$1/3$

Позже Залка показала, что алгоритм Гровера является абсолютно оптимальным.

---

^{1 В алгоритме Гровера знаки минус можно перемещать, поэтому, где знак минус, является несколько произвольным и не обязательно должен быть в определении оператора диффузии}

^{В качестве альтернативы, определение оператора диффузии без знака минус дает представление о$\left|+^\perp\right>$}

^{3 Определение машины, использующей оракула качестве и машины, использующей оракула качестве , это связано с тем, что существует набор битовых строк, где состояния и в момент времени равны -close 4 , с мощностью . Каждый оракул, в котором правильно решает, находится ли в может быть сопоставлен с оракулами, где терпит неудачу$A$$M^A$$A_y$$M^{A_y}$$S$$M^A$$M^{A_y}$$t$$\epsilon$$<2T^2/\epsilon^2$$M^A$$\left|1\right>^{\otimes n}$$\mathcal L_A$$2^n - \text{Card}\left(S\right)$$M^A$ правильно решить, если на языке этого оракула. Тем не менее, он должен дать один из потенциальных ответов, и поэтому, если , машина не сможет определить членство .$\left|1\right>^{\otimes n}$$2^n-1$$T\left(n\right)=\mathcal o\left(2^{n/2}\right)$$\mathcal L_A$}

^{4 Используя евклидово расстояние, вдвое больше трассы}