Алгоритм оценки квантовой фазы

В квантовых вычислениях алгоритм оценки квантовой фазы представляет собой квантовый алгоритм оценки фазы, соответствующей собственному значению данного унитарного оператора . Поскольку собственные значения унитарного оператора всегда имеют единичный модуль , они характеризуются своей фазой, и поэтому алгоритм можно эквивалентно описать как получение либо фазы, либо самого собственного значения. Алгоритм был первоначально представлен Алексеем Китаевым в 1995 году.

Оценка фазы часто используется как подпрограмма в других квантовых алгоритмах, таких как алгоритм Шора . квантовый алгоритм для линейных систем уравнений и алгоритм квантового счета .

Обзор алгоритма

Алгоритм работает с двумя наборами кубитов, называемых в данном контексте регистрами . Два регистра содержат $n$ и $m$ кубиты соответственно. Позволять $U$ быть унитарным оператором, действующим на $m$- кубита регистр . Собственные значения унитарного оператора имеют единичный модуль и поэтому характеризуются своей фазой. Таким образом, если $|\psi \rangle$ является собственным вектором $U$, затем $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle$ для некоторых $\theta \in \mathbb {R}$. Из-за периодичности комплексной экспоненты мы всегда можем предположить $0\leq \theta <1$.

Цель состоит в том, чтобы получить хорошее приближение для $\theta$ с небольшим количеством ворот и высокой вероятностью успеха. Алгоритм оценки квантовой фазы достигает этого, предполагая доступ оракула к $U$, и имея $|\psi \rangle$ доступен как квантовое состояние. Это означает, что при обсуждении эффективности алгоритма мы беспокоимся только о том, сколько раз $U$ необходимо использовать, а не о стоимости внедрения $U$ сам.

Точнее, алгоритм с высокой вероятностью возвращает аппроксимацию для $\theta$, в пределах аддитивной ошибки $\varepsilon$, с использованием $n=O(\log(1/\varepsilon ))$ кубиты в первом регистре и $O(1/\varepsilon )$ контролируемые операции . Кроме того, мы можем повысить вероятность успеха до $1-\Delta$ для любого $\Delta >0$ используя в общей сложности $O(\log(1/\Delta )/\varepsilon )$ использование контролируемого U, и это оптимально.

Подробное описание алгоритма

Схема оценки квантовой фазы.

Государственная подготовка

Исходное состояние системы:

$|\Psi _{0}\rangle =|0\rangle ^{\otimes n}|\psi \rangle ,$

где $|\psi \rangle$ это $m$-кубитное состояние, которое развивается через $U$. Сначала мы применим с n-кубитами. операцию вентиля Адамара $H^{\otimes n}$ в первом регистре, который создает состояние: $$|\Psi _{1}\rangle =(H^{\otimes n}\otimes I_{m})|\Psi _{0}\rangle ={\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle .$$Обратите внимание, что здесь мы переключаемся между двоичным и $n$-арное представление для $n$-кубитный регистр: кет $|j\rangle$ в правой части является сокращением $n$-кубитное состояние $|j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle$, где $j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }$ представляет собой бинарное разложение $j$.

-

Это состояние $|\Psi _{1}\rangle$ затем развивается посредством контролируемо-унитарной эволюции $U_{C}$ действие которого можно записать как $$U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),$$для всех $k=0,...,2^{n}-1$. Эту эволюцию также можно кратко записать как $$U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},$$что подчеркивает его контролируемый характер: он применяет $U^{k}$ во второй регистр условно, в первый регистр $|k\rangle$. Помня условие собственных значений, выполняемое для $|\psi \rangle$, применяя $U_{C}$ к $|\Psi _{1}\rangle$ таким образом дает $$|\Psi _{2}\rangle \equiv U_{C}|\Psi _{1}\rangle =\left({\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle \right)\otimes |\psi \rangle ,$$где мы использовали тождества $U^{2^{k}}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle$.

Чтобы показать это $U_{C}$ также может быть эффективно реализовано, заметьте, что мы можем написать $U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})$, где $C_{\ell }(U^{2^{\ell }})$ обозначает операцию применения $U^{2^{\ell }}$ во второй регистр условно $\ell$-й кубит первого регистра $|1\rangle$. Формально эти ворота можно охарактеризовать по своему действию как $$C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \rangle ).$$Это уравнение можно интерпретировать как говорящее, что состояние остается неизменным, когда $j_{\ell }=0$, то есть, когда $\ell$-й кубит $|0\rangle$, а ворота $U^{k}$ применяется ко второму регистру, когда $\ell$-й кубит $|1\rangle$. Таким образом, состав этих контролируемых ворот дает $$\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes \left(U^{\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}|\psi \rangle \right)=U_{C},$$последний шаг непосредственно следует из бинарного разложения $j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }$.

