Procedimento de estimação de fase

A seguir, vamos discutir o procedimento de estimação de fase, que é um algoritmo quântico para resolver o problema de estimação de fase.

Começaremos com um aquecimento de baixa precisão, que explica a intuição básica por trás do método. Em seguida, falaremos sobre a transformada quântica de Fourier, que é uma operação quântica importante usada no procedimento de estimação de fase, bem como sua implementação em circuito quântico. Com a transformada quântica de Fourier em mãos, descreveremos o procedimento de estimação de fase em sua generalidade completa e analisaremos seu desempenho.

Aquecimento: aproximando fases com baixa precisão

Começaremos com algumas versões simples do procedimento de estimação de fase que fornecem soluções de baixa precisão para o problema de estimação de fase. Isso é útil para explicar a intuição por trás do procedimento geral que veremos um pouco mais adiante na lição.

Usando o phase kickback

Uma abordagem simples para o problema de estimativa de fase, que nos permite aprender algo sobre o valor $\theta$ que buscamos, é baseada no fenômeno de phase kick-back. Como veremos, essa é essencialmente uma versão de um único qubit do procedimento geral de estimativa de fase a ser discutido mais adiante na lição.

Como parte da entrada para o problema de estimativa de fase, temos um circuito quântico unitário para a operação $U$. Podemos usar a descrição desse circuito para criar um circuito para uma operação controlada-$U$, que pode ser representada como esta figura sugere (com a operação $U$, vista como uma porta quântica, à esquerda e uma operação controlada-$U$ à direita).

Podemos criar um circuito quântico para uma operação controlada-$U$ primeiro adicionando um qubit de controle ao circuito de $U$ e, em seguida, substituindo cada porta no circuito de $U$ por uma versão controlada dessa porta — de modo que nosso novo qubit de controle efetivamente controla cada porta no circuito de $U$. Isso requer que tenhamos uma versão controlada de cada porta em nosso circuito, mas sempre podemos construir circuitos para essas operações controladas caso não estejam incluídas em nosso conjunto de portas.

Agora considere o circuito a seguir, onde o estado de entrada $\vert\psi\rangle$ de todos os qubits, exceto o de cima, é um vetor de estado quântico que é autovetor de $U$.

As probabilidades dos resultados de medição desse circuito dependem do autovalor de $U$ correspondente ao autovetor $\vert\psi\rangle$. Vamos analisar o circuito em detalhes para determinar exatamente como.

O estado inicial do circuito é

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

e a primeira porta Hadamard transforma esse estado em

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

Em seguida, a operação controlada-$U$ é realizada, o que resulta no 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.$$

Usando a suposição de que $\vert\psi\rangle$ é um autovetor de $U$ com autovalor $\lambda = e^{2\pi i\theta}$, podemos alternativamente expressar esse estado da seguinte forma.

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

Aqui observamos o fenômeno do phase kickback. É um pouco diferente desta vez do que foi para o algoritmo de Deutsch e o algoritmo de Deutsch-Jozsa porque não estamos trabalhando com uma porta de consulta — mas a ideia é semelhante.

Finalmente, a segunda porta Hadamard é realizada. Após uma pequena simplificação, obtemos esta expressão para esse 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)$$

A medição, portanto, produz os resultados $0$ e $1$ com 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}$$

Aqui está um gráfico das probabilidades para os dois possíveis resultados, $0$ e $1$, como funções de $\theta$.

Naturalmente, as duas probabilidades sempre somam $1$. Observe que quando $\theta = 0$, o resultado da medição é sempre $0$, e quando $\theta = 1/2$, o resultado da medição é sempre $1$. Portanto, embora o resultado da medição não revele exatamente qual é $\theta$, ele nos fornece alguma informação sobre ele — e se nos fosse prometido que ou $\theta = 0$ ou $\theta = 1/2$, poderíamos descobrir pelo circuito qual é o correto sem erro.

Intuitivamente falando, podemos pensar no resultado da medição do circuito como uma estimativa para $\theta$ com "um bit de precisão." Em outras palavras, se escrevêssemos $\theta$ em notação binária e o arredondássemos para um bit, teríamos um número assim:

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

