Algorytm Grovera

Szacowany czas obliczeń: poniżej jednej minuty na procesorze Eagle r3 (UWAGA: Jest to tylko szacunek. Rzeczywisty czas może się różnić.)

Cele nauki

• Jak konstruować wyrocznie Grovera oznaczające jeden lub więcej stanów bazy obliczeniowej

• Jak używać funkcji grover_operator() z biblioteki obwodów Qiskit

• Jak wyznaczać optymalną liczbę iteracji Grovera dla danego problemu

• Jak wykonywać algorytm Grovera przy użyciu prymitywu Sampler IBM Quantum

Wymagania wstępne

• Podstawy algorytmów kwantowych: algorytm Grovera

• Podstawy informacji kwantowej

Tło

Wzmocnienie amplitudy to ogólny algorytm kwantowy (lub podprogram), który można wykorzystać do uzyskania kwadratowego przyspieszenia względem garstki (niewielkiej liczby) klasycznych algorytmów. Algorytm Grovera był pierwszym, który zademonstrował to przyspieszenie w przypadku przeszukiwania nieuporządkowanych danych. Sformułowanie problemu wyszukiwania Grovera wymaga funkcji wyroczni, która oznacza jeden lub więcej stanów bazy obliczeniowej jako stany, które chcemy znaleźć, oraz obwodu wzmacniającego, który zwiększa amplitudę oznaczonych stanów, a tym samym tłumi pozostałe.

Tutaj pokazujemy, jak konstruować wyrocznie Grovera i używać funkcji grover_operator() z biblioteki obwodów Qiskit, aby w prosty sposób skonfigurować instancję wyszukiwania Grovera. Prymityw Sampler środowiska uruchomieniowego umożliwia płynne wykonywanie obwodów Grovera.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że masz zainstalowane następujące elementy:

• Qiskit SDK v2.0 lub nowszy, z obsługą wizualizacji

• Qiskit Runtime v0.22 lub nowszy (pip install qiskit-ibm-runtime)

Konfiguracja

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

Przykład na małą skalę z symulatorem

W tej sekcji przechodzimy przez każdy krok algorytmu Grovera na małą skalę przy użyciu lokalnego symulatora, zanim uruchomimy ten sam problem na prawdziwym sprzęcie kwantowym.

Krok 1: Odwzorowanie klasycznych danych wejściowych na problem kwantowy

Algorytm Grovera wymaga wyroczni, która określa jeden lub więcej oznaczonych stanów bazy obliczeniowej, gdzie „oznaczony" oznacza stan z fazą -1. Bramka kontrolowana-Z lub jej wielokrotnie kontrolowane uogólnienie na $N$ kubitach oznacza stan $2^{N}-1$ (ciąg bitów '1'*$N$). Oznaczenie stanów bazy z co najmniej jednym '0' w reprezentacji binarnej wymaga zastosowania bramek X na odpowiednich kubitach przed i po bramce controlled-Z — co jest równoważne posiadaniu otwartego sterowania na tym kubicie. W poniższym kodzie definiujemy wyrocznię, która oznacza jeden lub więcej wejściowych stanów bazy, zdefiniowanych przez reprezentację bitową. Bramka MCMT służy do implementacji wielokrotnie kontrolowanej bramki Z.

Konkretna instancja wyszukiwania Grovera

Teraz, gdy mamy funkcję wyroczni, możemy zdefiniować konkretną instancję wyszukiwania Grovera. W tym przykładzie oznaczymy dwa stany obliczeniowe spośród ośmiu dostępnych w trójkubitowej przestrzeni obliczeniowej:

marked_states = ["011", "100"]

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

Operator Grovera

Wbudowana funkcja Qiskit grover_operator() przyjmuje obwód wyroczni i zwraca obwód złożony z samego obwodu wyroczni oraz obwodu wzmacniającego stany oznaczone przez wyrocznię. Tutaj używamy metody decompose() na obwodzie, aby zobaczyć bramki wewnątrz operatora:

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

