El procedimiento de estimación de fase

A continuación, discutimos el procedimiento de estimación de fase, un algoritmo cuántico para resolver el problema de estimación de fase.

Comenzamos con un ejercicio de calentamiento de baja precisión que transmite la intuición básica detrás del método. Luego hablamos sobre la transformada cuántica de Fourier, una operación cuántica importante que se utiliza en el procedimiento de estimación de fase, así como sobre su implementación como circuito cuántico. Una vez que comprendamos la transformada cuántica de Fourier, describiremos el procedimiento de estimación de fase en toda su generalidad y analizaremos su rendimiento.

Calentamiento: aproximar fases con baja precisión

Comenzamos con un par de variantes simples del procedimiento de estimación de fase que proporcionan soluciones de baja precisión al problema de estimación de fase. Esto ayuda a explicar la intuición detrás del procedimiento general, que conoceremos un poco más adelante en la lección.

Usar el retroceso de fase

Un enfoque simple para el problema de estimación de fase, con el que podemos aprender algo sobre el valor buscado $\theta$, se basa en el fenómeno del retroceso de fase (phase kickback). Como veremos, se trata esencialmente de una versión de un solo qubit del procedimiento general de estimación de fase que se discutirá más adelante en la lección.

Como parte de la entrada para el problema de estimación de fase, tenemos un circuito cuántico unitario para la operación $U.$ Podemos usar la descripción de este circuito para crear un circuito para una operación $U$-controlada, lo cual ilustra la siguiente figura (con la operación $U,$ considerada como compuerta cuántica, a la izquierda, y una operación $U$-controlada a la derecha).

Podemos crear un circuito cuántico para una operación $U$-controlada añadiendo primero un qubit de control al circuito para $U$ y luego reemplazando cada compuerta en el circuito para $U$ por una versión controlada de esa compuerta — de modo que nuestro nuevo qubit de control controla efectivamente cada compuerta individual en el circuito para $U.$ Esto requiere que tengamos una versión controlada de cada compuerta en nuestro circuito, pero siempre podemos construir circuitos para estas operaciones controladas si no están incluidas en nuestro conjunto de compuertas.

Consideremos ahora el siguiente circuito, donde el estado de entrada $\vert\psi\rangle$ de todos los qubits excepto el superior es el estado cuántico de vector propio de $U$.

Las probabilidades del resultado de la medición para este circuito dependen del valor propio de $U$ que corresponde al vector propio $\vert\psi\rangle$. Analicemos el circuito en detalle para descubrir exactamente cómo.

El estado inicial del circuito es

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

y la primera compuerta de Hadamard transforma este estado a

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

A continuación se ejecuta la operación $U$-controlada, lo que lleva al estado

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Bajo el supuesto de que $\vert\psi\rangle$ es un vector propio de $U$ con valor propio $\lambda = e^{2\pi i\theta}$, podemos expresar este estado alternativamente de la siguiente manera.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Aquí observamos el fenómeno del retroceso de fase. Difiere un poco de lo que vimos con el algoritmo de Deutsch y el algoritmo de Deutsch-Jozsa, ya que no estamos trabajando con una compuerta de consulta — pero la idea es similar.

Finalmente, se ejecuta la segunda compuerta de Hadamard. Tras una pequeña simplificación, obtenemos la siguiente expresión para este estado.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

La medición produce por tanto los resultados $0$ y $1$ con estas probabilidades:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Aquí hay un diagrama de las probabilidades para los dos resultados posibles, $0$ y $1,$ como funciones de $\theta.$

Por su propia naturaleza, las dos probabilidades siempre suman $1.$ Obsérvese que si $\theta = 0,$ el resultado de la medición es siempre $0$, y si $\theta = 1/2,$ el resultado de la medición es siempre $1$. Así, aunque el resultado de la medición no revela exactamente cuál es $\theta$, nos proporciona cierta información al respecto — y si se nos hubiera prometido que $\theta = 0$ o $\theta = 1/2$, podríamos saber sin error cuál de los dos casos se da a partir del circuito.

Intuitivamente, el resultado de la medición del circuito puede entenderse como una estimación de $\theta$ con "un bit de precisión". En otras palabras, si escribiéramos $\theta$ en representación binaria y redondeáramos a un bit, obtendríamos un número como este:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