O resultado da medição pode ser visto como uma estimativa para o bit $a$. Quando $\theta$ não é nem $0$ nem $1/2$, há uma probabilidade não nula de que a estimativa esteja errada — mas a probabilidade de cometer um erro fica cada vez menor conforme nos aproximamos de $0$ ou $1/2$.

É natural perguntar qual papel as duas portas Hadamard desempenham neste procedimento:

• A primeira porta Hadamard coloca o qubit de controle em uma superposição uniforme de $\vert 0\rangle$ e $\vert 1\rangle$, de modo que quando o phase kickback ocorre, ele acontece para o estado $\vert 1\rangle$ e não para o $\vert 0\rangle$, criando uma diferença de fase relativa que afeta os resultados da medição. Se não fizéssemos isso e o phase kickback produzisse uma fase global, não teria nenhum efeito nas probabilidades de se obter diferentes resultados de medição.

• A segunda porta Hadamard nos permite aprender algo sobre o número $\theta$ através do fenômeno da interferência. Antes da segunda porta Hadamard, o estado do qubit do topo é

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

  e se fôssemos medir esse estado, obteríamos $0$ e $1$ cada um com probabilidade $1/2$, sem aprender nada sobre $\theta$. Ao aplicar a segunda porta Hadamard, porém, fazemos com que o número $\theta$ afete as probabilidades de saída.

Dobrando a fase

O circuito acima usa o fenômeno do phase kickback para aproximar $\theta$ com um único bit de precisão. Um bit de precisão pode ser tudo que precisamos em algumas situações — mas para a fatoração vamos precisar de muito mais precisão do que isso. Uma pergunta natural é: como podemos aprender mais sobre $\theta?$

Uma coisa muito simples que podemos fazer é substituir a operação controlada-$U$ em nosso circuito por duas cópias dessa operação, como neste circuito:

Duas cópias de uma operação controlada-$U$ são equivalentes a uma operação controlada-$U^2$. Se $\vert\psi\rangle$ é um autovetor de $U$ com autovalor $\lambda = e^{2\pi i \theta}$, então esse estado também é um autovetor de $U^2$, desta vez com autovalor $\lambda^2 = e^{2\pi i (2\theta)}$.

Portanto, se executarmos esta versão do circuito, estamos efetivamente realizando o mesmo cálculo de antes, exceto que o número $\theta$ é substituído por $2\theta$. Aqui está um gráfico ilustrando as probabilidades de saída conforme $\theta$ varia de $0$ a $1$.

Fazer isso pode de fato nos fornecer informações adicionais sobre $\theta$. Se a representação binária de $\theta$ for

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

então dobrar $\theta$ efetivamente desloca a vírgula binária uma posição para a direita:

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

E como estamos equiparando $\theta = 1$ com $\theta = 0$ ao percorrer o círculo unitário, vemos que o bit $a_1$ não influencia nossas probabilidades, e estamos efetivamente obtendo uma estimativa para o segundo bit após a vírgula binária se arredondarmos $\theta$ para dois bits. Por exemplo, se soubéssemos de antemão que $\theta$ era $0$ ou $1/4$, poderíamos confiar totalmente no resultado da medição para nos dizer qual é.

Não é imediatamente claro, porém, como essa estimativa deve ser conciliada com o que aprendemos do circuito original de phase kickback (não dobrado) para nos dar as informações mais precisas possíveis sobre $\theta$. Então, vamos dar um passo atrás e considerar como proceder.

Estimação de fase com dois qubits

Em vez de considerar as duas opções descritas acima separadamente, vamos combiná-las em um único circuito, assim.

As portas Hadamard após as operações controladas foram removidas e ainda não há medições aqui. Adicionaremos mais ao circuito conforme consideramos nossas opções para aprender o máximo possível sobre $\theta$.

Se executarmos este circuito quando $\vert\psi\rangle$ for um autovetor de $U$, o estado dos qubits inferiores permanecerá $\vert\psi\rangle$ durante todo o circuito, e as fases serão "chutadas" para o estado dos dois qubits superiores. Vamos analisar o circuito cuidadosamente, por meio da figura a seguir.

