Transformada de Fourier quântica

Para este módulo Qiskit em Salas de Aula, os alunos precisam ter um ambiente Python funcional com os seguintes pacotes instalados:

• qiskit v2.1.0 ou mais recente
• qiskit-ibm-runtime v0.40.1 ou mais recente
• qiskit-aer v0.17.0 ou mais recente
• qiskit.visualization
• numpy
• pylatexenc

Para configurar e instalar os pacotes acima, consulte o guia Instalar o Qiskit. Para executar jobs em computadores quânticos reais, os alunos precisarão criar uma conta no IBM Quantum® seguindo os passos do guia Configurar sua conta IBM Cloud.

Este módulo foi testado e utilizou 13 segundos de tempo de QPU. Esta é uma estimativa de boa-fé; o uso real pode variar.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introdução

A transformada de Fourier é uma ferramenta amplamente utilizada com aplicações em matemática, física, processamento de sinais, compressão de dados e inúmeros outros campos. Uma versão quântica da transformada de Fourier, apropriadamente chamada de transformada de Fourier quântica, forma a base de alguns dos algoritmos quânticos mais importantes.

Hoje, após uma revisão da transformada de Fourier clássica, falaremos sobre como implementamos a transformada de Fourier quântica em um computador quântico. Em seguida, discutiremos uma das aplicações da transformada de Fourier quântica a um algoritmo chamado algoritmo de estimativa de fase. A estimativa de fase quântica é uma sub-rotina do famoso algoritmo de fatoração de Shor, que às vezes é chamado de "joia da coroa" da computação quântica. Este módulo é um passo em direção a outro módulo totalmente dedicado ao algoritmo de Shor, mas também foi pensado para ser independente. A transformada de Fourier quântica é um algoritmo fascinante e útil por si só!

A transformada de Fourier clássica

Antes de mergulharmos na transformada de Fourier quântica, vamos primeiro nos lembrar da versão clássica. A transformada de Fourier é um método de transformar de uma chamada "base" para outra. Você pode pensar em duas bases como perspectivas diferentes do mesmo problema — ambas são formas válidas de expressar uma função, mas uma ou outra pode ser mais esclarecedora, dependendo do problema em questão. Alguns exemplos de pares de bases conectados pela transformada de Fourier são posição e momento, e tempo e frequência.

Vamos ver um exemplo de como a transformada de Fourier pode nos ajudar a descobrir qual nota um instrumento está tocando com base em sua forma de onda de áudio. Normalmente, vemos as formas de onda representadas na base temporal — ou seja, a amplitude da onda é expressa como uma função do tempo.

Podemos aplicar a transformada de Fourier a esta forma de onda para passar da base temporal para a base de frequências:

Na base de frequências, podemos ver claramente um pico em torno de 260 Hz. Isso é um dó central!

Agora, talvez você tenha conseguido identificar que um dó central estava sendo tocado sem usar a transformada de Fourier, mas e se várias notas forem tocadas ao mesmo tempo? Nesse caso, a forma de onda se torna mais complexa quando a plotamos na base temporal:

Mas o espectro de frequências identifica claramente três picos:

Este era um acorde de dó maior, tocando as notas dó, mi e sol.

Este tipo de análise de Fourier pode nos ajudar a extrair os componentes de frequência de qualquer tipo de sinal complexo.

Transformada discreta de Fourier

A transformada de Fourier é útil para diversas aplicações de processamento de sinais. Mas na maioria dessas aplicações do mundo real (incluindo o exemplo musical que usamos acima), queremos transformar um conjunto discreto de $N$ pontos de dados — não uma função contínua. Nesse caso, usamos a transformada de Fourier discreta. A transformada discreta de Fourier (TDF) atua em um vetor $(x_0, ..., x_{N-1})$ e o mapeia para o vetor $(y_0, ..., y_{N-1})$ de acordo com a fórmula:

$y_k = \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_j\omega_N^{jk}$