El resultado de la medición puede verse como una estimación del bit $a$. Si $\theta$ no es ni $0$ ni $1/2$, hay una probabilidad no nula de que la estimación sea incorrecta — pero la probabilidad de error se hace cada vez menor a medida que nos acercamos a $0$ o $1/2$.

Es natural preguntarse qué papel desempeñan las dos compuertas de Hadamard en este procedimiento:

• La primera compuerta de Hadamard pone el qubit de control en una superposición uniforme de $\vert 0\rangle$ y $\vert 1\rangle,$ de modo que el retroceso de fase ocurre en el estado $\vert 1\rangle$ y no en el estado $\vert 0\rangle,$ creando una diferencia de fase relativa que afecta a los resultados de la medición. Si no hiciéramos esto y el retroceso de fase creara una fase global, no tendría influencia en las probabilidades de los distintos resultados de la medición.

• La segunda compuerta de Hadamard nos permite aprender algo sobre el número $\theta$ a través del fenómeno de interferencia. Antes de la segunda compuerta de Hadamard, el qubit superior se encuentra en el estado

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  y si midiéramos este estado, obtendríamos $0$ y $1$ cada uno con probabilidad $1/2,$ lo que no nos dice nada sobre $\theta$. Sin embargo, mediante la segunda compuerta de Hadamard hacemos que el número $\theta$ influya en las probabilidades de salida.

Duplicar la fase

El circuito anterior utiliza el fenómeno del retroceso de fase para aproximar $\theta$ con un solo bit de precisión. Un bit de precisión puede ser suficiente en algunas situaciones — pero para la factorización necesitaremos mucha más precisión. Una pregunta natural es: ¿cómo podemos aprender más sobre $\theta$?

Una posibilidad muy sencilla consiste en reemplazar la operación $U$-controlada en nuestro circuito por dos copias de esta operación, como en este circuito:

Dos copias de una operación $U$-controlada equivalen a una operación $U^2$-controlada. Si $\vert\psi\rangle$ es un vector propio de $U$ con valor propio $\lambda = e^{2\pi i \theta}$, entonces este estado también es un vector propio de $U^2,$ esta vez con valor propio $\lambda^2 = e^{2\pi i (2\theta)}.$

Si ejecutamos esta versión del circuito, estamos realizando efectivamente el mismo cálculo que antes, solo que el número $\theta$ se reemplaza por $2\theta$. Aquí hay un diagrama que muestra las probabilidades de salida a medida que $\theta$ varía de $0$ a $1$.

Esto puede proporcionarnos efectivamente información adicional sobre $\theta$. Si la representación binaria de $\theta$ es

$$\theta = 0.a_1 a_2 a_3\cdots$$

entonces duplicar $\theta$ desplaza efectivamente el punto binario una posición a la derecha:

$$2\theta = a_1. a_2 a_3\cdots$$

Como identificamos $\theta = 1$ con $\theta = 0$ al movernos por el círculo unitario, el bit $a_1$ no tiene influencia en nuestras probabilidades, y obtenemos efectivamente una estimación del segundo bit después del punto binario al redondear $\theta$ a dos bits. Si supiéramos de antemano que $\theta$ es $0$ o $1/4$, por ejemplo, podríamos confiar completamente en el resultado de la medición.

Sin embargo, no queda inmediatamente claro cómo debería reconciliarse esta estimación con lo aprendido del circuito original (no duplicado) de retroceso de fase para obtener la información más precisa posible sobre $\theta$. Demos entonces un paso atrás y pensemos en cómo debemos proceder.

Estimación de fase con dos qubits

En lugar de considerar las dos opciones descritas anteriormente por separado, las combinamos en un único circuito de la siguiente manera.

Las compuertas de Hadamard después de las operaciones controladas se han eliminado, y aquí todavía no hay mediciones. Ampliaremos el circuito a medida que evaluemos nuestras opciones para obtener la mejor información posible sobre $\theta$.

