Algoritmo cuántico de estimación de fase

En computación cuántica, el algoritmo cuántico de estimación de fase es un algoritmo cuántico que encuentra muchas aplicaciones como subrutina en otros algoritmos. El algoritmo cuántico de estimación de fase permite estimar la fase de un autovector de una puerta unitaria ${\displaystyle U}$.

El problema

Sea U un operador unitario que actúa sobre t qubits. Entonces todos los autovalores de ${\displaystyle U}$ tienen valor absoluto 1. Así el espectro de un operador unitario consiste en ${\displaystyle e^{2\pi i\varphi }}$. Dado un autovector ${\displaystyle \left|\psi \right\rangle }$, tal que ${\displaystyle U\left|\psi \right\rangle =e^{2\pi i\varphi }\left|\psi \right\rangle }$ tal que ${\displaystyle 0<\varphi <1}$, el objetivo es estimar ${\displaystyle \varphi }$. El algoritmo de estimación de fase resuelve este problema. En este caso, se asumen cajas negras tanto para preparar el estado ${\displaystyle U^{2^{j}}}$ como para preparar el autoestado ${\displaystyle \left|\psi \right\rangle }$^[1]​^[2]​

Circuito cuántico que representa el algoritmo de estimación de fase.

El algoritmo

Supuesto que se desea calcular las fases con una precisión de t bits. Para ello se preparan t qubits en el estado ${\displaystyle \left|0\right\rangle }$ conformando el primer registro sobre el que se almacenará la fase. En el segundo registro se almacena el autovector con tantos qubits como precisión queramos introducirle.

Acto seguido, los qubits del primer registro pasan por puertas de Hadamard dando lugar a los estados ${\displaystyle \left|+\right\rangle }$. La función de onda global puede ser descrita por:

${\displaystyle {\frac {1}{\sqrt {2^{n}}}}\sum _{x}\left|x\right\rangle \otimes \left|\psi \right\rangle }$

Acto seguido, se realizan t operaciones con puertas lógicas ${\displaystyle U^{2^{j}}}$ sobre el segundo registro.

Se llega por tanto a que tras la aplicación del circuito la salida viene dada por

${\displaystyle {\frac {\left(\left|0\right\rangle +e^{2\pi i(0.\varphi _{t})}\left|1\right\rangle \right)\left(\left|0\right\rangle +e^{2\pi i(0.\varphi _{t-1}\varphi _{t})}\left|1\right\rangle \right)...\left(\left|0\right\rangle +e^{2\pi i(0.\varphi _{1}\varphi _{2}...\varphi _{t})}\left|1\right\rangle \right)}{2^{t/2}}}}$

Dicho resultado presenta la forma de una transformada cuántica de Fourier. Luego, si se aplica la transformada cuántica de Fourier inversa se llega al proyector ${\displaystyle \left|0.\varphi _{1}\varphi _{2}...\varphi _{t}\right\rangle }$ y si se realiza una medida sobre los primeros t qubits se obtiene una estimación de la fase.

Si la fase es exactamente una raíz ${\displaystyle 2^{n}}$ de la unidad, la transformada cuántica de Fourier separa esa fase en expansión binaria. Si no, habrá una distribución agrupada probabilista en torno a la fase correcta.

Si ${\displaystyle \left|\psi \right\rangle }$ es realmente una superposición de estados propios, hay una distribución de probabilidad ponderada sobre el autoestado individual, con la ponderación dada por la probabilidad de Born. Esto es así porque los autoestados correspondientes a diferentes autovalores son ortogonales.

Nótese que este algoritmo solo es eficiente si podemos computar ${\displaystyle U^{2^{j}}}$ en un tiempo polinomial en ${\displaystyle j}$. Hay operadores unitarios para cuando es el caso, y los hay para cuando no lo es. Si solo tenemos acceso a ${\displaystyle U}$ como un oráculo, necesitaremos exponencialmente muchas llamadas a ${\displaystyle U}$ para computar ${\displaystyle U^{2^{j}}}$.^[1]​^[3]​

Realización y probabilidades

Se supone que ${\displaystyle \varphi }$ puede ser descrito por t bits. En caso de no ser así, este método es una buena aproximación a ${\displaystyle \varphi }$ con alta probabilidad. Sea ${\displaystyle b}$ un número entero descrito por t bits tal que ${\displaystyle b/2^{t}=0.b_{1}b_{2}..b_{t}}$ en su expresión binaria. Dicho número será la mejor aproximación a ${\displaystyle \varphi }$ con t qubits. Se define la diferencia como:

