Алгоритм квантовой оценки фазы - Quantum phase estimation algorithm - Wikipedia

В Алгоритм квантовой оценки фазы (также называемый квантовый алгоритм оценки собственных значений), это квантовый алгоритм для оценки фазы (или собственного значения) собственного вектора унитарного оператора. Точнее, учитывая унитарная матрица ${\displaystyle U}$ и квантовое состояние ${\displaystyle |\psi \rangle }$ такой, что ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$, алгоритм оценивает значение ${\displaystyle \theta }$ с большой вероятностью в пределах аддитивной ошибки ${\displaystyle \varepsilon }$, с помощью ${\displaystyle O(\log(1/\varepsilon ))}$ кубиты (без учета тех, которые используются для кодирования состояния собственного вектора) и ${\displaystyle O(1/\varepsilon )}$ контролируемый-U операции.

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

Проблема

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

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

Алгоритм

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

Настраивать

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

Создать суперпозицию

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

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

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

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle }$.

Применять контролируемые унитарные операции

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

${\displaystyle U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle }$.

${\displaystyle C-U}$ это контролируемый-U ворота, применяющие унитарный оператор ${\displaystyle U}$ во втором регистре, только если его соответствующий управляющий бит (из первого регистра) ${\displaystyle |1\rangle }$.

Предполагая для ясности, что управляемые ворота применяются последовательно, после применения ${\displaystyle C-U^{2^{0}}}$к ${\displaystyle n^{th}}$ кубита первого и второго регистров состояние становится

${\displaystyle {\frac {1}{2^{\frac {1}{2}}}}\underbrace {\left(|0\rangle |\psi \rangle +|1\rangle e^{2\pi i2^{0}\theta }|\psi \rangle \right)} _{n^{th}\ qubit\ and\ second\ register}\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\underbrace {\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}} _{qubits\ 1^{st}\ to\ n-1^{th}}={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle |\psi \rangle +e^{2\pi i2^{0}\theta }|1\rangle |\psi \rangle \right)\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}}$${\displaystyle ={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)|\psi \rangle \otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}={\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}\otimes \left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}|\psi \rangle ,}$

где мы используем:

${\displaystyle |0\rangle |\psi \rangle +|1\rangle \otimes e^{2\pi i2^{j}\theta }|\psi \rangle =(|0\rangle +e^{2\pi i2^{j}\theta }|1\rangle )|\psi \rangle ,\ \forall j.}$

После нанесения всех оставшихся ${\displaystyle n-1}$ контролируемые операции ${\displaystyle C-U^{2^{j}}}$ с ${\displaystyle 1\leq j\leq n-1,}$ как видно на рисунке, состояние первая регистрация можно описать как

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle \right)} _{1^{st}\ qubit}\otimes \cdots \otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle \right)} _{n-1^{th}\ qubit}\otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle ,}$

куда ${\displaystyle |k\rangle }$ обозначает двоичное представление ${\displaystyle k}$, т.е. это ${\displaystyle k^{th}}$ вычислительная база и состояние второй регистр остается физически неизменным на ${\displaystyle |\psi \rangle }$.

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

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

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

дает

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}{\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\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 .}$

Состояние обоих регистров вместе

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

Представление фазовой аппроксимации

Мы можем приблизительно оценить значение ${\displaystyle \theta \in [0,1]}$ округляя ${\displaystyle 2^{n}\theta }$ до ближайшего целого числа. Это означает, что ${\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 {\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-a\right)}e^{2\pi i\delta k}|x\rangle \otimes |\psi \rangle .}$

Измерение

Выполнение измерение в вычислительной базе по первому регистру дает результат ${\displaystyle |a\rangle }$ с вероятностью

${\displaystyle \Pr(a)=\left|\left\langle a\underbrace {\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(x-a)}e^{2\pi i\delta k}\right|x} _{\text{State of the first register}}\right\rangle \right|^{2}={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\begin{cases}1&\delta =0\\&\\{\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&\delta \neq 0\end{cases}}}$

За ${\displaystyle \delta =0}$ приближение точное, поэтому ${\displaystyle a=2^{n}\theta }$ и ${\displaystyle \Pr(a)=1.}$ В этом случае мы всегда измеряем точное значение фазы.^{[2]:157[3]:347} Состояние системы после измерения ${\displaystyle |2^{n}\theta \rangle \otimes |\psi \rangle }$.^[1]:223

За ${\displaystyle \delta \neq 0}$ поскольку ${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$ алгоритм дает правильный результат с вероятностью ${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$. Докажем это следующим образом: ^{[2]:157 [3]:348}

${\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 |{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[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-битную оценку ${\displaystyle \theta }$ с большой вероятностью. Увеличивая количество кубитов на ${\displaystyle O(\log(1/\epsilon ))}$ и игнорируя эти последние кубиты, мы можем увеличить вероятность ${\displaystyle 1-\epsilon }$.^[3]

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

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

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

1. Нильсен, Майкл А. и Исаак Л. Чуанг (2001). Квантовые вычисления и квантовая информация (Ред. Ред.). Кембридж [u.a.]: Cambridge Univ. Нажмите. ISBN  978-0521635035.
2. Бененти, Гильяно; Касати, Джулио; Стрини, Джулиано (2004). Принципы квантовых вычислений и информации (Перепечатано. Ред.). Нью-Джерси [u.a.]: World Scientific. ISBN  978-9812388582.
3. Умная.; Ekert, A .; Macchiavello, C .; Моска, М. (8 января 1998 г.). «Возвращение к квантовым алгоритмам». Труды Королевского общества A: математические, физические и инженерные науки. 454 (1969). arXiv:Quant-ph / 9708016. Bibcode:1998RSPSA.454..339C. Дои:10.1098 / rspa.1998.0164.

• Китаев, А.Ю. (1995). «Квантовые измерения и проблема абелевых стабилизаторов». arXiv:Quant-ph / 9511026.