Si ejecutamos este circuito mientras $\vert\psi\rangle$ es un vector propio de $U$, el estado de los qubits inferiores permanece siendo $\vert\psi\rangle$ a lo largo de todo el circuito, y las fases se "retroceden" al estado de los dos qubits superiores. Analicemos el circuito cuidadosamente con la ayuda de la siguiente figura.

Podemos escribir el estado $\vert\pi_1\rangle$ de la siguiente manera:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Cuando se ejecuta la primera operación $U$-controlada, el valor propio $\lambda = e^{2\pi i\theta}$ se "retrocede" a la fase cuando $a_0$ (el qubit superior) es igual a $1$, pero no cuando es $0$. El estado resultante se puede expresar así:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Las segundas y terceras compuertas $U$-controladas hacen algo similar, pero para $a_1$ en lugar de $a_0,$ y con $\theta$ reemplazado por $2\theta.$ El estado resultante se puede expresar así:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Si consideramos la cadena binaria $a_1 a_0$ como un entero $x \in \{0,1,2,3\}$ en representación binaria, es decir, $x = 2 a_1 + a_0,$ podemos expresar este estado alternativamente de la siguiente manera.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Nuestro objetivo es extraer de este estado la mayor cantidad posible de información sobre $\theta$.

En este punto, consideramos un caso especial en el que se nos promete que $\theta = \frac{y}{4}$ para un entero $y\in\{0,1,2,3\}$. En otras palabras, $\theta\in \{0, 1/4, 1/2, 3/4\},$ de modo que podemos expresar este número exactamente en representación binaria con dos bits, como $$.00,$$.01,$$.10$o$.11.$En general,$\theta$no tiene por qué ser ninguno de estos cuatro valores, pero considerar este caso especial nos ayuda a determinar cómo extraer información sobre$\theta$ de la manera más efectiva en general.

Primero, definimos un vector de estado de dos qubits para cada valor posible $y \in \{0, 1, 2, 3\}$.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Tras simplificar los términos exponenciales, podemos escribir estos vectores de la siguiente manera.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Estos vectores son ortogonales: si elegimos cualquier par de ellos y calculamos su producto interno, obtenemos $0.$ Cada uno es también un vector unitario, de modo que $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ es una base ortonormal. Por lo tanto, sabemos inmediatamente que existe una medición que puede distinguirlos perfectamente — es decir, si se nos da uno de ellos sin decirnos cuál, podemos averiguar sin error cuál es.

Para realizar tal distinción con un circuito cuántico, podemos primero definir una operación unitaria $V$ que transforme los estados de la base estándar en los cuatro estados listados anteriormente.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Para escribir $V$ como una matriz $4\times 4$, simplemente tomamos los estados $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ como columnas de $V.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Esta es una matriz especial que algunos lectores seguramente ya habrán encontrado: se trata de la matriz asociada con la transformada discreta de Fourier de dimensión $4$. Dado este hecho, no la denotamos con $V,$ sino con $\mathrm{QFT}_4.$ El nombre $\mathrm{QFT}$ significa transformada cuántica de Fourier — que es esencialmente la transformada discreta de Fourier considerada como una operación unitaria. Discutiremos la transformada cuántica de Fourier con más detalle y mayor generalidad en breve.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Podemos aplicar la inversa de esta operación para ir en la dirección contraria y transformar los estados $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ en los estados de la base estándar $\vert 0\rangle,\ldots,\vert 3\rangle$. Si hacemos eso, podemos medir para descubrir qué valor $y\in\{0,1,2,3\}$ describe $\theta$ como $\theta = y/4$. Aquí hay un diagrama de un circuito cuántico que hace exactamente eso.

En resumen, cuando ejecutamos este circuito con $\theta = y/4$ para $y\in\{0,1,2,3\},$ el estado justo antes de las mediciones es $\vert \psi\rangle \vert y\rangle$ (donde $y$ se codifica como una cadena binaria de dos dígitos), de modo que las mediciones revelan el valor $y$ sin error.

Este circuito está motivado por el caso especial $\theta \in \{0,1/4,1/2,3/4\}$ — pero podemos ejecutarlo para cualquier elección de $U$ y $\vert \psi\rangle$ y, por tanto, para cualquier valor de $\theta$. Aquí hay un diagrama de las probabilidades de salida que produce el circuito para valores arbitrarios de $\theta$.

