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

Квантовый алгоритм оценки собственных значений

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

Оценка фазы часто используется в качестве подпрограммы в других квантовых алгоритмах, таких как алгоритм Шора ^{[2] : 131,} квантовый алгоритм для линейных систем уравнений и алгоритм квантового счета .

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

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

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

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

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

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

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

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

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

где находится состояние -кубита, которое развивается через . Сначала мы применяем операцию вентиля Адамара с n-кубитами к первому регистру, которая создает состояние: Обратите внимание, что здесь мы переключаемся между двоичным и -арным представлением для -кубитного регистра: кет в правой части является сокращением для -кубитное состояние , где – двоичное разложение . ${\displaystyle |\psi \rangle }$ ${\displaystyle m}$ ${\displaystyle U}$ ${\displaystyle H^{\otimes n}}$ $${\displaystyle |\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 .}$$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle |j\rangle }$ ${\displaystyle n}$ ${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$ ${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$ ${\displaystyle j}$

Операции Controlled-U

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

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

С этого момента второй регистр остается нетронутым, и поэтому его удобно записывать с состоянием регистра -кубита, который является единственным, который нам нужно учитывать в остальной части алгоритма. ${\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle }$ ${\displaystyle |{\tilde {\Psi }}_{2}\rangle }$ ${\displaystyle n}$

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

Заключительная часть схемы включает в себя применение обратного квантового преобразования Фурье (QFT) к первому регистру : QFT и его обратное характеризуются своим действием на базисные состояния следующим образом. Отсюда следует, что ${\displaystyle {\mathcal {QFT}}}$ ${\displaystyle |\Psi _{2}\rangle }$ $${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\tilde {\Psi }}_{2}\rangle .}$$ $${\displaystyle {\begin{aligned}{\mathcal {QFT}}_{N}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{{\frac {2\pi i}{N}}jk}|j\rangle ,\\{\mathcal {QFT}}_{N}^{-1}|k\rangle &=N^{-1/2}\sum _{j=0}^{N-1}e^{-{\frac {2\pi i}{N}}jk}|j\rangle .\end{aligned}}}$$

${\displaystyle |{\tilde {\Psi }}_{3}\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 .}$

Разложение состояния в вычислительном базисе по коэффициентам, равным тем местам, где мы написали, представляет собой ближайшее целое число к . Разница по определению должна удовлетворять . Это означает аппроксимацию значения путем округления до ближайшего целого числа. ${\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$ $${\displaystyle 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},}$$ ${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$ ${\displaystyle a}$ ${\displaystyle 2^{n}\theta }$ ${\displaystyle 2^{n}\delta }$ ${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$ ${\displaystyle \theta \in [0,1]}$ ${\displaystyle 2^{n}\theta }$

Измерение

Последний шаг включает выполнение измерения в вычислительной базе первого регистра. Это дает результат с вероятностью. Отсюда следует, что если , то есть когда можно записать как , всегда можно найти результат . С другой стороны, если , вероятность читается Из этого выражения мы видим, что когда . Чтобы убедиться в этом, заметим, что из определения мы имеем неравенство , и таким образом: ^{[4] : 157  [5] : 348} ${\displaystyle |y\rangle }$ $${\displaystyle \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}.}$$ ${\displaystyle \operatorname {Pr} (a)=1}$ ${\displaystyle \delta =0}$ ${\displaystyle \theta }$ ${\displaystyle \theta =a/2^{n}}$ ${\displaystyle y=a}$ ${\displaystyle \delta \neq 0}$ $${\displaystyle \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}.}$$ ${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$ ${\displaystyle \delta \neq 0}$ ${\displaystyle \delta }$ ${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$ $${\displaystyle {\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}}}$$

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

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

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

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

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

Смотрите также

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

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

1. Китаев, А. Ю. (1995-11-20). «Квантовые измерения и проблема абелева стабилизатора». arXiv : Quant-ph/9511026 .
2. Нильсен, Майкл А. и Исаак Л. Чуанг (2001). Квантовые вычисления и квантовая информация (Отв. ред.). Кембридж [ua]: Cambridge Univ. Нажимать. ISBN 978-0521635035.
3. Манде, Нихил С.; Рональд де Вольф (2023). «Жесткие границы для оценки квантовой фазы и связанных с ней проблем». arXiv : 2305.04908 [квант-ph].
4. Бененти, Гильяно; Казати, Джулио; Стрини, Джулиано (2004). Принципы квантовых вычислений и информации (перепечатано под ред.). Нью-Джерси [ua]: World Scientific. ISBN 978-9812388582.
5. Клив, Р.; Экерт, А.; Маккиавелло, К.; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: Математические, физические и технические науки . 454 (1969): 339–354. arXiv : Quant-ph/9708016 . Бибкод : 1998RSPSA.454..339C. дои : 10.1098/rspa.1998.0164. S2CID  16128238.