Algoritma Grover

Estimasi penggunaan: kurang dari satu menit pada prosesor Eagle r3 (CATATAN: Ini hanya estimasi. Waktu eksekusi aktual bisa berbeda-beda.)

Hasil Pembelajaran

Setelah menyelesaikan tutorial ini, kamu diharapkan memahami hal-hal berikut:

• Cara membangun oracle Grover yang menandai satu atau lebih state basis komputasi
• Cara menggunakan fungsi grover_operator() dari pustaka Circuit Qiskit
• Cara menentukan jumlah iterasi Grover yang optimal untuk suatu masalah
• Cara mengeksekusi algoritma Grover menggunakan primitif Sampler Qiskit Runtime

Prasyarat

Disarankan agar kamu terlebih dahulu memahami topik-topik berikut:

• Dasar-dasar algoritma kuantum: Algoritma Grover
• Dasar-dasar informasi kuantum

Latar Belakang

Amplifikasi amplitudo adalah algoritma kuantum serbaguna, atau subrutin, yang dapat digunakan untuk mendapatkan percepatan kuadratik dibandingkan sejumlah algoritma klasik. Algoritma Grover adalah yang pertama mendemonstrasikan percepatan ini pada masalah pencarian tak terstruktur. Untuk merumuskan masalah pencarian Grover, dibutuhkan fungsi oracle yang menandai satu atau lebih state basis komputasi sebagai state yang ingin kita temukan, serta Circuit amplifikasi yang meningkatkan amplitudo state yang ditandai, sekaligus menekan state lainnya.

Di sini, kita akan menunjukkan cara membangun oracle Grover dan menggunakan grover_operator() dari pustaka Circuit Qiskit untuk menyiapkan instans pencarian Grover dengan mudah. Primitif Sampler runtime memungkinkan eksekusi Circuit Grover yang mulus.

Persyaratan

Sebelum memulai tutorial ini, pastikan kamu sudah menginstal hal-hal berikut:

• Qiskit SDK v2.0 atau lebih baru, dengan dukungan visualisasi
• Qiskit Runtime v0.22 atau lebih baru (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

Contoh Simulator Skala Kecil

Di bagian ini, kita akan membahas setiap langkah algoritma Grover dalam skala kecil menggunakan simulator lokal, sebelum menjalankan masalah yang sama pada hardware kuantum nyata.

Langkah 1: Petakan Input Klasik ke Masalah Kuantum

Algoritma Grover membutuhkan sebuah oracle yang menentukan satu atau lebih state basis komputasi yang ditandai, di mana "ditandai" berarti state dengan fase -1. Gate controlled-Z, atau generalisasi multi-controlled-nya pada $N$ qubit, menandai state $2^{N}-1$ ('1'*$N$ bit-string). Menandai state basis dengan satu atau lebih '0' dalam representasi biner memerlukan penerapan Gate X pada qubit yang bersangkutan sebelum dan sesudah Gate controlled-Z; setara dengan memiliki open-control pada qubit tersebut. Pada kode berikut, kita mendefinisikan oracle yang melakukan hal tersebut, menandai satu atau lebih state basis input yang didefinisikan melalui representasi bit-string-nya. Gate MCMT digunakan untuk mengimplementasikan Gate Z multi-controlled.

Instans Grover Spesifik

Sekarang setelah kita punya fungsi oracle, kita bisa mendefinisikan instans spesifik dari pencarian Grover. Pada contoh ini kita akan menandai dua state komputasi dari delapan yang tersedia dalam ruang komputasi tiga qubit:

marked_states = ["011", "100"]

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

Operator Grover

Fungsi bawaan Qiskit grover_operator() menerima Circuit oracle dan mengembalikan Circuit yang terdiri dari Circuit oracle itu sendiri beserta Circuit yang mengamplifikasi state yang ditandai oleh oracle. Di sini, kita menggunakan metode decompose() pada Circuit untuk melihat Gate-Gate di dalam operator:

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

Penerapan berulang Circuit grover_op ini mengamplifikasi state yang ditandai, sehingga menjadi bit-string paling mungkin dalam distribusi output dari Circuit. Ada jumlah penerapan optimal yang ditentukan oleh rasio state yang ditandai terhadap total jumlah state komputasi yang mungkin:

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

Circuit Grover Lengkap

Eksperimen Grover yang lengkap dimulai dengan Gate Hadamard pada setiap qubit; membuat superposisi merata dari semua state basis komputasi, diikuti oleh operator Grover (grover_op) yang diulang sebanyak jumlah optimal. Di sini kita memanfaatkan metode 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: Optimalkan Masalah untuk Eksekusi pada Hardware Kuantum

Untuk simulasi skala kecil, kita melakukan transpilasi Circuit tanpa menargetkan hardware 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: Eksekusi Menggunakan Primitif Qiskit

Amplifikasi amplitudo adalah masalah sampling yang cocok untuk dieksekusi dengan primitif SamplerV2. Di sini kita menggunakan StatevectorSampler dari qiskit.primitives untuk simulasi lokal.

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: Pasca-proses dan Kembalikan Hasil dalam Format Klasik yang Diinginkan

plot_distribution(dist)

Contoh Hardware

Langkah 1-4

Algoritma Grover pada dasarnya adalah algoritma fault-tolerant — Gate Z multi-controlled yang menjadi inti oracle dan operator difusi menghasilkan kedalaman Gate dua-Qubit yang tumbuh sangat cepat seiring bertambahnya jumlah qubit (seperti yang akan kita tunjukkan di bagian selanjutnya). Ini berarti algoritma tidak berskala baik pada hardware noisy saat ini. Untuk alasan ini, kita mendemonstrasikan eksekusi hardware pada skala kecil yang sama seperti contoh simulator di atas, alih-alih mencoba ukuran 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)

