Groverův algoritmus

Odhadovaná spotřeba: méně než jedna minuta na procesoru Eagle r3 (POZNÁMKA: Jedná se pouze o odhad. Tvůj skutečný čas běhu se může lišit.)

Výsledky učení

• Jak sestavit Groverova orákula, která označují jeden nebo více stavů výpočetní báze

• Jak používat funkci grover_operator() z knihovny Qiskit circuit library

• Jak určit optimální počet Groverových iterací pro daný problém

• Jak spustit Groverův algoritmus pomocí primitiva Sampler od IBM Quantum

Předpoklady

• Základy kvantových algoritmů: Groverův algoritmus

• Základy kvantové informace

Pozadí

Amplifikace amplitudy je kvantový algoritmus obecného účelu neboli podprogram, který lze použít k dosažení kvadratického zrychlení oproti hrstce klasických algoritmů. Groverův algoritmus jako první demonstroval toto zrychlení na nestrukturovaných problémech vyhledávání. Formulace Groverova vyhledávacího problému vyžaduje orákulovou funkci, která označí jeden nebo více stavů výpočetní báze jako stavy, které chceme najít, a zesilovací obvod, který zvyšuje amplitudu označených stavů a potlačuje zbývající stavy.

Zde ukážeme, jak sestavit Groverova orákula a použít grover_operator() z knihovny Qiskit circuit library k snadnému nastavení instance Groverova vyhledávání. Primitivum Sampler z Qiskit Runtime umožňuje bezproblémové spuštění Groverových obvodů.

Požadavky

Před zahájením tohoto tutoriálu se ujisti, že máš nainstalováno následující:

• Qiskit SDK v2.0 nebo novější, s podporou vizualizace

• Qiskit Runtime v0.22 nebo novější (pip install qiskit-ibm-runtime)

Nastavení

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"matplotlib": "matplotlib", "qiskit": "qiskit", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

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

Příklad na malém simulátoru

V této části projdeme každý krok Groverova algoritmu v malém měřítku pomocí lokálního simulátoru, než spustíme stejný problém na skutečném kvantovém hardwaru.

Krok 1: Mapování klasických vstupů na kvantový problém

Groverův algoritmus vyžaduje orákulum, které specifikuje jeden nebo více označených stavů výpočetní báze, přičemž „označený" znamená stav s fází -1. Gate řízené-Z, nebo jeho víceřízené zobecnění na $N$ Qubitů, označuje stav $2^{N}-1$ ('1'*$N$ bitový řetězec). Označení stavů báze s jednou nebo více hodnotami '0' v binární reprezentaci vyžaduje aplikaci Gate X na odpovídající Qubity před a po Gate řízené-Z, což je ekvivalentní otevřenému řízení na daném Qubitu. V následujícím kódu definujeme orákulum, které označuje jeden nebo více vstupních stavů báze definovaných prostřednictvím jejich bitstringové reprezentace. Gate MCMT slouží k implementaci víceřízeného Gate Z.

Konkrétní instance Groverova algoritmu

Nyní, když máme funkci orákula, můžeme definovat konkrétní instanci Groverova vyhledávání. V tomto příkladu označíme dva výpočetní stavy z osmi dostupných v tříqubitovém výpočetním prostoru:

marked_states = ["011", "100"]

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

Groverův operátor

Vestavěná funkce Qiskit grover_operator() přijme obvod orákula a vrátí obvod, který se skládá ze samotného obvodu orákula a obvodu, který amplifikuje stavy označené orákulem. Zde použijeme metodu decompose() na obvod, abychom viděli Gate uvnitř operátoru:

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

Opakované aplikace tohoto obvodu grover_op amplifikují označené stavy, čímž se stanou nejpravděpodobnějšími bitovými řetězci ve výstupním rozdělení z obvodu. Existuje optimální počet takových aplikací, který je určen poměrem označených stavů k celkovému počtu možných výpočetních stavů:

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

Kompletní Groverův obvod

Kompletní Groverův experiment začíná Gate Hadamard na každém qubit; vytváří rovnoměrnou superpozici všech stavů výpočetní báze, následovanou Groverovým operátorem (grover_op) opakovaným optimální počet krát. Zde využíváme metody QuantumCircuit.power(INT) k opakované aplikaci Groverova operátoru.

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

Krok 2: Optimalizace problému pro spuštění na kvantovém hardwaru

Pro simulaci v malém měřítku transpiloujeme obvod bez cílení na konkrétní hardware.

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

Krok 3: Spuštění pomocí primitiv Qiskit

Amplifikace amplitudy je vzorkovací problém vhodný pro spuštění s primitivem SamplerV2. Zde používáme StatevectorSampler z qiskit.primitives pro lokální simulaci.

from qiskit.primitives import StatevectorSampler

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

Krok 4: Zpracování výsledků a vrácení v požadovaném klasickém formátu

plot_distribution(dist)

Příklad na hardwaru

Kroky 1–4

Groverův algoritmus je v zásadě algoritmus určený pro kvantové počítače odolné vůči chybám — víceřízené Gate Z v jádru orákula a difúzního operátoru vedou k hloubkám dvouqubitových Gate, které s počtem Qubitů velmi rychle rostou (jak ukážeme v další části). To znamená, že algoritmus se na dnešním hlučném hardwaru špatně škáluje. Z tohoto důvodu demonstrujeme spuštění na hardwaru ve stejném malém měřítku jako výše uvedený příklad simulátoru, místo abychom se pokoušeli o větší velikost problému.

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

Diskuse: Škálování hloubky dvouqubitových Gate

Klíčovým důvodem, proč je Groverův algoritmus považován za algoritmus odolný vůči chybám, je rychlý nárůst hloubky dvouqubitových Gate s rostoucím počtem Qubitů. Víceřízené Gate Z v jádru orákula i difúzního operátoru se rozloží na počet dvouqubitových Gate, který exponenciálně roste s počtem řídících Qubitů. V kombinaci se skutečností, že optimální počet Groverových iterací sám roste jako $O(\sqrt{2^n})$, se celková hloubka dvouqubitových Gate rychle stane nepraktickou pro hlučný hardware.

Níže sestavujeme Groverovy obvody pro rostoucí počty Qubitů, transpiloujeme je a vykreslujeme výslednou hloubku dvouqubitových Gate pro ilustraci tohoto škálování.

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

Jak graf ukazuje, hloubka dvouqubitových Gate s počtem Qubitů roste extrémně rychle — přibližně exponenciálně. To činí Groverův algoritmus nepraktickým na současném hlučném kvantovém hardwaru pro více než velmi malé velikosti problémů. Algoritmus zůstává důležitým cílem pro budoucí kvantové počítače odolné vůči chybám, kde oprava chyb umožní spolehlivé spouštění hlubokých obvodů.

Další kroky

Doporučení

Pokud tě tato práce zaujala, mohlo by tě zajímat i následující:

• Knihovna Qiskit circuit library: reference API pro grover_operator()
• Tutoriál QAOA a lekce o QAOA v utilitním měřítku poskytují příklady optimalizace pomocí kvantových počítačů v krátkodobém horizontu
• Pro podrobnější pohled na krátkodobé algoritmy si prohlédni kurz Kvantové výpočty v praxi