Algoritmi cuantici: Căutarea Grover și aplicații

notă

Atsushi Matsuo (10 mai 2024)

Descarcă PDF-ul al cursului original. Reține că unele fragmente de cod ar putea deveni deprecate, deoarece acestea sunt imagini statice.

Timpul aproximativ de QPU pentru a rula acest experiment este de 2 secunde.

1. Introducere în algoritmul lui Grover

Acest notebook este al patrulea dintr-o serie de cursuri despre Calea spre Utilitate în Calculul Cuantic. În acest notebook, vom învăța despre algoritmul lui Grover.

Algoritmul lui Grover este unul dintre cei mai cunoscuți algoritmi cuantici datorită accelerării sale pătratice față de metodele clasice de căutare. În calculul clasic, căutarea într-o bază de date nesortată de $N$ elemente necesită o complexitate de timp $O(N)$, ceea ce înseamnă că, în cel mai rău caz, ar trebui să examinezi fiecare element individual. Cu toate acestea, algoritmul lui Grover ne permite să realizăm această căutare în timp $O(\sqrt{N})$, valorificând principiile mecanicii cuantice pentru a identifica elementul țintă mai eficient.

Algoritmul folosește amplificarea amplitudinii, un proces care crește amplitudinea de probabilitate a stării cu răspunsul corect dintr-o superpoziție cuantică, permițând măsurarea acesteia cu o probabilitate mai mare. Această accelerare face algoritmul lui Grover valoros în diverse aplicații dincolo de simpla căutare în baze de date, mai ales când dimensiunea setului de date este mare. Explicații detaliate ale algoritmului sunt furnizate în notebook-ul algoritmului Grover.

Structura de bază a algoritmului lui Grover

Algoritmul lui Grover cuprinde patru componente principale:

1. Inițializare: Configurarea superpoziției peste toate stările posibile.
2. Oracle: Aplicarea unei funcții oracle care marchează starea țintă prin inversarea fazei sale.
3. Operatorul de difuzie: Aplicarea unei serii de operații pentru a amplifica probabilitatea stării marcate.

Fiecare dintre acești pași joacă un rol esențial în a face algoritmul să funcționeze eficient. Explicații detaliate pentru fiecare pas sunt furnizate mai târziu.

2. Implementarea algoritmului lui Grover

2.1 Pregătire

Importă bibliotecile necesare și configurează mediul pentru rularea circuitului cuantic.

# 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

Pasul 1: Maparea problemei pe circuite și operatori cuantici

Consideră o listă de 4 elemente, unde scopul nostru este să identificăm indexul unui element care îndeplinește o condiție specifică. De exemplu, dorim să găsim indexul elementului egal cu 2. În acest exemplu, starea cuantică $|01\rangle$ reprezintă indexul elementului care satisface această condiție, deoarece indică poziția unde se află valoarea 2.

Pasul 2: Optimizare pentru hardware-ul țintă

1: Inițializare

În pasul de inițializare, creăm o superpoziție a tuturor stărilor posibile. Aceasta se realizează prin aplicarea unui Hadamard Gate la fiecare qubit dintr-un registru de n qubiți, ceea ce va rezulta într-o superpoziție egală a $2^n$ stări. Din punct de vedere matematic, aceasta poate fi reprezentată astfel:

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

unde $N = 2^n$ este numărul total de stări posibile. De asemenea, schimbăm starea bitului ancilă la $|-\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: Oracle

Oracle-ul este o parte esențială a algoritmului lui Grover. Acesta marchează starea țintă aplicând o deplasare de fază, inversând de obicei semnul amplitudinii asociate cu acea stare. Oracle-ul este adesea specific problemei și construit pe baza criteriilor de identificare a stării țintă. Din punct de vedere matematic, oracle-ul aplică următoarea transformare:

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

Această inversare de fază se realizează prin aplicarea unui semn negativ la amplitudinea stării țintă prin intermediul 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: Operatorul de difuzie

Procesul de amplificare a amplitudinii este ceea ce diferențiază algoritmul lui Grover de o căutare clasică. După ce oracle-ul a marcat starea țintă, aplicăm o serie de operații care cresc amplitudinea acestei stări marcate, făcând-o mai probabil să fie observată la măsurare. Acest proces se realizează prin Operatorul de difuzie, care efectuează efectiv o inversare față de amplitudinea medie. Operația matematică este următoarea:

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

unde $D$ este operatorul de difuzie, $I$ este matricea identitate, iar $|\psi\rangle$ este starea de superpoziție egală. Combinația oracle-ului și a operatorului de difuzie este aplicată de aproximativ $\sqrt{N}$ ori pentru a obține probabilitatea maximă de măsurare a stării marcate.

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 Un exemplu de căutare Grover cu 2 qubiți

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 Experiment cu Simulatoare

Pasul 3: Executarea circuitului.

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

Pasul 4: Post-procesarea rezultatelor.

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Am obținut răspunsul corect $|01\rangle$. Reține că trebuie să fii atent la ordinea qubiților.

3. Experiment cu dispozitive reale

Pasul 2: Optimizare pentru hardware-ul țintă

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)

Prin transpilarea circuitului, acesta a fost convertit într-un circuit care folosește porțile de bază native ale dispozitivului.

Pasul 3: Executarea circuitului.

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}

Pasul 4: Post-procesarea rezultatelor.

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

4. O căutare Grover cu 3 qubiți

Acum, să încercăm un exemplu de căutare Grover cu 3 qubiți.

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

De data aceasta, $|111\rangle$ este starea „bună".

# 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$ este observat cu cea mai mare probabilitate, după cum era de așteptat. Reține că două iterații sunt optime în acest caz. Cu toate acestea, probabilitatea de a obține răspunsul corect nu este 100%, ceea ce este obișnuit în căutarea lui Grover.

Ce se întâmplă dacă iterăm de 3 ori?

Acum, să încercăm să iterăm de 3 ori.

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$ este în continuare observat cu cea mai mare probabilitate, deși probabilitatea de a obține răspunsul corect a scăzut ușor.

Dar de 4 ori?

Acum, să încercăm să iterăm de 4 ori.

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$ este observat cu cea mai mică probabilitate, iar probabilitatea de a obține răspunsul corect a scăzut și mai mult. Aceasta demonstrează importanța alegerii numărului optim de iterații pentru algoritmul lui Grover în vederea obținerii celor mai bune rezultate.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'