Podemos escrever o estado $\vert\pi_1\rangle$ assim:

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

Quando a primeira operação controlada-$U$ é executada, o autovalor $\lambda = e^{2\pi i\theta}$ é kickeado para a fase quando $a_0$ (o qubit do topo) é igual a $1$, mas não quando é $0$. Assim, podemos expressar o estado resultante dessa forma:

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

As segunda e terceira portas controladas-$U$ fazem algo semelhante, exceto para $a_1$ em vez de $a_0$, e com $\theta$ substituído por $2\theta$. Podemos expressar o estado resultante assim:

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

Se pensarmos na string binária $a_1 a_0$ como representando um inteiro $x \in \{0,1,2,3\}$ em notação binária, que é $x = 2 a_1 + a_0$, podemos expressar esse estado de forma alternativa como segue.

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

Nosso objetivo é extrair o máximo de informação possível sobre $\theta$ a partir desse estado.

Neste ponto, vamos considerar um caso especial, em que nos é prometido que $\theta = \frac{y}{4}$ para algum inteiro $y\in\{0,1,2,3\}.$ Em outras palavras, temos $\theta\in \{0, 1/4, 1/2, 3/4\},$ portanto podemos expressar esse número exatamente em notação binária com dois bits, como .$00,$ .$01,$ .$10,$ ou .$11.$ Em geral, $\theta$ pode não ser um desses quatro valores, mas pensar nesse caso especial nos ajudará a descobrir como extrair informações sobre $\theta$ da forma mais eficaz em geral.

Primeiro, vamos definir um vetor de estado de dois qubits para cada valor possível $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$$

Após simplificar as exponenciais, podemos escrever esses vetores da seguinte forma.

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

Esses vetores são ortogonais: se escolhermos qualquer par deles e calcularmos o produto interno, obtemos $0$. Cada um é também um vetor unitário, portanto $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ é uma base ortonormal. Portanto, sabemos imediatamente que existe uma medição capaz de discriminá-los perfeitamente — o que significa que, se nos for dado um deles sem saber qual, podemos descobrir qual é sem erro.

Para realizar essa discriminação com um circuito quântico, podemos primeiro definir uma operação unitária $V$ que transforma estados da base padrão nos quatro estados listados acima.

$$\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 escrever $V$ como uma matriz $4\times 4$, basta tomar as colunas de $V$ como os estados $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$.

$$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 é uma matriz especial, e é provável que alguns leitores já a tenham encontrado antes: é a matriz associada à transformada discreta de Fourier de dimensão $4$. Em vista desse fato, vamos chamá-la pelo nome $\mathrm{QFT}_4$ em vez de $V$. O nome $\mathrm{QFT}$ é uma abreviação de quantum Fourier transform — que é essencialmente apenas a transformada discreta de Fourier, vista como uma operação unitária. Discutiremos a transformada quântica de Fourier com mais detalhes e generalidade em 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 a inversa dessa operação para ir no sentido contrário, transformando os estados $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ de volta nos estados da base padrão $\vert 0\rangle,\ldots,\vert 3\rangle$. Se fizermos isso, podemos medir para descobrir qual valor $y\in\{0,1,2,3\}$ descreve $\theta$ como $\theta = y/4$. Aqui está o diagrama de um circuito quântico que faz isso.

Para resumir, se executarmos este circuito quando $\theta = y/4$ para $y\in\{0,1,2,3\}$, o estado imediatamente antes das medições ocorrerem será $\vert \psi\rangle \vert y\rangle$ (com $y$ codificado como uma string binária de dois bits), portanto as medições revelarão o valor $y$ sem erro.

Este circuito é motivado pelo caso especial em que $\theta \in \{0,1/4,1/2,3/4\}$ — mas podemos executá-lo para qualquer escolha de $U$ e $\vert \psi\rangle$, e portanto para qualquer valor de $\theta$, que desejarmos. Aqui está um gráfico das probabilidades de saída que o circuito produz para escolhas arbitrárias de $\theta$.