Wielokrotne zastosowania obwodu grover_op wzmacniają oznaczone stany, czyniąc je najbardziej prawdopodobnymi ciągami bitów w wynikowym rozkładzie z obwodu. Istnieje optymalna liczba takich zastosowań, wyznaczana przez stosunek liczby oznaczonych stanów do całkowitej liczby możliwych stanów obliczeniowych:

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

Pełny obwód Grovera

Pełny eksperyment Grovera rozpoczyna się od bramki Hadamarda na każdym kubicie, tworząc równą superpozycję wszystkich stanów bazy obliczeniowej, a następnie operator Grovera (grover_op) jest stosowany optymalną liczbę razy. Tutaj korzystamy z metody QuantumCircuit.power(INT), aby wielokrotnie zastosować operator Grovera.

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: Optymalizacja problemu pod kątem wykonania na sprzęcie kwantowym

Dla symulacji na małą skalę transpilujemy obwód bez wskazywania konkretnego sprzętu.

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: Wykonanie przy użyciu prymitywów Qiskit

Wzmocnienie amplitudy to problem próbkowania, który nadaje się do wykonania przy użyciu prymitywu SamplerV2. Tutaj używamy StatevectorSampler z qiskit.primitives do lokalnej symulacji.

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: Przetwarzanie końcowe i zwrócenie wyniku w pożądanym formacie klasycznym

plot_distribution(dist)

Przykład na sprzęcie

Kroki 1–4

Algorytm Grovera jest z założenia algorytmem tolerującym błędy — wielokrotnie kontrolowane bramki Z stanowiące serce wyroczni i operatora dyfuzji prowadzą do głębokości bramek dwukubitowych, która rośnie bardzo szybko wraz z liczbą kubitów (co pokażemy w następnej sekcji). Oznacza to, że algorytm nie skaluje się dobrze na obecnym zaszumionym sprzęcie. Z tego powodu demonstrujemy wykonanie na sprzęcie na tej samej małej skali co przykład z symulatorem, zamiast próbować rozwiązać większy problem.

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

Omówienie: skalowanie głębokości bramek dwukubitowych

Kluczowym powodem, dla którego algorytm Grovera jest uważany za algorytm tolerujący błędy, jest szybki wzrost głębokości bramek dwukubitowych wraz ze wzrostem liczby kubitów. Wielokrotnie kontrolowana bramka Z stanowiąca rdzeń zarówno wyroczni, jak i operatora dyfuzji rozkłada się na liczbę bramek dwukubitowych rosnącą wykładniczo wraz z liczbą kubitów sterujących. W połączeniu z faktem, że optymalna liczba iteracji Grovera sama w sobie rośnie jak $O(\sqrt{2^n})$, całkowita głębokość dwukubitowa szybko staje się niepraktyczna dla zaszumionego sprzętu.

Poniżej konstruujemy obwody Grovera dla rosnącej liczby kubitów, transpilujemy je i rysujemy wynikową głębokość bramek dwukubitowych, aby zilustrować to skalowanie.

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 pokazuje wykres, głębokość bramek dwukubitowych rośnie niezwykle szybko wraz z liczbą kubitów — mniej więcej wykładniczo. Sprawia to, że algorytm Grovera jest niepraktyczny na obecnym zaszumionym sprzęcie kwantowym dla jakichkolwiek rozmiarów problemów poza bardzo małymi. Algorytm pozostaje ważnym celem dla przyszłych kwantowych komputerów tolerujących błędy, gdzie korekcja błędów umożliwi niezawodne wykonywanie głębokich obwodów.

Następne kroki

Zalecenia

Jeśli ta praca wydała ci się interesująca, możesz zainteresować się następującymi materiałami:

• Biblioteka obwodów Qiskit: dokumentacja API grover_operator()
• Samouczek QAOA i lekcja QAOA w skali użytkowej pokazują przykłady optymalizacji na komputerach kwantowych w bliskiej perspektywie (near-term)
• Aby uzyskać głębsze spojrzenie na algorytmy krótkoterminowe (near-term), zapoznaj się z kursem Obliczenia kwantowe w praktyce