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 determinado . 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 si recuperara la fase o el 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 formal del problema.

Sea un operador unitario que actúa sobre un registro - qubit . La unitaridad implica que todos los valores propios de tienen módulo unitario y, por lo tanto, pueden caracterizarse por su fase. Por tanto, si es un vector propio de , entonces para algunos . Debido a la periodicidad de la exponencial compleja, siempre podemos suponer . ${\displaystyle U}$ ${\displaystyle m}$ ${\displaystyle U}$ ${\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}$

Nuestro objetivo es encontrar una buena aproximación con un número pequeño de puertas y con alta probabilidad. El algoritmo de estimación de fase cuántica logra esto bajo el supuesto de tener acceso oracular y tener disponible un estado cuántico. ${\displaystyle \theta }$ ${\displaystyle U}$ ${\displaystyle |\psi \rangle }$

Más precisamente, el algoritmo devuelve una aproximación para , con alta probabilidad dentro del error aditivo , utilizando qubits (sin contar los utilizados para codificar el estado del vector propio) y operaciones U controladas . Además, podemos mejorar la probabilidad de éxito de cualquiera utilizando un total de usos de U controlada, y esto es óptimo. ^[3] ${\displaystyle \theta }$ ${\displaystyle \varepsilon }$ ${\displaystyle O(\log(1/\varepsilon ))}$ ${\displaystyle O(1/\varepsilon )}$ ${\displaystyle 1-\Delta }$ ${\displaystyle \Delta >0}$ ${\displaystyle O(\log(1/\Delta )/\varepsilon )}$

el algoritmo

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

Configuración

La entrada consta de dos registros (es decir, dos partes): los qubits superiores comprenden el primer registro y los qubits inferiores son el segundo registro. ${\displaystyle n}$ ${\displaystyle m}$

El estado inicial del sistema es:

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

Después de aplicar la operación de puerta Hadamard de n bits en el primer registro, el estado pasa a ser: ${\displaystyle H^{\otimes n}}$

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

Sea un operador unitario con vector propio tal que . De este modo, ${\displaystyle U}$ ${\displaystyle |\psi \rangle }$ ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$

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

En general, la transformación implementada en los dos registros por las puertas controladas que se aplican es ${\displaystyle U,U^{2},U^{2^{2}},\ldots ,U^{2^{n-1}}}$

$${\displaystyle |k\rangle |\psi \rangle \mapsto |k\rangle U^{k}|\psi \rangle }$$

representación binaria ${\displaystyle k}$ ${\displaystyle k_{n-1}k_{n-2}\ldots k_{1}k_{0}}$ ${\displaystyle 2^{n-1}k_{n-1}+2^{n-2}k_{n-2}+\ldots +2k_{1}+k_{0}}$ ${\displaystyle k_{n-1},\ldots ,k_{1},k_{0}\in \{0,1\}}$ ${\displaystyle U^{k}}$

$${\displaystyle U^{2^{n-1}k_{n-1}+\ldots +2^{2}k_{2}+2k_{1}+k_{0}}=U^{2^{n-1}k_{n-1}}\ldots U^{2^{2}k_{2}}U^{2k_{1}}U^{k_{0}}}$$

${\displaystyle U^{2^{j}k_{j}}}$ ${\displaystyle k_{j}}$ ${\displaystyle 1}$ ${\displaystyle |k\rangle U^{k}|\psi \rangle }$ ${\displaystyle U^{2^{j}}}$ ${\displaystyle j}$

Por lo tanto, el estado será transformado por las puertas controladas así: ${\displaystyle U^{2^{j}}}$

$${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle \mapsto {\frac {1}{\sqrt {2^{n}}}}\sum _{j=0}^{2^{n}-1}e^{2\pi ij\theta }|j\rangle |\psi \rangle }$$

${\displaystyle |\psi \rangle }$

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

Aplicar la transformada cuántica inversa de Fourier

Aplicando la transformada cuántica inversa de Fourier en

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

rendimientos

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

Podemos aproximar el valor de redondeando al número entero más cercano. Esto significa que ¿ dónde está el número entero más cercano y la diferencia satisface ? ${\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}}}$

Usando esta descomposición podemos reescribir el estado como donde ${\textstyle \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}.}$

Medición

Realizar una medición en la base computacional en el primer registro produce el resultado con probabilidad ${\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}.}$$

^{[4] : 157  [5] : 348} ${\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) 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

Considere la instancia más simple posible del algoritmo, donde solo intervienen qubits, además de los qubits necesarios para codificar . Supongamos el valor propio de las lecturas . La primera parte del algoritmo genera el estado de un qubit . La aplicación del QFT inverso equivale en este caso a aplicar una puerta de Hadamard . Las probabilidades de resultado final son, por tanto , donde , o más explícitamente, ${\displaystyle n=1}$ ${\displaystyle |\psi \rangle }$ ${\displaystyle |\psi \rangle }$ ${\displaystyle \lambda =e^{2\pi i\theta }}$ ${\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 el contrario , 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é 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}$

De manera más general, si , entonces si y sólo si . Esto es consistente 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 cerca están de 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}$

Ver 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 (Repr. ed.). Cambridge [ua]: Universidad de Cambridge. Prensa. ISBN 978-0521635035.
3. Mande, Nikhil S.; Ronald de Wolf (2023). "Límites estrictos para la estimación de la fase cuántica y problemas relacionados". arXiv : 2305.04908 [cuántico-ph].
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.
5. Cleve, R.; Ekert, A.; Maquiavelo, C.; Mosca, M. (8 de enero de 1998). "Revisión de los algoritmos cuánticos". Actas de la Royal Society A: Ciencias Matemáticas, Físicas y de Ingeniería . 454 (1969): 339–354. arXiv : quant-ph/9708016 . Código Bib : 1998RSPSA.454..339C. doi :10.1098/rspa.1998.0164. S2CID  16128238.