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

Усиление амплитуды это техника в квантовые вычисления который обобщает идею, лежащую в основе Алгоритм поиска Гровера, и дает начало семьеквантовые алгоритмы Это было обнаружено Жиль Брассар иПитер Хойер в 1997 г.^[1]и независимо заново открыты Лов Гровер в 1998 г.^[2]

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

Алгоритм

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

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

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

$${\displaystyle {\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}}}$$

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

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

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

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

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

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

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

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

${\displaystyle 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 }$ и

${\displaystyle 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 }$.

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

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

Применение ${\displaystyle Q}$ ${\displaystyle n}$ раз по состоянию${\displaystyle |\psi \rangle }$дает

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

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

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

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

Приложения

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

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

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

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

${\displaystyle 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}}).}$

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

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

Рекомендации

1. Жиль Брассар; Питер Хойер (июнь 1997 г.). "Точный квантовый алгоритм полиномиального времени для проблемы Саймона". Материалы пятого израильского симпозиума по теории вычислений и систем. IEEE Computer Society Press: 12–23. arXiv:Quant-ph / 9704027. Bibcode:1997квант.ч..4027B.
2. Гровер, Лов К. (май 1998 г.). «Квантовые компьютеры могут быстро искать, используя практически любые преобразования». Phys. Rev. Lett. 80 (19): 4329–4332. arXiv:Quant-ph / 9712011. Bibcode:1998ПхРвЛ..80.4329Г. Дои:10.1103 / PhysRevLett.80.4329.
3. Жиль Брассар; Питер Хойер; Микеле Моска; Ален Тапп (2000-05-15). «Квантовое амплитудное усиление и оценка». arXiv:Quant-ph / 0005055.