Algorithm ni Grover

Tinatayang paggamit: wala pang isang minuto sa isang Eagle r3 processor (TANDAAN: Ito ay isang tantiya lamang. Maaaring mag-iba ang iyong runtime.)

Mga resulta ng pagkatuto

Pagkatapos makumpleto ang tutorial na ito, maaari mong asahang maunawaan ang sumusunod na impormasyon:

• Kung paano bumuo ng mga Grover oracle na nagmamarka ng isa o higit pang computational basis states
• Kung paano gamitin ang function na grover_operator() mula sa Qiskit circuit library
• Kung paano matukoy ang optimal na bilang ng mga Grover iteration para sa isang partikular na problema
• Kung paano ipatupad ang algorithm ni Grover gamit ang Qiskit Runtime Sampler primitive

Mga kinakailangan

Inirerekomenda na pamilyarisado ka sa mga paksang ito:

• Mga pangunahing kaalaman sa quantum algorithms: algorithm ni Grover
• Mga pangunahing kaalaman sa quantum information

Background

Ang amplitude amplification ay isang pangkalahatang-layuning quantum algorithm, o subroutine, na maaaring gamitin upang makakuha ng quadratic speedup sa ilang classical algorithms. Ang algorithm ni Grover ang unang nagpakita ng speedup na ito sa mga unstructured search problems. Ang pagbuo ng Grover's search problem ay nangangailangan ng oracle function na nagmamarka ng isa o higit pang computational basis states bilang mga states na interesado tayong hanapin, at ng amplification circuit na nagpapataas ng amplitude ng mga markadong states, at dahil dito ay pinipigilan ang natitirang mga states.

Dito, ipapakita natin kung paano bumuo ng mga Grover oracle at gamitin ang grover_operator() mula sa Qiskit circuit library upang madaling mag-set up ng Grover's search instance. Ang runtime Sampler primitive ay nagbibigay-daan sa walang-sagabal na pagpapatupad ng mga Grover circuit.

Requirements

Bago magsimula sa tutorial na ito, siguraduhing mayroon kayong mga sumusunod na naka-install:

• Qiskit SDK v2.0 o mas bago, kasama ang suporta sa visualization
• Qiskit Runtime v0.22 o mas bago (pip install qiskit-ibm-runtime)

Setup

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib 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

Halimbawa sa maliit na sukat na simulator

Sa seksyong ito, tatahak tayo sa bawat hakbang ng algorithm ni Grover sa maliit na sukat gamit ang isang lokal na simulator, bago patakbuhin ang parehong problema sa tunay na quantum hardware.

Hakbang 1: I-map ang mga klasikal na input sa isang quantum na problema

Ang algorithm ni Grover ay nangangailangan ng oracle na tumutukoy ng isa o higit pang markadong computational basis states, kung saan ang "markado" ay nangangahulugang isang state na may phase na -1. Ang controlled-Z gate, o ang multi-controlled generalization nito sa $N$ qubits, ay nagmamarka ng $2^{N}-1$ state ('1'*$N$ bit-string). Ang pagmamarka ng mga basis state na may isa o higit pang '0' sa binary representation ay nangangailangan ng paglalapat ng mga X-gate sa mga kaukulang qubit bago at pagkatapos ng controlled-Z gate, na katumbas ng pagkakaroon ng open-control sa qubit na iyon. Sa sumusunod na code, tinutukoy natin ang isang oracle na nagmamarka ng isa o higit pang input basis states na tinukoy sa pamamagitan ng kanilang bitstring representation. Ang MCMT gate ay ginagamit upang ipatupad ang multi-controlled Z-gate.

Specific Grover's instance

Ngayong mayroon na tayong oracle function, maaari na tayong tumukoy ng isang partikular na instance ng Grover search. Sa halimbawang ito, markahan natin ang dalawang computational states sa walong magagamit sa three-qubit computational space:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Grover operator

Ang built-in Qiskit grover_operator() ay tumatanggap ng oracle circuit at nagbabalik ng circuit na binubuo ng oracle circuit mismo at ng circuit na nagpapalakas ng mga states na minarkahan ng oracle. Dito, ginagamit natin ang decompose() method ng circuit upang makita ang mga gate sa loob ng operator:

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

