Quantenalgorithmen: Grover-Suche und Anwendungen

hinweis

Atsushi Matsuo (10. Mai 2024)

Das PDF herunterladen der ursprünglichen Vorlesung. Beachte, dass einige Code-Ausschnitte veraltet sein könnten, da es sich um statische Bilder handelt.

Die ungefähre QPU-Zeit für dieses Experiment beträgt 2 Sekunden.

1. Einführung in den Grover-Algorithmus

Dieses Notebook ist das vierte in einer Reihe von Vorlesungen über den Weg zur Praxistauglichkeit im Quantencomputing. In diesem Notebook lernen wir den Grover-Algorithmus kennen.

Der Grover-Algorithmus ist einer der bekanntesten Quantenalgorithmen aufgrund seiner quadratischen Beschleunigung gegenüber klassischen Suchmethoden. Beim klassischen Rechnen erfordert die Suche in einer unsortierten Datenbank mit $N$ Einträgen eine Zeitkomplexität von $O(N)$, was bedeutet, dass man im schlimmsten Fall jeden Eintrag einzeln untersuchen muss. Der Grover-Algorithmus ermöglicht es uns jedoch, diese Suche in $O(\sqrt{N})$ Zeit durchzuführen, indem er sich die Prinzipien der Quantenmechanik zunutze macht, um das Zielelement effizienter zu finden.

Der Algorithmus nutzt Amplitudenverstärkung, einen Prozess, der die Wahrscheinlichkeitsamplitude des korrekten Antwortzustands in einer Quantenüberlagerung erhöht, sodass er mit höherer Wahrscheinlichkeit gemessen werden kann. Diese Beschleunigung macht den Grover-Algorithmus in verschiedenen Anwendungen über die einfache Datenbanksuche hinaus wertvoll, insbesondere wenn der Datensatz groß ist. Detaillierte Erklärungen des Algorithmus werden im Grover-Algorithmus-Notebook bereitgestellt.

Die grundlegende Struktur des Grover-Algorithmus

Der Grover-Algorithmus besteht aus vier Hauptkomponenten:

1. Initialisierung: Aufbau der Überlagerung über alle möglichen Zustände.
2. Orakel: Anwenden einer Orakelfunktion, die den Zielzustand durch Invertierung seiner Phase markiert.
3. Diffusionsoperator: Anwenden einer Reihe von Operationen zur Verstärkung der Wahrscheinlichkeit des markierten Zustands.

Jeder dieser Schritte spielt eine entscheidende Rolle dabei, den Algorithmus effizient funktionieren zu lassen. Detaillierte Erklärungen für jeden Schritt werden später gegeben.

2. Implementierung des Grover-Algorithmus

2.1 Vorbereitung

Importiere die notwendigen Bibliotheken und richte die Umgebung für die Ausführung des Quantum Circuits ein.

# 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

Schritt 1: Problem auf Quantum Circuits und Operatoren abbilden

Betrachte eine Liste von 4 Elementen, bei der unser Ziel darin besteht, den Index eines Elements zu identifizieren, das eine bestimmte Bedingung erfüllt. Zum Beispiel möchten wir den Index des Elements finden, das gleich 2 ist. In diesem Beispiel stellt der Quantenzustand $|01\rangle$ den Index des Elements dar, der diese Bedingung erfüllt, da er auf die Position zeigt, an der sich der Wert 2 befindet.

Schritt 2: Für Zielhardware optimieren

1: Initialisierung

Im Initialisierungsschritt erstellen wir eine Überlagerung aller möglichen Zustände. Dies wird erreicht, indem ein Hadamard Gate auf jedes Qubit in einem n-Qubit-Register angewendet wird, was zu einer gleichmäßigen Überlagerung von $2^n$ Zuständen führt. Mathematisch lässt sich dies darstellen als:

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

wobei $N = 2^n$ die Gesamtzahl der möglichen Zustände ist. Wir ändern auch den Zustand des Hilfs-Qubits zu $|-\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: Orakel

Das Orakel ist ein zentraler Bestandteil des Grover-Algorithmus. Es markiert den Zielzustand, indem es eine Phasenverschiebung anwendet, typischerweise durch das Invertieren des Vorzeichens der dem Zustand zugeordneten Amplitude. Das Orakel ist oft problemspezifisch und wird basierend auf den Kriterien zur Identifizierung des Zielzustands konstruiert. In mathematischen Begriffen wendet das Orakel die folgende Transformation an:

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

Diese Phaseinvertierung wird durch das Anwenden eines negativen Vorzeichens auf die Amplitude des Zielzustands über Phasen-Kickback erreicht.

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: Diffusionsoperator

Der Amplitudenverstärkungsprozess ist das, was den Grover-Algorithmus von einer klassischen Suche unterscheidet. Nachdem das Orakel den Zielzustand markiert hat, wenden wir eine Reihe von Operationen an, die die Amplitude dieses markierten Zustands erhöhen und seine Beobachtung bei der Messung wahrscheinlicher machen. Dieser Prozess wird durch den Diffusionsoperator erreicht, der effektiv eine Invertierung um die durchschnittliche Amplitude durchführt. Die mathematische Operation lautet:

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

wobei $D$ der Diffusionsoperator ist, $I$ die Identitätsmatrix und $|\psi\rangle$ der gleichmäßige Überlagerungszustand. Die Kombination aus Orakel und Diffusionsoperator wird ungefähr $\sqrt{N}$ Mal angewendet, um die maximale Wahrscheinlichkeit für die Messung des markierten Zustands zu erreichen.

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 Ein 2-Qubit-Grover-Suchbeispiel

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 mit Simulatoren

Schritt 3: Ausführen des Circuits

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

Schritt 4: Nachverarbeitung der Ergebnisse

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Wir haben die richtige Antwort $|01\rangle$ erhalten. Beachte dabei die Reihenfolge der Qubits.

3. Experiment mit echten Geräten

Schritt 2: Für Zielhardware optimieren

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)

Durch das Transpilieren des Circuits wurde er in einen Circuit mit den nativen Basis-Gates des Geräts umgewandelt.

Schritt 3: Ausführen des Circuits

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}

Schritt 4: Nachverarbeitung der Ergebnisse

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

4. Eine 3-Qubit-Grover-Suche

Lass uns jetzt ein 3-Qubit-Grover-Suchbeispiel ausprobieren.

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

Diesmal ist $|111\rangle$ der „gute" Zustand.

# 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$ wird wie erwartet mit der höchsten Wahrscheinlichkeit beobachtet. Beachte, dass zwei Iterationen in diesem Fall optimal sind. Die Wahrscheinlichkeit, die richtige Antwort zu erhalten, beträgt jedoch nicht 100 %, was bei der Grover-Suche üblich ist.

Was passiert, wenn wir 3 Mal iterieren?

Lass uns jetzt 3 Iterationen ausprobieren.

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$ wird weiterhin mit der höchsten Wahrscheinlichkeit beobachtet, obwohl die Wahrscheinlichkeit, die richtige Antwort zu erhalten, leicht abgenommen hat.

Wie sieht es bei 4 Iterationen aus?

Lass uns jetzt 4 Iterationen ausprobieren.

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$ wird mit der niedrigsten Wahrscheinlichkeit beobachtet, und die Wahrscheinlichkeit, die richtige Antwort zu erhalten, hat weiter abgenommen. Dies verdeutlicht, wie wichtig es ist, die optimale Anzahl von Iterationen für den Grover-Algorithmus zu wählen, um die besten Ergebnisse zu erzielen.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'