Esto es una mejora notable respecto a la variante de un solo qubit descrita anteriormente en la lección. No es perfecto — puede darnos una respuesta incorrecta — pero el resultado está fuertemente concentrado en valores de $y$ para los cuales $y/4$ está cerca de $\theta$. En particular, el resultado más probable siempre corresponde al valor $y/4$ más cercano a $\theta$ (identificando de nuevo $\theta = 0$ y $\theta = 1$), y a partir del diagrama parece que este valor más cercano para $x$ siempre aparece con una probabilidad justo por encima del $40\%.$ Si $\theta$ está exactamente a medio camino entre dos de tales valores, como por ejemplo $\theta = 0.375,$ los dos valores de $y$ igualmente cercanos son igualmente probables.

Preparación para generalizar a muchos qubits

Dada la mejora que acabamos de lograr al usar dos qubits de control en lugar de uno junto con la inversa de la transformada cuántica de Fourier de dimensión $4$, es natural generalizar esto aún más — añadiendo más qubits de control. Al hacerlo, obtenemos el procedimiento de estimación de fase general. Veremos pronto cómo funciona, pero para poder describirlo con precisión, necesitamos discutir la transformada cuántica de Fourier con mayor generalidad, para ver cómo se define para otras dimensiones y cómo podemos implementarla (o su inversa) con un circuito cuántico.

Transformada cuántica de Fourier

La transformada cuántica de Fourier es una operación unitaria que puede definirse para cualquier entero positivo $N$. En esta sección vemos cómo se define esta operación y cómo puede implementarse con un circuito cuántico sobre $m$ qubits con un coste de $O(m^2)$ cuando $N = 2^m.$

Las matrices que describen la transformada cuántica de Fourier se derivan de una operación análoga sobre vectores $N$-dimensionales conocida como transformada discreta de Fourier. Esta operación puede entenderse de diversas maneras. Por ejemplo, podemos considerar la transformada discreta de Fourier en términos puramente abstractos y matemáticos como una aplicación lineal. O podemos considerarla en términos computacionales, donde se nos da un vector $N$-dimensional de números complejos (suponiendo que las partes real e imaginaria de las entradas están codificadas en representación binaria) y el objetivo es calcular el vector $N$-dimensional que resulta de aplicar la transformada discreta de Fourier. Nuestro enfoque está en una tercera forma de ver esta transformación, a saber, como una operación unitaria que puede realizarse sobre un sistema cuántico.

Existe un algoritmo eficiente para calcular la transformada discreta de Fourier sobre un vector de entrada dado, conocido como la transformada rápida de Fourier. Tiene aplicaciones en el procesamiento de señales y muchos otros campos, y es considerado por muchos como uno de los algoritmos más importantes jamás descubiertos. La implementación de la transformada cuántica de Fourier para el caso en que $N$ es una potencia de dos se basa exactamente en la misma estructura subyacente que hace posible la transformada rápida de Fourier.

Definición de la transformada cuántica de Fourier

Para definir la transformada cuántica de Fourier, primero definimos un número complejo $\omega_N$ para cada entero positivo $N$ de la siguiente manera:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Este es el número en el círculo unitario complejo que obtenemos si comenzamos en $1$ y nos movemos en sentido antihorario un ángulo de $2\pi/N$ radianes, es decir, una fracción de $1/N$ de la circunferencia. Aquí hay algunos ejemplos:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Ahora podemos definir la transformada cuántica de Fourier $N$-dimensional, que se describe mediante una matriz $N\times N$ cuyas filas y columnas se asocian a los estados de la base estándar $\vert 0\rangle,\ldots,\vert N-1\rangle$. Para la estimación de fase solo necesitamos esta operación para $N = 2^m$ como potencia de dos, pero la operación puede definirse para cualquier entero positivo $N$.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Como ya se menciónó, esta es la matriz asociada con la transformada discreta de Fourier $N$-dimensional. A menudo el factor inicial $1/\sqrt{N}$ no se incluye en la definición de esta matriz, pero debemos incluirlo para obtener una matriz unitaria.

