El problema de estimación de fase

Esta sección de la lección explica el problema de estimación de fase. Comenzamos con una breve discusión del teorema espectral de álgebra lineal y luego pasamos a la formulación del problema de estimación de fase en sí.

Teorema espectral

El teorema espectral es un resultado importante del álgebra lineal que establece que las matrices de cierto tipo — llamadas matrices normales — pueden representarse de una forma simple y útil. Necesitamos este teorema en esta lección solo para matrices unitarias, pero más adelante en esta serie también lo aplicaremos a matrices hermitianas.

Matrices normales

Una matriz cuadrada $M$ con entradas complejas se denomina matriz normal si conmuta con su conjugada traspuesta: $M M^{\dagger} = M^{\dagger} M.$

Toda matriz unitaria $U$ es normal, porque

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

Las matrices hermitianas, es decir, matrices que son iguales a su propia conjugada traspuesta, son otra clase importante de matrices normales. Si $H$ es una matriz hermitiana, entonces

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

por lo que $H$ es normal.

No toda matriz cuadrada es normal. Por ejemplo, la siguiente matriz no es normal:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

(Este es un ejemplo simple pero excelente de una matriz que a menudo resulta muy útil de considerar.) No es normal porque

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

mientras que

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

Enunciado del teorema

Aquí hay un enunciado del teorema espectral.

Teorema

Teorema espectral: Sea $M$ una matriz compleja normal de $N\times N$. Existe una base ortonormal de vectores complejos $N$-dimensionales $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ y números complejos $\lambda_1,\ldots,\lambda_N$ tales que

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

La representación de una matriz en la forma

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

se conoce generalmente como descomposición espectral. Observa: si $M$ es una matriz normal expresada en la forma $(1)$, entonces la ecuación

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

debe cumplirse para cada $j = 1,\ldots,N$. Esto se deduce del hecho de que $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ es ortonormal:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

Es decir, cada número $\lambda_j$ es un valor propio de $M$ y $\vert\psi_j\rangle$ es un vector propio correspondiente a ese valor propio.

• Ejemplo 1. Sea

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  que es normal. El teorema implica que $\mathbb{I}$ puede escribirse en la forma $(1)$ para una elección adecuada de $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle$ y $\vert\psi_2\rangle$. Hay varias posibilidades, incluyendo

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  Observa que el teorema no dice que los números complejos $\lambda_1,\ldots,\lambda_N$ deban ser distintos — el mismo número complejo puede aparecer más de una vez, lo cual es necesario en este ejemplo. Esta elección funciona porque

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  De hecho, podríamos elegir $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ como cualquier base ortonormal y la ecuación se cumpliría. Por ejemplo:

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• Ejemplo 2. Consideremos una operación de Hadamard.

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

  Es una matriz unitaria, así que es normal. El teorema espectral implica que $H$ puede escribirse en la forma $(1)$, y en particular

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  donde

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  Más explícitamente:

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  Podemos verificar que esta descomposición es correcta realizando los cálculos necesarios:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

Como muestra el primer ejemplo anterior, puede haber cierta libertad en la elección de los vectores propios. En la elección de los valores propios, sin embargo, no hay ninguna libertad, salvo su orden: para una matriz dada $M$, siempre aparecen los mismos $N$ números complejos $\lambda_1,\ldots,\lambda_N$ en la ecuación $(1)$, que pueden incluir repeticiones del mismo número complejo.

Centrémonos ahora en las matrices unitarias. Supongamos que tenemos un número complejo $\lambda$ y un vector no nulo $\vert\psi\rangle$ que satisfacen la ecuación

$$U\vert\psi\rangle = \lambda\vert\psi\rangle \tag{2}$$

Es decir, $\lambda$ es un valor propio de $U$ y $\vert\psi\rangle$ es un vector propio correspondiente a ese valor propio.

Las matrices unitarias preservan la norma euclídea, y por lo tanto concluimos de $(2)$ lo siguiente.

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

La condición de que $\vert\psi\rangle$ no sea nulo implica que $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, por lo que podemos simplificar ambos lados y obtener:

$$\vert \lambda \vert = 1.$$

Esto muestra que los valores propios de matrices unitarias siempre tienen módulo uno y, por lo tanto, se encuentran en el círculo unitario.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(El símbolo $\mathbb{T}$ es un nombre común para el círculo unitario complejo. El nombre $S^1$ también es común.)

Enunciado del problema de estimación de fase

En el problema de estimación de fase, se da un estado cuántico $\vert \psi\rangle$ de $n$ qubits junto con un circuito cuántico unitario que actúa sobre $n$ qubits. Se promete que $\vert \psi\rangle$ es un vector propio de la matriz unitaria $U$ que describe la acción del circuito, y nuestro objetivo es calcular o aproximar el valor propio $\lambda$ correspondiente a $\vert \psi\rangle$. Como $\lambda$ está en el círculo unitario complejo, podemos escribir

$$\lambda = e^{2\pi i \theta}$$

para un número real único $\theta$ con $0\leq\theta<1$. El objetivo del problema es calcular o aproximar este número real $\theta$.

Problema de estimación de fase

Entrada: Un circuito cuántico unitario para una operación de $n$ qubits $U$ y un estado cuántico de $n$ qubits $\vert\psi\rangle$
Promesa: $\vert\psi\rangle$ es un vector propio de $U$
Salida: una aproximación del número $\theta\in[0,1)$ con $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Aquí hay algunas observaciones sobre esta formulación del problema:

1. El problema de estimación de fase difiere de otros problemas tratados hasta ahora en el curso en que la entrada incluye un estado cuántico. Normalmente nos centramos en problemas con entradas y salidas clásicas, pero nada impide considerar estados cuánticos como entradas. En cuanto a su relevancia práctica, el problema de estimación de fase típicamente aparece como un subproblema dentro de un cálculo mayor, como veremos más adelante en la lección en el contexto de la factorización de enteros.

2. La formulación anterior del problema de estimación de fase no es específica sobre qué constituye una aproximación de $\theta$, pero podemos establecer formulaciones más precisas del problema según nuestras necesidades e intereses. En el contexto de la factorización de enteros, requerimos una aproximación muy precisa de $\theta$, pero en otros casos podría bastarnos una aproximación muy burda. Comentaremos brevemente cómo la precisión requerida afecta al costo computacional de una solución.

3. Observa: cuando en el problema de estimación de fase pasamos de $\theta = 0$ hacia $\theta = 1$, recorremos completamente el círculo unitario, comenzando en $e^{2\pi i \cdot 0} = 1$ y moviéndonos en sentido antihorario hacia $e^{2\pi i \cdot 1} = 1$. Es decir, cuando alcanzamos $\theta = 1$, estamos de nuevo donde empezamos con $\theta = 0$. Así que cuando evaluamos la precisión de las aproximaciones, los valores de $\theta$ cercanos a $1$ deben considerarse cercanos a $0$. Por ejemplo, una aproximación $\theta = 0{,}999$ debe considerarse como dentro de $1/1000$ de $\theta = 0$.