onde tomamos $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$. (Note que existem outras convenções que têm um sinal negativo no expoente, portanto, tenha cuidado ao encontrar a TDF na prática.) Lembre-se de que $e^{2\pi i \frac{jk}{N}}$ é uma função periódica, com período $\frac{N}{k}$. Portanto, ao multiplicar por esta função, a transformada de Fourier é essencialmente uma maneira de decompor a função (discreta) $\{x_{j}\}$ em uma combinação linear de suas funções periódicas constituintes, cada uma com período $\frac{N}{k}$.

A transformada de Fourier quântica

Agora, vimos como a transformada de Fourier é usada para representar uma função como uma combinação linear de um novo conjunto das chamadas "funções de base". Transformações de base também são feitas regularmente em estados de qubits. Por exemplo, o estado de um único qubit $|\psi\rangle$ pode ser expresso na base computacional $|\psi\rangle = c_0 |0\rangle + c_1 |1\rangle$, com estados de base $|0\rangle$ e $|1\rangle$, ou na base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ com estados de base $|+\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |1\rangle)$ e $|-\rangle = \frac{1}{\sqrt{2}} (|0\rangle - |1\rangle)$. Ambas são igualmente válidas, mas uma pode ser mais natural que a outra, dependendo do tipo de problema que você está tentando resolver.

Os estados de qubits também podem ser expressos na base de Fourier, onde um estado é expresso em termos de uma combinação linear dos estados de base de Fourier $|\phi_y\rangle$, em vez dos estados de base computacional usuais, $|x\rangle$. Para isso, você precisa aplicar uma transformada de Fourier quântica (TFQ):

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

com $\omega_N^{yx} = e^{\frac{2\pi i y x}{N}}$ como acima, e $N$ é o número de estados de base em seu sistema quântico. Note que, como estamos trabalhando com qubits, $m$ qubits fornecem $2^m$ estados de base, então $N=2^m$. Aqui, os estados de base são escritos como um único número $|x\rangle$, onde $x$ vai de $0$ a $N-1$, mas você pode vê-los mais comumente expressos como $|00...00\rangle$, $|00...01\rangle$, $|00...11\rangle$, ..., $|11...11\rangle$, onde cada dígito binário representa o estado do qubit 0 ao $m-1$, da direita para a esquerda. Há uma maneira fácil de converter esses estados binários em um único número: basta tratá-los como números binários! Assim, $|00...00\rangle = |0\rangle$, $|00...01\rangle = |1\rangle$, $|00...10\rangle = |2\rangle$, $|00...11\rangle = |3\rangle$, e assim por diante, até $|11...11\rangle = |2^m -1\rangle = |N-1\rangle$.

Desenvolva intuição para os estados de base de Fourier

Então, acabamos de revisar quais são os estados de base computacional e como eles são ordenados: são o conjunto de estados onde cada qubit está em $0$ ou $1$, e os ordenamos do estado onde todos os qubits são $0$, $|00...00\rangle$, até o estado onde todos são $1$, $|11...11\rangle$.

Mas como podemos entender os estados de base de Fourier? Todos os estados de base de Fourier são superposições iguais de todos os estados de base computacional, mas cada estado difere dos outros pela periodicidade na fase dos componentes. Para entender isso de forma mais concreta, vamos analisar os quatro estados de base de Fourier de um sistema de dois qubits. O estado de Fourier mais baixo é aquele cuja fase não varia:

$|\phi_0\rangle = \frac{1}{2} (|00\rangle + |01\rangle + |10\rangle + |11\rangle)$

Podemos visualizar este estado plotando a amplitude complexa de cada um dos termos. A linha vermelha guia o olho para mostrar como a fase desta amplitude gira em torno do plano complexo em função do estado de base computacional. Para $|\phi_0\rangle$, a fase permanece constante:

O próximo estado de base de Fourier é aquele cujas fases dos componentes giram de $0$ a $2\pi$ exatamente uma vez:

$|\phi_1\rangle = \frac{1}{2} (|00\rangle + e^{i\pi/2}|01\rangle + e^{i\pi}|10\rangle + e^{3i\pi/2}|11\rangle) = \frac{1}{2}(|00\rangle + i|01\rangle - |10\rangle - i|11\rangle)$

E podemos ver essa rotação no gráfico de amplitude complexa versus estado de base computacional:

Então, cada estado tem uma fase que é $2\pi/4$ radianos maior do que o estado anterior quando ordenados da forma padrão, já que neste exemplo temos quatro estados de base ($N=4$). O próximo estado de base gira de 0 a $2\pi$ duas vezes:

$|\phi_2\rangle = \frac{1}{2} (|00\rangle + e^{i\pi}|01\rangle + e^{2i\pi}|10\rangle + e^{3i\pi}|11\rangle) = \frac{1}{2} (|00\rangle - |01\rangle + |10\rangle - |11\rangle)$

Por fim, o componente de Fourier mais alto é aquele com a fase que varia mais rapidamente. Em nosso exemplo com dois qubits, é aquele cujas fases giram de 0 a $2\pi$ três vezes:

$|\phi_3\rangle = \frac{1}{2} (|00\rangle + e^{3i\pi/2}|01\rangle + e^{6i\pi/2}|10\rangle + e^{9i\pi/2}|11\rangle) = \frac{1}{2} (|00\rangle - i|01\rangle - |10\rangle + i|11\rangle)$

Em geral, para um estado de $m$ qubits, haverá $2^m$ estados de base de Fourier, cuja frequência na variação de fase vai de constante, para $|\phi_0\rangle$, a rapidamente variante para $|\phi_{2^m-1}\rangle$, completando $2^m-1$ rotações em torno de $2\pi$ sobre a superposição de estados. Então, quando aplicamos uma TFQ a um estado quântico, estamos essencialmente fazendo a mesma análise básica que fizemos para a forma de onda musical na Introdução. Estamos determinando os componentes de frequência de Fourier que contribuem para criar o estado quântico de interesse.

Experimente alguns exemplos de TFQs

Vamos continuar a desenvolver nossa intuição para a transformada de Fourier quântica criando um estado na base computacional e vendo o que acontece quando aplicamos a TFQ a ele. Por enquanto, vamos tratar a TFQ como uma caixa preta que aplicamos usando o QFTGate da biblioteca de circuitos do Qiskit. Mais tarde, daremos uma olhada por baixo do capô para ver como ela é implementada.

Começamos carregando os pacotes necessários e selecionando um dispositivo para executar nosso circuito:

import numpy as np
from qiskit import QuantumCircuit
from qiskit.visualization import plot_histogram
from qiskit.circuit.library import QFTGate

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

service = QiskitRuntimeService()

# Use the least busy backend
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_pinguino2")

print(backend.name)

ibm_pinguino2

Se você não tiver tempo disponível em sua conta ou quiser usar um simulador por qualquer motivo, você pode executar a célula abaixo para configurar um simulador que imitará o dispositivo quântico que selecionamos acima:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# Alternatively, load a fake backend with generic properties and define a simulator.
from qiskit.providers.fake_provider import GenericBackendV2

backend_gen = GenericBackendV2(num_qubits=18)
sampler_gen = BackendSamplerV2(backend=backend_gen)

Um único estado de base computacional

Primeiro, vamos tentar transformar um único estado de base computacional. Começaremos criando um estado computacional aleatório:

# Step 1: Map

qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# flip state of random qubits to put in a random single computational basis state
for i in range(1, qubits):
    if np.random.randint(0, 2):
        qc.x(i)

# make a copy of the above circuit. (to be used when we apply the QFT in next part)
qc_qft = qc.copy()

qc.measure_all()
qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Agora, vamos aplicar a transformada de Fourier a este estado com QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR Run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-Process
plot_histogram(counts)

Como você pode ver, medimos as populações de cada estado como sendo mais ou menos iguais, com algum ruído experimental e estatístico. Portanto, se você aplica a TFQ a um único estado de base computacional, o resultado é uma superposição igual de todos os estados. Se você está familiarizado com transformadas de Fourier, isso provavelmente não te surpreende. Um princípio básico que pode nos ajudar a construir uma conexão intuitiva entre uma função e sua transformada de Fourier é que a largura de uma função é inversamente proporcional à largura de sua transformada de Fourier. Assim, algo muito localizado no tempo, por exemplo, como um pulso muito curto, exigirá uma ampla faixa de frequências para gerar aquele pulso. Esse sinal será muito amplo no espaço de Fourier.

