Grovers Algorithmus

Nutzungsschätzung: unter eene Minute uffn Eagle r3-Prozessor (HINWEIS: Dit is nur ne Schätzung. Deine Laufzeit kann anders sein.)

Hintergrund

Amplitudenverstärkung is een alljeemeena Quantealgorithmus oda Unterroutine, die wa nutzen können, um ne quadratische Beschleunigung jejnüba eenem Haufen klassische Algorithmen zu kriegen. Grovers Algorithmus wa da erste, der dit Tempo bei unstrukturierten Suchproblemen jezeicht hat. Um een Groversches Suchproblem zu formulieren braucht wa ne Orakelfunktion, die eenen oda mehrere Basiszustände als die Zustände markiert, die wa finden wollen, un een Verstärkungsschaltkreis, der die Amplitude von de markierten Zuständen erhöht un damit die übrijen Zustände unterdrückt.

Hier zeejen wa, wie wa Grover-Orakel bauen un den grover_operator() aus da Qiskit-Schaltkreisbibliothek verwenden, um eenfach ne Groversche Suchinstanz ufzusetzen. Det Runtime Sampler-Primitiv ermöglicht die nahtlose Ausführung von Grover-Schaltkreisen.

Anforderungen

Bevor de mit dit Tutorial anfängst, sorje dafür, datte dit Folgende installierthaast:

• Qiskit SDK v1.4 oda neua, mit visualization-Untastützung
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 oda neua

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 uff een Quanteproblem abbilden

Grovers Algorithmus braucht een Orakel, det eenen oda mehrere markierte Basiszustände spezifiziert, wobei "markiert" een Zustand mit eena Phase von -1 bedeutet. Een Controlled-Z-Gate, oda seine mehrfach kontrollierte Veralljeemeinerung üba $N$ Qubits, markiert den $2^{N}-1$-Zustand ('1'*$N$ Bit-String). Um Basiszustände zu markieren mit eenem oda mehreren '0' in da binären Darstellung muss wa X-Gates uff die entsprechenden Qubits vor un nach dit Controlled-Z-Gate anwenden; dit entspricht eena offenen Kontrolle uff dit Qubit. Im folgenden Code definieren wa een Orakel, det jenau dit macht un eenen oda mehrere Eingabe-Basiszustände markiert, die durch ihre Bit-String-Darstellung definiert sind. Dit MCMT-Gate wird verwendet, um dit 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

Nu woa die Orakelfunktion haben, können wa ne spezifische Instanz von da Groverschen Suche definieren. In dit Beispiel wollen wa zwee Berechnungszustände aus de acht verfügbaren in eenem 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

Da einjebaute Qiskit grover_operator() nimmt een Orakel-Schaltkreis un gibt een Schaltkreis zurück, der aus dit Orakel-Schaltkreis selba un eenem Schaltkreis besteht, der die vom Orakel markierten Zustände vastärkt. Hier verwenden wa 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 dit grover_op-Schaltkreis vastärken die markierten Zustände un machen se zu de wahrscheinlichsten Bit-Strings in da Ausgabeverteijung vom Schaltkreis. Et jibt ne optimale Anzahl von solchen Anwendungen, die durch dit Verhältnis von markierten Zuständen zua Jesamtzahl möglicha 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ändja Grover-Schaltkreis

Een vollständja Grover-Experiment fängt an mit eenem Hadamard-Gate uff jedes Qubit; dit erzeugt ne jleichmäßige Überlagerung von allen Berechnungsbasiszuständen, jefolgt vom Grover-Operator (grover_op), der die optimale Anzahl Mal wiederholt wird. Hier verwenden wa 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 uff Quantehardware 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

Amplitudenvastärkung is een Sampling-Problem, det für die Ausführung mit dit Sampler-Runtime-Primitiv jeeignet is.

Merk dia, datte die run()-Methode vom Qiskit Runtime SamplerV2 een Iterable von primitive unified blocks (PUBs) akzeptiert. Für den Sampler is jedes PUB een Iterable im Format (circuit, parameter_values). Mindestens muss wa aba ne 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 un Rückgabe vom Ergebnis im jewünschten klassischen Format

plot_distribution(dist)

Tutorial-Umfrage

Bitte nimm an disa kurzen Umfrage teil, um Feedback zu dit Tutorial zu geben. Deine Erkenntnisse helfen uns, unsre Inhaltsangebote un Benutzererfahrung zu verbessern.

Link zua Umfrage