Ang paulit-ulit na paggamit ng grover_op circuit na ito ay nagpapalakas sa mga markadong states, na ginagawa silang pinakamalamang na mga bit-string sa output distribution mula sa circuit. Mayroong optimal na bilang ng mga application na ito na tinutukoy ng ratio ng mga markadong states sa kabuuang bilang ng posibleng computational states:

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

Full Grover circuit

Ang isang kumpletong Grover experiment ay nagsisimula sa Hadamard gate sa bawat qubit; lumilikha ng pantay na superposition ng lahat ng computational basis states, na sinusundan ng Grover operator (grover_op) na inuulit ng optimal na bilang ng beses. Dito ay ginagamit natin ang QuantumCircuit.power(INT) method upang paulit-ulit na ilapat ang Grover operator.

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

Hakbang 2: I-optimize ang problema para sa pagpapatupad sa quantum hardware

Para sa maliit na sukat na simulation, tina-transpile natin ang circuit nang hindi nagta-target ng partikular na hardware.

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Hakbang 3: Ipatupad gamit ang mga Qiskit primitive

Ang amplitude amplification ay isang sampling problem na angkop para sa pagpapatupad gamit ang SamplerV2 primitive. Dito ay ginagamit natin ang StatevectorSampler mula sa qiskit.primitives para sa lokal na simulation.

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

Hakbang 4: I-post-process at ibalik ang resulta sa nais na klasikal na format

plot_distribution(dist)

Halimbawa sa hardware

Mga Hakbang 1-4

Ang algorithm ni Grover ay isang fault-tolerant na algorithm sa panimula — ang mga multi-controlled Z gate sa puso ng oracle at diffusion operator ay humahantong sa mga two-qubit gate depth na mabilis na lumalaki kasabay ng bilang ng mga qubit (tulad ng ipapakita natin sa susunod na seksyon). Nangangahulugan ito na hindi maganda ang scaling ng algorithm sa kasalukuyang maingay na hardware. Dahil dito, ipinapakita natin ang pagpapatupad sa hardware sa parehong maliit na sukat tulad ng halimbawa sa simulator sa itaas, sa halip na sumubok ng mas malaking sukat ng problema.

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

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

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Talakayan: Scaling ng two-qubit gate depth

Isang pangunahing dahilan kung bakit ang algorithm ni Grover ay itinuturing na fault-tolerant na algorithm ay ang mabilis na paglaki ng two-qubit gate depth ng circuit habang tumataas ang bilang ng mga qubit. Ang multi-controlled Z gate sa puso ng parehong oracle at diffusion operator ay nagsasagawa ng bilang ng mga two-qubit gate na lumalaki nang exponentially kasabay ng bilang ng mga control qubit. Kasama ang katotohanang ang optimal na bilang ng mga Grover iteration mismo ay lumalaki bilang $O(\sqrt{2^n})$, ang kabuuang two-qubit depth ay mabilis na nagiging hindi praktikal para sa maingay na hardware.

Sa ibaba, binubuo natin ang mga Grover circuit para sa dumaraming bilang ng mga qubit, tina-transpile ang mga ito, at itinatala ang resultang two-qubit gate depth upang mailarawan ang scaling na ito.

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()

n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Tulad ng ipinakikita ng plot, ang two-qubit gate depth ay lumalaki nang napakabilis kasabay ng bilang ng mga qubit — halos exponentially. Dahil dito, ang algorithm ni Grover ay hindi praktikal sa kasalukuyang maingay na quantum hardware higit sa napakaliit na sukat ng problema. Ang algorithm ay nananatiling mahalagang target para sa mga susunod na fault-tolerant na quantum computer, kung saan ang error correction ay magbibigay-daan sa malalim na mga circuit na maipatupad nang maaasahan.

Mga susunod na hakbang

Mga rekomendasyon

Kung nakahanap ka ng interes dito, maaaring interesado ka sa sumusunod na materyal:

• Qiskit circuit library: grover_operator() API reference
• Ang QAOA tutorial at utility-scale QAOA lesson ay nagbibigay ng mga near-term na halimbawa ng optimization gamit ang mga quantum computer
• Para sa mas malalim na pagtingin sa mga near-term na algorithm, tingnan ang kursong Quantum computing in practice