Transformação de Fourier quântica

Para este módulo do Qiskit in Classrooms, os alunos devem ter um ambiente de trabalho Python 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 trabalhos em computadores quânticos reais, os alunos precisarão configurar uma conta no site IBM Quantum® seguindo as etapas do guia Configurar sua conta IBM Cloud.

Esse módulo foi testado e usou 13 segundos de tempo de QPU. Essa é uma estimativa de boa-fé; seu uso real pode variar.

# 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 onipresente com aplicações em matemática, física, processamento de sinais, compactação de dados e inúmeros outros campos. Uma versão quântica da transformada de Fourier, apropriadamente chamada de transformada quântica de Fourier, forma a base de alguns dos algoritmos quânticos mais importantes.

Hoje, depois de relembrarmos a 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 quântica de Fourier em 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 se baseia em outro módulo sobre o algoritmo do Shor, mas também foi criado para ser autônomo. A transformada quântica de Fourier é um algoritmo fascinante e útil por si só!

A transformada clássica de Fourier

Antes de entrarmos na transformada quântica de Fourier, vamos primeiro nos lembrar da versão clássica. A transformada de Fourier é um método de transformação de uma "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 que são conectados pela transformada de Fourier são posição e momento, e tempo e frequência.

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

Podemos transformar essa forma de onda em Fourier para passar da base de tempo para a base de frequência:

Na base de frequência, podemos ver facilmente um pico claro em cerca de 260 Hz. Isso é um dó médio!

Agora, você pode ter conseguido determinar que um dó médio estava sendo tocado sem o uso de uma transformada de Fourier, mas e se várias notas forem tocadas ao mesmo tempo? Em seguida, a forma de onda se torna mais complicada quando a plotamos na base de tempo:

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

Esse foi um acorde de dó maior, tocando as notas dó, mi e sol.

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

Transformada discreta de Fourier

A transformada de Fourier é útil para várias aplicações de processamento de sinais. Mas na maioria desses aplicativos do mundo real (incluindo o exemplo de música 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 discreta de Fourier. A transformada discreta de Fourier (DFT) 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}}$. (Observe que há outras convenções que têm um sinal de menos no exponencial, portanto, tenha cuidado ao ver a DFT na natureza) 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 essa função, a transformada de Fourier é essencialmente uma forma 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" As transformações de base também são feitas regularmente em estados de qubit. 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 os estados da base $|0\rangle$ e $|1\rangle$, ou na base $X$ $|\psi\rangle = c_+ |+\rangle + c_- |-\rangle$ com os estados da 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 do que a outra, dependendo do tipo de problema que você está tentando resolver.

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

$| \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 básicos no seu sistema quântico. Observe que, como estamos trabalhando com qubits agora, $m$ qubits fornece $2^m$ estados básicos, portanto $N=2^m$. Aqui, os estados básicos são escritos como um único número $|x\rangle$, onde $x$ varia de $0$ a $N-1$, mas é mais comum ver os estados básicos 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 a $m-1$, da direita para a esquerda. Existe uma maneira fácil de converter esses estados binários em um único número: basta tratá-los como números binários! Portanto, $|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 a intuição para os estados básicos de Fourier

Portanto, acabamos de explicar o que são os estados da base computacional e como eles são ordenados: são o conjunto de estados em que cada qubit está em $0$ ou $1$, e os ordenamos a partir do estado em que todos os qubits são $0$, $|00...00\rangle$, até o estado em que todos são $1$, $|11...11\rangle$.

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

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

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

O próximo estado da base de Fourier é aquele cujas fases dos componentes variam de $0$ a $2\pi$ apenas 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 esse enrolamento no gráfico da amplitude complexa em relação ao estado da base computacional:

Portanto, cada estado tem uma fase que é $2\pi/4$ radianos mais alta do que o estado anterior quando ordenado da maneira padrão, já que neste exemplo temos quatro estados básicos ( $N=4$ ). O próximo estado da base vai 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 de variação mais rápida. Em nosso exemplo com dois qubits, é aquele cujas fases variam 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 qubit $m$, haverá um $2^m$ e estados de base de Fourier, cuja variação de fase varia de constante, para $|\phi_0\rangle$, a rapidamente variável para $|\phi_{2^m-1}\rangle$, completando $2^m-1$ voltas em torno de $2\pi$ sobre a superposição de estados. Portanto, quando fazemos uma QFT de 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 QFTs

