Algoritmo de estimación de fase cuántica

En computación cuántica , el algoritmo de estimación de fase cuántica es un algoritmo cuántico para estimar la fase correspondiente a un valor propio de un operador unitario dado . Dado que los valores propios de un operador unitario siempre tienen módulo unitario , se caracterizan por su fase, y por lo tanto, el algoritmo puede describirse equivalentemente como la recuperación de la fase o del propio valor propio. El algoritmo fue introducido inicialmente por Alexei Kitaev en 1995. ^{[ 1 ]}^{[ 2 ]}^{: 246}

La estimación de fase se utiliza frecuentemente como subrutina en otros algoritmos cuánticos, como el algoritmo de Shor , ^{[ 2 ]}^{: 131} el algoritmo cuántico para sistemas lineales de ecuaciones y el algoritmo de conteo cuántico .

Descripción general del algoritmo

El algoritmo opera sobre dos conjuntos de cúbits, denominados en este contexto registros . Los dos registros contienen $n$ y $m$ cúbits, respectivamente. Sea $U$ ser un operador unitario que actúa sobre el $m$ - registro de cúbit . Los autovalores de un operador unitario tienen módulo unitario y, por lo tanto, se caracterizan por su fase. Así, si $|\psi \rangle$ es un vector propio de $U$ , entonces $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle$ para algunos $\theta \in \mathbb {R}$ Debido a la periodicidad de la exponencial compleja, siempre podemos asumir $0\leq \theta <1$ .

El objetivo es producir una buena aproximación para $\theta$ con un pequeño número de puertas y una alta probabilidad de éxito. El algoritmo de estimación de fase cuántica logra esto asumiendo acceso oracular a $U$ y tener $|\psi \rangle$ disponible como un estado cuántico . Esto significa que al hablar de la eficiencia del algoritmo solo nos preocupamos por la cantidad de veces. $U$ debe usarse, pero no se trata del costo de implementación. $U$ sí mismo.

Más precisamente, el algoritmo devuelve con alta probabilidad una aproximación para $\theta$ dentro del error aditivo $\varepsilon$ , usando $n=O(\log(1/\varepsilon ))$ cúbits en el primer registro, y $O(1/\varepsilon)$ operaciones U controladas . Además, podemos mejorar la probabilidad de éxito para $1-\Delta$ para cualquier $\Delta >0$ utilizando un total de $O(\log(1/\Delta )/\varepsilon )$ usos de U controlada, y esto es óptimo. ^{[ 3 ]}

Descripción detallada del algoritmo

El circuito para la estimación de fase cuántica.

Preparación del estado

El estado inicial del sistema es:

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

dónde $|\psi \rangle$ es el $m$ -estado de cúbit que evoluciona a través de $U$ Primero aplicamos la operación de puerta de Hadamard de n cúbits . $H^{\otimes n}$ en el primer registro, que produce el estado: $|\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 .$ Tenga en cuenta que aquí estamos cambiando entre binario y $n$ representación -aria para la $n$ -registro de cúbits: el ket $|j\rangle$ en el lado derecho es una abreviatura de $n$ -estado del cúbit $|j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle$ , dónde $j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }$ es la descomposición binaria de $j$ .

Operaciones controladas en U

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

Para demostrar que $U_{C}$ También se puede implementar de manera eficiente, observe que podemos escribir $U_{C}=\prod _{\ell =0}^{n-1}C_{\ell }(U^{2^{\ell }})$ , dónde $C_{\ell }(U^{2^{\ell }})$ denota la operación de aplicación $U^{2^{\ell }}$ al segundo registro condicionalmente al $\ell$ -ésimo cúbit del primer registro siendo $|1\rangle$ Formalmente, estas puertas pueden caracterizarse por su acción como $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 $j_{\ell }=0$ , es decir, cuando el $\ell$ -ésimo cúbit es $|0\rangle$ , mientras que la puerta $U^{k}$ se aplica al segundo registro cuando el $\ell$ -ésimo cúbit es $|1\rangle$ La composición de estas compuertas controladas da como resultado $\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 $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 $|\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle$ , con $|{\tilde {\Psi }}_{2}\rangle$ el estado de la $n$ -registro de cúbits, que es el único que necesitamos considerar para el resto del algoritmo.

Aplicar la transformada cuántica inversa de Fourier

