Усиление амплитуды

Усиление амплитуды — это метод квантовых вычислений , который обобщает идею алгоритма поиска Гровера и дает начало семейству квантовых алгоритмов .Он был открыт Жилем Брассаром и Питером Хойером в 1997 году. и независимо переоткрыт Ловом Гровером в 1998 году.

В квантовом компьютере усиление амплитуды можно использовать для получения квадратичного ускорения по сравнению с несколькими классическими алгоритмами.

Алгоритм

Представленный здесь вывод примерно соответствует выводу, данному Brassard et al. в 2000 году. Предположим, у нас есть $N$-мерное гильбертово пространство ${\mathcal {H}}$ представляющее пространство состояний квантовой системы, охватываемое ортонормированными состояниями вычислительного базиса $B:=\{|k\rangle \}_{k=0}^{N-1}$.Кроме того, предположим, что у нас есть эрмитов оператор проектирования $P\colon {\mathcal {H}}\to {\mathcal {H}}$.Альтернативно, $P$ может быть задано в виде булевой оракула функции $\chi \colon \mathbb {Z} \to \{0,1\}$и ортонормированный операционный базис $B_{\text{op}}:=\{|\omega _{k}\rangle \}_{k=0}^{N-1}$,в этом случае

$P:=\sum _{\chi (k)=1}|\omega _{k}\rangle \langle \omega _{k}|$.

$P$ можно использовать для разделения ${\mathcal {H}}$ в прямую сумму двух взаимно ортогональных подпространств, хорошее подпространство ${\mathcal {H}}_{1}$ и плохое подпространство ${\mathcal {H}}_{0}$:

$${\begin{aligned}{\mathcal {H}}_{1}&:={\text{Image}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=1\},\\{\mathcal {H}}_{0}&:={\text{Ker}}\;P&=\operatorname {span} \{|\omega _{k}\rangle \in B_{\text{op}}\;|\;\chi (k)=0\}.\end{aligned}}$$

Другими словами, мы определяем « хорошее подпространство ». ${\mathcal {H}}_{1}$ через проектор $P$. Целью алгоритма является создание некоторого начального состояния. $|\psi \rangle \in {\mathcal {H}}$ в государство, принадлежащее ${\mathcal {H}}_{1}$.

Учитывая нормализованный вектор состояния $|\psi \rangle \in {\mathcal {H}}$ с ненулевым перекрытием с обоими подпространствами, мы можем однозначно разложить его как

$|\psi \rangle =\sin(\theta )|\psi _{1}\rangle +\cos(\theta )|\psi _{0}\rangle$,

где $\theta =\arcsin \left(\left|P|\psi \rangle \right|\right)\in [0,\pi /2]$,и $|\psi _{1}\rangle$ и $|\psi _{0}\rangle$ являются нормализованными проекциями $|\psi \rangle$ в подпространства ${\mathcal {H}}_{1}$ и ${\mathcal {H}}_{0}$, соответственно. Это разложение определяет двумерное подпространство ${\mathcal {H}}_{\psi }$, натянутый векторами $|\psi _{0}\rangle$ и $|\psi _{1}\rangle$.Вероятность обнаружить систему в исправном состоянии при измерении равна $\sin ^{2}(\theta )$.

Определите унитарный оператор $Q(\psi ,P):=-S_{\psi }S_{P}\,\!$, где

${\begin{aligned}S_{\psi }&=I-2|\psi \rangle \langle \psi |\quad {\text{and}}\\S_{P}&=I-2P.\end{aligned}}$

$S_{P}$ переворачивает фазу состояний в хорошем подпространстве, тогда как $S_{\psi }$ переворачивает фазу исходного состояния $|\psi \rangle$.

Действие этого оператора на ${\mathcal {H}}_{\psi }$ дается

$Q|\psi _{0}\rangle =-S_{\psi }|\psi _{0}\rangle =(2\cos ^{2}(\theta )-1)|\psi _{0}\rangle +2\sin(\theta )\cos(\theta )|\psi _{1}\rangle$ и

$Q|\psi _{1}\rangle =S_{\psi }|\psi _{1}\rangle =-2\sin(\theta )\cos(\theta )|\psi _{0}\rangle +(1-2\sin ^{2}(\theta ))|\psi _{1}\rangle$.

