Algoritma Grover

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

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

Persediaan

# 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 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; bersamaan dengan mempunyai open-control pada Qubit tersebut. Dalam kod berikut, kita takrifkan oracle yang melakukan perkara tersebut, menandakan satu atau lebih keadaan asas input yang ditakrifkan melalui perwakilan bit-string mereka. Gate MCMT digunakan untuk melaksanakan 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 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")

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

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: Jalankan menggunakan primitif Qiskit

Amplifikasi amplitud ialah masalah pensampelan yang sesuai untuk dilaksanakan dengan primitif masa jalan Sampler.

Perlu diingat bahawa kaedah run() bagi Qiskit Runtime SamplerV2 mengambil iterable berupa primitive unified blocks (PUBs). Untuk Sampler, setiap PUB ialah iterable dalam format (circuit, parameter_values). Walau bagaimanapun, sekurang-kurangnya ia mengambil senarai 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: Proses selepas dan kembalikan keputusan dalam format klasik yang dikehendaki

plot_distribution(dist)

Tinjauan tutorial

Sila ambil tinjauan ringkas ini untuk memberikan maklum balas tentang tutorial ini. Pandangan anda akan membantu kami memperbaiki kandungan dan pengalaman pengguna kami.

Pautan ke tinjauan

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.