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

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

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

Формальное описание проблемы

Позволять $U$ быть унитарным оператором, действующим на $m$- кубита регистр . Унитарность означает, что все собственные значения $U$ имеют единичный модуль и поэтому могут быть охарактеризованы своей фазой. Таким образом, если $|\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$ доступен как квантовое состояние.

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

Алгоритм

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

Настройка

Вход состоит из двух регистров (а именно двух частей): верхнего $n$ кубиты составляют первый регистр, а нижний $m$ кубиты — второй регистр.

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

$|0\rangle ^{\otimes n}|\psi \rangle .$

После применения n-битной операции вентиля Адамара $H^{\otimes n}$ в первом регистре состояние становится:

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

Позволять $U$ быть унитарным оператором с собственным вектором $|\psi \rangle$ такой, что $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$. Таким образом,

$U^{2^{j}}|\psi \rangle =e^{2\pi i2^{j}\theta }|\psi \rangle$.

В целом, преобразование, реализованное в двух регистрах с помощью управляемых вентилей, применяющих $U,U^{2},U^{2^{2}},\ldots ,U^{2^{n-1}}$ является

$$|k\rangle |\psi \rangle \mapsto |k\rangle U^{k}|\psi \rangle$$

Это можно увидеть по разложению $k$ в свою битовую строку $k_{n-1}k_{n-2}\ldots k_{1}k_{0}$ и двоичное представление $2^{n-1}k_{n-1}+2^{n-2}k_{n-2}+\ldots +2k_{1}+k_{0}$, где $k_{n-1},\ldots ,k_{1},k_{0}\in \{0,1\}$. Четко, $U^{k}$ становится

$$U^{2^{n-1}k_{n-1}+\ldots +2^{2}k_{2}+2k_{1}+k_{0}}=U^{2^{n-1}k_{n-1}}\ldots U^{2^{2}k_{2}}U^{2k_{1}}U^{k_{0}}$$

Каждый $U^{2^{j}k_{j}}$ будет применяться только в том случае, если кубит $k_{j}$ является $1$, подразумевая, что он контролируется этим битом. Поэтому общее преобразование в $|k\rangle U^{k}|\psi \rangle$ эквивалентно контролируемому $U^{2^{j}}$ ворота из каждого $j$-й кубит.

Следовательно, государство будет трансформироваться под контролем $U^{2^{j}}$ ворота такие:

$${\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle |\psi \rangle$$

На этом этапе второй регистр с собственным вектором не нужен. Его можно повторно использовать снова при следующем запуске оценки фазы. Государство без $|\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 }$. Первая часть алгоритма генерирует однокубитное состояние. ${\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$, фаза извлекается детерминированно, а остальные фазы извлекаются с большей точностью, чем ближе они к этим двум.

См. также

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