Vamos tentar continuar a construir nossa intuição para a transformada quântica de Fourier criando um estado na base computacional e, em seguida, vendo o que acontece quando aplicamos a QFT a ele. Por enquanto, trataremos o QFT apenas como uma caixa preta que aplicamos usando o site QFTGate da biblioteca de circuitos Qiskit. Mais tarde, daremos uma olhada nos bastidores para ver como isso é implementado.

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)

Output:

ibm_pinguino2

Se você não tiver tempo disponível em sua conta ou quiser usar um simulador por qualquer motivo, poderá 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)

Estado de base computacional único

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")

Output:

# 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)

Output:

Agora, vamos fazer a transformação de Fourier desse estado com QFTGate:

# Step 1: Map

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

Output:

# 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)

Output:

Como você pode ver, medimos as populações de cada estado para que sejam mais ou menos iguais, com ou sem algum ruído experimental e estatístico. Portanto, se você pegar a QFT de um único estado da base computacional, o resultado será uma superposição igual de todos os estados. Se você estiver familiarizado com as transformadas de Fourier, isso provavelmente não o surpreenderá. Um princípio básico que pode nos ajudar a criar 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. Portanto, algo que é muito localizado no tempo, por exemplo, como um pulso muito curto, exigirá uma ampla gama de frequências para gerar esse pulso. Esse sinal será muito amplo no espaço de Fourier.

Na verdade, esse fato está relacionado à incerteza quântica! O princípio da incerteza de Heisenberg é normalmente declarado como $\Delta x \Delta p \ge \hbar / 2$. Portanto, se a incerteza em $x$ ( $\Delta x$ ) for 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.

Observação: lembre-se de que estamos medindo as populações em cada um dos estados da base, portanto, estamos perdendo informações sobre as fases relativas entre as várias partes da superposição. Portanto, embora o QFT de qualquer estado de base computacional único produza a mesma distribuição uniforme na população em 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 da base computacional. Como você acha que será a transformada de Fourier 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")

Output:

# 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)

Output:

Agora, vamos fazer a transformação de Fourier desse estado com QFTGate:

# Step 1: Map

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

Output:

# 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)

Output:

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

Verifique sua compreensão

Usando a dica acima, explique por que o resultado que obtivemos para a Teoria Quântica dos Campos (QFT) de um $|\psi\rangle = \frac{1}{\sqrt{2}} (|0\rangle + |N/2\rangle)$ o é o 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 esse estado tem componentes de Fourier cujas fases também coincidem dessa forma: aqueles que têm 0 de mudança de fase entre o termo |0000> e o termo |1000>. Cada estado da base de Fourier $|\phi_y\rangle$ é composto de termos cuja fase se acumula a uma taxa de $2\pi y/N$, o que significa que, quando ordenado da maneira usual, cada termo na superposição tem uma fase de $2\pi y/N$ maior do que o termo anterior. Portanto, na metade do caminho $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 Teoria Quântica dos Campos com picos em todos os números binários ímpares?

• Resposta

  Se você pegar o QFT do estado $\psi = |0\rangle - |N/2\rangle$, verá picos em todos os estados com números binários ímpares.

Analise o algoritmo QFT

Agora que adquirimos mais intuição sobre a relação entre os estados do qubit na base computacional e na base de Fourier, vamos nos aprofundar no próprio algoritmo QFT. Em outras palavras, quais portas realmente implementamos no computador quântico para realizar essa transformação?

Vamos começar com um único qubit. Portanto, isso significa que teremos dois estados-base. A QFT $_2$ transforma os estados da base computacional $|0\rangle$ e $|1\rangle$ em 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 sua compreensão

Use a equação da Teoria Quântica dos Campos (QFT) apresentada na seção anterior para verificar esses dois estados de 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)$

Dê uma olhada nessas duas equações. Talvez você já conheça uma porta quântica que pode ser usada para implementar essa transformação. Ou seja, há 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$. É uma porta Hadamard! Isso fica ainda mais claro se introduzirmos uma 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 estiver familiarizado com essa notação para expressar um operador quântico, não tem problema! É uma forma de representar uma matriz $N \times N$, em que $x$ e $y$ indexam as colunas e as linhas da matriz, de $0$ a $N-1$, e $\omega_N^{xy}$ é o valor dessa entrada específica. Portanto, a entrada na 0ª coluna e na 2ª linha, por exemplo, seria apenas $\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 da base:

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

Vamos tentar construir a matriz para QFT $_4$. Usando a fórmula acima, descobrimos 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 nos dará uma transformação unitária que corresponda à matriz acima. Já conhecemos um dos portões que serão necessários: o Hadamard. Outra porta de que precisaremos é a porta de fase controlada, que aplica uma fase relativa $\alpha$ ao estado do qubit de destino, desde que o qubit de controle esteja no estado $|1\rangle$. Na forma de matriz, isso 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 verdade não importa qual qubit é considerado o "controle" e qual é o "alvo" O resultado será o mesmo de qualquer maneira.

