Algorytmy kwantowe: wyszukiwanie Grovera i zastosowania

uwaga

Atsushi Matsuo (10 maja 2024)

Pobierz plik pdf oryginalnego wykładu. Należy pamiętać, że niektóre fragmenty kodu mogą być przestarzałe, ponieważ są to obrazy statyczne.

Przybliżony czas QPU potrzebny do wykonania tego eksperymentu to 2 sekundy.

1. Wprowadzenie do algorytmu Grovera

Ten notatnik jest czwartym z serii wykładów dotyczących Path to Utility in Quantum Computing. W tym notatniku poznamy algorytm Grovera.

Algorytm Grovera jest jednym z najbardziej znanych algorytmów kwantowych ze względu na jego kwadratowe przyspieszenie w stosunku do klasycznych metod wyszukiwania. W obliczeniach klasycznych przeszukanie nieposortowanej bazy danych zawierającej $N$ elementów wymaga złożoności czasowej $O(N)$, co oznacza, że w najgorszym przypadku trzeba zbadać każdy element z osobna. Algorytm Grovera pozwala jednak osiągnąć to wyszukiwanie w czasie $O(\sqrt{N})$, wykorzystując zasady mechaniki kwantowej do bardziej efektywnego zidentyfikowania docelowego elementu.

Algorytm wykorzystuje wzmacnianie amplitudy, proces, który zwiększa amplitudę prawdopodobieństwa stanu poprawnej odpowiedzi w superpozycji kwantowej, umożliwiając jego pomiar z wyższym prawdopodobieństwem. To przyspieszenie kwantowe sprawia, że algorytm Grovera jest cenny w różnych zastosowaniach wykraczających poza proste przeszukiwanie baz danych, zwłaszcza gdy rozmiar zbioru danych jest duży. Szczegółowe wyjaśnienia algorytmu znajdują się w notatniku o algorytmie Grovera.

Podstawowa struktura algorytmu Grovera

Algorytm Grovera składa się z czterech głównych komponentów:

1. Inicjalizacja: przygotowanie superpozycji po wszystkich możliwych stanach.
2. Wyrocznia: zastosowanie funkcji oracle, która oznacza stan docelowy poprzez odwrócenie jego fazy.
3. Operator dyfuzji: zastosowanie serii operacji w celu wzmocnienia prawdopodobieństwa marked state.

Każdy z tych kroków odgrywa kluczową rolę w zapewnieniu efektywnego działania algorytmu. Szczegółowe wyjaśnienia każdego kroku są przedstawione w dalszej części.

2. Implementacja algorytmu Grovera

2.1 Przygotowanie

Zaimportuj niezbędne biblioteki i skonfiguruj środowisko do uruchomienia obwodu kwantowego.

# 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: Odwzoruj problem na obwody i operatory kwantowe

Rozważmy listę 4 elementów, w której naszym celem jest zidentyfikowanie indeksu elementu spełniającego określony warunek. Na przykład chcemy znaleźć indeks elementu równego 2. W tym przykładzie stan kwantowy $|01\rangle$ reprezentuje indeks elementu spełniającego ten warunek, ponieważ wskazuje na pozycję, w której znajduje się wartość 2.

Krok 2: Optymalizacja pod kątem docelowego sprzętu

1: Inicjalizacja

W kroku inicjalizacji tworzymy superpozycję wszystkich możliwych stanów. Osiąga się to przez zastosowanie bramki Hadamard do każdego kubita w n-kubitowym rejestrze, co w rezultacie daje równomierną superpozycję $2^n$ stanów. Matematycznie można to przedstawić jako:

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

gdzie $N = 2^n$ to całkowita liczba możliwych stanów. Zmieniamy również stan bitu ancilla 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 jest kluczowym elementem algorytmu Grovera. Oznacza stan docelowy poprzez zastosowanie przesunięcia fazowego, zazwyczaj odwracając znak amplitudy związanej z tym stanem. Oracle jest często specyficzny dla problemu i konstruowany na podstawie kryteriów identyfikacji stanu docelowego. W ujęciu matematycznym oracle stosuje następujące przekształcenie:

f(x) = \begin\{cases\} 1, & \text\{jeśli \} x = x_\{\text\{target}\} \\ 0, & \text\{w przeciwnym razie\} \end\{cases\}

To odwrócenie fazy uzyskuje się poprzez zastosowanie ujemnego znaku do amplitudy stanu docelowego za pomocą 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: Operator dyfuzji

Proces wzmacniania amplitudy jest tym, co odróżnia algorytm Grovera od klasycznego wyszukiwania. Po tym, jak oracle oznaczył stan docelowy, stosujemy serię operacji, które zwiększają amplitudę tego oznaczonego stanu, zwiększając prawdopodobieństwo jego zaobserwowania podczas pomiaru. Proces ten realizowany jest przez operator dyfuzji (diffuser), który w praktyce wykonuje inwersję względem średniej amplitudy. Operacja matematyczna wygląda następująco:

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

gdzie $D$ to operator dyfuzji, $I$ to macierz jednostkowa, a $|\psi\rangle$ to stan równej superpozycji. Kombinacja oracle i operatora dyfuzji jest stosowana w przybliżeniu $\sqrt{N}$ razy, aby uzyskać maksymalne prawdopodobieństwo pomiaru oznaczonego stanu.

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 Przykład wyszukiwania Grovera dla 2 kubitów.

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 Eksperyment z symulatorami

Krok 3: Wykonanie obwodu.

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: Przetwarzanie końcowe wyników.

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Otrzymaliśmy poprawną odpowiedź $|01\rangle$. Uwaga: należy zwrócić uwagę na kolejność kubitów

3. Eksperyment na prawdziwych urządzeniach

Krok 2: Optymalizacja pod kątem docelowego sprzętu

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)

Dzięki transpilacji obwód został przekonwertowany na obwód wykorzystujący natywne bramki bazowe urządzenia.

Krok 3: Wykonanie obwodu.

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: Przetwarzanie końcowe wyników.

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

4. 3-kubitowe wyszukiwanie Grovera

Teraz wypróbujmy przykład 3-kubitowego wyszukiwania Grovera.

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

Tym razem $|111\rangle$ jest stanem „dobrym”.

# 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$ jest obserwowane z największym prawdopodobieństwem, zgodnie z oczekiwaniami. Zauważ, że dwie iteracje są w tym przypadku optymalne. Jednak prawdopodobieństwo uzyskania poprawnej odpowiedzi nie wynosi 100%, co jest typowe dla wyszukiwania Grovera.

Co się stanie, jeśli wykonamy 3 iteracje?

Teraz spróbujmy wykonać 3 iteracje.

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$ jest nadal obserwowane z największym prawdopodobieństwem, choć prawdopodobieństwo uzyskania poprawnej odpowiedzi nieco spadło.

A co z 4 iteracjami?

Teraz spróbujmy wykonać 4 iteracje.

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$ jest obserwowany z najmniejszym prawdopodobieństwem, a prawdopodobieństwo uzyskania poprawnej odpowiedzi jeszcze bardziej spadło. To pokazuje, jak ważny jest wybór optymalnej liczby iteracji w algorytmie Grovera, aby uzyskać najlepsze wyniki.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'