Grovers Algorithmus

Nutzungsschätzung: unnern ener Minute uffm Eagle r3-Prozessor (HIENWEIS: Das is bloß ne Schätzung. Deine Laufzeid gann annerscher sein.)

Hintergrund

Amplitudeverstärkung is en universeller Quantealgorithmus oodr Unterroutine, die mer bruchen gönne, um ne quadratische Beschleunigung gegenüber ner Handvoll glassische Algorithme zu errreichen. Grovers Algorithmus war der erschde, der die Beschleunigung bei unstrukturierten Suchproblämen gezeigt hadd. Zum en Groversch Suchprobleem zu formuliern brauchd mer ne Oragelfunktion, die eenen oder mehrere Basiszustände als die Zustände margiert, die mer finne wolle, un nen Verstärkungsschaltkreis, der die Amplitude von de margierten Zuständen erhöht un domit die verbleibenden Zustände unnerdrickt.

Hier zeige mer, wie mer Grover-Orakel baun un den grover_operator() aus der Qiskit-Schaltkreisbibliothek verwenden, um eenfach ne Groversche Suchinstanz eenzurichten. Das Runtime Sampler-Primitiv ermöglicht die nahdlose Ausführung von Grover-Schaltkreisen.

Anforderungen

Bevor de mit däm Tutorial anfängst, sorsch dafier, dass de das Folgende installierd hasd:

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

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

Schriet 1: Glassische Eingaben uff en Quanteprobleem abbillen

Grovers Algorithmus brauchd en Orakel, das eenen oodr mehrere margierte Basiszustände spezifiziert, wobei "margiert" en Zustand mit ner Phase von -1 bedeit. En Controlled-Z-Gate, oodr seine mehrfach gontrollierte Verallgemeeinerung über $N$ Qubits, margiert den $2^{N}-1$-Zustand ('1'*$N$ Bit-String). Zum Basiszustände zu margiern mit eeem oodr mehrern '0' in der binären Darstellung muss mer X-Gates uff die entsprechenden Qubits vor un nach däm Controlled-Z-Gate anwenden; das entsprücht ner offenen Gontrolle uff däm Qubit. Im folgenden Code definiern mer en Orakel, das genau das macht un eenen oodr mehrere Eingabe-Basiszustände margiert, die durch ihre Bit-String-Darstellung definiert sind. Das MCMT-Gate werd verwendd, um das mehrfach gontrollierte Z-Gate zu 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

Nu wo mer die Oragelfunktion ham, gönne mer ne spezifische Instanz von der Groverschen Suche definiern. In däm Beispiel wolle mer zwee Berechnungszustände aus de acht verfügbaren in nem Drei-Qubit-Berechnungsraum margiern:

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 eingebauete Qiskit grover_operator() nimmt nen Orakel-Schaltkreis un gibt nen Schaltkreis zurück, der aus däm Orakel-Schaltkreis selbsd un nem Schaltkreis besteht, der die vum Orakel margierten Zustände verstärkd. Hier verwenden mer die decompose()-Methode vum Schaltkreis, um die Gates innerhalb vum Operator zu sehn:

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

Widderhoolte Anwendungen von däm grover_op-Schaltkreis verstärgen die margierten Zustände un machen se zu de wahrscheinlichsten Bit-Strings in der Ausgabeverdeijung vum Schaltkreis. Es gibbd ne optimale Anzahl von solchen Anwendungen, die durch das Verhältnis von margierten Zuständen zur Gesamdzahl müchlicher Berechnungszustände bestimmt werd:

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

Vollständcher Grover-Schaltkreis

En vollständchers Grover-Experiment fängt an mit nem Hadamard-Gate uff jedem Qubit; das errzeigt ne gleichmäßche Überlagerung von allen Berechnungsbasiszuständen, gefolgt vum Grover-Operator (grover_op), der die optimale Anzahl Mal widderholt werd. Hier verwenden mer die QuantumCircuit.power(INT)-Methode, um den Grover-Operator widderholt 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")

Schriet 2: Probleem fer die Ausführung uff Quantehardware 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")

Schriet 3: Mit Qiskit-Primitiven ausführn

Amplitudeverstärkung is en Sampling-Probleem, das fer die Ausführung mit däm Sampler-Runtime-Primitiv geeigend is.

Merg dir, dass die run()-Methode vum Qiskit Runtime SamplerV2 en Iterable von primitive unified blocks (PUBs) agzeptierd. Fer den Sampler is jedes PUB en Iterable im Format (circuit, parameter_values). Mindestens muss mer abber ne Lischte 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()

Schriet 4: Nachbearbeetung un Rückgabe vum Ergebnis im gewünschten glassischen Format

plot_distribution(dist)

Tutorial-Umfrooche

Bidde nemm an dieser gurzen Umfrooche deel, um Feedback zu däm Tutorial zu geben. Deine Ergenndnisse helfen uns, unsere Inhaldsangebote un Benutzererfahrung zu verbessern.

Link zur Umfrooche