Grover sien Algorithmus

Bruuktied-Schattung: ünner een Minuut op'n Eagle r3-Prozessor (HENWIES: Dat is blots 'ne Schattung. Dien Looptied kann annersweg wesen.)

Achtergrund

Amplitudenverstärken is een allgemene Quantenalgorithmus oder Ünnerprogramm, dat wi bruken köönt, üm 'ne quadratische Versnellung gegen 'ne Handvull klassische Algorithmen to kriegen. Grover sien Algorithmus weer de eerste, de disse Versnellung bi unstruktureerde Sökproblemen wiest hett. För 'n Grovers Sökprobleem to formuleren bruukt wi 'ne Orakelfunkschoon, de een oder mehr Basistoständ as de Toständ markeert, de wi finnen wüllt, un 'n Verstärkenssschaltkreis, de de Amplitude vun de markeerde Toständ verhögt un dormit de övrigen Toständ ünnerdrückt.

Hier wiesen wi, wo wi Grover-Orakels bugen un den grover_operator() ut de Qiskit-Schaltkreisbibliothek bruken, üm eenfach 'ne Groversche Sökinstanz optosetten. Dat Runtime Sampler-Primitiv maakt dat mööglich, Grover-Schaltkresen nahtlos uttofören.

Vörderumsetten

Bevör du mit dit Tutorial anfängst, sorg dorfför, dat du dit folgende installeert hest:

• Qiskit SDK v1.4 oder neger, mit visualization-Ünnerstütten
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 oder neger

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 Ingaven op 'n Quantenprobleem afbilden

Grover sien Algorithmus bruukt 'n Orakel, dat een oder mehr markeerde Basistoständ spezifizeert, wobei "markeert" 'n Tostand mit 'ne Phase vun -1 bedüdden deit. 'n Controlled-Z-Gate, oder sien mehrfach kontrolleerde Verallgemenerung över $N$ Qubits, markeert den $2^{N}-1$-Tostand ('1'*$N$ Bit-String). För Basistoständ to markeren mit een oder mehr '0' in de binäre Dorstellen mutt wi X-Gates op de entspreken Qubits vör un na dat Controlled-Z-Gate anwennen; dat entspreekt 'ne apene Kontroll op dit Qubit. In'n folgenden Code defineren wi 'n Orakel, dat genau dat deit un een oder mehr Ingaven-Basistoständ markeert, de dörch ehr Bit-String-Dorstellen defeneert sünd. Dat MCMT-Gate warrt bruukt, üm dat mehrfach kontrolleerde Z-Gate to implementeren.

# 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 wi de Orakelfunkschoon hebbt, köönt wi 'ne spezifische Instanz vun de Groverschen Sök defineren. In dit Bispeel wüllt wi twee Rekentoständ ut de acht verfögbaren in 'n Dree-Qubit-Rekenruum markeren:

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

De inbugde Qiskit grover_operator() nimmt 'n Orakel-Schaltkreis un gifft 'n Schaltkreis trüch, de ut den Orakel-Schaltkreis sülvst un 'n Schaltkreis bestaht, de de vun't Orakel markeerde Toständ verstärkt. Hier bruken wi de decompose()-Methode vun'n Schaltkreis, üm de Gates binnen den Operator to sehn:

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

Wedderhoolte Anwennen vun dissen grover_op-Schaltkreis verstärkt de markeerde Toständ un maakt se to de wahrschienlichsten Bit-Strings in de Utgavenverdeelen vun'n Schaltkreis. Dat gifft 'ne optimale Antall vun sokke Anwennen, de dörch dat Verhältnis vun markeerde Toständ to de Gesamtantall mööglich Rekentoständ bestimmt warrt:

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

Vullstännig Grover-Schaltkreis

'n Vullstännig Grover-Experiment fängt an mit 'n Hadamard-Gate op jeed Qubit; dat maakt 'ne gliekeförmige Överlagerung vun all Rekenbasistoständ, folgt vun'n Grover-Operator (grover_op), de de optimale Antall Maal wedderholt warrt. Hier bruken wi de QuantumCircuit.power(INT)-Methode, üm den Grover-Operator wedderholt antowennen.

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: Probleem för de Utfören op Quantenhardware optimeren

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 utfören

Amplitudenverstärken is 'n Sampling-Probleem, dat för de Utfören mit den Sampler-Runtime-Primitiv egnet is.

Merk di, dat de run()-Methode vun't Qiskit Runtime SamplerV2 'n Iterable vun primitive unified blocks (PUBs) akzepteert. För den Sampler is jedes PUB 'n Iterable in't Format (circuit, parameter_values). Mindestens mutt wi aver 'ne List vun Quantenschaltkreis(en) övergeven.

# 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: Nabearbeiten un Trüchgaav vun't Resultaat in't wünschte klassische Format

plot_distribution(dist)

Tutorial-Ümfraag

Bitte maak bi disse korte Ümfraag mit, üm Feedback to dit Tutorial to geven. Dien Erkenntnissen helpt uns, unse Inholten un Brukerfarung to verbettern.

Link to de Ümfraag