${\displaystyle \delta =\varphi -b/2^{t}}$

tal que cumple ${\displaystyle 0<\delta <2^{-t}}$. Esto supone que ambos se diferencian en el qubit t. Conocido que el estado final es una transformada de Fourier puede ser descrito por la siguiente expresión:

${\displaystyle {\frac {1}{2^{t/2}}}\sum _{k=0}^{2^{t}-1}e^{2\pi i\varphi k}\left|k\right\rangle }$

Conocido también que la transformada cuántica inversa de Fourier viene dada por

${\displaystyle \left|k\right\rangle \longrightarrow {\frac {1}{\sqrt {2^{t}}}}{\sum _{l=0}^{2^{t}-1}}e^{-2\pi ilk/2^{t}}\left|l\right\rangle }$

Si se le aplica al estado resultante del circuito se obtiene

${\displaystyle {\frac {1}{2^{t/2}}}{\frac {1}{2^{t/2}}}{\sum _{l=0}^{2^{t}-1}}{\sum _{k=0}^{2^{t}-1}}e^{-2\pi ilk/2^{t}}e^{2\pi i\varphi k}\left|l\right\rangle }$

Si se define ${\displaystyle \alpha _{l}}$ como la amplitud asociada al vector de la base ${\displaystyle \left|l+b\right\rangle }$ obtenemos

${\displaystyle {\frac {1}{2^{t}}}\sum _{k=0}^{2^{t}-1}e^{-2\pi i(l+b)k/2^{t}}e^{2\pi i\varphi k}\left|l+b\right\rangle }$ luego ${\displaystyle \alpha _{l}={\frac {1}{2^{t}}}\sum _{k=0}^{2^{t}-1}(e^{-2\pi i(l+b)/2^{t}}e^{2\pi i\varphi })^{k}}$

Si se aplica la fórmula de la suma de la serie geométrica se obtiene

${\displaystyle \alpha _{l}=2^{-t}\left({\frac {1-e^{2\pi i\{\varphi -(l+b)/2^{t}\}2^{t}}}{1-e^{2\pi i\{\varphi -(l+b)/2^{t}\}}}}\right)}$ y recordando la definición de ${\displaystyle \delta =\varphi -b/2^{t}}$

${\displaystyle \alpha _{l}=2^{-t}\left({\frac {1-e^{2\pi i(\delta -l/2^{t})2^{t}}}{1-e^{2\pi i(\delta -l/2^{t})}}}\right)}$

Conocido que ${\displaystyle \forall \theta }$ se cumple ${\displaystyle \mid 1-exp(i\theta )\mid \leq 2}$ se puede acotar el numerador por

${\displaystyle \alpha _{l}\leq {\frac {1}{2^{t}}}\left({\frac {2}{1-e^{2\pi i(\delta -l/2^{t})}}}\right)}$

Conocido que se puede demostrar también que ${\displaystyle \mid 1-exp(i\theta )\mid \geq {\frac {2\mid \theta \mid }{\pi }}}$ para ${\displaystyle -\pi \leq \theta \leq \pi }$ se puede acotar el denominador por

${\displaystyle \alpha _{l}\leq {\frac {1}{2^{t+1}}}\left({\frac {1}{\delta -l/2^{t}}}\right)}$

Al medir obtenemos un resultado ${\displaystyle m}$ cuya probabilidad de que se aleje una distancia ${\displaystyle e}$ de ${\displaystyle b}$ viene dada por

${\displaystyle P(\left|m-b\right|>e)={\underset {\scriptstyle -2^{t-1}<l<e+1}{\sum }}\left|\alpha _{l}\right|^{2}+{\underset {\scriptstyle e+1<l<2^{t-1}}{\sum }}\left|\alpha _{l}\right|^{2}}$

Sustituimos la acotación anterior y se llega a

${\displaystyle P(\left|m-b\right|>e)\leq {\underset {\scriptstyle -2^{t-1}+1<l<-(e+1)}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l-2^{t}\delta }}\right|^{2}+{\underset {\scriptstyle e+1<l<2^{t-1}}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l-2^{t}\delta }}\right|^{2}}$

Recordando que ${\displaystyle 0\leq 2^{t}\delta \leq 1}$ se puede llegar a

