Algoritmos quânticos: Estimativa de fase

nota

Kento Ueda (15 de maio de 2024)

Este notebook apresenta os conceitos fundamentais e a implementação da Transformada de Fourier Quântica (QFT) e da Estimativa de Fase Quântica (QPE).

Baixe o PDF da aula original. Observe que alguns trechos de código podem estar desatualizados, pois são imagens estáticas.

O tempo aproximado de QPU para rodar esse experimento é de 7 segundos.

1. Introdução

Transformada de Fourier Quântica (QFT)

A Transformada de Fourier Quântica é a versão quântica da transformada discreta de Fourier clássica. É uma transformação linear aplicada a estados quânticos que mapeia as bases computacionais para suas representações na base de Fourier. A QFT tem um papel fundamental em muitos algoritmos quânticos, oferecendo um método eficiente para extrair informações de periodicidade de estados quânticos. A QFT pode ser implementada com $O(N^2)$ operações usando portas quânticas como portas de Hadamard e portas de Fase Controlada para $N$ qubits, possibilitando uma aceleração exponencial em relação à transformada de Fourier clássica.

• Aplicações: É um componente fundamental em algoritmos quânticos como o algoritmo de Shor para fatoração de inteiros grandes e logaritmo discreto.

Estimativa de Fase Quântica (QPE)

A Estimativa de Fase Quântica é um algoritmo quântico usado para estimar a fase associada a um autovetor de um operador unitário. Esse algoritmo cria uma ponte entre as propriedades matemáticas abstratas dos estados quânticos e suas aplicações computacionais.

• Aplicações: Ele consegue resolver problemas como encontrar autovalores de matrizes unitárias e simular sistemas quânticos.

Juntos, QFT e QPE formam a espinha dorsal essencial de muitos algoritmos quânticos que resolvem problemas inviáveis para computadores clássicos. Ao fim deste notebook, você vai entender como essas técnicas são implementadas.

2. Fundamentos da Transformada de Fourier Quântica (QFT)

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

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit_aer import AerSimulator
from qiskit.visualization import plot_histogram, plot_bloch_multivector
from qiskit.quantum_info import Statevector
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager
from qiskit_ibm_runtime import Sampler

from numpy import pi

Por analogia com a transformada discreta de Fourier, a QFT age sobre um estado quântico $\vert X\rangle = \sum_{j=0}^{N-1} x_j \vert j \rangle$ para $N$ qubits e o mapeia para o estado quântico $\vert Y\rangle = \sum_{k=0}^{N-1} y_k \vert k \rangle$.

$$QFT_{N}: \vert j \rangle \mapsto \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\omega_N^{jk} \vert k \rangle$$

onde $\omega_N^{jk} = e^{2\pi i \frac{jk}{N}}$.

Ou a representação em matriz unitária:

$$U_{QFT} = \frac{1}{\sqrt{N}} \sum_{j=0}^{N-1} \sum_{k=0}^{N-1} \omega_N^{jk} \vert k \rangle \langle j \vert$$

2.1. Intuição

A transformada de Fourier quântica (QFT) transforma entre duas bases: a base computacional (Z) e a base de Fourier. Mas o que significa a base de Fourier nesse contexto? Você provavelmente lembra que a transformada de Fourier $F(\omega)$ de uma função $f(x)$ descreve a convolução de $f(x)$ com uma função senoidal de frequência $\omega$. Em termos simples: a transformada de Fourier é uma função que descreve quanto de cada frequência $\omega$ precisaríamos para construir uma função $f(x)$ a partir de funções seno (ou cosseno). Para entender melhor o que a QFT significa nesse contexto, observe as imagens em sequência abaixo, que mostram um número codificado em binário usando quatro qubits:

Na base computacional, armazenamos números em binário usando os estados $|0\rangle$ e $|1\rangle$.

Observe a frequência com que os diferentes qubits mudam: o qubit mais à esquerda vira a cada incremento no número, o seguinte a cada 2 incrementos, o terceiro a cada 4 incrementos, e assim por diante.

Se aplicarmos uma transformada de Fourier quântica a esses estados, mapeamos

$$|\text{Estado na Base Computacional}\rangle \quad \xrightarrow[]{\text{QFT}} \quad |\text{Estado na Base de Fourier}\rangle$$ $$\text{QFT}|x\rangle = |\widetilde{x}\rangle$$

(Costumamos denotar estados na base de Fourier usando o til (~)).

Na base de Fourier, armazenamos números usando diferentes rotações ao redor do eixo Z:

IFRAME

