Quantum phase estimation algorithm

The initial state of the system is:

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

where ${\displaystyle |\psi \rangle }$ is the ${\displaystyle m}$-qubit state that evolves through ${\displaystyle U}$. We first apply the n-qubit Hadamard gate operation${\displaystyle H^{\otimes n}}$ on the first register, which produces the state:$${\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 .}$$Note that here we are switching between binary and ${\displaystyle n}$representación -aria para la${\displaystyle n}$-registro de cúbits: el ket${\displaystyle |j\rangle }$en el lado derecho es una abreviatura de${\displaystyle n}$-estado del cúbit${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$, dónde${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$es la descomposición binaria de${\displaystyle j}$.

Este estado${\displaystyle |\Psi _ {1}\rangle }$Luego evoluciona a través de la evolución unitaria controlada.${\displaystyle U_{C}}$cuya acción puede escribirse como$${\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),}$$a pesar de${\displaystyle k=0,...,2^{n}-1}$Esta evolución también puede escribirse de forma concisa como$${\displaystyle U_{C}=\sum _ {k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},}$$lo que resalta su naturaleza controlada: se aplica${\displaystyle U^{k}}$al segundo registro condicionalmente al primer registro siendo${\displaystyle |k\rangle }$. Recordando que la condición de autovalor se cumple para${\displaystyle |\psi \rangle }$, aplicando${\displaystyle U_{C}}$a${\displaystyle |\Psi _ {1}\rangle }$así da$${\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 ,}$$donde usamos${\displaystyle U^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$.

Para demostrar que${\displaystyle U_{C}}$También se puede implementar de manera eficiente, observe que podemos escribir${\displaystyle U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})}$, dónde${\displaystyle C_{\ell }(U^{2^{\ell }})}$denota la operación de aplicación${\displaystyle U^{2^{\ell }}}$al segundo registro condicionalmente al${\displaystyle \ell }$-ésimo cúbit del primer registro siendo${\displaystyle |1\rangle }$Formalmente, estas puertas pueden caracterizarse por su acción como$${\displaystyle C_{\ell }(U^{k})(|j\rangle \otimes |\psi \rangle )=|j\rangle \otimes (U^{j_{\ell }k}|\psi \rangle ).}$$Esta ecuación puede interpretarse como que el estado permanece sin cambios cuando${\displaystyle j_{\ell }=0}$, es decir, cuando el${\displaystyle \ell }$-ésimo cúbit es${\displaystyle |0\rangle }$, mientras que la puerta${\displaystyle U^{k}}$se aplica al segundo registro cuando el${\displaystyle \ell }$-ésimo cúbit es${\displaystyle |1\rangle }$La composición de estas compuertas controladas da como resultado$${\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}\left(|j\rangle \otimes |\psi \rangle \right),}$$con el último paso directamente derivado de la descomposición binaria${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$.

A partir de este punto, el segundo registro queda intacto, y por lo tanto es conveniente escribir${\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle }$, con${\displaystyle |{\tilde {\Psi }}_{2}\rangle }$el estado de la${\displaystyle n}$-registro de cúbits, que es el único que necesitamos considerar para el resto del algoritmo.

La parte final del circuito implica la aplicación de la transformada cuántica inversa de Fourier (QFT).${\displaystyle {\mathcal {QFT}}}$en el primer registro de${\displaystyle |\Psi _{2}\rangle }$:$${\displaystyle |{\tilde {\Psi }}_{3}\rangle ={\mathcal {QFT}}_{2^{n}}^{-1}|{\tilde {\Psi }}_{2}\rangle .}$$La QFT y su inversa se caracterizan por su acción sobre los estados base como$${\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}}}$$Resulta que

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

Descomponiendo el estado en la base computacional como${\textstyle |{\tilde {\Psi }}_{3}\rangle =\sum _{x=0}^{2^{n}-1}c_{x}|x\rangle ,}$los coeficientes son, por lo tanto, iguales$${\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},}$$donde escribimos${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$con${\displaystyle a}$es el entero más cercano a${\displaystyle 2^{n}\theta }$La diferencia${\displaystyle 2^{n}\delta }$ debe por definición satisfacer${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$Esto equivale a aproximar el valor de${\displaystyle \theta \in [0,1]}$redondeando${\displaystyle 2^{n}\theta }$al entero más cercano.

El paso final consiste en realizar una medición en la base computacional en el primer registro. Esto produce el resultado.${\displaystyle |y\rangle }$con probabilidad$${\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}.}$$Resulta que${\displaystyle \operatorname {Pr} (a)=1}$si${\displaystyle \delta =0}$, es decir, cuando${\displaystyle \theta }$se puede escribir como${\displaystyle \theta =a/2^{n}}$Siempre se encuentra el resultado${\displaystyle y=a}$. Por otro lado, si${\displaystyle \delta \neq 0}$, la probabilidad dice$${\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}.}$$De esta expresión podemos ver que${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$cuando${\displaystyle \delta \neq 0}$Para ver esto, observamos que a partir de la definición de${\displaystyle \delta }$tenemos la desigualdad${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$y así: ^{[ 4 ] : 157 [ 5 ] : 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\\&={\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}\\&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\&\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 |\\&\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}}}\\&\geqslant {\frac {4}{\pi ^{2}}}.\end{aligned}}}$$

Concluimos que el algoritmo proporciona el mejor${\displaystyle n}$estimación de bits (es decir, una que esté dentro${\displaystyle 1/2^{n}}$de la respuesta correcta) de${\displaystyle \theta }$con probabilidad al menos${\displaystyle 4/\pi ^{2}}$. Al agregar una cantidad de cúbits adicionales del orden de${\displaystyle O(\log(1/\epsilon ))}$y truncando los cúbits adicionales la probabilidad puede aumentar a${\displaystyle 1-\epsilon }$. ^{[ 5 ]}