${\displaystyle P(\left|m-b\right|>e)\leq {\underset {\scriptstyle -2^{t-1}+1<l<-(e+1)}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l-1}}\right|^{2}+{\underset {\scriptstyle e+1<l<2^{t-1}}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l-1}}\right|^{2}}$

Dado que el índice de la primera sumatoria es negativo se puede acotar por

${\displaystyle P(\left|m-b\right|>e)\leq {\underset {\scriptstyle -2^{t-1}+1<l<-(e+1)}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l}}\right|^{2}+{\underset {\scriptstyle e+1<l<2^{t-1}}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l-1}}\right|^{2}}$ Si sobre la segunda sumatoria se define ${\displaystyle l'=-(l-1)}$

${\displaystyle P(\left|m-b\right|>e)\leq {\underset {\scriptstyle -2^{t-1}+1<l<-(e+1)}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l}}\right|^{2}+{\underset {\scriptstyle e<l'<2^{t-1}}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l'}}\right|^{2}}$

Si ahora sobre la primera sumatoria defino ${\displaystyle l''=-l}$

${\displaystyle P(\left|m-b\right|>e)\leq {\underset {\scriptstyle -(e+1)<l''<-2^{t-1}+1}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l''}}\right|^{2}+{\underset {\scriptstyle e<l'<2^{t-1}}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l'}}\right|^{2}\leq {\underset {\scriptstyle -(e+1)<l''<-2^{t-1}+1}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l''}}\right|^{2}+{\underset {\scriptstyle -(e+1)<l'<-2^{t-1}+1}{\sum }}{\frac {1}{4}}\left|{\frac {1}{l'}}\right|^{2}}$

Dado que se tiene la misma sumatoria se puede llegar a

${\displaystyle P(\left|m-b\right|>e)\leq {\frac {1}{2}}{\underset {\scriptstyle e<l<2^{t-1}-1}{\sum }}\left|{\frac {1}{l}}\right|^{2}}$ Dicha sumatoria se puede aproximar a integral como

${\displaystyle P(\left|m-b\right|>e)\leq {\frac {1}{2}}\int _{e-1}^{2^{t-1}-1}\left({\frac {1}{l}}\right)^{2}dl={\frac {1}{2(e-1)}}}$ donde se ha asumido que ${\displaystyle t}$ es muy grande

La probabilidad de que ${\displaystyle m}$ y ${\displaystyle b}$ disten menos que ${\displaystyle e}$ vendrá dada por

${\displaystyle P(\left|m-b\right|<e)=1-{\frac {1}{2(e-1)}}}$

Si tomo ${\displaystyle e=2^{t-n}-1}$ definiendo ${\displaystyle p=t-n}$ y sustituyendo la probabilidad de acierto será

${\displaystyle P(\left|m-b\right|<e)=1-{\frac {1}{2(2^{p}-1)}}}$ si se pretende que esta probabilidad sea prácticamente 1

${\displaystyle P(\left|m-b\right|<e)=1-{\frac {1}{2(2^{p}-1)}}=1-\epsilon }$ Entonces

${\displaystyle p=log\left(2+{\frac {2}{2\epsilon }}\right)}$ Luego, ${\displaystyle t=n+log\left(2+{\frac {2}{2\epsilon }}\right)}$

Luego, el número de qubits t debe repartirse entre ${\displaystyle p}$ que está relacionado con la probabilidad de error y ${\displaystyle n}$ que está relacionado con el número de qubits de precisión en ${\displaystyle \varphi }$^[1]​

Véase también

• Transformada cuántica de Fourier
• Algoritmo de Shor
• Algoritmo de búsqueda de orden para algoritmos cuánticos

Referencias

1. 1974-, Nielsen, Michael A., (2000). Quantum computation and quantum information. Cambridge University Press. ISBN 0521632358. OCLC 43641333. 
2. Aydinlioglu, Baris; Melkebeek, Dieter van (2012-06). «Nondeterministic Circuit Lower Bounds from Mildly De-randomizing Arthur-Merlin Games». 2012 IEEE 27th Conference on Computational Complexity (IEEE). ISBN 9780769547084. doi:10.1109/ccc.2012.32. 
3. «Abelian Hidden Subgroup Problem, 1995; Kitaev». SpringerReference (Springer-Verlag). 

• Datos: Q2835770