O número que queremos armazenar determina o ângulo em que cada qubit é girado ao redor do eixo Z. No estado $|\widetilde{0}\rangle$, todos os qubits estão no estado $|{+}\rangle$. Como visto no exemplo acima, para codificar o estado $|\widetilde{5}\rangle$ em 4 qubits, giramos o qubit mais à esquerda em $\tfrac{5}{2^n} = \tfrac{5}{16}$ voltas completas ($\tfrac{5}{16}\times 2\pi$ radianos). O próximo qubit é girado o dobro disso ($\tfrac{10}{16}\times 2\pi$ radianos, ou $10/16$ voltas completas), esse ângulo é então dobrado para o qubit seguinte, e assim sucessivamente.

Novamente, observe a frequência com que cada qubit muda. O qubit mais à esquerda (qubit 0) tem a menor frequência nesse caso, e o mais à direita tem a maior.

2.2 Exemplo: QFT de 1 qubit

Vamos considerar o caso de $N = 2^1 = 2$.

A matriz unitária pode ser escrita como:

$$\begin{aligned} U_{QFT} & = \frac{1}{\sqrt{2}} \sum_{j=0}^{1} \sum_{k=0}^{1} \omega_2^{jk} \vert k \rangle \langle j \vert \\ & = \frac{1}{\sqrt{2}} (\omega_2^{0} \vert 0 \rangle \langle 0 \vert + \omega_2^{0} \vert 0 \rangle \langle 1 \vert + \omega_2^{0} \vert 1 \rangle \langle 0 \vert + \omega_2^{1} \vert 1 \rangle \langle 1 \vert) \\ & = \frac{1}{\sqrt{2}} (\vert 0 \rangle \langle 0 \vert + \vert 0 \rangle \langle 1 \vert + \vert 1 \rangle \langle 0 \vert - \vert 1 \rangle \langle 1 \vert) \\ & = H \end{aligned}$$

Essa operação é o resultado de aplicar a porta de Hadamard ($H$).

2.3 Representação em produto da QFT

Vamos generalizar uma transformação para $N = 2^n$, $QFT_{N}$ agindo sobre o estado $\vert x \rangle = \vert x_1\ldots x_n \rangle$.

$$\begin{aligned} QFT_N\vert x \rangle & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1}\omega_N^{xy} \vert y \rangle \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i xy / 2^n} \vert y \rangle ~\text{já que}\: \omega_N^{xy} = e^{2\pi i \frac{xy}{N}} \:\text{e}\: N = 2^n \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} e^{2 \pi i \left(\sum_{k=1}^n y_k/2^k\right) x} \vert y_1 \ldots y_n \rangle \:\text{reescrevendo em notação binária fracionária}\: y = y_1\ldots y_n, y/2^n = \sum_{k=1}^n y_k/2^k \\ & = \frac{1}{\sqrt{N}} \sum_{y=0}^{N-1} \prod_{k=1}^n e^{2 \pi i x y_k/2^k } \vert y_1 \ldots y_n \rangle \:\text{após expandir o exponencial de uma soma como produto de exponenciais,} \\ & = \frac{1}{\sqrt{N}} \bigotimes_{k=1}^n \left(\vert0\rangle + e^{2 \pi i x /2^k } \vert1\rangle \right) \:\text{após reorganizar a soma e os produtos, e expandir} \sum_{y=0}^{N-1} = \sum_{y_1=0}^{1}\sum_{y_2=0}^{1}\ldots\sum_{y_n=0}^{1} \\ & = \frac{1}{\sqrt{N}} \left(\vert0\rangle + e^{\frac{2\pi i}{2}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^2}x} \vert1\rangle\right) \otimes \ldots \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^{n-1}}x} \vert1\rangle\right) \otimes \left(\vert0\rangle + e^{\frac{2\pi i}{2^n}x} \vert1\rangle\right) \end{aligned}$$

2.4 Exemplo: Construção de circuito QFT com 3 qubits

A partir da descrição acima, pode não estar claro como construir um circuito QFT. Por enquanto, basta notar que esperamos que três qubits tenham fases que evoluem em "taxas" diferentes. Entender exatamente como isso se traduz em um circuito fica como exercício para o leitor. Há vários diagramas e exemplos no PDF da aula. Recursos adicionais incluem esta lição do curso de Fundamentos de algoritmos quânticos.

Vamos demonstrar a QFT usando apenas simuladores e, portanto, não usaremos o framework de padrões do Qiskit até chegarmos na estimativa de fase quântica.

# Prepare for 3 qubits circuit
qr = QuantumRegister(3)
cr = ClassicalRegister(3)
qc = QuantumCircuit(qr, cr)