Aquí está la transformada cuántica de Fourier como matriz para algunos valores pequeños de $N.$

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Obsérvese en particular que $\mathrm{QFT}_2$ es otro nombre para la operación de Hadamard.

Unitariedad

Verifiquemos que $\mathrm{QFT}_N$ es unitaria para cada elección de $N$. Una forma de hacerlo es mostrar que sus columnas forman una base ortonormal. Podemos definir un vector correspondiente a la columna numerada $y$, comenzando en $y = 0$ y hasta $y = N-1,$ de la siguiente manera:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

El producto interno de cualquier par de estos vectores da la siguiente expresión:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Tales sumas pueden evaluarse utilizando la siguiente fórmula para la suma de los primeros $N$ términos de una serie geométrica.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

En particular, podemos aplicar esta fórmula con $\alpha = \omega_N^{y-z}$. Para $y = z$ tenemos $\alpha = 1,$ y la fórmula da, tras dividir por $N$:

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Para $y\neq z$ tenemos $\alpha \neq 1,$ y la fórmula da:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Esto se debe a que $\omega_N^N = e^{2\pi i} = 1,$ por lo que $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ lo que hace el numerador cero, mientras que el denominador es distinto de cero ya que $\omega_N^{y-z} \neq 1.$ Intuitivamente, estamos sumando una serie de puntos distribuidos uniformemente sobre el círculo unitario — se cancelan mutuamente y dan $0.$

Hemos demostrado así que $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ es un conjunto ortonormal,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

lo que demuestra que $\mathrm{QFT}_N$ es unitaria.

Compuertas de fase controladas

Para implementar la transformada cuántica de Fourier con un circuito cuántico, necesitamos compuertas de fase controladas. Recordemos que una operación de fase es una operación unitaria de un solo qubit de la forma

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

para un número real arbitrario $\alpha.$ La versión controlada de esta compuerta tiene la siguiente matriz:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Para esta compuerta controlada, no importa cuál qubit es el qubit de control y cuál es el qubit objetivo, ya que ambas posibilidades son equivalentes. En los diagramas de circuitos cuánticos, esta compuerta puede representarse mediante cualquiera de los siguientes símbolos.

En la tercera forma, la etiqueta $\alpha$ a veces se coloca al costado de la línea de control o debajo del punto de control inferior, si eso resulta más práctico.

Para realizar la transformada cuántica de Fourier para $N = 2^m$ con $m\geq 2$, necesitamos ejecutar una operación sobre $m$ qubits cuyo efecto sobre los estados de la base estándar puede describirse de la siguiente manera:

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

donde $a$ es un bit e $y \in \{0,\ldots,2^{m-1} - 1\}$ es un número codificado en representación binaria como una cadena de $m-1$ bits. Esto puede lograrse utilizando compuertas de fase controladas, generalizando el siguiente ejemplo para $m=5$.

En general, para una elección arbitraria de $m\geq 2$, el qubit superior, que corresponde al bit $a$, puede considerarse como el qubit de control, con las compuertas de fase $P_{\alpha}$ variando desde $\alpha = \pi/2^{m-1}$ en el qubit del bit menos significativo de $y$ hasta $\alpha = \frac{\pi}{2}$ en el qubit del bit más significativo de $y$. Estas compuertas de fase controladas conmutan entre sí y pueden ejecutarse en cualquier orden.

Implementación en circuito de la QFT

Ahora veamos cómo puede implementarse la transformada cuántica de Fourier con un circuito cuando la dimensión $N = 2^m$ es una potencia de dos. De hecho, hay varias formas de implementar la transformada cuántica de Fourier, pero este es posiblemente el método conocido más sencillo. Una vez que sabemos cómo implementar la transformada cuántica de Fourier con un circuito cuántico, implementar su inversa es directo: podemos reemplazar cada compuerta por su inversa (es decir, su traspuesta conjugada) y aplicar las compuertas en orden inverso. Cualquier circuito cuántico compuesto exclusivamente por compuertas unitarias puede invertirse de esta manera.

La implementación tiene naturaleza recursiva, por lo que se describe más naturalmente de esa forma. El caso base es $m=1,$ en el que la transformada cuántica de Fourier corresponde a una operación de Hadamard.