Por fim, também precisaremos de alguns portões SWAP. Uma porta SWAP troca os estados de dois qubits. Parece que sim:

$\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}$ nos qubits $m$ é iterativo: primeiro, você aplica a QFT $_{2^{m-1}}$ aos qubits $1$ a $m-1$ e, em seguida, adiciona algumas portas entre o qubit $0$ e os outros qubits $m-1$. Mas para aplicar a QFT $_{2^{m-1}}$, primeiro você precisa aplicar a QFT $_{2^{m-2}}$ aos qubits 2 a $m-1$ e, em seguida, adicionar algumas portas entre o qubit 1 e os qubits restantes $2$ a $m-1$. É como um ninho de bonecas russo: cada boneca acrescenta um fator de dois na dimensão do circuito QFT, com a menor boneca no centro, sendo a QFT $_2$, ou a porta Hadamard.

Para colocar uma boneca dentro da boneca de tamanho maior seguinte, aumentando assim a dimensão do QFT por um fator de dois, você sempre segue o mesmo procedimento:

1. Primeiro, aplique a QFT $_{2^{m-1}}$ aos qubits $m-1$ mais baixos. Essa é a sua "boneca menor" do conjunto de bonecas russas que você colocará dentro da próxima boneca maior.
2. Use o próximo qubit acima como controle e aplique portas de fase controladas a cada um dos $m-1$ qubits inferiores, com fases para os estados de base padrão de cada um dos $m-1$ qubits restantes.
3. Execute um Hadamard no mesmo qubit superior que foi usado como controle nas portas de fase.
4. Use as portas SWAP para alterar a ordem dos qubits de modo que o bit menos significativo (superior) se torne o bit mais significativo (inferior) e todos os outros sejam deslocados para cima em um.

Já usamos a função QFTGate da biblioteca de circuitos do Qiskit, mas agora vamos dar uma olhada em 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")

Output:

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

Output:

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

Output:

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

Output:

Portanto, esperamos que, a partir dos quatro primeiros QFTs, você possa começar a ver como cada um deles está aninhado dentro do próximo maior. Você deve ter notado, no entanto, que algumas das portas de fase não são exatamente como prescritas no procedimento que descrevemos acima, e os SWAPs não aparecem após cada sub-rotina, mas apenas no final do QFT completo. Isso nos poupa de portas desnecessárias, o que faria com que o circuito demorasse mais e fosse mais propenso a erros. Em vez de implementar o SWAP após cada boneco aninhado, o circuito mantém o controle de onde cada estado de qubit deve estar e ajusta os qubits aos quais está aplicando as portas de fase de acordo. Em seguida, um conjunto final de SWAPs no final coloca tudo em seu devido lugar.

Aplique o QFT: Estimativa de fase

Vamos ver como a QFT pode ser usada para resolver um problema útil na computação quântica. O cálculo da transformada quântica inversa de Fourier é uma etapa necessária em um algoritmo conhecido como Estimativa de Fase Quântica (QPE), que é, por sua vez, 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 do QPE é estimar os valores próprios de um operador unitário. Os operadores unitários são onipresentes na computação quântica e, muitas vezes, encontrar os valores próprios de seus vetores próprios associados é uma etapa necessária em um algoritmo maior. Dependendo do problema, um valor próprio pode representar uma energia de um Hamiltoniano em um problema do tipo simulação, pode nos ajudar a encontrar fatores primos de um número no algoritmo de Shor ou pode conter outras informações essenciais. O QPE é uma das subrotinas mais importantes e amplamente usadas na computação quântica.

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

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

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

Observe que $\lambda$ é periódico em $\theta$. Isso já pode lhe sugerir que uma QFT pode estar envolvida, pois vimos como as QFTs são úteis para analisar funções periódicas. A seguir, examinaremos o algoritmo e veremos exatamente como a QFT entra em ação.

Como funciona o QPE

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

Os qubits são preparados no estado $|\pi_0\rangle = |\psi\rangle|0\rangle$, em que o qubit $0$ está no estado $|0\rangle$ e os qubits restantes estão no estado $|\psi\rangle$, que é um estado próprio de $U$. Após o primeiro Hadamard, o estado do qubit se torna:

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

