Grovers Algorithmus

Nutzungsschätzung: unter ana Minute auf am Eagle r3-Prozessor (HINWEIS: Des is nur a Schätzung. Ihri Laufzeit ko variirn.)

Hintergrund

Amplitudenverstärkung is a universeller Quantenalgorithmus oder a Unterroutine, de mia verwenda kenna, um a quadratische Beschleunigung gegenüber ana Handvoll klassischer Algorithmen z'erzieln. Grovers Algorithmus war da Erschte, wo diese Beschleunigung bei unstrukturierten Suchproblemen demonstriert hod. D'Formulierung von am Groverschen Suchproblem erfordert a Orakelfunktion, de oana oder mehrere Basiszuständ als de Zuständ markiert, wo mia findn woin, und an Verstärkungsschaltkreis, de d'Amplitude von de markierten Zuständ erhöht und folglich de verbleibenden Zuständ unterdrückt.

Do zeign mia, wia mia Grover-Orakel konstruiern und den grover_operator() aus da Qiskit-Schaltkreisbibliothek verwendn, um einfach a Groversche Suchinstanz einzurichtn. Des Runtime Sampler-Primitiv ermöglicht de nahtlose Ausführung von Grover-Schaltkreisen.

Anforderungen

Schau vor'm Anfanga von diesem Tutorial, dass mia des Folgende installierd ham:

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

Setup

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# 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 abbildn

Grovers Algorithmus braucht a Orakel, de oana oder mehrere markierte Basiszuständ spezifiziert, wobei "markiert" an Zustand mit ana Phase von -1 bedeutet. A Controlled-Z-Gate oder sei mehrfach kontrollierte Verallgemeinerung über $N$ Qubits markiert de $2^{N}-1$-Zustand ('1'*$N$ Bit-String). Des Markiern von Basiszuständen mit oam oder mehreren '0' in da binären Darstellung erfordert des Anwendn von X-Gates auf de entsprechenden Qubits vor und nach'm Controlled-Z-Gate; des entspricht ana offenen Kontrolle auf diesem Qubit. Im nachfolgnden Code definiern mia a Orakel, de genau des macht und oana oder mehrere Eingabe-Basiszuständ markiert, de durch ihre Bit-String-Darstellung definiert san. Des MCMT-Gate wird verwendt, um des mehrfach kontrollierte Z-Gate z'implementiern.

# 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

Weil mia jetzt d'Orakelfunktion ham, kenna mia a spezifische Instanz von da Groverschen Suche definiern. In diesem Beispü wern mia zwoa Berechnungszuständ aus de acht verfügbarn in am Drei-Qubit-Berechnungsraum markiern:

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

Da eingebaute Qiskit grover_operator() nimmt an Orakel-Schaltkreis entgegn und gibt an Schaltkreis zruck, wo aus'm Orakel-Schaltkreis selber und am Schaltkreis besteht, de de vom Orakel markierten Zuständ verstärkt. Do verwendn mia d'decompose()-Methode von dem Schaltkreis, um de Gates innerhalb vom Operator z'segn:

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

Wiederholte Anwendungen von diesem grover_op-Schaltkreis verstärkn de markierten Zuständ und machns zu de wahrscheinlichsten Bit-Strings in da Ausgabeverteilung von dem Schaltkreis. Es gibt a optimale Anzahl solcher Anwendungen, de durch des Verhältnis von markierten Zuständen zur Gesamtzahl möglicher Berechnungszuständ 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 fangt mit am Hadamard-Gate auf jedem Qubit oo; des erzeugt a gleichmäßige Überlagerung aller Berechnungsbasisstände, gefolgt vom Grover-Operator (grover_op), de d'optimale Anzahl von Moi widderholt wird. Do verwendn mia d'QuantumCircuit.power(INT)-Methode, um de Grover-Operator wiederholt anzwendn.

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 d'Ausführung auf Quantenhardware optimiern

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: Ausführn mit Qiskit-Primitiven

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

Beachts, dass d'run()-Methode vom Qiskit Runtime SamplerV2 a Iterable von primitive unified blocks (PUBs) akzeptiert. Für de Sampler is jedes PUB a Iterable im Format (circuit, parameter_values). Mindestens akzeptiert er aber a Listn von Quantenschaltkreis(en).

# 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ünschtn klassischen Format

plot_distribution(dist)

Tutorial-Umfrage

Bitte nehmt's an dieser kurzen Umfrage teil, um Feedback zu diesem Tutorial z'gebm. Eure Erkenntnisse helfn uns, unsere Inhaltsangebote und Benutzererfahrung z'verbessern.

Link zur Umfrage