Para realizar la transformada cuántica de Fourier sobre $m$ qubits para $m \geq 2$, podemos ejecutar los siguientes pasos, cuyo efecto describimos para estados de la base estándar de la forma $\vert x \rangle \vert a\rangle$, donde $x\in\{0,\ldots,2^{m-1} - 1\}$ es un entero codificado como $m-1$ bits en representación binaria, y $a$ es un solo bit.

1. Primero, se aplica la transformada cuántica de Fourier $2^{m-1}$-dimensional a los $m-1$ qubits inferiores/izquierdos para obtener este estado:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Esto se hace aplicando recursivamente el método aquí descrito para un qubit menos, con la operación de Hadamard sobre un solo qubit como caso base.

2. El qubit superior/derecho se usa como qubit de control para inyectar la fase $\omega_{2^m}^y$ para cada estado de la base estándar $\vert y\rangle$ de los $m-1$ qubits restantes (como se describió anteriormente), para obtener este estado:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Se aplica una compuerta de Hadamard al qubit superior/derecho para obtener este estado:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. El orden de los qubits se permuta de modo que el bit menos significativo se convierta en el bit más significativo y todos los demás se desplacen hacia arriba/derecha:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Aquí está, por ejemplo, el circuito que obtenemos para $N = 32 = 2^5$. En este diagrama, los qubits se etiquetan con nombres que corresponden a los vectores de la base estándar $\vert x\rangle \vert a\rangle$ (para la entrada) e $\vert b\rangle \vert y\rangle$ (para la salida), para mejorar la claridad.

Análisis

La fórmula clave que necesitamos para verificar que el circuito recién descrito implementa la transformada cuántica de Fourier $2^m$-dimensional es:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Esta fórmula es válida para enteros arbitrarios $a,$ $b,$ $x$ e $y,$ pero solo se necesita para $a,b\in\{0,1\}$ y $x,y\in\{0,\ldots,2^{m-1}-1\}$. Puede verificarse expandiendo el producto en el exponente del lado derecho:

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

donde la segunda igualdad utiliza la observación de que

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

La transformada cuántica de Fourier $2^m$-dimensional se define, para cada $u\in\{0,\ldots,2^m - 1\}$, de la siguiente manera.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Escribiendo $u$ y $v$ como

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

para $a,b\in\{0,1\}$ y $x,y\in\{0,\ldots,2^{m-1} - 1\},$ obtenemos

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Finalmente, cuando consideramos los estados de la base estándar $\vert x \rangle \vert a\rangle$ e $\vert b \rangle \vert y \rangle$ como codificaciones binarias de enteros en el rango $\{0,\ldots,2^m-1\}$,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

reconocemos que el circuito anterior implementa la operación deseada. Si este método para realizar la transformada cuántica de Fourier parece notable — lo es: es esencialmente la transformada rápida de Fourier en forma de circuito cuántico.

Para terminar, contemos cuántas compuertas utiliza el circuito descrito. Las compuertas de fase controladas no pertenecen al conjunto de compuertas estándar que discutimos en la lección anterior, pero por ahora ignoramos eso y contamos cada una de ellas como una sola compuerta.

Sea $s_m$ el número de compuertas necesarias para cada elección posible de $m$. Para $m=1$ la transformada cuántica de Fourier es solo una operación de Hadamard, así que

$$s_1 = 1.$$

Para $m\geq 2$ necesitamos en el circuito anterior $s_{m-1}$ compuertas para la transformada cuántica de Fourier sobre $m-1$ qubits, más $m-1$ compuertas de fase controladas, más una compuerta de Hadamard, más $m-1$ compuertas de intercambio (swap), así que

$$s_m = s_{m-1} + (2m - 1).$$

Sumando obtenemos una expresión cerrada:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

En realidad, no necesitamos tantas compuertas de intercambio como describe el método. Si reordenamos un poco las compuertas, podemos desplazar todas las compuertas de intercambio a la derecha y reducir el número de compuertas de intercambio necesarias a $\lfloor m/2\rfloor$. Asintóticamente, esto no es una mejora esencial: seguimos obteniendo circuitos de tamaño $O(m^2)$ para calcular $\mathrm{QFT}_{2^m}.$