O próximo portão é um portão "controlado - $U$ ". Isso aplica a operação unitária $U$ aos qubits inferiores que estão no estado $|\psi\rangle$ se o qubit 0 estiver no estado $|1\rangle$, mas não faz nada para $|\psi\rangle$ se o qubit 0 estiver no estado $|0\rangle$. Isso transforma os qubits no 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 estranho acabou de acontecer: a porta controlled- $U$ usa apenas o qubit $0$ como qubit de controle, portanto, pode-se pensar que essa porta não alteraria o estado do qubit 0. Mas, de alguma forma, isso acontece! Embora a operação tenha sido aplicada aos qubits inferiores, o efeito geral da porta é alterar a fase do qubit $0$. Isso é conhecido como "mecanismo de retrocesso de fase" e é usado em muitos algoritmos quânticos, incluindo os algoritmos de Deutsch-Josza e Grover. Se você quiser saber mais sobre o mecanismo de phase-kickback, consulte a lição de John Watrous sobre algoritmos de consulta quântica em Fundamentos de algoritmos quânticos.

Após a fase-kickback, aplicamos mais um 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)$

Portanto, quando medirmos o qubit $0$ no final, mediremos $|0\rangle$ com 100% de certeza se for $\theta = 0$ e mediremos $|1\rangle$ com 100% de certeza se for $\theta = \frac{1}{2}$ (e se nosso computador quântico for perfeito, sem ruído). Se $\theta$ for algo diferente disso, a medição final será apenas probabilística e nos dirá apenas uma parte.

QPE com mais precisão: mais qubits

Podemos estender esse conceito simples a um algoritmo mais complicado com precisão arbitrária. Se, em vez de usar apenas o qubit $0$ para medir a fase, usarmos os qubits $m$ $0$ a $m-1$, poderemos 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 bit único: Hadamards são aplicados 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, os unitários controlados são aplicados. O Qubit $0$ é o controle para o mesmo $U$ unitário de antes. Mas agora, o qubit $1$ é o controle para o unitário $U^2$, que é simplesmente $U$ aplicado 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 do unitário $U^{2^k}$. Isso significa que cada um desses qubits sofrerá 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 dos 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? É um QFT! Lembre-se da equação de uma 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 número inteiro $y$ entre $0$ e $2^m-1$, então a QFT inversa desse estado resultará no estado:

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

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

No entanto, se $\theta/2^m$ não for um múltiplo inteiro, a aplicação da QFT inversa apenas aproximará $\theta$. O grau de aproximação de $\theta$ será probabilístico, o que significa que nem sempre obteremos a melhor aproximação, mas ela será bem próxima, e quanto mais qubits $m$ você usar, melhor será a aproximação. Para saber como quantificar essa aproximação de $\theta$, confira a lição de John Watrous sobre Estimativa de fase e fatoração em Fundamentos de algoritmos quânticos.

Conclusão

Este módulo apresentou uma visão geral do que é um QFT, como ele é implementado em um computador quântico e como ele pode ser útil na solução de problemas. Demos a você uma amostra de sua utilidade quando vimos como ele pode ser usado na estimativa de fase quântica para aprender sobre os valores próprios de uma matriz unitária.

Conceitos críticos

• A Transformada Quântica de Fourier é o análogo quântico da Transformada Discreta de Fourier.
• A QFT é um exemplo de uma transformação de base.
• O procedimento de estimativa de fase quântica se baseia no mecanismo de retrocesso de fase das operações unitárias controladas, bem como em uma QFT inversa.
• A QFT e a QPE são sub-rotinas amplamente usadas em vários algoritmos quânticos.

Perguntas

Verdadeiro/Falso

1. T/F A transformada quântica de Fourier é o análogo quântico da transformada clássica discreta de Fourier (DFT).
2. O T/F QFT pode ser implementado usando apenas portas Hadamard e CNOT.
3. T/F A QFT é um componente essencial do algoritmo de Shor.
4. T/F O resultado da Estimativa de Fase Quântica é um estado quântico que representa o vetor próprio do operador.
5. T/F O QPE requer o uso da Transformada Quântica de Fourier inversa (QFT $^\dag$ ).
6. T/F No QPE, se a fase $\phi$ for exatamente representável com $n$ bits, o algoritmo fornecerá o resultado correto com probabilidade 1.

Respostas curtas

1. Quantos qubits são necessários para realizar um 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 de base computacional? Em caso afirmativo, o que acontece?
3. Como o número de qubits de controle usados no QPE afeta a resolução da estimativa de fase resultante?

Problemas

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

(Não é necessário 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, execute uma QFT no estado. Qual é o estado resultante? Explique por que seu resultado faz sentido, usando seu conhecimento de transformadas de Fourier.