qc.h(2)
qc.cp(pi / 2, 1, 2)  # Controlled-phase gate from qubit 1 to qubit 2
qc.cp(pi / 4, 0, 2)  # Controlled-phase gate from qubit 0 to qubit 2
qc.draw(output="mpl")

qc.h(1)
qc.cp(pi / 2, 0, 1)  # Controlled-phase gate from qubit 0 to qubit 1

qc.draw(output="mpl")

qc.h(0)

qc.draw(output="mpl")

qc.swap(0, 2)

qc.draw(output="mpl")

Vamos aplicar a QFT em $|5\rangle$ como exemplo.

Primeiro, confirmamos a notação binária do inteiro 5 e criamos o circuito que codifica o estado 5:

bin(5)

'0b101'

qc = QuantumCircuit(3)

qc.x(0)
qc.x(2)
qc.draw(output="mpl")

Verificamos os estados quânticos usando o simulador Aer:

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Por fim, adicionamos a QFT e visualizamos o estado final dos nossos qubits:

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

Podemos ver que nossa função QFT funcionou corretamente. O qubit 0 foi girado em $\tfrac{5}{8}$ de uma volta completa, o qubit 1 em $\tfrac{10}{8}$ voltas completas (equivalente a $\tfrac{1}{4}$ de volta completa), e o qubit 2 em $\tfrac{20}{8}$ voltas completas (equivalente a $\tfrac{1}{2}$ de volta completa).

2.5 Exercício: QFT

(1) Implemente a QFT de 4 qubits.

##your code goes here##

(2) Aplique a QFT em $|14\rangle$, simule e plote o vetor de estado usando a esfera de Bloch.

##your code goes here##

Solução do exercício: QFT

(1)

qr = QuantumRegister(4)
cr = ClassicalRegister(4)
qc = QuantumCircuit(qr, cr)

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)

qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

(2)

bin(14)

'0b1110'

qc = QuantumCircuit(4)

qc.x(1)
qc.x(2)
qc.x(3)
qc.draw("mpl")

qc.h(3)
qc.cp(pi / 2, 2, 3)
qc.cp(pi / 4, 1, 3)
qc.cp(pi / 8, 0, 3)

qc.h(2)
qc.cp(pi / 2, 1, 2)
qc.cp(pi / 4, 0, 2)

qc.h(1)
qc.cp(pi / 2, 0, 1)
qc.h(0)

qc.swap(0, 3)
qc.swap(1, 2)

qc.draw(output="mpl")

statevector = Statevector(qc)
plot_bloch_multivector(statevector)

3. Fundamentos da Estimativa de Fase Quântica (QPE)

Dado uma operação unitária $U$, a QPE estima $\theta$ em $U\vert\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$. Como $U$ é unitária, todos os seus autovalores têm norma 1.

3.1 Procedimento

1. Configuração

$\vert\psi\rangle$ está em um conjunto de registradores de qubits. Um conjunto adicional de $n$ qubits forma o registrador de contagem, onde armazenaremos o valor $2^n\theta$:

$$|\psi_0\rangle = \lvert 0 \rangle^{\otimes n} \lvert \psi \rangle$$

2. Superposição

Aplique uma operação Hadamard de $n$ bits $H^{\otimes n}$ no registrador de contagem:

