Algoritmul lui Grover

Estimare de utilizare: sub un minut pe procesorul Eagle r3 (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Fundal

Amplificarea amplitudinii este un algoritm cuantic de uz general, sau subrutină, care poate fi utilizat pentru a obține o accelerare pătratică față de o serie de algoritmi clasici. Algoritmul lui Grover a fost primul care a demonstrat această accelerare pe probleme de căutare nestructurată. Formularea unei probleme de căutare Grover necesită o funcție oracle care marchează una sau mai multe stări ale bazei computaționale ca fiind stările pe care dorim să le găsim, și un Circuit de amplificare care crește amplitudinea stărilor marcate, suprimând astfel stările rămase.

Aici demonstrăm cum să construiești oracole Grover și să folosești grover_operator() din biblioteca de circuite Qiskit pentru a configura cu ușurință o instanță de căutare Grover. Primitiva runtime Sampler permite execuția fără probleme a circuitelor Grover.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalat următoarele:

• Qiskit SDK v1.4 sau mai recent, cu suport pentru vizualizare
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 sau mai recent

Configurare

# 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

Pasul 1: Mapează intrările clasice la o problemă cuantică

Algoritmul lui Grover necesită un oracle care specifică una sau mai multe stări marcate ale bazei computaționale, unde „marcat" înseamnă o stare cu o fază de -1. Un Gate controlled-Z, sau generalizarea sa multi-controlată peste $N$ Qubiți, marchează starea $2^{N}-1$ ('1'*$N$ bit-string). Marcarea stărilor bazei cu unul sau mai mulți '0' în reprezentarea binară necesită aplicarea X-Gate-urilor pe Qubiții corespunzători înainte și după Gate-ul controlled-Z; echivalent cu a avea un control deschis pe acel Qubit. În codul următor, definim un oracle care face exact asta, marcând una sau mai multe stări ale bazei de intrare definite prin reprezentarea lor ca șir de biți. Gate-ul MCMT este folosit pentru a implementa Gate-ul Z multi-controlat.

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

Instanță specifică Grover

Acum că avem funcția oracle, putem defini o instanță specifică de căutare Grover. În acest exemplu vom marca două stări computaționale din cele opt disponibile într-un spațiu computațional de trei Qubiți:

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

Operatorul Grover

Funcția built-in Qiskit grover_operator() primește un Circuit oracle și returnează un Circuit compus din Circuit-ul oracle însuși și un Circuit care amplifică stările marcate de oracle. Aici folosim metoda decompose() a Circuit-ului pentru a vedea Gate-urile din cadrul operatorului:

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

Aplicările repetate ale acestui Circuit grover_op amplifică stările marcate, făcându-le cele mai probabile șiruri de biți în distribuția de ieșire a Circuit-ului. Există un număr optim de astfel de aplicări, determinat de raportul dintre stările marcate și numărul total de stări computaționale posibile:

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

Circuit Grover complet

Un experiment Grover complet începe cu un Hadamard Gate pe fiecare Qubit; creând o superpoziție uniformă a tuturor stărilor bazei computaționale, urmată de operatorul Grover (grover_op) repetat de numărul optim de ori. Aici folosim metoda QuantumCircuit.power(INT) pentru a aplica în mod repetat operatorul Grover.

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

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

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

Pasul 3: Execuție folosind primitivele Qiskit

Amplificarea amplitudinii este o problemă de eșantionare potrivită pentru execuție cu primitiva runtime Sampler.

Reține că metoda run() a SamplerV2 din Qiskit Runtime primește un iterabil de primitive unified blocks (PUBs). Pentru Sampler, fiecare PUB este un iterabil în formatul (circuit, parameter_values). Cu toate acestea, la minimum, acceptă o listă de Circuit(e) cuantice.

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

Pasul 4: Post-procesare și returnarea rezultatului în formatul clasic dorit

plot_distribution(dist)

Sondaj tutorial

Te rog să completezi acest scurt sondaj pentru a oferi feedback despre acest tutorial. Părerile tale ne vor ajuta să îmbunătățim oferta noastră de conținut și experiența utilizatorilor.

Link către sondaj

Note: This survey is provided by IBM Quantum and relates to the original English content. To give feedback on doQumentation's website, translations, or code execution, please open a GitHub issue.