Algoritmos quânticos: busca de Grover e aplicações

nota

Atsushi Matsuo (10 de maio de 2024)

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

O tempo aproximado de QPU para executar este experimento é de 2 segundos.

1. Introdução ao algoritmo de Grover

Este notebook é o quarto de uma série de aulas sobre o Caminho para a Utilidade na Computação Quântica. Nele, vamos aprender sobre o algoritmo de Grover.

O algoritmo de Grover é um dos algoritmos quânticos mais conhecidos, graças ao seu ganho de velocidade quadrático em relação aos métodos clássicos de busca. Na computação clássica, buscar em um banco de dados não ordenado com $N$ elementos requer complexidade de tempo $O(N)$, o que significa que, no pior caso, pode ser necessário examinar cada item individualmente. Porém, o algoritmo de Grover permite realizar essa busca em tempo $O(\sqrt{N})$, aproveitando os princípios da mecânica quântica para identificar o elemento alvo de forma mais eficiente.

O algoritmo utiliza amplificação de amplitude, um processo que aumenta a amplitude de probabilidade do estado correto em uma superposição quântica, permitindo que ele seja medido com maior probabilidade. Esse ganho de velocidade torna o algoritmo de Grover valioso em diversas aplicações além de simples buscas em banco de dados, especialmente quando o tamanho do conjunto de dados é grande. Explicações detalhadas do algoritmo estão disponíveis no notebook do algoritmo de Grover.

A estrutura básica do algoritmo de Grover

O algoritmo de Grover é composto por quatro componentes principais:

1. Inicialização: configuração da superposição sobre todos os estados possíveis.
2. Oráculo: aplicação de uma função oráculo que marca o estado alvo invertendo sua fase.
3. Operador de difusão: aplicação de uma série de operações para amplificar a probabilidade do estado marcado.

Cada uma dessas etapas tem um papel fundamental para que o algoritmo funcione de forma eficiente. Explicações detalhadas de cada etapa são fornecidas adiante.

2. Implementando o algoritmo de Grover

2.1 Preparação

Importe as bibliotecas necessárias e configure o ambiente para executar o circuito quântico.

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

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

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

Considere uma lista de 4 elementos, em que o objetivo é identificar o índice de um elemento que atende a uma condição específica. Por exemplo, queremos encontrar o índice do elemento igual a 2. Neste exemplo, o estado quântico $|01\rangle$ representa o índice do elemento que satisfaz essa condição, pois aponta para a posição onde o valor 2 está localizado.

Passo 2: Otimizar para o hardware alvo

1: Inicialização

Na etapa de inicialização, criamos uma superposição de todos os estados possíveis. Isso é feito aplicando uma porta Hadamard a cada qubit em um registrador de n qubits, o que resulta em uma superposição uniforme de $2^n$ estados. Matematicamente, isso pode ser representado como:

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

onde $N = 2^n$ é o número total de estados possíveis. Também alteramos o estado do bit ancilla para $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: Oráculo

O oráculo é uma parte fundamental do algoritmo de Grover. Ele marca o estado alvo aplicando uma mudança de fase, tipicamente invertendo o sinal da amplitude associada a esse estado. O oráculo costuma ser específico para o problema e é construído com base nos critérios de identificação do estado alvo. Em termos matemáticos, o oráculo aplica a seguinte transformação:

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

Essa inversão de fase é obtida aplicando um sinal negativo à amplitude do estado alvo por meio do phase kickback.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: Operador de difusão

O processo de amplificação de amplitude é o que diferencia o algoritmo de Grover de uma busca clássica. Após o oráculo marcar o estado alvo, aplicamos uma série de operações que aumentam a amplitude desse estado marcado, tornando mais provável que ele seja observado na medição. Esse processo é realizado pelo Operador de difusão, que efetivamente executa uma inversão em torno da amplitude média. A operação matemática é a seguinte:

$D = 2|\psi\rangle\langle\psi| - I$

onde $D$ é o operador de difusão, $I$ é a matriz identidade e $|\psi\rangle$ é o estado de superposição uniforme. A combinação do oráculo e do operador de difusão é aplicada aproximadamente $\sqrt{N}$ vezes para atingir a probabilidade máxima de medir o estado marcado.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Exemplo de busca de Grover com 2 qubits

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Experimento com Simuladores

Passo 3: Executar o circuito.

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Passo 4: Pós-processamento dos resultados.

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Obtivemos a resposta correta $|01\rangle$. Preste atenção à ordem dos qubits.

3. Experimento com dispositivos reais

Passo 2: Otimizar para o hardware alvo.

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Ao transpilar o circuito, ele foi convertido para um circuito utilizando as portas nativas do dispositivo.

Passo 3: Executar o circuito.

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Passo 4: Pós-processamento dos resultados.

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

4. Uma busca de Grover com 3 qubits

Agora, vamos experimentar um exemplo de busca de Grover com 3 qubits.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Desta vez, $|111\rangle$ é o estado "bom".

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ é observado com a maior probabilidade, como esperado. Note que duas iterações são ótimas nesse caso. Porém, a probabilidade de obter a resposta correta não é 100%, o que é comum na busca de Grover.

O que acontece se iterarmos 3 vezes?

Agora, vamos tentar iterar 3 vezes.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ ainda é observado com a maior probabilidade, embora a probabilidade de obter a resposta correta tenha diminuído um pouco.

E com 4 vezes?

Agora, vamos tentar iterar 4 vezes.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ é observado com a menor probabilidade, e a chance de obter a resposta correta diminuiu ainda mais. Isso demonstra a importância de escolher o número ideal de iterações para o algoritmo de Grover a fim de alcançar os melhores resultados.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'