Algoritma Grover

Anggaran penggunaan: kurang dari satu minit pada pemproses Eagle r3 (NOTA: Ini adalah anggaran sahaja. Masa larian anda mungkin berbeza.)

Hasil pembelajaran

Setelah menyelesaikan tutorial ini, anda dijangka dapat memahami maklumat berikut:

• Cara membina oracle Grover yang menandakan satu atau lebih keadaan asas pengiraan
• Cara menggunakan fungsi grover_operator() daripada perpustakaan Circuit Qiskit
• Cara menentukan bilangan iterasi Grover yang optimum untuk masalah tertentu
• Cara melaksanakan algoritma Grover menggunakan primitif Sampler Qiskit Runtime

Prasyarat

Adalah disyorkan agar anda membiasakan diri dengan topik-topik berikut:

• Asas algoritma kuantum: Algoritma Grover
• Asas maklumat kuantum

Latar belakang

Amplifikasi amplitud ialah algoritma kuantum atau subrutin tujuan umum yang boleh digunakan untuk mendapatkan pecutan kuadratik berbanding beberapa algoritma klasik. Algoritma Grover adalah yang pertama menunjukkan pecutan ini pada masalah carian tidak berstruktur. Untuk merumuskan masalah carian Grover, kita memerlukan fungsi oracle yang menandakan satu atau lebih keadaan asas pengiraan sebagai keadaan yang ingin kita cari, dan Circuit amplifikasi yang meningkatkan amplitud keadaan yang ditandakan, seterusnya menekan keadaan yang lain.

Di sini, kami menunjukkan cara membina oracle Grover dan menggunakan grover_operator() dari perpustakaan Circuit Qiskit untuk menyediakan instans carian Grover dengan mudah. Primitif Sampler masa jalan membolehkan pelaksanaan Circuit Grover dengan lancar.

Keperluan

Sebelum memulakan tutorial ini, pastikan anda telah memasang yang berikut:

• Qiskit SDK v2.0 atau lebih baharu, dengan sokongan visualisasi
• Qiskit Runtime v0.22 atau lebih baharu (pip install qiskit-ibm-runtime)

Persediaan

# 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

Contoh simulator skala kecil

Dalam bahagian ini, kita akan melalui setiap langkah algoritma Grover pada skala kecil menggunakan simulator tempatan, sebelum menjalankan masalah yang sama pada perkakasan kuantum sebenar.

Langkah 1: Petakan input klasik kepada masalah kuantum

Algoritma Grover memerlukan sebuah oracle yang menentukan satu atau lebih keadaan asas pengiraan yang ditandakan, di mana "ditandakan" bermaksud keadaan dengan fasa -1. Gate controlled-Z, atau generalisasi multi-controlled-nya ke atas $N$ qubit, menandakan keadaan $2^{N}-1$ ('1'*$N$ bit-string). Menandakan keadaan asas dengan satu atau lebih '0' dalam perwakilan binari memerlukan penerapan X-Gate pada qubit yang berkaitan sebelum dan selepas gate controlled-Z, yang bersamaan dengan mempunyai open-control pada qubit tersebut. Dalam kod berikut, kita takrifkan oracle yang menandakan satu atau lebih keadaan asas input yang ditakrifkan melalui perwakilan bitstring mereka. Gate MCMT digunakan untuk melaksanakan gate Z multi-controlled.

Instans Grover tertentu

Sekarang kita dah ada fungsi oracle, kita boleh takrifkan instans carian Grover yang tertentu. Dalam contoh ini kita akan menandakan dua keadaan pengiraan daripada lapan yang tersedia dalam ruang pengiraan tiga qubit:

marked_states = ["011", "100"]

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

Operator Grover

Fungsi grover_operator() terbina dalam Qiskit mengambil Circuit oracle dan mengembalikan Circuit yang terdiri daripada Circuit oracle itu sendiri serta Circuit yang mengamplifikasi keadaan yang ditandakan oleh oracle. Di sini, kita gunakan kaedah decompose() pada Circuit untuk melihat gate dalam operator tersebut:

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