Esta é uma melhora clara em relação à variante de um único qubit descrita anteriormente na lição. Não é perfeita — pode nos dar a resposta errada — mas a resposta está fortemente inclinada para valores de $y$ para os quais $y/4$ está próximo de $\theta$. Em particular, o resultado mais provável sempre corresponde ao valor de $y/4$ mais próximo de $\theta$ (equiparando $\theta = 0$ e $\theta = 1$ como antes), e pelo gráfico parece que esse valor mais próximo para $x$ sempre aparece com probabilidade um pouco acima de $40\%$. Quando $\theta$ está exatamente no meio entre dois desses valores, como $\theta = 0.375$ por exemplo, os dois valores de $y$ igualmente próximos são igualmente prováveis.

Preparando-se para generalizar para muitos qubits

Dada a melhoria que acabamos de obter usando dois qubits de controle em vez de um, em conjunto com a inversa da transformada quântica de Fourier de dimensão $4$, é natural considerar generalizá-la ainda mais — adicionando mais qubits de controle. Quando fazemos isso, obtemos o procedimento geral de estimação de fase. Veremos como isso funciona em breve, mas para descrevê-lo com precisão precisaremos discutir a transformada quântica de Fourier com maior generalidade, para ver como ela é definida em outras dimensões e como podemos implementá-la (ou sua inversa) com um circuito quântico.

Transformada Quântica de Fourier

A transformada quântica de Fourier é uma operação unitária que pode ser definida para qualquer dimensão inteira positiva $N$. Nesta seção, veremos como essa operação é definida e como ela pode ser implementada com um circuito quântico em $m$ qubits com custo $O(m^2)$ quando $N = 2^m$.

As matrizes que descrevem a transformada quântica de Fourier são derivadas de uma operação análoga em vetores de dimensão $N$ conhecida como transformada discreta de Fourier. Essa operação pode ser vista de diferentes ângulos. Por exemplo, podemos pensar na transformada discreta de Fourier em termos puramente abstratos e matemáticos, como um mapeamento linear. Ou podemos pensá-la em termos computacionais, onde recebemos um vetor de dimensão $N$ de números complexos (usando notação binária para codificar as partes real e imaginária das entradas, por exemplo) e o objetivo é calcular o vetor de dimensão $N$ obtido ao aplicar a transformada discreta de Fourier. Nosso foco será numa terceira abordagem: ver essa transformação como uma operação unitária que pode ser realizada em um sistema quântico.

Existe um algoritmo eficiente para calcular a transformada discreta de Fourier em um vetor de entrada dado, conhecido como transformada rápida de Fourier. Ela tem aplicações em processamento de sinais e em muitas outras áreas, sendo considerada por muitos como um dos algoritmos mais importantes já descobertos. Como veremos, a implementação da transformada quântica de Fourier quando $N$ é uma potência de 2 se baseia exatamente na mesma estrutura subjacente que torna a transformada rápida de Fourier possível.

Definição da transformada quântica de Fourier

Para definir a transformada quântica de Fourier, vamos primeiro definir um número complexo $\omega_N$, para cada inteiro positivo $N$, da seguinte forma:

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

Esse é o número no círculo unitário complexo que obtemos partindo de $1$ e nos movendo no sentido anti-horário por um ângulo de $2\pi/N$ radianos, ou seja, uma fração de $1/N$ da circunferência do círculo. Aqui estão alguns exemplos:

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

Agora podemos definir a transformada quântica de Fourier de dimensão $N$, descrita por uma matriz $N\times N$ cujas linhas e colunas estão associadas aos estados da base padrão $\vert 0\rangle,\ldots,\vert N-1\rangle$. Vamos precisar dessa operação apenas quando $N = 2^m$ é uma potência de $2$ para a estimação de fase, mas a operação pode ser definida para qualquer inteiro 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 já foi dito, essa é a matriz associada à transformada discreta de Fourier de dimensão $N$. Frequentemente o fator prefatorial de $1/\sqrt{N}$ não é incluído na definição dessa matriz, mas precisamos incluí-lo para obter uma matriz unitária.

