Grovers Algorithmus

Nutzungsschätzung: unter einer Minute aufm Eagle r3-Prozessor (HINWEIS: Des is nur a Schätzung. Deine Laufzeit kann anders sein.)

Hintergrund

Amplitudenverstärkung is a universeller Quantenalgorithmus oder a Unterroutine, die ma verwenden kann, um a quadratische Beschleunigung gegenüber a Handvoll klassische Algorithmen zu erreichen. Grovers Algorithmus war der erste, der diese Beschleunigung bei unstrukturierten Suchproblemen g'zeigt hat. Zum a Groversches Suchproblem zu formulieren braucht ma a Orakelfunktion, die einen oder mehrere Basiszustände als die Zustände markiert, die ma finden will, und an Verstärkungsschaltkreis, der die Amplitude von de markierten Zuständen erhöht und damit die übrigen Zustände unterdrückt.

Hier zeigen ma, wie ma Grover-Orakel baut und den grover_operator() aus der Qiskit-Schaltkreisbibliothek verwendet, um einfach a Groversche Suchinstanz aufzusetzen. Des Runtime Sampler-Primitiv ermöglicht die nahtlose Ausführung von Grover-Schaltkreisen.

Anforderungen

Bevor du mit dem Tutorial anfängst, schau dass du des Folgende installiert hast:

• Qiskit SDK v1.4 oder neuer, mit visualization-Unterstützung
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 oder neuer

Setup

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Imports from Qiskit Runtime
from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bit-string to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bit-string
        zero_inds = [
            ind
            for ind in range(num_qubits)
            if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bit-string has a '0' entry
        if zero_inds:
            qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        if zero_inds:
            qc.x(zero_inds)
    return qc

Schritt 1: Klassische Eingaben auf a Quantenproblem abbilden

Grovers Algorithmus braucht a Orakel, des einen oder mehrere markierte Basiszustände spezifiziert, wobei "markiert" an Zustand mit a Phase von -1 bedeutet. A Controlled-Z-Gate, oder seine mehrfach kontrollierte Verallgemeinerung über $N$ Qubits, markiert den $2^{N}-1$-Zustand ('1'*$N$ Bit-String). Zum Basiszustände zu markieren mit einem oder mehreren '0' in der binären Darstellung muss ma X-Gates auf die entsprechenden Qubits vor und nach dem Controlled-Z-Gate anwenden; des entspricht a offenen Kontrolle auf dem Qubit. Im folgenden Code definieren ma a Orakel, des genau des macht und einen oder mehrere Eingabe-Basiszustände markiert, die durch ihre Bit-String-Darstellung definiert san. Des MCMT-Gate wird verwendet, um des mehrfach kontrollierte Z-Gate zu implementieren.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

Spezifische Grover-Instanz

Jetzt wo ma die Orakelfunktion haben, können ma a spezifische Instanz von der Groverschen Suche definieren. In dem Beispiel wollen ma zwei Berechnungszustände aus de acht verfügbaren in am Drei-Qubit-Berechnungsraum markieren:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Grover-Operator

Der eingebaute Qiskit grover_operator() nimmt an Orakel-Schaltkreis und gibt an Schaltkreis zurück, der aus dem Orakel-Schaltkreis selber und am Schaltkreis besteht, der die vom Orakel markierten Zustände verstärkt. Hier verwenden ma die decompose()-Methode vom Schaltkreis, um die Gates innerhalb vom Operator zu sehen:

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Wiederholte Anwendungen von dem grover_op-Schaltkreis verstärken die markierten Zustände und machen's zu de wahrscheinlichsten Bit-Strings in der Ausgabeverteilung vom Schaltkreis. Es gibt a optimale Anzahl von solchen Anwendungen, die durch des Verhältnis von markierten Zuständen zur Gesamtzahl möglicher Berechnungszustände bestimmt wird:

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

Vollständiger Grover-Schaltkreis

A vollständiges Grover-Experiment fängt an mit am Hadamard-Gate auf jedem Qubit; des erzeugt a gleichmäßige Überlagerung von allen Berechnungsbasiszuständen, gefolgt vom Grover-Operator (grover_op), der die optimale Anzahl Mal wiederholt wird. Hier verwenden ma die QuantumCircuit.power(INT)-Methode, um den Grover-Operator wiederholt anzuwenden.

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

Schritt 2: Problem für die Ausführung auf Quantenhardware optimieren

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Schritt 3: Mit Qiskit-Primitiven ausführen

Amplitudenverstärkung is a Sampling-Problem, des für die Ausführung mit dem Sampler-Runtime-Primitiv geeignet is.

Merk dir, dass die run()-Methode vom Qiskit Runtime SamplerV2 a Iterable von primitive unified blocks (PUBs) akzeptiert. Für den Sampler is jedes PUB a Iterable im Format (circuit, parameter_values). Mindestens muss ma aber a Liste von Quantenschaltkreis(en) übergeben.

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Schritt 4: Nachbearbeitung und Rückgabe vom Ergebnis im gwünschten klassischen Format

plot_distribution(dist)

Tutorial-Umfrage

Bitte nimm an dieser kurzen Umfrage teil, um Feedback zu dem Tutorial zu geben. Deine Erkenntnisse helfen uns, unsere Inhaltsangebote und Benutzererfahrung zu verbessern.

Link zur Umfrage