Алгоритм Гровера

Оцінка використання: менше однієї хвилини на процесорі Eagle r3 (ПРИМІТКА: Це лише оцінка. Твій час виконання може відрізнятися.)

Результати навчання

Після завершення цього посібника ти зможеш розуміти таку інформацію:

• Як побудувати оракули Гровера, що позначають один або більше станів обчислювального базису
• Як використовувати функцію grover_operator() з бібліотеки схем Qiskit
• Як визначити оптимальну кількість ітерацій Гровера для заданої задачі
• Як виконати алгоритм Гровера за допомогою примітива Sampler у Qiskit Runtime

Передумови

Рекомендується ознайомитися з такими темами:

• Основи квантових алгоритмів: алгоритм Гровера
• Основи квантової інформації

Загальна інформація

Підсилення амплітуди — це квантовий алгоритм загального призначення або підпрограма, яку можна використовувати для отримання квадратичного прискорення порівняно з деякими класичними алгоритмами. Алгоритм Гровера був першим, хто продемонстрував це прискорення на неструктурованих задачах пошуку. Формулювання задачі пошуку Гровера вимагає функції-оракула, яка позначає один або більше станів обчислювального базису як стани, що нас цікавлять, і схеми підсилення, яка збільшує амплітуду позначених станів, пригнічуючи тим самим решту станів.

Тут ми демонструємо, як побудувати оракули Гровера та використовувати grover_operator() з бібліотеки схем Qiskit для легкого налаштування екземпляра пошуку Гровера. Примітив Sampler виконавчого середовища дозволяє безперебійне виконання схем Гровера.

Вимоги

Перед початком цього посібника переконайся, що у тебе встановлено таке:

• Qiskit SDK v2.0 або новіший, з підтримкою візуалізації
• Qiskit Runtime v0.22 або новіший (pip install qiskit-ibm-runtime)

Налаштування

# 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

Приклад з симулятором малого масштабу

У цьому розділі ми крок за кроком розглянемо алгоритм Гровера у малому масштабі за допомогою локального симулятора, перш ніж запустити ту саму задачу на реальному квантовому обладнанні.

Крок 1: Відображення класичних входів на квантову задачу

Алгоритм Гровера вимагає оракула, який визначає один або більше позначених станів обчислювального базису, де "позначений" означає стан з фазою -1. Контрольований Z-вентиль або його багатоконтрольована узагальнення для $N$ кубітів позначає стан $2^{N}-1$ (бітовий рядок '1'*$N$). Позначення базисних станів з одним або більше '0' у двійковому представленні вимагає застосування X-вентилів на відповідних кубітах до та після контрольованого Z-вентиля, що еквівалентно наявності відкритого контролю на цьому кубіті. У наступному коді ми визначаємо оракул, який позначає один або більше вхідних базисних станів, визначених через їх бітрядкове представлення. Вентиль MCMT використовується для реалізації багатоконтрольованого Z-вентиля.

Конкретний екземпляр Гровера

Тепер, коли у нас є функція оракула, ми можемо визначити конкретний екземпляр пошуку Гровера. У цьому прикладі ми позначимо два обчислювальних стани з восьми доступних у тривимірному обчислювальному просторі:

marked_states = ["011", "100"]

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

Оператор Гровера

Вбудована функція Qiskit grover_operator() приймає схему оракула та повертає схему, яка складається зі самої схеми оракула та схеми, яка підсилює стани, позначені оракулом. Тут ми використовуємо метод decompose() схеми, щоб побачити вентилі всередині оператора:

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

Повторні застосування цієї схеми grover_op підсилюють позначені стани, роблячи їх найбільш ймовірними бітрядками у вихідному розподілі зі схеми. Існує оптимальна кількість таких застосувань, яка визначається відношенням позначених станів до загальної кількості можливих обчислювальних станів:

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

Повна схема Гровера

Повний експеримент Гровера починається з вентиля Адамара на кожному кубіті, створюючи рівну суперпозицію всіх станів обчислювального базису, за яким слідує оператор Гровера (grover_op), повторений оптимальну кількість разів. Тут ми використовуємо метод QuantumCircuit.power(INT) для повторного застосування оператора Гровера.

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

Крок 2: Оптимізація задачі для виконання на квантовому обладнанні

Для симуляції малого масштабу ми транспілюємо схему без прив'язки до конкретного обладнання.

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

Крок 3: Виконання за допомогою примітивів Qiskit

Підсилення амплітуди — це задача вибірки, яка підходить для виконання з примітивом SamplerV2. Тут ми використовуємо StatevectorSampler з qiskit.primitives для локальної симуляції.

from qiskit.primitives import StatevectorSampler

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

Крок 4: Постобробка та повернення результату в бажаному класичному форматі

plot_distribution(dist)

Приклад на реальному обладнанні

Кроки 1-4

Алгоритм Гровера є принципово відмовостійким алгоритмом — багатоконтрольовані Z-вентилі в основі оракула та оператора дифузії призводять до глибини двокубітних вентилів, яка дуже швидко зростає зі збільшенням кількості кубітів (як ми покажемо в наступному розділі). Це означає, що алгоритм погано масштабується на сучасному зашумленому обладнанні. З цієї причини ми демонструємо виконання на обладнанні в тому самому малому масштабі, що й у прикладі з симулятором вище, а не намагаємося розв'язати задачу більшого розміру.

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

Обговорення: масштабування глибини двокубітних вентилів

Ключова причина, чому алгоритм Гровера вважається відмовостійким алгоритмом, — це швидке зростання глибини двокубітних вентилів схеми зі збільшенням кількості кубітів. Багатоконтрольований Z-вентиль в основі як оракула, так і оператора дифузії розкладається на кількість двокубітних вентилів, яка зростає експоненціально зі збільшенням кількості контрольних кубітів. У поєднанні з тим, що оптимальна кількість ітерацій Гровера сама по собі зростає як $O(\sqrt{2^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

Як показує графік, глибина двокубітних вентилів зростає надзвичайно швидко зі збільшенням кількості кубітів — приблизно експоненціально. Це робить алгоритм Гровера непрактичним на сучасному зашумленому квантовому обладнанні для задач більш ніж дуже малого розміру. Алгоритм залишається важливою ціллю для майбутніх відмовостійких квантових комп'ютерів, де корекція помилок дозволить надійно виконувати глибокі схеми.

Наступні кроки

Рекомендації

Якщо ця робота тебе зацікавила, тебе можуть зацікавити такі матеріали:

• Бібліотека схем Qiskit: довідник API grover_operator()
• Посібник з QAOA і урок з QAOA у промисловому масштабі наводять ближньострокові приклади оптимізації з квантовими комп'ютерами
• Для більш детального ознайомлення з ближньостроковими алгоритмами дивись курс Квантові обчислення на практиці