A seguir temos a transformada quântica de Fourier, escrita como matriz, para alguns valores pequenos 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}$$

Observe, em particular, que $\mathrm{QFT}_2$ é outro nome para a operação de Hadamard.

Unitariedade

Vamos verificar que $\mathrm{QFT}_N$ é unitária para qualquer escolha de $N$. Uma forma de fazer isso é mostrar que suas colunas formam uma base ortonormal. Podemos definir um vetor correspondente à coluna número $y$, começando em $y = 0$ e indo até $y = N-1$, da seguinte forma:

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

Calculando o produto interno entre dois desses vetores quaisquer, obtemos a seguinte expressão:

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

Podemos avaliar somas como essa usando a seguinte fórmula para a soma dos primeiros $N$ termos de uma série 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}$$

Especificamente, podemos usar essa fórmula quando $\alpha = \omega_N^{y-z}$. Quando $y = z$, temos $\alpha = 1$, e aplicando a fórmula e dividindo por $N$ obtemos

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

Quando $y\neq z$, temos $\alpha \neq 1$, e a fórmula revela o seguinte:

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

Isso ocorre porque $\omega_N^N = e^{2\pi i} = 1$, logo $\omega_N^{N(y-z)} = 1^{y-z} = 1$, tornando o numerador zero, enquanto o denominador é não nulo pois $\omega_N^{y-z} \neq 1$. Intuitivamente, o que estamos fazendo é somar um conjunto de pontos distribuídos ao longo do círculo unitário — e eles se cancelam, resultando em $0$ quando somados.

Estabelecemos, portanto, que $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ é um conjunto ortonormal,

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

o que revela que $\mathrm{QFT}_N$ é unitário.

Portas de fase controladas

Para implementar a transformada quântica de Fourier com um circuito quântico, precisaremos usar as portas de fase controlada. Lembre-se de que uma operação de fase é uma operação unitária de um qubit da forma

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

para qualquer número real $\alpha$. A versão controlada dessa porta tem a seguinte 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 essa porta controlada, não importa qual qubit é o controle e qual é o alvo, pois as duas possibilidades são equivalentes. Podemos usar qualquer um dos seguintes símbolos para representar essa porta em diagramas de circuito quântico.

Na terceira forma, o rótulo $\alpha$ às vezes também é colocado na lateral da linha de controle ou abaixo do controle inferior, quando isso for conveniente.

Para realizar a transformada quântica de Fourier quando $N = 2^m$ e $m\geq 2$, vamos precisar de uma operação em $m$ qubits cuja ação sobre os estados da base padrão pode ser descrita como

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

onde $a$ é um bit e $y \in \{0,\ldots,2^{m-1} - 1\}$ é um número codificado em notação binária como uma cadeia de $m-1$ bits. Isso pode ser feito usando portas de fase controlada generalizando o exemplo a seguir, para o qual $m=5$.

Em geral, para uma escolha arbitrária de $m\geq 2$, o qubit do topo, correspondente ao bit $a$, pode ser visto como o controle, com as portas de fase $P_{\alpha}$ variando de $\alpha = \pi/2^{m-1}$ no qubit correspondente ao bit menos significativo de $y$ até $\alpha = \frac{\pi}{2}$ no qubit correspondente ao bit mais significativo de $y$. Essas portas de fase controlada comutam entre si e podem ser realizadas em qualquer ordem.

Implementação em circuito da QFT

Agora veremos como implementar a transformada quântica de Fourier com um circuito quando a dimensão $N = 2^m$ é uma potência de $2$. Existem, na verdade, múltiplas formas de implementar a transformada quântica de Fourier, mas essa é indiscutivelmente o método mais simples conhecido. Uma vez que sabemos como implementar a transformada quântica de Fourier com um circuito quântico, implementar sua inversa é direto: basta substituir cada porta por sua inversa (ou, equivalentemente, sua transposta conjugada) e aplicar as portas na ordem inversa. Todo circuito quântico composto apenas de portas unitárias pode ser invertido dessa forma.