Si queremos implementar la transformada cuántica de Fourier usando exclusivamente compuertas de nuestro conjunto estándar, necesitamos construir exactamente o aproximar cada compuerta de fase controlada mediante compuertas de nuestro conjunto. El número necesario depende de cuánta precisión exijamos, pero como función de $m$, el coste total sigue siendo cuadrático.

De hecho, es posible aproximar muy bien la transformada cuántica de Fourier con un número subcuadrático de compuertas, aprovechando que $P_{\alpha}$ está muy cerca de la operación identidad cuando $\alpha$ es muy pequeño — lo que significa que podemos simplemente omitir la mayoría de las compuertas de fase controladas sin perder demasiada precisión.

Procedimiento general y análisis

Ahora examinamos el procedimiento de estimación de fase en general. La idea consiste en generalizar de la manera natural la versión de dos qubits de la estimación de fase que consideramos anteriormente, como muestra el siguiente diagrama.

Obsérvese que por cada nuevo qubit de control añadido arriba, el número de ejecuciones de la operación unitaria $U$ se duplica. Esto se indica en el diagrama mediante las potencias de $U$ en las operaciones unitarias controladas individuales.

La forma más directa de implementar una operación $U^k$-controlada para una elección de $k$ es simplemente repetir una operación $U$-controlada $k$ veces. Si se usa realmente este método, hay que tener en cuenta que añadir qubits de control afecta significativamente el tamaño del circuito: si tenemos $m$ qubits de control, como se muestra en el diagrama, se necesitan un total de $2^m - 1$ copias de la operación $U$-controlada. Esto significa que a medida que $m$ aumenta, se incurre en un coste computacional considerable — pero como veremos, esto también conduce a una aproximación significativamente más precisa de $\theta.$

Sin embargo, es importante señalar que para ciertas elecciones de $U$, puede ser posible crear un circuito que implemente la operación $U^k$ para valores grandes de $k$ de manera más eficiente que simplemente repetir el circuito para $U$ $k$ veces. Veremos un ejemplo concreto de esto en el contexto de la factorización de enteros más adelante en esta lección, donde el algoritmo eficiente para la exponenciación modular, tratado en la lección anterior, viene en nuestra ayuda.

Ahora analicemos el circuito que acabamos de describir. El estado inmediatamente antes de la transformada cuántica de Fourier inversa es el siguiente:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Un caso especial

De forma similar a la versión con $m=2$, consideremos primero el caso especial en que $\theta = y/2^m$ para $y\in\{0,\ldots,2^m-1\}.$ En este caso, el estado antes de la transformada cuántica de Fourier inversa puede escribirse alternativamente como:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Tras aplicar la transformada cuántica de Fourier inversa, el estado se convierte en

$$\vert\psi\rangle \vert y\rangle$$

y las mediciones dan $y$ (en codificación binaria).

Acotación de las probabilidades

Para otros valores de $\theta,$ es decir, aquellos que no tienen la forma $y/2^m$ para un entero $y$, los resultados de la medición no son predecibles con certeza, pero podemos demostrar cotas para las probabilidades de los distintos resultados. A continuación consideramos una elección arbitraria de $\theta$ con $0\leq \theta < 1.$

Tras aplicar la transformada cuántica de Fourier inversa, el circuito se encuentra en el estado:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Al medir los $m$ qubits superiores, cada resultado $y$ ocurre con probabilidad

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2$$

Para entender mejor estas probabilidades, usamos la misma fórmula de antes para la suma del segmento inicial de una serie geométrica.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Podemos simplificar la suma en la fórmula de $p_y$ estableciendo $\alpha = e^{2\pi i (\theta - y/2^m)}$. El resultado es:

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

En el caso $\theta = y/2^m$ obtenemos $p_y = 1$ (lo que ya sabíamos del caso especial), y en el caso $\theta \neq y/2^m$ obtenemos

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Aprendemos más sobre estas probabilidades examinando la relación entre longitudes de arco y cuerda en el círculo unitario. La siguiente figura muestra las relaciones relevantes para un número real arbitrario $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