Таким образом, в ${\mathcal {H}}_{\psi }$ подпространство $Q$ соответствует повороту на угол $2\theta \,\!$:

$Q={\begin{pmatrix}\cos(2\theta )&-\sin(2\theta )\\\sin(2\theta )&\cos(2\theta )\end{pmatrix}}$.

Применение $Q$ $n$ раз в штате $|\psi \rangle$дает

$Q^{n}|\psi \rangle =\cos((2n+1)\theta )|\psi _{0}\rangle +\sin((2n+1)\theta )|\psi _{1}\rangle$,

вращение состояния между хорошим и плохим подпространствами.После $n$ итераций вероятность найтисистема в хорошем состоянии $\sin ^{2}((2n+1)\theta )\,\!$.
Вероятность максимизируется, если мы выберем

$n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor$.

До этого момента каждая итерация увеличивает амплитуду хороших состояний, отсюда и название метода.

Приложения

Предположим, у нас есть несортированная база данных с N элементами и функция оракула. $\chi$ которые могут распознавать хорошие записи, которые мы ищем, и $B_{\text{op}}=B$ для простоты.

Если есть $G$ всего хороших записей в базе данных, то мы сможем найти их, инициализировав квантовый регистр $|\psi \rangle$ с $n$ кубиты где $2^{n}=N$ в единую суперпозицию всех элементов базы данных $N$ такой, что

$|\psi \rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N-1}|k\rangle$

и запускаем вышеуказанный алгоритм. В этом случае перекрытие начального состояния с хорошим подпространством равно квадратному корню из частоты хороших записей в базе данных, $\sin(\theta )=|P|\psi \rangle |={\sqrt {G/N}}$. Если $\sin(\theta )\ll 1$, мы можем аппроксимировать количество необходимых итераций как

$n=\left\lfloor {\frac {\pi }{4\theta }}\right\rfloor \approx \left\lfloor {\frac {\pi }{4\sin(\theta )}}\right\rfloor =\left\lfloor {\frac {\pi }{4}}{\sqrt {\frac {N}{G}}}\right\rfloor =O({\sqrt {N}}).$

Измерение состояния теперь даст один из хороших результатов с высокой вероятностью . Поскольку каждое применение $S_{P}$ требуется один запрос оракула (при условии, что оракул реализован как квантовый вентиль ), мы можем найти хорошую запись, просто $O({\sqrt {N}})$ запросы оракула, тем самым получая квадратичное ускорение по сравнению с лучшим классическим алгоритмом. (Классическим методом поиска в базе данных было бы выполнение запроса для каждого $e\in \{0,1,\dots ,N-1\}$ пока решение не будет найдено, что приводит к затратам $O(N)$ запросы.) Более того, мы можем найти все $G$ решения с использованием $O({\sqrt {GN}})$ запросы.

Если мы установим размер набора $G$ к одному, приведенный выше сценарий по существу сводится к исходному поиску Гровера .

Квантовый счёт

Предположим, что количество хороших записей неизвестно. Мы стремимся оценить ${\tilde {G}}$ такой, что $(1-\delta )G\leq {\tilde {G}}\leq (1+\delta )G$ для маленьких $\delta >0$. Мы можем решить для ${\tilde {G}}$ путем применения алгоритма оценки квантовой фазы к унитарному оператору $Q$.

С $e^{2i\theta }$ и $e^{-2i\theta }$ являются единственными двумя собственными значениями $Q$, мы можем позволить их соответствующим собственным векторам быть $|\psi _{1}\rangle$ и $|\psi _{2}\rangle$. Мы можем найти собственное значение $e^{2i\theta }$ из $|\psi \rangle$, что в данном случае эквивалентно оценке фазы $\theta$. Это можно сделать, применив преобразования Фурье и управляемые унитарные операции, как описано в алгоритме оценки квантовой фазы. С оценкой ${\tilde {\theta }}$, мы можем оценить $\sin {\theta }$, что, в свою очередь, оценивает $G$.

Предположим, мы хотим оценить $\theta$ с произвольным начальным состоянием $|s\rangle$, вместо собственных векторов $|\psi _{1}\rangle$ и $|\psi _{2}\rangle$. Мы можем сделать это, разложив $|s\rangle$ в линейную комбинацию $|\psi _{1}\rangle$ и $|\psi _{2}\rangle$, а затем применив алгоритм оценки фазы.