A implementação tem natureza recursiva, e por isso é mais natural descrevê-la dessa forma. O caso base é $m=1$, em que a transformada quântica de Fourier é uma operação de Hadamard.

Para realizar a transformada quântica de Fourier em $m$ qubits quando $m \geq 2$, podemos executar os seguintes passos, cujas ações descreveremos para estados da base padrão da forma $\vert x \rangle \vert a\rangle$, onde $x\in\{0,\ldots,2^{m-1} - 1\}$ é um inteiro codificado como $m-1$ bits em notação binária e $a$ é um único bit.

1. Primeiro aplique a transformada quântica de Fourier de dimensão $2^{m-1}$ aos $m-1$ qubits inferiores/da esquerda para obter 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.$$

   Isso é feito aplicando recursivamente o método descrito para um qubit a menos, usando a operação de Hadamard em um único qubit como caso base.

2. Use o qubit superior/da direita como controle para injetar a fase $\omega_{2^m}^y$ para cada estado da base padrão $\vert y\rangle$ dos $m-1$ qubits restantes (conforme descrito acima) para obter 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. Aplique uma porta de Hadamard no qubit superior/da direita para obter 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. Permute a ordem dos qubits de forma que o bit menos significativo se torne o mais significativo, com todos os outros deslocados para cima/direita:

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

Por exemplo, aqui está o circuito que obtemos para $N = 32 = 2^5$. Neste diagrama, os qubits recebem nomes que correspondem aos vetores da base padrão $\vert x\rangle \vert a\rangle$ (para a entrada) e $\vert b\rangle \vert y\rangle$ (para a saída), para maior clareza.

Análise

A fórmula-chave que precisamos para verificar que o circuito descrito acima implementa a transformada quântica de Fourier de dimensão $2^m$ é a seguinte:

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

Essa fórmula vale para qualquer escolha de inteiros $a,$ $b,$ $x,$ e $y,$ mas só vamos precisar dela para $a,b\in\{0,1\}$ e $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Ela pode ser verificada expandindo o produto no expoente do lado direito:

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

onde a segunda igualdade usa a observação de que

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

A transformada quântica de Fourier de dimensão $2^m$ é definida da seguinte forma para todo $u\in\{0,\ldots,2^m - 1\}$.

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

Se escrevermos $u$ e $v$ como

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

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

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

Por fim, pensando nos estados da base padrão $\vert x \rangle \vert a\rangle$ e $\vert b \rangle \vert y \rangle$ como codificações binárias de inteiros no intervalo $\{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}$$

vemos que o circuito acima implementa a operação requerida. Se esse método para realizar a transformada quântica de Fourier parece notável, é porque realmente é: trata-se essencialmente da transformada rápida de Fourier na forma de um circuito quântico.

Por fim, vamos contar quantas portas são usadas no circuito descrito. As portas de fase controlada não fazem parte do conjunto de portas padrão que discutimos na lição anterior, mas, por ora, vamos ignorar isso e contar cada uma delas como uma única porta.

Seja $s_m$ o número de portas necessárias para cada possível escolha de $m$. Se $m=1$, a transformada quântica de Fourier é apenas uma operação de Hadamard, portanto

$$s_1 = 1.$$

Se $m\geq 2$, então no circuito acima precisamos de $s_{m-1}$ portas para a transformada quântica de Fourier em $m-1$ qubits, mais $m-1$ portas de fase controlada, mais uma porta de Hadamard e mais $m-1$ portas de troca (swap), portanto

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

Podemos obter uma expressão em forma fechada somando:

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

Na prática, não precisamos de tantas portas de troca quanto o método descreve. Se reorganizarmos um pouco as portas, podemos empurrar todas as portas de troca para a direita e reduzir o número necessário a $\lfloor m/2\rfloor$. Assintoticamente, isso não é uma grande melhoria: ainda obtemos circuitos de tamanho $O(m^2)$ para realizar $\mathrm{QFT}_{2^m}$.