$$|\psi_1\rangle = {\frac {1}{2^{\frac {n}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes n} \lvert \psi \rangle$$

3. Operações Unitárias Controladas

Precisamos introduzir a unitária controlada $CU$, que aplica o operador unitário $U$ no registrador-alvo somente quando o bit de controle correspondente é $|1\rangle$. Como $U$ é um operador unitário com autovetor $|\psi\rangle$ tal que $U|\psi \rangle =e^{\boldsymbol{2\pi i} \theta }|\psi \rangle$, temos:

$$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$$

3.2 Exemplo: QPE com a gate T

Vamos usar a gate $T$ como exemplo de QPE e estimar sua fase $\theta$.

$$T|1\rangle = \begin{pmatrix} 1 & 0\\ 0 & e^\frac{i\pi}{4}\\ \end{pmatrix} \begin{pmatrix} 0\\ 1\\ \end{pmatrix} = e^\frac{i\pi}{4}|1\rangle$$

Esperamos encontrar:

$$\theta = \frac{1}{8}$$

onde

$$T|1\rangle = e^{2i\pi\theta}|1\rangle$$

Inicializamos $\vert\psi\rangle = \vert1\rangle$ como o autovetor da gate $T$ aplicando uma gate $X$:

qpe = QuantumCircuit(4, 3)
qpe.x(3)
qpe.draw(output="mpl")

Em seguida, aplicamos gates Hadamard aos qubits de contagem:

for qubit in range(3):
    qpe.h(qubit)
qpe.draw(output="mpl")

Realizamos as operações unitárias controladas:

repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.draw(output="mpl")

Aplicamos a transformada quântica de Fourier inversa para converter o estado do registrador de contagem e, em seguida, medimos esse registrador:

from qiskit.circuit.library import QFT

# Apply inverse QFT
qpe.append(QFT(3, inverse=True), [0, 1, 2])
qpe.draw(output="mpl")

for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

Podemos simular usando o simulador Aer:

aer_sim = AerSimulator()
shots = 2048

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

Observamos que obtemos um único resultado (001) com certeza, o que corresponde ao decimal 1. Agora precisamos dividir nosso resultado (1) por $2^n$ para obter $\theta$:

$$\theta = \frac{1}{2^3} = \frac{1}{8}$$

O algoritmo de Shor nos permite fatorar um número construindo um circuito com $\theta$ desconhecido e obtendo $\theta$.

3.3 Exercício

Estime $\theta = 1/3$ usando 3 qubits para contagem e um qubit para o autovetor.

$P|1\rangle = e^{i\lambda}|1\rangle$. Como queremos implementar $U|1\rangle = e^{2\pi i \tfrac{1}{3}}|1\rangle$, precisamos definir $\lambda = \tfrac{2 \pi}{3}$.

##your code goes here##

Solução do exercício: $\theta = 1/3$

# Create and set up circuit
qpe = QuantumCircuit(4, 3)

# Apply H-Gates to counting qubits:
for qubit in range(3):
    qpe.h(qubit)

# Prepare our eigenstate |psi>:
qpe.x(3)

# Do the controlled-U operations:
angle = 2 * pi / 3
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(angle, counting_qubit, 3)
    repetitions *= 2

# Do the inverse QFT:
qpe.append(QFT(3, inverse=True), [0, 1, 2])

for n in range(3):
    qpe.measure(n, n)

qpe.draw(output="mpl")

aer_sim = AerSimulator()
shots = 4096

pm = generate_preset_pass_manager(backend=aer_sim, optimization_level=1)
t_qpe = pm.run(qpe)

sampler = Sampler(mode=aer_sim)
job = sampler.run([t_qpe], shots=shots)
result = job.result()
answer = result[0].data.c.get_counts()

plot_histogram(answer)

4. Execução com a primitiva Sampler do Qiskit Runtime

Vamos executar a QPE em um dispositivo quântico real seguindo as 4 etapas dos padrões Qiskit.

1. Mapear o problema para um formato nativo quântico
2. Otimizar os circuitos
3. Executar o circuito-alvo
4. Pós-processar os resultados

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import Sampler

# Loading your IBM Quantum® account(s)

service = QiskitRuntimeService()

4.1 Passo 1: Mapear o problema para circuitos e operadores quânticos

qpe = QuantumCircuit(4, 3)
qpe.x(3)
for qubit in range(3):
    qpe.h(qubit)
repetitions = 1
for counting_qubit in range(3):
    for i in range(repetitions):
        qpe.cp(pi / 4, counting_qubit, 3)  # This is C-U
    repetitions *= 2
qpe.append(QFT(3, inverse=True), [0, 1, 2])
for n in range(3):
    qpe.measure(n, n)
qpe.draw(output="mpl")

backend = service.least_busy(simulator=False, operational=True, min_num_qubits=4)

print(backend)

<IBMBackend('ibm_strasbourg')>

4.2 Passo 2: Otimizar para o hardware-alvo

# Transpile the circuit into basis gates executable on the hardware
pm = generate_preset_pass_manager(backend=backend, optimization_level=2)
qc_compiled = pm.run(qpe)

qc_compiled.draw("mpl", idle_wires=False)

4.3 Passo 3: Executar no hardware-alvo

real_sampler = Sampler(mode=backend)
job = real_sampler.run([qc_compiled], shots=1024)
job_id = job.job_id()
print("job id:", job_id)

job id: d13p4zb5z6q00087ag00

job = service.job(job_id)  # Input your job-id between the quotations
job.status()

'DONE'

result_real = job.result()
print(result_real)

PrimitiveResult([SamplerPubResult(data=DataBin(c=BitArray(<shape=(), num_shots=1024, num_bits=3>)), metadata={'circuit_metadata': {}})], metadata={'execution': {'execution_spans': ExecutionSpans([DoubleSliceSpan(<start='2025-06-09 22:39:00', stop='2025-06-09 22:39:00', size=1024>)])}, 'version': 2})

4.4 Passo 4: Pós-processar os resultados

from qiskit.visualization import plot_histogram

plot_histogram(result_real[0].data.c.get_counts())

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'