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

Техника квантовых вычислений

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

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

Алгоритм

Представленный здесь вывод примерно соответствует выводу, данному Brassard et al. в 2000 году. ^[3] Предположим, что у нас есть -мерное гильбертово пространство , представляющее пространство состояний квантовой системы, натянутое на ортонормированные вычислительные базисные состояния . Кроме того, предположим, что у нас есть эрмитов оператор проектирования . Альтернативно, может быть задано в терминах булевой функции оракула и ортонормированного операционного базиса , и в этом случае ${\displaystyle N}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle B:=\{|k\rangle \}_{k=0}^{N-1}}$ ${\displaystyle P\colon {\mathcal {H}}\to {\mathcal {H}}}$ ${\displaystyle P}$ ${\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}})}$ ${\displaystyle e\in \{0,1,\dots ,N-1\}}$ ${\displaystyle O(N)}$ ${\displaystyle G}$ ${\displaystyle O({\sqrt {GN}})}$

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

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

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

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

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

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

1. Жиль Брассар; Питер Хойер (июнь 1997 г.). «Точный квантовый алгоритм с полиномиальным временем для задачи Саймона». Труды Пятого израильского симпозиума по теории вычислений и систем . Издательство Компьютерного общества IEEE. стр. 12–23. arXiv : Quant-ph/9704027 . Бибкод : 1997quant.ph..4027B. дои : 10.1109/ISTCS.1997.595153. ISBN 0-8186-8037-7. S2CID  5177739.
2. Гровер, Лов К. (май 1998 г.). «Квантовые компьютеры могут осуществлять быстрый поиск, используя практически любое преобразование». Физ. Преподобный Летт . 80 (19): 4329–4332. arXiv : Quant-ph/9712011 . Бибкод : 1998PhRvL..80.4329G. doi : 10.1103/PhysRevLett.80.4329. S2CID  17879840.
3. Жиль Брассар; Питер Хойер; Мишель Моска; Ален Тапп (15 мая 2000 г.). «Квантовое амплитудное усиление и оценка». Квантовые вычисления и информация . Современная математика. Том. 305. стр. 53–74. arXiv : Quant-ph/0005055 . doi : 10.1090/conm/305/05215. ISBN 9780821821404. S2CID  54753.