Se quisermos implementar a transformada quântica de Fourier usando apenas portas do nosso conjunto padrão, precisamos construir ou aproximar cada uma das portas de fase controlada com portas do nosso conjunto. O número necessário depende da precisão requerida, mas como função de $m$ o custo total permanece quadrático.

De fato, é possível aproximar a transformada quântica de Fourier com bastante precisão usando um número sub-quadrático de portas, aproveitando o fato de que $P_{\alpha}$ é muito próxima da operação identidade quando $\alpha$ é muito pequeno — o que significa que podemos simplesmente omitir a maioria das portas de fase controlada sem perder muita precisão.

Procedimento geral e análise

Agora vamos examinar o procedimento de estimativa de fase de forma geral. A ideia é estender a versão de dois qubits da estimativa de fase que consideramos acima, da maneira natural sugerida pelo diagrama a seguir.

Observe que, para cada novo qubit de controle adicionado no topo, dobramos o número de vezes que a operação unitária $U$ é executada. Isso é indicado no diagrama pelas potências em $U$ para cada uma das operações unitárias controladas.

A forma mais direta de implementar uma operação $U^k$ controlada para algum valor de $k$ é simplesmente repetir a operação $U$ controlada $k$ vezes. Se essa for de fato a metodologia utilizada, é preciso reconhecer que a adição de qubits de controle contribui significativamente para o tamanho do circuito: se temos $m$ qubits de controle, como o diagrama mostra, um total de $2^m - 1$ cópias da operação $U$ controlada são necessárias. Isso significa que um custo computacional significativo é incorrido conforme $m$ aumenta — mas, como veremos, isso também leva a uma aproximação de $\theta$ significativamente mais precisa.

É importante notar, entretanto, que para algumas escolhas de $U$ pode ser possível criar um circuito que implemente a operação $U^k$ para valores grandes de $k$ de forma mais eficiente do que simplesmente repetir $k$ vezes o circuito para $U$. Veremos um exemplo específico disso no contexto da fatoração de inteiros mais adiante na lição, onde o algoritmo eficiente para exponenciação modular discutido na lição anterior entra em cena.

Agora vamos analisar o circuito recém-descrito. O estado imediatamente antes da transformada quântica de Fourier inversa é o seguinte:

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

Um caso especial

De maneira semelhante ao que fizemos no caso $m=2$, vamos primeiro considerar o caso especial em que $\theta = y/2^m$ para $y\in\{0,\ldots,2^m-1\}$. Nesse caso, o estado antes da transformada quântica de Fourier inversa pode ser escrito alternativamente assim:

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

Assim, quando a transformada quântica de Fourier inversa é aplicada, o estado se torna

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

e as medições revelam $y$ (codificado em binário).

Limitando as probabilidades

Para outros valores de $\theta$, ou seja, aqueles que não assumem a forma $y/2^m$ para um inteiro $y$, os resultados das medições não serão certos, mas podemos provar limites para as probabilidades dos diferentes resultados. A partir de agora, vamos considerar uma escolha arbitrária de $\theta$ satisfazendo $0\leq \theta < 1$.

Após a transformada quântica de Fourier inversa ser realizada, o estado do circuito é:

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

Assim, quando as medições nos $m$ qubits do topo são realizadas, observamos cada resultado $y$ com probabilidade

$$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 melhor essas probabilidades, vamos usar a mesma fórmula que vimos antes, para a soma da porção inicial de uma série 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 a soma que aparece na fórmula de $p_y$ tomando $\alpha = e^{2\pi i (\theta - y/2^m)}$. Eis o que obtemos.

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

Portanto, no caso em que $\theta = y/2^m$, encontramos que $p_y = 1$ (como já sabíamos ao considerar esse caso especial), e no caso em que $\theta \neq y/2^m$, encontramos que

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

Podemos aprender mais sobre essas probabilidades pensando em como os comprimentos de arco e de corda no círculo unitário se relacionam. Aqui está uma figura que ilustra as relações de que precisamos para qualquer número real $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$.

Primeiro, o comprimento da corda (desenhado em azul) não pode ser maior do que o comprimento do arco (desenhado em roxo):

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