La parte final del circuito implica la aplicación de la transformada cuántica inversa de Fourier (QFT). ${\mathcal {QFT}}$ en el primer registro de $|\Psi _{2}\rangle$ : $|{\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 ${\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

|{\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 $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 $2^{n}\theta =a+2^{n}\delta ,$ con $a$ es el entero más cercano a $2^{n}\theta$ La diferencia $2^{n}\delta$ debe por definición satisfacer $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$ Esto equivale a aproximar el valor de $\theta \in [0,1]$ redondeando $2^{n}\theta$ al entero más cercano.

Medición

El paso final consiste en realizar una medición en la base computacional en el primer registro. Esto produce el resultado. $|y\rangle$ con probabilidad $\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 $\operatorname {Pr} (a)=1$ si $\delta =0$ , es decir, cuando $\theta$ se puede escribir como $\theta =a/2^{n}$ Siempre se encuentra el resultado $y=a$ . Por otro lado, si $\delta \neq 0$ , la probabilidad dice $\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 $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$ cuando $\delta \neq 0$ Para ver esto, observamos que a partir de la definición de $\delta$ tenemos la desigualdad $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$ y así: ^{[ 4 ]}^{: 157}^{[ 5 ]}^{: 348} ${\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 $n$ estimación de bits (es decir, una que esté dentro $1/2^{n}$ de la respuesta correcta) de $\theta$ con probabilidad al menos $4/\pi ^{2}$ . Al agregar una cantidad de cúbits adicionales del orden de $O(\log(1/\epsilon ))$ y truncando los cúbits adicionales la probabilidad puede aumentar a $1-\epsilon$ . ^{[ 5 ]}

Ejemplos de juguetes

Consideremos la instancia más simple posible del algoritmo, donde solo $n=1$ cúbito, además de los cúbitos necesarios para codificar $|\psi \rangle$ , está involucrado. Supongamos que el valor propio de $|\psi \rangle$ lecturas $\lambda =e^{2\pi i\theta }$ , $\theta \in [0,1)$ La primera parte del algoritmo genera el estado de un cúbit. ${\textstyle |\phi \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle +\lambda |1\rangle )}$ . Aplicando la QFT inversa se obtienen en este caso aplicando una puerta de Hadamard . Las probabilidades del resultado final son, por lo tanto, $p_{\pm }=|\langle \pm |\phi \rangle |^{2}$ dónde ${\textstyle |\pm \rangle \equiv {\frac {1}{\sqrt {2}}}(|0\rangle \pm |1\rangle )}$ , o más explícitamente, $p_{\pm }={\frac {|1\pm \lambda |^{2}}{4}}={\frac {1\pm \cos(2\pi \theta )}{2}}.$ Suponer $\lambda =1$ , significado $|\phi \rangle =|+\rangle$ . Entonces $p_{+}=1$ , $p_{-}=0$ y recuperamos de forma determinista el valor preciso de $\lambda$ a partir de los resultados de la medición. Lo mismo se aplica si $\lambda =-1$ .

Si por otro lado $\lambda =e^{2\pi i/3}$ , entonces $p_{\pm }=[1\pm \cos(2\pi /3)]/2$ , eso es, $p_{+}=1/4$ y $p_{-}=3/4$ En este caso, el resultado no es determinista, pero aun así encontramos el resultado. $|-\rangle$ como más probable, compatible con el hecho de que $2/3$ está más cerca de 1 que de 0.

En términos más generales, si $\lambda =e^{2\pi i\theta }$ , entonces $p_{+}\geq 1/2$ si y solo si $|\theta |\leq 1/4$ Esto es consistente con los resultados anteriores porque en los casos $\lambda =\pm 1$ , correspondiente a $\theta =0,1/2$ La fase se recupera de forma determinista, y las demás fases se recuperan con mayor precisión cuanto más cerca estén de estas dos.

Véase también

Referencias

↑ Kitaev, A. Yu (1995-11-20). "Mediciones cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .
1 2 Nielsen, Michael A. y Isaac L. Chuang (2001). Computación cuántica e información cuántica (Ed. reimpresa ). Cambridge [ua]: Cambridge Univ. Press. ISBN 978-0521635035.
↑ Mande, Nikhil S.; Ronald de Wolf (2023). "Límites ajustados para la estimación de fase cuántica y problemas relacionados". arXiv : 2305.04908 [ quant-ph ].
^ Benenti, Giuliano; Casati, Giulio; Strini, Giuliano (2004). Principios de información y computación cuántica (Reimpreso. Ed.). Nueva Jersey [ua]: Científico mundial. ISBN 978-9812388582.
1 2 Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 de enero de 1998). "Algoritmos cuánticos revisados". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 454 (1969): 339– 354. arXiv : quant-ph/9708016 . Bibcode : 1998RSPSA.454..339C . doi : 10.1098/rspa.1998.0164 . S2CID 16128238 .

[kitaev-1] Kitaev, A. Yu (1995-11-20). "Mediciones cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .

[nielchuan-2] 1 2 Nielsen, Michael A. y Isaac L. Chuang (2001). Computación cuántica e información cuántica (Ed. reimpresa ). Cambridge [ua]: Cambridge Univ. Press. ISBN 978-0521635035.

[optimality-3] Mande, Nikhil S.; Ronald de Wolf (2023). "Límites ajustados para la estimación de fase cuántica y problemas relacionados". arXiv : 2305.04908 [ quant-ph ].

[benet-4] Benenti, Giuliano; Casati, Giulio; Strini, Giuliano (2004). Principios de información y computación cuántica (Reimpreso. Ed.). Nueva Jersey [ua]: Científico mundial. ISBN 978-9812388582.

[ekert-5] 1 2 Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 de enero de 1998). "Algoritmos cuánticos revisados". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 454 (1969): 339– 354. arXiv : quant-ph/9708016 . Bibcode : 1998RSPSA.454..339C . doi : 10.1098/rspa.1998.0164 . S2CID 16128238 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]