Algoritma Grover

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

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 v1.4 atau lebih baru, dengan dukungan visualisasi
• Qiskit Runtime (pip install qiskit-ibm-runtime) v0.36 atau lebih baru

Setup

# Added by doQumentation — required packages for this notebook
!pip install -q 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

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.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

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

marked_states = ["011", "100"]

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

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

target = backend.target
pm = generate_preset_pass_manager(target=target, 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 runtime Sampler.

Perlu diperhatikan bahwa metode run() dari Qiskit Runtime SamplerV2 menerima iterable dari primitive unified blocks (PUBs). Untuk Sampler, setiap PUB adalah iterable dalam format (circuit, parameter_values). Namun, minimal, ia menerima daftar Circuit kuantum.

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

Langkah 4: Pasca-proses dan Kembalikan Hasil dalam Format Klasik yang Diinginkan

plot_distribution(dist)

Survei tutorial

Silakan isi survei singkat ini untuk memberikan masukan tentang tutorial ini. Pendapatmu akan membantu kami meningkatkan konten dan pengalaman pengguna.

Tautan ke survei

Note: This survey is provided by IBM Quantum and relates to the original English content. To give feedback on doQumentation's website, translations, or code execution, please open a GitHub issue.