Esse fato está, na verdade, relacionado à incerteza quântica! O princípio da incerteza de Heisenberg é tipicamente enunciado como $\Delta x \Delta p \ge \hbar / 2$. Portanto, se a incerteza em $x$ ($\Delta x$) é pequena, a incerteza no momento ($\Delta p$) deve ser grande, e vice-versa. Acontece que a transformação da base de posição $x$ para a base de momento $p$ é realizada por meio de uma transformada de Fourier.

Nota: Tenha em mente que estamos medindo populações em cada um dos estados de base, então estamos perdendo informações sobre as fases relativas entre as diversas partes da superposição. Portanto, embora a TFQ de qualquer estado de base computacional único produza a mesma distribuição uniforme de população sobre todos os estados de base, as fases não serão necessariamente as mesmas.

Dois estados de base computacional

Agora, vamos ver o que acontece quando preparamos uma superposição de estados de base computacional. O que você acha que a transformada de Fourier vai parecer nesse caso?

Vamos escolher a superposição:

$|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle) = \frac{1}{\sqrt{2}} (|000...0\rangle + |100...0\rangle)$

# Step 1: Map
qubits = 4
N = 2**qubits

qc = QuantumCircuit(qubits)

# To make this state, we just need to apply a Hadamard to the last qubit

qc.h(qubits - 1)

qc_qft = qc.copy()

qc.measure_all()

qc.draw("mpl")

# First, let's go through steps 2-4 for the first circuit, qc

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer - try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Agora, vamos aplicar a transformada de Fourier a este estado com QFTGate:

# Step 1: Map

qc_qft.compose(QFTGate(qubits), inplace=True)
qc_qft.measure_all()
qc_qft.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

qc_isa = pm.run(qc_qft)

# Step 3: Run the job on a real quantum computer OR try fake backend

sampler = Sampler(mode=backend)
pubs = [qc_isa]

# Run the job on real quantum device

job = sampler.run(pubs, shots=1000)
res = job.result()
counts = res[0].data.meas.get_counts()

# OR run the job on the Aer simulator with noise model from real backend

# job = sampler_sim.run([qc_isa])
# res = job.result()
# counts = res[0].data.meas.get_counts()

# Step 4: Post-process
plot_histogram(counts)

Este resultado pode ser um pouco surpreendente. Parece que a TFQ do estado $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ é uma superposição de todos os estados de base pares. Mas se pensarmos na nossa visualização de cada estado de base $|\phi_y\rangle$, e em como a fase de cada componente gira $2\pi$ $y$ vezes, então o motivo pelo qual obtemos este resultado pode ficar claro.

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Usando a dica acima, explique por que o resultado que obtivemos para a TFQ de $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ é esperado.

Resposta:

O estado original tem uma fase relativa de 0 (ou um múltiplo inteiro de $2\pi$) entre as duas partes da superposição. Portanto, sabemos que este estado tem componentes de Fourier cujas fases também coincidem dessa forma: aquelas que têm deslocamento de fase 0 entre o termo |0000> e o termo |1000>. Cada estado de base de Fourier $|\phi_y\rangle$ é composto de termos cuja fase se acumula a uma taxa de $2\pi y/N$, ou seja, quando ordenados da forma usual, cada termo na superposição tem uma fase $2\pi y/N$ maior do que o termo anterior. Assim, no ponto intermediário $N/2$, queremos que a fase $2\pi y/N * N/2$ seja um múltiplo inteiro de $2\pi$. Isso acontece quando $y$ é par.

Que superposição de estados computacionais corresponderia a uma TFQ com picos em todo número binário ímpar?

Resposta:

Se você aplicasse a TFQ ao estado $\psi = |0\rangle - |N/2\rangle$, você veria picos em cada estado numerado binário ímpar.

Desmembrando o algoritmo da QFT

Agora que desenvolvemos uma intuição melhor sobre a relação entre os estados de qubits na base computacional e na base de Fourier, vamos mergulhar no próprio algoritmo da QFT. Em outras palavras, quais portas precisamos realmente implementar no computador quântico para realizar essa transformada?