На этом этапе второй регистр с собственным вектором не нужен. Его можно повторно использовать снова при следующем запуске оценки фазы. Государство без $|\psi \rangle$ является $${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle .$$

преобразование Фурье

Применяя обратное квантовое преобразование Фурье к

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle$

урожайность

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}\left({\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle \right)={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .$

Мы можем приблизительно оценить стоимость $\theta \in [0,1]$ путем округления $2^{n}\theta$ до ближайшего целого числа. Это означает, что $2^{n}\theta =a+2^{n}\delta ,$ где $a$ является ближайшим целым числом к $2^{n}\theta ,$ и разница $2^{n}\delta$ удовлетворяет $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$.

Используя это разложение, мы можем переписать состояние как ${\textstyle \sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$ где

$c_{x}\equiv {\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}(x-2^{n}\theta )}={\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}.$

Измерение

Выполнение измерения в вычислительной основе по первому регистру дает результат $|y\rangle$ с вероятностью $$\Pr(y)=|c_{y}|^{2}=\left|{\frac {1}{2^{n}}}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(y-a)}e^{2\pi i\delta k}\right|^{2}.$$Отсюда следует, что $\operatorname {Pr} (a)=1$ если $\delta =0$, то есть когда $\theta$ можно записать как $\theta =a/2^{n}$, всегда можно найти результат $y=a$. С другой стороны, если $\delta \neq 0$, вероятность читается $$\operatorname {Pr} (a)={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}.$$Из этого выражения мы видим, что $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$ когда $\delta \neq 0$. Чтобы убедиться в этом, заметим, что из определения $\delta$ у нас есть неравенство $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$, и таким образом: $${\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\[6pt]&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}$$

Делаем вывод, что алгоритм обеспечивает наилучшее $n$-битовая оценка (т. е. та, которая находится в пределах $1/2^{n}$ правильный ответ) $\theta$ с вероятностью по крайней мере $4/\pi ^{2}$. Добавив несколько дополнительных кубитов порядка $O(\log(1/\epsilon ))$ и усекая лишние кубиты, вероятность может увеличиться до $1-\epsilon$.

Примеры игрушек

Рассмотрим простейший возможный пример алгоритма, где только $n=1$ кубит, помимо кубитов, необходимых для кодирования $|\psi \rangle$, участвует. Предположим, что собственное значение $|\psi \rangle$ читает $\lambda =e^{2\pi i\theta }$, $\theta \in [0,1)$. Первая часть алгоритма генерирует однокубитное состояние. ${\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )}$. Применение обратной КТП в данном случае эквивалентно применению вентиля Адамара . Таким образом, окончательные вероятности исхода равны $p_{\pm }=|\langle \pm |\phi \rangle |^{2}$ где ${\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )}$или, более явно, $$p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.$$Предполагать $\lambda =1$, значение $|\phi \rangle =|+\rangle$. Затем $p_{+}=1$, $p_{-}=0$, и мы детерминированно восстанавливаем точное значение $\lambda$ по результатам измерений. То же самое применимо, если $\lambda =-1$.

Если с другой стороны $\lambda =e^{2\pi i/3}$, затем $p_{\pm }=[1\pm \cos(2\pi /3)]/2$, то есть, $p_{+}=1/4$ и $p_{-}=3/4$. В этом случае результат не является детерминированным, но мы все равно находим результат $|-\rangle$ как более вероятно, совместимо с тем, что $2/3$ ближе к 1, чем к 0.

В более общем смысле, если $\lambda =e^{2\pi i\theta }$, затем $p_{+}\geq 1/2$ тогда и только тогда, когда $|\theta |\leq 1/4$. Это согласуется с полученными выше результатами, поскольку в случаях $\lambda =\pm 1$, соответствующий $\theta =0,1/2$, фаза извлекается детерминированно, а остальные фазы извлекаются с большей точностью, чем ближе они к этим двум.

См. также

• Алгоритм Шора
• Алгоритм квантового счета
• Измерение четности