Diskusi: Penskalaan Kedalaman Gate Dua-Qubit

Salah satu alasan utama algoritma Grover dianggap sebagai algoritma fault-tolerant adalah pertumbuhan pesat kedalaman Gate dua-Qubit pada Circuit seiring bertambahnya jumlah qubit. Gate Z multi-controlled yang menjadi inti oracle dan operator difusi terdekomposisi menjadi sejumlah Gate dua-Qubit yang tumbuh secara eksponensial dengan jumlah qubit kontrol. Dikombinasikan dengan fakta bahwa jumlah iterasi Grover yang optimal sendiri tumbuh sebesar $O(\sqrt{2^n})$, kedalaman dua-Qubit secara keseluruhan dengan cepat menjadi tidak praktis untuk hardware noisy.

Di bawah ini, kita membangun Circuit Grover untuk jumlah qubit yang semakin meningkat, melakukan transpilasi, dan memplot kedalaman Gate dua-Qubit yang dihasilkan untuk mengilustrasikan 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 tumbuh sangat cepat seiring bertambahnya jumlah qubit — kira-kira secara eksponensial. Ini membuat algoritma Grover tidak praktis pada hardware kuantum noisy saat ini untuk ukuran masalah yang lebih dari sangat kecil. Algoritma ini tetap menjadi target penting bagi komputer kuantum fault-tolerant di masa depan, di mana koreksi kesalahan akan memungkinkan Circuit yang dalam untuk dieksekusi secara andal.

Langkah Berikutnya

Rekomendasi

Jika kamu merasa konten ini menarik, mungkin kamu juga tertarik dengan materi berikut:

• Pustaka Circuit Qiskit: referensi API grover_operator()
• Tutorial QAOA dan pelajaran QAOA skala utilitas memberikan contoh optimasi jangka pendek dengan komputer kuantum
• Untuk tinjauan lebih mendalam tentang algoritma jangka pendek, lihat kursus Komputasi kuantum dalam praktik