Vamos começar com algo simples: um único qubit. Isso significa que teremos dois estados de base. A QFT$_2$ transforma os estados da base computacional $|0\rangle$ e $|1\rangle$ nos estados da base de Fourier $\phi_0$ e $\phi_1$:

$|\phi_0\rangle = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$|\phi_1\rangle = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Verifique seu entendimento

Leia a(s) pergunta(s) abaixo, pense na sua resposta e clique no triângulo para revelar a solução.

Use a equação da QFT da seção anterior para verificar esses dois estados da base de Fourier acima.

Resposta:

A fórmula geral da QFT é:

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

Para um único qubit ($n=1$), $N=2^n=2$, e $\omega_N^{xy} = e^{2\pi i \frac {y x}{2}}$. Portanto, temos

$| \phi_0 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {0 \times 0}{2}}|0\rangle + e^{2\pi i \frac {0 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$

$| \phi_1 \rangle = \frac{1}{\sqrt{2}}(e^{2\pi i \frac {1 \times 0}{2}}|0\rangle + e^{2\pi i \frac {1 \times 1}{2}}|1\rangle) = \frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$

Observe essas duas equações. Você talvez já conheça uma porta quântica que pode ser usada para implementar essa transformada. Ou seja, existe uma porta que transforma os estados da base computacional $|0\rangle$ e $|1\rangle$ nos respectivos estados da base de Fourier $|\phi_0\rangle$ e $|\phi_1\rangle$. É a porta Hadamard! Isso fica ainda mais claro quando introduzimos a representação matricial da operação QFT$_N$:

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

Se você não está familiarizado com essa notação para expressar um operador quântico, tudo bem! É uma forma de representar uma matriz $N \times N$, em que $x$ e $y$ indexam as colunas e linhas da matriz, de $0$ a $N-1$, e $\omega_N^{xy}$ é o valor de cada entrada específica. Assim, a entrada na coluna 0 e na linha 2, por exemplo, seria simplesmente $\omega_N^{0,2} = e^{2 \pi i \frac{0 \times 2}{N}} = 1$.

Nessa representação, cada um dos estados da base computacional está associado a um dos vetores de base:

$$\begin{pmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{pmatrix}, |1\rangle = \begin{pmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{pmatrix}, |N-1\rangle = \begin{pmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{pmatrix}.$$

Se você quiser aprender mais sobre essa representação, consulte a aula de John Watrous sobre múltiplos sistemas no curso Noções básicas de informação quântica.

Vamos tentar construir a matriz para QFT$_4$. Usando a fórmula acima, encontramos que

\text\{QFT\}_4 = \frac\{1\}\{2\} \begin\{pmatrix\} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end\{pmatrix\}

Para implementar essa matriz em um computador quântico, precisaremos descobrir qual combinação de portas aplicadas a quais qubits produzirá uma transformação unitária que corresponde à matriz acima. Já sabemos qual é uma das portas necessárias: a Hadamard. Outra porta que precisaremos é a porta de fase controlada, que aplica uma fase relativa $\alpha$ ao estado do qubit alvo, desde que o qubit de controle esteja no estado $|1\rangle$. Em forma matricial, ela se parece com:

\text\{CP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & e^\{i\alpha\} \\ \end\{pmatrix\}

Como apenas o estado $|11\rangle$ é alterado, na prática não importa qual qubit é considerado o "controle" e qual é o "alvo". O resultado será o mesmo de qualquer jeito.

Por fim, também precisaremos de algumas portas SWAP. Uma porta SWAP troca os estados de dois qubits. Ela tem a seguinte forma:

\text\{SWAP\}_\alpha = \begin\{pmatrix\} 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ \end\{pmatrix\}

O procedimento para construir um circuito QFT$_{2^m}$ em $m$ qubits é iterativo — primeiro você aplica a QFT$_{2^{m-1}}$ aos qubits $1$ até $m-1$ e depois adiciona algumas portas entre o qubit $0$ e os outros $m-1$ qubits. Mas para aplicar a QFT$_{2^{m-1}}$, você primeiro precisa aplicar a QFT$_{2^{m-2}}$ aos qubits 2 até $m-1$ e depois adicionar algumas portas entre o qubit 1 e os qubits restantes $2$ até $m-1$. É como uma matrioska russa: cada boneca adiciona um fator de dois à dimensão do circuito QFT, sendo a menor boneca, no centro, a QFT$_2$, ou seja, a porta Hadamard.

Para encaixar uma boneca dentro da próxima (maior), aumentando assim a dimensão da QFT por um fator de dois, você sempre segue o mesmo procedimento:

1. Primeiro, aplique a QFT$_{2^{m-1}}$ aos $m-1$ qubits mais abaixo. Essa é a sua "boneca menor" do conjunto de matrioskas que você irá encaixar dentro da próxima.
2. Use o próximo qubit acima como controle e aplique portas de fase controlada a cada um dos $m-1$ qubits inferiores, com fases para os estados da base padrão de cada um dos $m-1$ qubits restantes.
3. Aplique uma Hadamard nesse mesmo qubit do topo que foi usado como controle nas portas de fase.
4. Use portas SWAP para permutar a ordem dos qubits de modo que o bit menos significativo (topo) se torne o mais significativo (fundo), e todos os outros se desloquem uma posição para cima.

Já estávamos usando a função QFTGate da biblioteca de circuitos do Qiskit, mas agora vamos dar uma olhada dentro de algumas dessas portas QFT para verificar o procedimento acima. Podemos fazer isso com decompose().

qc = QuantumCircuit(1)
qc.compose(QFTGate(1), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(2)
qc.compose(QFTGate(2), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(3)
qc.compose(QFTGate(3), inplace=True)
qc.decompose().draw("mpl")

qc = QuantumCircuit(4)
qc.compose(QFTGate(4), inplace=True)
qc.decompose().draw("mpl")

Esperamos que, a partir das quatro primeiras QFTs, você consiga perceber como cada uma está aninhada dentro da próxima. Você pode ter notado, porém, que algumas das portas de fase não são exatamente as prescritas no procedimento que delineamos acima, e os SWAPs não aparecem após cada sub-rotina, mas apenas no final da QFT completa. Isso nos poupa portas desnecessárias, que tornariam o circuito mais lento e mais suscetível a erros. Em vez de implementar o SWAP após cada boneca aninhada, o circuito mantém o controle de onde cada estado de qubit deveria estar e ajusta os qubits aos quais aplica as portas de fase de acordo. Em seguida, um conjunto final de SWAPs no final coloca tudo em seu lugar correto.

Aplicando a QFT: Estimação de fase

Vamos ver como a QFT pode ser usada para resolver um problema útil em computação quântica. Calcular a transformada quântica de Fourier inversa é uma etapa necessária em um algoritmo conhecido como Estimação de Fase Quântica (QPE), que é em si uma sub-rotina em muitos outros algoritmos, incluindo a "joia da coroa" dos algoritmos quânticos, o algoritmo de fatoração de Shor.

O objetivo da QPE é estimar os autovalores de um operador unitário. Operadores unitários são onipresentes na computação quântica e, frequentemente, encontrar os autovalores de seus autovetores associados é uma etapa necessária em um algoritmo maior. Dependendo do problema, um autovalor pode representar a energia de um Hamiltoniano em um problema de simulação, pode nos ajudar a encontrar os fatores primos de um número no algoritmo de Shor, ou pode conter outras informações essenciais. A QPE é uma das sub-rotinas mais importantes e amplamente utilizadas na computação quântica.

Então, o que isso tem a ver com a transformada quântica de Fourier? Bem, como você pode se lembrar, qualquer autovalor $\lambda$ de um operador unitário tem magnitude $|\lambda| = 1$. Portanto, podemos escrever cada autovalor como um número complexo de magnitude um:

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

onde $\theta$ é um número real entre 0 e 1. Se você quiser mais informações sobre matrizes unitárias, consulte a aula de John Watrous sobre o assunto em Noções básicas de informação quântica.

Note que $\lambda$ é periódico em $\theta$. Isso já pode sugerir que uma QFT esteja envolvida, já que vimos como as QFTs são úteis para analisar funções periódicas. A seguir, percorreremos o algoritmo e veremos precisamente como a QFT entra em cena.

Como a QPE funciona

Primeiro, começaremos com o algoritmo QPE mais simples, que estima a fase aproximadamente com um único dígito binário de precisão. Em outras palavras, esse algoritmo consegue distinguir entre $\theta = 0$ e $\theta = 1/2$, mas não consegue ir além disso. Aqui está o diagrama do circuito:

Os qubits são preparados no estado $|\pi_0\rangle = |\psi\rangle|0\rangle$, onde o qubit $0$ está no estado $|0\rangle$ e os qubits restantes estão no estado $|\psi\rangle$, que é um autoestado de $U$. Após a primeira Hadamard, o estado dos qubits se torna:

$|\pi_1\rangle = \frac{1}{\sqrt{2}}|\psi\rangle (|0\rangle + |1\rangle)$

A próxima porta é uma porta "$U$ controlada". Ela aplica a operação unitária $U$ aos qubits inferiores no estado $|\psi\rangle$ se o qubit 0 estiver no estado $|1\rangle$, mas não faz nada a $|\psi\rangle$ se o qubit 0 estiver no estado $|0\rangle$. Isso transforma os qubits para o estado:

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

Algo curioso acabou de acontecer: a porta $U$ controlada usa apenas o qubit $0$ como qubit de controle, então alguém poderia pensar que essa porta não mudaria o estado do qubit 0 de forma alguma. Mas de alguma forma, muda! Embora a operação tenha sido aplicada aos qubits inferiores, o efeito geral da porta é alterar a fase do qubit $0$. Isso é conhecido como o "mecanismo de retorno de fase" (phase kickback) e é usado em muitos algoritmos quânticos, incluindo os algoritmos de Deutsch-Josza e de Grover. Se você quiser saber mais sobre o mecanismo de retorno de fase, consulte a aula de John Watrous sobre Algoritmos de consulta quântica em Fundamentos de algoritmos quânticos.

Após o retorno de fase, aplicamos mais uma Hadamard ao qubit $0$, o que resulta no estado:

$|\pi_3\rangle = |\psi\rangle ( \frac{1+e^{2\pi i \theta}}{2} |0\rangle + \frac{1 - e^{2\pi i \theta}}{2}|1\rangle) = |\psi\rangle ( \cos(\pi\theta) |0\rangle - i \sin(\pi\theta)|1\rangle)$

Assim, quando medimos o qubit $0$ ao final, mediremos $|0\rangle$ com 100% de certeza se $\theta = 0$, e mediremos $|1\rangle$ com 100% de certeza se $\theta = \frac{1}{2}$ (e se nosso computador quântico for perfeito, sem ruído). Se $\theta$ for diferente disso, a medição final é apenas probabilística e nos diz apenas até certo ponto.

QPE com mais precisão: mais qubits

Podemos estender esse conceito simples para um algoritmo mais elaborado com precisão arbitrária. Se, em vez de usar apenas o qubit $0$ para medir a fase, usarmos $m$ qubits de $0$ a $m-1$, seremos capazes de estimar a fase com $m$ bits de precisão. Vamos ver como isso funciona:

Esse circuito QPE mais preciso começa da mesma forma que a versão de um bit: Hadamards são aplicadas aos primeiros $m$ qubits, e os qubits restantes são preparados no estado $|\psi\rangle$, criando o estado:

$|\pi_1\rangle = \frac{1}{2^{m/2}}|\psi\rangle(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)...(|0\rangle+|1\rangle)$

Agora, as unitárias controladas são aplicadas. O qubit $0$ é o controle para a mesma unitária $U$ de antes. Mas agora, o qubit $1$ é o controle para a unitária $U^2$, que é simplesmente $U$ aplicada duas vezes. Portanto, o autovalor de $U^2$ é $e^{2*2\pi i \theta}$. Em geral, cada qubit $k$ de 0 a $m-1$ será o controle para a unitária $U^{2^k}$. Isso significa que cada um desses qubits experimentará um retorno de fase de $e^{2^k*2\pi i \theta}$. Isso resulta no estado:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} (|0\rangle+e^{2^{m-1}2\pi i \theta}|1\rangle)(|0\rangle+e^{2^{m-2}2\pi i \theta}|1\rangle)...(|0\rangle+e^{2\pi i \theta}|1\rangle)$

Isso pode ser reescrito como uma soma sobre os estados da base computacional:

$|\pi_2\rangle = |\psi\rangle \otimes \frac{1}{2^{m/2}} \sum_{k=0}^{2^{m}-1} e^{2\pi i k \theta} |k\rangle$

A soma parece familiar? É uma QFT! Lembre-se da equação da transformada quântica de Fourier:

$\text{QFT}_{2^m}| y \rangle = \frac{1}{\sqrt{2^m}}\sum_{x=0}^{2^m-1}\omega_{2^m}^{y x} \vert x \rangle$

Portanto, se a fase $\theta = y/2^m$ para algum inteiro $y$ entre $0$ e $2^m-1$, então aplicar a QFT inversa a esse estado resultará no estado:

$|\pi_3\rangle = |\psi\rangle \otimes |y\rangle$

e a partir de $|y\rangle$, podemos deduzir $\theta$.

Se $\theta/2^m$ não for um múltiplo inteiro, no entanto, aplicar a QFT inversa apenas aproximará $\theta$. Quão bem ela aproxima $\theta$ será probabilístico, o que significa que nem sempre obteremos a melhor aproximação, mas será bastante próximo, e quanto mais qubits $m$ você usar, melhor será a aproximação. Para aprender como quantificar essa aproximação de $\theta$, confira a aula de John Watrous sobre Estimação de fase e fatoração em Fundamentos de algoritmos quânticos.

Conclusão

Este módulo forneceu uma visão geral do que é uma QFT, como ela é implementada em um computador quântico e quão útil ela pode ser para resolver problemas. Você teve uma amostra de sua utilidade quando vimos como ela pode ser usada na estimação de fase quântica para aprender sobre os autovalores de uma matriz unitária.

Conceitos fundamentais

• A Transformada Quântica de Fourier é o análogo quântico da Transformada Discreta de Fourier.
• A QFT é um exemplo de transformação de base.
• O procedimento de Estimação de Fase Quântica depende do mecanismo de retorno de fase das operações unitárias controladas, bem como de uma QFT inversa.
• A QFT e a QPE são sub-rotinas amplamente utilizadas em inúmeros algoritmos quânticos.

Perguntas

Verdadeiro/Falso

1. V/F A Transformada Quântica de Fourier é o análogo quântico da transformada discreta de Fourier (DFT) clássica.
2. V/F A QFT pode ser implementada usando apenas portas Hadamard e CNOT.
3. V/F A QFT é um componente essencial do algoritmo de Shor.
4. V/F A saída da Estimação de Fase Quântica é um estado quântico que representa o autovetor do operador.
5. V/F A QPE requer o uso da Transformada Quântica de Fourier inversa (QFT$^\dag$).
6. V/F Na QPE, se a fase $\phi$ for exatamente representável com $n$ bits, o algoritmo fornece o resultado correto com probabilidade 1.

Respostas curtas

1. Quantos qubits são necessários para realizar uma QFT em um sistema com $2^n$ pontos de dados?
2. A QFT pode ser usada em um estado que não seja um estado da base computacional? Se sim, o que acontece?
3. Como o número de qubits de controle usados na QPE afeta a resolução da estimativa de fase resultante?

Problemas

1. Use multiplicação de matrizes para verificar que as etapas do algoritmo da QFT resultam de fato na matriz $\text{QFT}_4$:

$$\text{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \\ \end{pmatrix}$$

(Você não precisa fazer isso à mão!)

Problemas desafiadores

1. Crie um estado de quatro qubits que seja uma superposição igual de todas as bases computacionais ímpares: $|\psi\rangle = |0001\rangle + |0011\rangle + |0101\rangle + |0111\rangle +|1001\rangle +|1011\rangle +|1101\rangle +|1111\rangle$. Em seguida, realize uma QFT sobre o estado. Qual é o estado resultante? Explique por que seu resultado faz sentido, usando seu conhecimento sobre transformadas de Fourier.