Primero, la longitud de la cuerda (azul) nunca puede ser mayor que la longitud del arco (violeta):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Considerando la relación en la otra dirección: la razón entre la longitud del arco y la longitud de la cuerda es mayor en $\delta = \pm 1/2,$ y en ese caso la razón corresponde a la mitad de la circunferencia del círculo dividida por el diámetro, es decir, $\pi/2.$ Por tanto:

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

y así

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Un análisis basado en estas relaciones produce las dos afirmaciones siguientes.

1. Supongamos que $\theta$ es un número real e $y\in \{0,\ldots,2^m-1\}$ satisface

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Esto significa que $y/2^m$ es la mejor aproximación de $m$ bits de $\theta$, o que se encuentra exactamente a medio camino entre $y/2^m$ y $(y-1)/2^m$ o $(y+1)/2^m$ — es decir, representa una de las dos mejores aproximaciones de $\theta$.

   Mostraremos que $p_y$ debe ser bastante grande en este caso. De la suposición considerada se deduce que $\vert 2^m \theta - y \vert \leq 1/2,$ por lo que podemos aplicar la segunda observación sobre longitudes de arco y cuerda para concluir:

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   También podemos usar la primera observación sobre longitudes de arco y cuerda para concluir:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   De estas dos desigualdades se obtiene para $p_y$:

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Esto explica nuestra observación de que el mejor resultado en la versión con $m=2$ de la estimación de fase aparece con una probabilidad superior al $40\%$. Exactamente, no es $40\%$, sino $4/\pi^2,$ y esta cota es válida para cualquier elección de $m.$

2. Supongamos ahora que $y\in \{0,\ldots,2^m-1\}$ satisface:

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Esto significa que existe una mejor aproximación $z/2^m$ de $\theta$ que se encuentra entre $\theta$ e $y/2^m$.

   Esta vez mostraremos que $p_y$ no puede ser demasiado grande. Comenzamos con la observación simple de que

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   lo que se deduce del hecho de que dos puntos cualesquiera sobre el círculo unitario pueden estar separados en valor absoluto a lo sumo por $2$.

   También podemos aplicar la segunda observación sobre longitudes de arco y cuerda de arriba, esta vez al denominador de $p_y$ en lugar del numerador, para concluir:

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Juntas, las dos desigualdades dan:

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Esta cota es suficiente para nuestros propósitos, pero es bastante burda — la probabilidad suele ser significativamente menor que $1/4.$

La conclusión más importante de este análisis es que las muy buenas aproximaciones de $\theta$ ocurren con alta probabilidad — obtenemos una mejor aproximación de $m$ bits con una probabilidad superior al $40\%$ — mientras que las aproximaciones que se desvían más de $2^{-m}$ ocurren con menos frecuencia, con una probabilidad de a lo sumo $25\%.$

Dadas estas garantías, es posible aumentar la confianza en el resultado repitiendo el procedimiento de estimación de fase varias veces para recopilar evidencia estadística sobre $\theta$. Es importante señalar que el estado $\vert\psi\rangle$ del grupo inferior de qubits no se altera por el procedimiento de estimación de fase y, por lo tanto, puede usarse para cualquier número de ejecuciones del procedimiento. En particular, en cada ejecución del circuito obtenemos una mejor aproximación de $m$ bits de $\theta$ con una probabilidad superior al $40\%,$ mientras que la probabilidad de una desviación mayor que $2^{-m}$ está acotada superiormente por $25\%$. Si ejecutamos el circuito varias veces y tomamos el resultado que aparece con más frecuencia, es muy poco probable que este resultado más frecuente sea uno que ocurre a lo sumo el $25\%$ de las veces. Como consecuencia, obtendremos con muy alta probabilidad una aproximación $y/2^m$ que difiere de $\theta$ en menos de $1/2^m$. La probabilidad de equivocarse por más de $1/2^m$ disminuye de hecho exponencialmente con el número de ejecuciones del procedimiento.

Aquí hay dos diagramas que muestran las probabilidades para tres valores consecutivos de $y$ con $m = 3$ y $m=4$ como funciones de $\theta$. (Por claridad, solo se muestran tres resultados. Las probabilidades para otros resultados se obtienen por desplazamiento cíclico de la misma función base.)