Pengulangan penerapan Circuit grover_op ini akan mengamplifikasi keadaan yang ditandakan, menjadikannya bit-string yang paling mungkin dalam taburan output dari Circuit. Terdapat bilangan penerapan optimum yang ditentukan oleh nisbah keadaan yang ditandakan kepada jumlah keseluruhan keadaan pengiraan yang mungkin:

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

Circuit Grover penuh

Eksperimen Grover yang lengkap bermula dengan gate Hadamard pada setiap qubit; mencipta superposisi sekata bagi semua keadaan asas pengiraan, diikuti dengan operator Grover (grover_op) yang diulang sebanyak bilangan optimum. Di sini kita menggunakan kaedah QuantumCircuit.power(INT) untuk menerapkan operator Grover secara berulang.

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

Langkah 2: Optimumkan masalah untuk pelaksanaan perkakasan kuantum

Untuk simulasi skala kecil ini, kita transpilkan Circuit tanpa menyasarkan perkakasan tertentu.

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

Langkah 3: Laksanakan menggunakan primitif Qiskit

Amplifikasi amplitud ialah masalah pensampelan yang sesuai untuk dilaksanakan dengan primitif SamplerV2. Di sini kita gunakan StatevectorSampler daripada qiskit.primitives untuk simulasi tempatan.

from qiskit.primitives import StatevectorSampler

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

Langkah 4: Proses selepas dan kembalikan keputusan dalam format klasik yang dikehendaki

plot_distribution(dist)

Contoh perkakasan

Langkah 1-4

Algoritma Grover pada dasarnya ialah algoritma tahan kesalahan — gate Z multi-controlled yang menjadi teras oracle dan operator peresapan membawa kepada kedalaman gate dua-Qubit yang berkembang sangat pesat dengan bilangan qubit (seperti yang akan kita tunjukkan dalam bahagian seterusnya). Ini bermakna algoritma ini tidak berskala dengan baik pada perkakasan bising masa kini. Atas sebab itu, kita menunjukkan pelaksanaan perkakasan pada skala kecil yang sama seperti contoh simulator di atas, daripada mencuba saiz masalah yang lebih besar.

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

Perbincangan: Penskalaan kedalaman gate dua-Qubit

Sebab utama algoritma Grover dianggap sebagai algoritma tahan kesalahan ialah pertumbuhan pesat kedalaman gate dua-Qubit Circuit apabila bilangan qubit meningkat. Gate Z multi-controlled yang menjadi teras oracle dan operator peresapan terurai kepada bilangan gate dua-Qubit yang berkembang secara eksponen dengan bilangan qubit kawalan. Digabungkan dengan fakta bahawa bilangan iterasi Grover optimum itu sendiri berkembang sebagai $O(\sqrt{2^n})$, kedalaman dua-Qubit keseluruhan menjadi tidak praktikal untuk perkakasan bising dengan cepat.

Di bawah, kita membina Circuit Grover untuk bilangan qubit yang semakin meningkat, mentranspilkannya, dan memplot kedalaman gate dua-Qubit yang terhasil untuk menggambarkan penskalaan ini.

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

Seperti yang ditunjukkan oleh plot, kedalaman gate dua-Qubit berkembang dengan sangat pesat mengikut bilangan qubit — lebih kurang secara eksponen. Ini menjadikan algoritma Grover tidak praktikal pada perkakasan kuantum bising masa kini di luar saiz masalah yang sangat kecil. Algoritma ini tetap menjadi sasaran penting untuk komputer kuantum tahan kesalahan masa depan, di mana pembetulan ralat akan membolehkan Circuit yang dalam dilaksanakan dengan boleh dipercayai.

Langkah seterusnya

Cadangan

Jika anda mendapati kerja ini menarik, anda mungkin berminat dengan bahan berikut:

• Perpustakaan Circuit Qiskit: Rujukan API grover_operator()
• Tutorial QAOA dan pelajaran QAOA skala utiliti memberikan contoh jangka pendek pengoptimuman dengan komputer kuantum
• Untuk pandangan lebih mendalam tentang algoritma jangka pendek, lihat kursus Pengkomputeran kuantum dalam amalan