Kvantové algoritmy: Groverovo vyhledávání a aplikace

poznámka

Atsushi Matsuo (10. května 2024)

Stáhnout pdf původní přednášky. Upozorňujeme, že některé ukázky kódu mohou být zastaralé, protože se jedná o statické obrázky.

Přibližný QPU čas pro spuštění tohoto experimentu je 2 sekundy.

1. Úvod do Groverova algoritmu

Tento notebook je čtvrtý v sérii přednášek o Cestě k užitečnosti v kvantovém počítání. V tomto notebooku se seznámíme s Groverovým algoritmem.

Groverův algoritmus je jedním z nejznámějších kvantových algoritmů díky svému kvadratickému zrychlení oproti klasickým vyhledávacím metodám. V klasickém počítání vyžaduje prohledávání neseřazené databáze o $N$ prvcích časovou složitost $O(N)$, což znamená, že v nejhorším případě je nutné prozkoumat každý prvek jednotlivě. Groverův algoritmus nám však umožňuje provést toto vyhledávání v čase $O(\sqrt{N})$ díky využití principů kvantové mechaniky k efektivnější identifikaci cílového prvku.

Algoritmus využívá amplitudovou amplifikaci, proces, který zvyšuje amplitudu pravděpodobnosti stavu se správnou odpovědí v kvantové superpozici, což umožňuje jeho změření s vyšší pravděpodobností. Toto zrychlení činí Groverův algoritmus cenným v různých aplikacích nad rámec jednoduchého vyhledávání v databázi, zejména když je velikost datové sady velká. Podrobná vysvětlení algoritmu jsou uvedena v notebooku o Groverově algoritmu.

Základní struktura Groverova algoritmu

Groverův algoritmus se skládá ze čtyř hlavních komponent:

1. Inicializace: Nastavení superpozice přes všechny možné stavy.
2. Oracle: Aplikace funkce Oracle, která označí cílový stav obrácením jeho fáze.
3. Difuzní operátor: Aplikace série operací, které zesílí pravděpodobnost označeného stavu.

Každý z těchto kroků hraje klíčovou roli v tom, aby algoritmus fungoval efektivně. Podrobná vysvětlení jednotlivých kroků jsou uvedena později.

2. Implementace Groverova algoritmu

2.1 Příprava

Importuj potřebné knihovny a nastav prostředí pro spuštění kvantového Circuitu.

# 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

Krok 1: Mapování problému na kvantové Circuity a operátory

Uvažuj seznam 4 prvků, kde je naším cílem identifikovat index prvku, který splňuje určitou podmínku. Například chceme najít index prvku rovného 2. V tomto příkladu kvantový stav $|01\rangle$ reprezentuje index prvku, který splňuje tuto podmínku, protože ukazuje na pozici, kde se nachází hodnota 2.

Krok 2: Optimalizace pro cílový hardware

1: Inicializace

V kroku inicializace vytvoříme superpozici všech možných stavů. Toho docílíme aplikací Hadamardova Gate na každý Qubit v n-qubitovém registru, což povede k rovnoměrné superpozici $2^n$ stavů. Matematicky to lze vyjádřit takto:

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

kde $N = 2^n$ je celkový počet možných stavů. Také změníme stav ancilla bitu na $|-\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 je klíčovou součástí Groverova algoritmu. Označuje cílový stav tím, že aplikuje fázový posun, obvykle obrací znaménko amplitudy spojené s tímto stavem. Oracle bývá často specifický pro daný problém a je konstruován na základě kritérií pro identifikaci cílového stavu. Matematicky Oracle aplikuje následující transformaci:

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

Tento fázový obrat je dosažen aplikací záporného znaménka na amplitudu cílového stavu pomocí fázového kickbacku.

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: Difúzní operátor

Proces amplitudového zesílení je to, co odlišuje Groverův algoritmus od klasického vyhledávání. Poté, co Oracle označí cílový stav, aplikujeme sérii operací, které zvyšují amplitudu tohoto označeného stavu, čímž zvyšují pravděpodobnost, že bude pozorován při měření. Tento proces je realizován pomocí difúzního operátoru, který v podstatě provádí inverzi okolo průměrné amplitudy. Matematická operace je následující:

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

kde $D$ je difúzní operátor, $I$ je jednotková matice a $|\psi\rangle$ je stav rovnoměrné superpozice. Kombinace Oracle a difúzního operátoru se aplikuje přibližně $\sqrt{N}$krát, aby bylo dosaženo maximální pravděpodobnosti naměření označeného stavu.

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 Příklad Groverova hledání se 2 qubity.

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 se simulátory

Krok 3: Spuštění obvodu.

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

Krok 4: Zpracování výsledků.

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

3. Experiment se skutečnými zařízeními

Krok 2: Optimalizace pro cílový hardware

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)

Transpilací byl Circuit převeden na obvod využívající nativní bázové Gates daného zařízení.

Krok 3: Spuštění obvodu.

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}

Krok 4: Zpracování výsledků.

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

4. Groverovo hledání se 3 qubity

Nyní si vyzkoušejme příklad Groverova hledání se 3 qubity.

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

Tentokrát je „dobrým“ stavem $|111\rangle$.

# 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$ je pozorováno s nejvyšší pravděpodobností, jak se očekává. Všimni si, že dvě iterace jsou v tomto případě optimální. Pravděpodobnost získání správné odpovědi však není 100 %, což je u Groverova hledání běžné.

Co se stane, když iterujeme 3krát?

Nyní zkusme provést 3 iterace.

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$ je stále pozorován s nejvyšší pravděpodobností, i když pravděpodobnost získání správné odpovědi se mírně snížila.

A co 4krát?

Nyní zkusme provést 4 iterace.

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$ je pozorován s nejnižší pravděpodobností a pravděpodobnost získání správné odpovědi se dále snížila. To ukazuje, jak důležité je zvolit optimální počet iterací Groverova algoritmu pro dosažení nejlepších výsledků.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'