Der Grover sing Algorithmus

Nutzungsschätzung: unger ener Menutt op nem Eagle r3-Prozessor (HENWIES: Dat es nur en Schätzung. Ding Laufzick künnt andersch sin.)

Hintergrund

Amplitudeverstärkung es ene universelle Quantealgorithmus oder Ungerroutine, die mer bruche künne, öm quadratisch schneller ze sin wie e paar klassische Algorithme. Der Grover sing Algorithmus wor dä eeschte, dä dat för unstrukturierte Sochprobläme jezeich hät. För e Groversches Sochprobleem ze formuliere bruchs de en Orakelfunktion, die ein oder mih Basiszostände als de Zostände markeet, die mer finge welle, un ne Verstärkungsschaltkreis, dä de Amplitude vun de markeete Zostände erhöht un domet de övvrige Zostände ungerdröck.

Hee zeije mer, wie mer Grover-Orakel baue un der grover_operator() us dä Qiskit-Schaltkreisbibliothek bruche, öm e Groversches Sochinstanz einfach opzesetze. Dat Runtime Sampler-Primitiv maht et möjlich, Grover-Schaltkreise nahtlos uszföhre.

Aanforderunge

Bevör de met däm Tutorial aanfängks, sörch doför, dat de dat Follgende installeert häss:

• Qiskit SDK v1.4 oder neuer, met visualization-Ungerstö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

Schredd 1: Klassische Ingabe op e Quanteprobleem avbilde

Der Grover sing Algorithmus bruch en Orakel, dat ein oder mih markeete Basiszostände spezifizeert, wobei "markeert" ne Zostand met ener Phase vun -1 bedügg. E Controlled-Z-Gate, oder sing mihrfach kontrollierte Verallgemeinung övver $N$ Qubits, markeet dä $2^{N}-1$-Zostand ('1'*$N$ Bit-String). För Basiszostände ze markeere met einem oder mih '0' en dä binäre Dostellung moss mer X-Gates op de entsprechende Qubits vör un noh däm Controlled-Z-Gate anwende; dat entsprech ener offene Kontroll op däm Qubit. Em follgende Code definiere mer en Orakel, dat jenau dat maht un ein oder mih Ingabe-Basiszostände markeet, die dörch ehr Bit-String-Dostellung defeneert sin. Dat MCMT-Gate weed jebruch, öm dat mihrfach kontrollierte Z-Gate ze implementeere.

# 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 dat mer de Orakelfunktion han, künne mer en spezifische Instanz vun dä Groverschen Soch definiere. En däm Beispill welle mer zwee Berächnungszostände us de aat verfögbare en nem Drei-Qubit-Berächnungsruum markeere:

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

Dä enjebaute Qiskit grover_operator() nemmp ne Orakel-Schaltkreis un jitt ne Schaltkreis retuur, dä us däm Orakel-Schaltkreis selver un nem Schaltkreis besteiht, dä de vum Orakel markeete Zostände verstärk. Hee bruche mer de decompose()-Methode vum Schaltkreis, öm de Gates benne em Operator ze sinn:

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

Widderholte Aanwendunge vun däm grover_op-Schaltkreis verstärke de markeete Zostände un maache se zo de wahrscheinlichste Bit-Strings en dä Ußgabeverdeijung vum Schaltkreis. Et jitt en optimale Aanzahl vun su Aanwendunge, die dörch dat Verhältnis vun markeete Zostände zor Jesamtzahl müjlicher Berächnungszostände bestemmp weed:

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

Vollständije Grover-Schaltkreis

E vollständije Grover-Experiment fängk aan met nem Hadamard-Gate op jedem Qubit; dat erzügg en jlieche Övverlaajerung vun alle Berächnungsbasiszostände, jefolg vum Grover-Operator (grover_op), dä de optimale Aanzahl Mol widderhollt weed. Hee bruche mer de QuantumCircuit.power(INT)-Methode, öm dä Grover-Operator widderhollt aanzeweende.

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

Schredd 2: Probleem för de Ußföhrung op Quantehardware optimiere

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

Schredd 3: Met Qiskit-Primitive ußföhre

Amplitudeverstärkung es e Sampling-Probleem, dat för de Ußföhrung met däm Sampler-Runtime-Primitiv jeeiggnet es.

Merk der, dat de run()-Methode vum Qiskit Runtime SamplerV2 en Iterable vun primitive unified blocks (PUBs) akzepteert. För dä Sampler es jedes PUB en Iterable em Format (circuit, parameter_values). Mer moss mindestens ävver en Leß vun Quanteschaltkreis(en) üvverjävve.

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

Schredd 4: Nohbeärbeitung un Retuurjaab vum Erjebbnis em jewönschte klassische Format

plot_distribution(dist)

Tutorial-Ömfrooch

Bess esu jot un maach bei dä kooze Ömfrooch met, öm Feedback zo däm Tutorial ze jävve. Ding Erkenntnisse helfe uns, unsere Inhalte un Benutzerfahrung ze verbessere.

Link zor Ömfrooch