O problema da estimativa de fase

Esta seção da lição explica o problema da estimativa de fase. Começaremos com uma breve discussão sobre o teorema espectral da álgebra linear e, em seguida, passaremos para o enunciado do problema da estimativa de fase em si.

Teorema espectral

O teorema espectral é um fato importante da álgebra linear que afirma que matrizes de um certo tipo, chamadas matrizes normais, podem ser expressas de uma forma simples e útil. Vamos precisar desse teorema apenas para matrizes unitárias nesta lição, mas mais adiante nesta série também o aplicaremos a matrizes hermitianas.

Matrizes normais

Uma matriz quadrada $M$ com entradas de números complexos é dita normal se ela comuta com sua transposta conjugada: $M M^{\dagger} = M^{\dagger} M.$

Toda matriz unitária $U$ é normal porque

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

As matrizes Hermitianas, que são matrizes iguais à sua própria transposta conjugada, são outra classe importante de matrizes normais. Se $H$ é uma matriz Hermitiana, então

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

portanto $H$ é normal.

Nem toda matriz quadrada é normal. Por exemplo, esta matriz não é normal:

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

(Este é um exemplo simples, mas excelente, de uma matriz que costuma ser muito útil de considerar.) Ela não é 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}$$

enquanto

$$\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 do teorema

A seguir está um enunciado do teorema espectral.

Teorema

Teorema espectral: Seja $M$ uma matriz complexa normal $N\times N$. Existe uma base ortonormal de vetores complexos $N$-dimensionais $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ junto com números complexos $\lambda_1,\ldots,\lambda_N$ tais que

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

A expressão de uma matriz na forma

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

é comumente chamada de decomposição espectral. Observe que, se $M$ é uma matriz normal expressa na forma $(1)$, então a equação

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

deve ser verdadeira para todo $j = 1,\ldots,N$. Isso é consequência do fato de que $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ é 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$$

Ou seja, cada número $\lambda_j$ é um autovalor de $M$ e $\vert\psi_j\rangle$ é um autovetor correspondente a esse autovalor.

• Exemplo 1. Seja

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

  que é normal. O teorema implica que $\mathbb{I}$ pode ser escrita na forma $(1)$ para alguma escolha de $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle$ e $\vert\psi_2\rangle.$ Há múltiplas escolhas que funcionam, incluindo

  $$\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.$$

  Observe que o teorema não diz que os números complexos $\lambda_1,\ldots,\lambda_N$ são distintos — podemos ter o mesmo número complexo repetido, o que é necessário para este exemplo. Essas escolhas funcionam porque

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

  De fato, poderíamos escolher $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ como qualquer base ortonormal e a equação continuaria válida. Por exemplo,

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

• Exemplo 2. Considere uma operação de Hadamard.

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

  Esta é uma matriz unitária, portanto é normal. O teorema espectral implica que $H$ pode ser escrita na forma $(1)$, e em particular temos

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

  onde

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

  De forma mais explícita,

  $$\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 essa decomposição está correta realizando os cálculos necessários:

  $$\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 o primeiro exemplo acima revela, pode haver alguma liberdade na escolha dos autovetores. No entanto, não há nenhuma liberdade na escolha dos autovalores, exceto quanto à sua ordenação: os mesmos $N$ números complexos $\lambda_1,\ldots,\lambda_N$, que podem incluir repetições do mesmo número complexo, sempre aparecerão na equação $(1)$ para uma dada matriz $M$.

Agora vamos nos concentrar nas matrizes unitárias. Suponha que temos um número complexo $\lambda$ e um vetor não nulo $\vert\psi\rangle$ que satisfazem a equação

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

Ou seja, $\lambda$ é um autovalor de $U$ e $\vert\psi\rangle$ é um autovetor correspondente a esse autovalor.

As matrizes unitárias preservam a norma euclidiana, e por isso concluímos o seguinte a partir de $(2)$.

$$\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\|$$

A condição de que $\vert\psi\rangle$ é não nulo implica que $\bigl\| \vert\psi\rangle \bigr\|\neq 0$, portanto podemos cancelá-lo de ambos os lados para obter

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

Isso revela que os autovalores de matrizes unitárias devem sempre ter valor absoluto igual a um, portanto estão sobre o círculo unitário.

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

(O símbolo $\mathbb{T}$ é um nome comum para o círculo unitário complexo. O nome $S^1$ também é comum.)

Enunciado do problema da estimativa de fase

No problema da estimativa de fase, recebemos um estado quântico $\vert \psi\rangle$ de $n$ qubits, juntamente com um circuito quântico unitário que age sobre $n$ qubits. Temos a promessa de que $\vert \psi\rangle$ é um autovetor da matriz unitária $U$ que descreve a ação do circuito, e nosso objetivo é calcular ou aproximar o autovalor $\lambda$ ao qual $\vert \psi\rangle$ corresponde. Mais precisamente, como $\lambda$ está sobre o círculo unitário complexo, podemos escrever

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

para um único número real $\theta$ satisfazendo $0\leq\theta<1$. O objetivo do problema é calcular ou aproximar esse número real $\theta$.

Problema da estimativa de fase

Entrada: Um circuito quântico unitário para uma operação $U$ de $n$ qubits juntamente com um estado quântico $\vert\psi\rangle$ de $n$ qubits
Promessa: $\vert\psi\rangle$ é um autovetor de $U$
Saída: uma aproximação para o número $\theta\in[0,1)$ satisfazendo $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Aqui estão algumas observações sobre este enunciado do problema:

1. O problema da estimativa de fase é diferente de outros problemas que vimos até agora no curso, pois a entrada inclui um estado quântico. Normalmente nos concentramos em problemas com entradas e saídas clássicas, mas nada nos impede de considerar entradas de estado quântico como esta. Em termos de relevância prática, o problema da estimativa de fase é tipicamente encontrado como um subproblema dentro de uma computação maior, como veremos no contexto da fatoração de inteiros mais adiante na lição.

2. O enunciado do problema da estimativa de fase acima não especifica o que constitui uma aproximação de $\theta$, mas podemos formular enunciados de problema mais precisos dependendo de nossas necessidades e interesses. No contexto da fatoração de inteiros, exigiremos uma aproximação muito precisa de $\theta$, mas em outros casos podemos nos satisfazer com uma aproximação muito grosseira. Discutiremos em breve como a precisão exigida afeta o custo computacional de uma solução.

3. Observe que, ao passarmos de $\theta = 0$ em direção a $\theta = 1$ no problema da estimativa de fase, estamos percorrendo todo o círculo unitário, partindo de $e^{2\pi i \cdot 0} = 1$ e movendo no sentido anti-horário em direção a $e^{2\pi i \cdot 1} = 1$. Ou seja, quando atingimos $\theta = 1$ voltamos ao ponto de partida em $\theta = 0$. Assim, ao considerarmos a precisão das aproximações, valores de $\theta$ próximos de $1$ devem ser considerados próximos de $0$. Por exemplo, uma aproximação $\theta = 0{,}999$ deve ser considerada a uma distância de no máximo $1/1000$ de $\theta = 0$.