Relacionando esses comprimentos na direção oposta, vemos que a razão entre o comprimento do arco e o comprimento da corda é máxima quando $\delta = \pm 1/2$, e nesse caso a razão é metade da circunferência do círculo dividida pelo diâmetro, que é $\pi/2$. Assim, temos

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

e portanto

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

Uma análise baseada nessas relações revela os dois fatos a seguir.

1. Suponha que $\theta$ seja um número real e que $y\in \{0,\ldots,2^m-1\}$ satisfaça

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

   Isso significa que $y/2^m$ é ou a melhor aproximação de $m$ bits para $\theta$, ou está exatamente no meio entre $y/2^m$ e $(y-1)/2^m$ ou $(y+1)/2^m$, sendo portanto uma das duas melhores aproximações para $\theta$.

   Vamos provar que $p_y$ precisa ser bem grande nesse caso. Pela hipótese que estamos considerando, segue que $\vert 2^m \theta - y \vert \leq 1/2$, então podemos usar a segunda observação acima sobre comprimentos de arco e de corda para concluir que

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

   Também podemos usar a primeira observação sobre comprimentos de arco e de corda para concluir que

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

   Aplicando essas duas desigualdades a $p_y$, obtemos

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

   Isso explica nossa observação de que o melhor resultado ocorre com probabilidade maior que $40\%$ na versão $m=2$ da estimativa de fase discutida anteriormente. Na verdade não é exatamente 40%, é $4/\pi^2$, e de fato esse limite vale para qualquer escolha de $m$.

2. Agora suponha que $y\in \{0,\ldots,2^m-1\}$ satisfaça

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

   Isso significa que existe uma aproximação melhor $z/2^m$ para $\theta$ entre $\theta$ e $y/2^m$.

   Desta vez, vamos provar que $p_y$ não pode ser muito grande. Podemos começar com a observação simples de que

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

   o que decorre do fato de que quaisquer dois pontos no círculo unitário podem diferir em valor absoluto em no máximo $2$.

   Também podemos usar a segunda observação sobre comprimentos de arco e corda de cima, desta vez trabalhando com o denominador de $p_y$ em vez do 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}.$$

   Juntando as duas desigualdades, revela-se

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

   Observe que, embora esse limite seja suficiente para nossos propósitos, ele é bastante grosseiro — a probabilidade geralmente é muito menor que $1/4$.

A conclusão importante dessa análise é que aproximações muito próximas de $\theta$ têm probabilidade de ocorrer — obteremos a melhor aproximação de $m$ bits com probabilidade maior que $40\%$ — enquanto aproximações com erro maior que $2^{-m}$ são menos prováveis de ocorrer, com probabilidade limitada superiormente por $25\%$.

Dadas essas garantias, é possível aumentar nossa confiança repetindo o procedimento de estimativa de fase várias vezes, para reunir evidências estatísticas sobre $\theta$. É importante observar que o estado $\vert\psi\rangle$ do conjunto de qubits de baixo não é alterado pelo procedimento de estimativa de fase, então ele pode ser usado para executar o procedimento quantas vezes quisermos. Em particular, cada vez que executamos o circuito, obtemos a melhor aproximação de $m$ bits para $\theta$ com probabilidade maior que $40\%$, enquanto a probabilidade de o erro ser maior que $2^{-m}$ é limitada por $25\%$. Se executarmos o circuito várias vezes e considerarmos o resultado mais comum entre as execuções, é, portanto, extremamente provável que o resultado mais comum não seja um que ocorra no máximo $25\%$ das vezes. Como resultado, é muito provável que obtenhamos uma aproximação $y/2^m$ que esteja dentro de $1/2^m$ do valor $\theta$. De fato, a chance improvável de o erro ser maior que $1/2^m$ diminui exponencialmente com o número de vezes que o procedimento é executado.

Aqui estão dois gráficos mostrando as probabilidades para três valores consecutivos de $y$ quando $m = 3$ e $m=4$ como funções de $\theta$. (Apenas três resultados são mostrados para maior clareza. Probabilidades para outros resultados são obtidas deslocando ciclicamente a mesma função subjacente.)