Algoritmo de estimación de fase cuántica

Algoritmo cuántico para la estimación de valores propios

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 . Debido a 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 de manera equivalente como la recuperación de la fase o del valor propio en sí. El algoritmo fue introducido inicialmente por Alexei Kitaev en 1995. ^{[1] [2] : 246}

La estimación de fase se utiliza con frecuencia como una 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 y cúbits, respectivamente. Sea un operador unitario que actúa sobre el registro - cúbit . Los valores propios de un operador unitario tienen módulo unitario y, por lo tanto, se caracterizan por su fase. Por lo tanto, si es un vector propio de , entonces, para algún . Debido a la periodicidad de la exponencial compleja, siempre podemos suponer que . ${\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}$

El objetivo es producir una buena aproximación para 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 suponiendo un acceso oracular a y teniendo disponible como un estado cuántico. Esto significa que cuando analizamos la eficiencia del algoritmo solo nos preocupamos por la cantidad de veces que se necesita usarlo, pero no por el costo de implementación en sí. ${\displaystyle \theta }$ ${\displaystyle U}$ ${\displaystyle |\psi \rangle }$ ${\displaystyle U}$ ${\displaystyle U}$

Más precisamente, el algoritmo retorna con alta probabilidad una aproximación para , dentro de un error aditivo , usando qubits en el primer registro y operaciones U controladas . Además, podemos mejorar la probabilidad de éxito a para cualquier usando un total de usos de U controladas, y esto es óptimo. ^[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 )}$

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:

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

donde es el estado del -qubit que evoluciona a través de . Primero aplicamos la operación de compuerta Hadamard de n-qubits en el primer registro, que produce el estado: Nótese que aquí estamos cambiando entre la representación binaria y -aria para el registro del -qubit: el ket en el lado derecho es una abreviatura para el estado del -qubit , donde es la descomposición binaria de . ${\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}$

Operaciones en U controlada

Este estado evoluciona entonces a través de la evolución unitaria controlada cuya acción puede escribirse como para todos . Esta evolución también puede escribirse concisamente como lo que resalta su naturaleza controlada: se aplica al segundo registro condicionalmente a que el primer registro sea . Recordando la condición del valor propio que se cumple para , al aplicar a , obtenemos , donde usamos . ${\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^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$

Para demostrar que también se puede implementar de manera eficiente, observe que podemos escribir , donde denota la operación de aplicar al segundo registro condicionalmente al -ésimo qubit del primer registro siendo . Formalmente, estas puertas se pueden caracterizar por su acción como Esta ecuación se puede interpretar como que dice que el estado se deja sin cambios cuando , es decir, cuando el -ésimo qubit es , mientras que la puerta se aplica al segundo registro cuando el -ésimo qubit es . La composición de estas puertas controladas da así con el último paso que sigue directamente de la descomposición binaria . ${\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 }}$

A partir de este punto, el segundo registro queda intacto, por lo que conviene escribir , con el estado del registro -qubit, que es el único que debemos tener en cuenta para el resto del algoritmo. ${\displaystyle |\Psi _{2}\rangle =|{\tilde {\Psi }}_{2}\rangle \otimes |\psi \rangle }$ ${\displaystyle |{\tilde {\Psi }}_{2}\rangle }$ ${\displaystyle n}$

Aplicar la transformada cuántica de Fourier inversa

La parte final del circuito implica aplicar la transformada cuántica de Fourier inversa (QFT) en el primer registro de : La QFT y su inversa se caracterizan por su acción sobre los estados base como Se deduce que ${\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 .}$

Descomponiendo el estado en la base computacional como los coeficientes, entonces iguales , donde escribimos con es el entero más cercano a . La diferencia debe satisfacer por definición . Esto equivale a aproximar el valor de redondeándolo al entero más cercano. ${\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 }$

Medición

El paso final implica realizar una medición en la base computacional en el primer registro. Esto produce el resultado con probabilidad De ello se deduce que si , es decir, cuando se puede escribir como , siempre se encuentra el resultado . Por otro lado, si , la probabilidad se lee De esta expresión podemos ver que cuando . Para ver esto, observamos que de la definición de tenemos la desigualdad , y por lo tanto: ^{[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}}}$$

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

Ejemplos de juguetes

Consideremos la instancia más simple posible del algoritmo, donde solo qubit, además de los qubits requeridos para codificar , está involucrado. Supongamos que el valor propio de las lecturas , . La primera parte del algoritmo genera el estado de un qubit . Aplicar la QFT inversa equivale en este caso a aplicar una puerta de Hadamard . Las probabilidades del resultado final son, por lo tanto , donde , o más explícitamente, Supongamos , lo que significa . Entonces , , y recuperamos de manera determinista el valor preciso de a partir de los resultados de la medición. Lo mismo se aplica si . ${\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}$

Si, por otra parte , entonces , es decir, y . En este caso, el resultado no es determinista, pero aun así encontramos que el resultado es más probable, compatible con el hecho de que está más cerca de 1 que de 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}$

En términos más generales, si , entonces si y solo si . Esto es coherente con los resultados anteriores porque en los casos , correspondientes a , la fase se recupera de manera determinista, y las otras fases se recuperan con mayor precisión cuanto más cercanas estén a estas dos. ${\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}$

Véase también

• Algoritmo de Shor
• Algoritmo de conteo cuántico
• Medición de paridad

Referencias

1. Kitaev, A. Yu (20 de noviembre de 1995). "Medidas cuánticas y el problema del estabilizador abeliano". arXiv : quant-ph/9511026 .
2. Nielsen, Michael A. e Isaac L. Chuang (2001). Computación cuántica e información cuántica (edición revisada). Cambridge [ua]: Cambridge Univ. Press. ISBN 978-0521635035.
3. Mande, Nikhil S.; Ronald de Wolf (2023). "Límites estrictos para la estimación de fase cuántica y problemas relacionados". arXiv : 2305.04908 [quant-ph].
4. Benenti, Giuliano; Casati, Giulio; Strini, Giuliano (2004). Principios de computación cuántica e información (edición reimpresa). Nueva Jersey [ua]: World Scientific. ISBN 978-9812388582.
5. Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 de enero de 1998). "Revisión de algoritmos cuánticos". Actas de la Royal Society A: Ciencias matemáticas, físicas e ingeniería . 454 (1969): 339–354. arXiv : quant-ph/9708016 . Bibcode :1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.