Algoritma kuantum: Carian Grover dan aplikasinya

nota

Atsushi Matsuo (10 Mei 2024)

Muat turun pdf kuliah asal. Perlu diingat bahawa beberapa coretan kod mungkin sudah lapuk kerana ia adalah imej statik.

Anggaran masa QPU untuk menjalankan eksperimen ini ialah 2 saat.

1. Pengenalan kepada algoritma Grover

Buku nota ini adalah yang keempat dalam siri kuliah mengenai Laluan ke Utiliti dalam Pengkomputeran Kuantum. Dalam buku nota ini, kita akan belajar tentang algoritma Grover.

Algoritma Grover adalah salah satu algoritma kuantum yang paling terkenal kerana peningkatan kelajuan kuadratiknya berbanding kaedah carian klasik. Dalam pengkomputeran klasik, mencari pangkalan data tidak tersusun yang mengandungi $N$ item memerlukan kerumitan masa $O(N)$, bermaksud dalam kes terburuk, seseorang mungkin perlu memeriksa setiap item satu persatu. Namun, algoritma Grover membolehkan kita mencapai carian ini dalam masa $O(\sqrt{N})$, memanfaatkan prinsip mekanik kuantum untuk mengenal pasti item sasaran dengan lebih cekap.

Algoritma ini menggunakan amplifikasi amplitud, satu proses yang meningkatkan amplitud kebarangkalian bagi keadaan jawapan yang betul dalam superposisi kuantum, membolehkannya diukur dengan kebarangkalian yang lebih tinggi. Peningkatan kelajuan ini menjadikan algoritma Grover berguna dalam pelbagai aplikasi selain carian pangkalan data mudah, terutama apabila saiz set data adalah besar. Penjelasan terperinci mengenai algoritma ini disediakan dalam buku nota algoritma Grover.

Struktur Asas Algoritma Grover

Algoritma Grover terdiri daripada empat komponen utama:

1. Permulaan: Menyediakan superposisi ke atas semua keadaan yang mungkin.
2. Oracle: Menggunakan fungsi oracle yang menandai keadaan sasaran dengan membalik fasanya.
3. Operator Resapan: Menggunakan siri operasi untuk memperkuat kebarangkalian keadaan yang ditandai.

Setiap langkah ini memainkan peranan penting dalam menjadikan algoritma berfungsi dengan cekap. Penjelasan terperinci untuk setiap langkah disediakan kemudian.

2. Melaksanakan Algoritma Grover

2.1 Persediaan

Import perpustakaan yang diperlukan dan sediakan persekitaran untuk menjalankan Circuit kuantum.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-aer qiskit-ibm-runtime

%config InlineBackend.figure_format = 'svg' # Makes the images look nice

# importing Qiskit
from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister

# import basic plot tools
from qiskit.visualization import plot_histogram

Langkah 1: Petakan masalah kepada Circuit kuantum dan operator

Pertimbangkan senarai 4 elemen, di mana matlamat kita adalah mengenal pasti indeks elemen yang memenuhi syarat tertentu. Sebagai contoh, kita ingin mencari indeks elemen yang sama dengan 2. Dalam contoh ini, keadaan kuantum $|01\rangle$ mewakili indeks elemen yang memenuhi syarat ini, kerana ia menunjuk kepada kedudukan di mana nilai 2 terletak.

Langkah 2: Optimalkan untuk perkakasan sasaran

1: Permulaan

Dalam langkah permulaan, kita mencipta superposisi semua keadaan yang mungkin. Ini dicapai dengan menggunakan Gate Hadamard kepada setiap Qubit dalam daftar n-Qubit, yang akan menghasilkan superposisi sama rata bagi $2^n$ keadaan. Secara matematik, ini boleh diwakili sebagai:

$$\frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle$$

di mana $N = 2^n$ adalah jumlah keseluruhan keadaan yang mungkin. Kita juga menukar keadaan bit ancilla kepada $|-\rangle$.

def initialization(circuit):
    # Initialization
    n = circuit.num_qubits
    # For input qubits
    for qubit in range(n - 1):
        circuit.h(qubit)
    # For the ancilla bit
    circuit.x(n - 1)
    circuit.h(n - 1)
    circuit.barrier()
    return circuit

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
initialization_circuit = QuantumCircuit(qr, anc)

initialization(initialization_circuit)
initialization_circuit.draw(output="mpl", idle_wires=False)

2: Oracle

Oracle adalah bahagian penting dalam algoritma Grover. Ia menandai keadaan sasaran dengan menggunakan anjakan fasa, biasanya membalik tanda amplitud yang berkaitan dengan keadaan tersebut. Oracle sering bersifat khusus mengikut masalah dan dibina berdasarkan kriteria untuk mengenal pasti keadaan sasaran. Dalam istilah matematik, oracle menggunakan transformasi berikut:

f(x) = \begin\{cases\} 1, & \text\{if \} x = x_\{\text\{target}\} \\ 0, & \text\{otherwise\} \end\{cases\}

Pembalikan fasa ini dicapai dengan menggunakan tanda negatif kepada amplitud keadaan sasaran melalui tendangan balik fasa.

def oracle(circuit):
    circuit.x(1)
    circuit.ccx(0, 1, 2)
    circuit.x(1)
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
oracle_circuit = QuantumCircuit(qr, anc)

oracle(oracle_circuit)
oracle_circuit.draw(output="mpl", idle_wires=False)

3: Operator Resapan

Proses amplifikasi amplitud inilah yang membezakan algoritma Grover daripada carian klasik. Selepas oracle menandai keadaan sasaran, kita menggunakan siri operasi yang meningkatkan amplitud keadaan yang ditandai ini, menjadikannya lebih mudah diperhatikan semasa pengukuran. Proses ini dicapai melalui Operator Resapan, yang secara efektif melakukan penyongsangan sekitar amplitud purata. Operasi matematik adalah seperti berikut:

$D = 2|\psi\rangle\langle\psi| - I$

di mana $D$ adalah operator resapan, $I$ adalah matriks identiti, dan $|\psi\rangle$ adalah keadaan superposisi sama rata. Gabungan oracle dan operator resapan digunakan kira-kira $\sqrt{N}$ kali untuk mencapai kebarangkalian maksimum bagi mengukur keadaan yang ditandai.

def diffusion(circuit):
    input_qubits = circuit.num_qubits - 1
    circuit.h(range(0, input_qubits))
    circuit.x(range(0, input_qubits))
    circuit.h(input_qubits - 1)
    circuit.mcx([i for i in range(0, input_qubits - 1)], input_qubits - 1)
    circuit.h(input_qubits - 1)
    circuit.x(range(0, input_qubits))
    circuit.h(range(0, input_qubits))
    circuit.barrier()

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
diffusion_circuit = QuantumCircuit(qr, anc)

diffusion(diffusion_circuit)
diffusion_circuit.draw(output="mpl", idle_wires=False)

2.2 Contoh carian Grover 2-Qubit.

n = 2
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
meas = ClassicalRegister(3, "meas")
grover_circuit = QuantumCircuit(qr, anc, meas)

# the number of iterations
num_iterations = 1

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)
grover_circuit.measure_all(add_bits=False)

grover_circuit.draw(output="mpl", idle_wires=False)

2.3 Eksperimen dengan Simulator

Langkah 3: Menjalankan Circuit.

from qiskit_aer import AerSimulator
from qiskit_ibm_runtime import Sampler
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(mode=backend)
job = sampler.run([isa_qc])
result = job.result()

Langkah 4: Memproses keputusan.

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Kita mendapat jawapan yang betul $|01\rangle$. Perlu diingat untuk berhati-hati dengan susunan Qubit.

3. Eksperimen dengan Peranti Sebenar

Langkah 2: Optimalkan untuk perkakasan sasaran

from qiskit_ibm_runtime import QiskitRuntimeService

service = QiskitRuntimeService()
real_backend = service.backend("ENTER-QPU-NAME-HERE")

# You can also identify the least busy device

real_backend = service.least_busy(simulator=False, operational=True)
print("The least busy device is ", real_backend)

# Transpile the circuit into basis gates executable on the hardware
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

pm = generate_preset_pass_manager(backend=real_backend, optimization_level=1)
target_circuit = pm.run(grover_circuit)

target_circuit.draw(output="mpl", idle_wires=False)

Dengan mentranspil Circuit, ia ditukar kepada Circuit menggunakan gate asas natif peranti.

Langkah 3: Menjalankan Circuit.

sampler = Sampler(real_backend)
job_real = sampler.run([target_circuit])
job_id = job_real.job_id()
print("job id:", job_id)

job id: cw69csv19rzg0080yfkg

# Check the job status
job_real.status()

'QUEUED'

# If the Notebook session got disconnected you can also check your job status by running the following code
job_real = service.job(job_id)  # Input your job-id between the quotations
job_real.status()

'DONE'

# Execute after job has successfully run
result_real = job_real.result()
print(result_real[0].data.meas.get_counts())

{'101': 540, '001': 2253, '011': 476, '000': 251, '110': 105, '100': 100, '010': 168, '111': 203}

Langkah 4: Memproses keputusan.

plot_histogram(result_real[0].data.meas.get_counts())

4. Carian Grover 3-Qubit

Sekarang, jom cuba contoh carian Grover 3-Qubit.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancilla")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 2

def oracle(circuit):
    circuit.mcx([0, 1, 2], 3)
    circuit.barrier()

Kali ini, $|111\rangle$ adalah keadaan "baik".

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0111': 977, '0100': 11, '0001': 8, '0000': 8, '0011': 5, '0010': 12, '0110': 3}

$|0111\rangle$ diperhatikan dengan kebarangkalian tertinggi, seperti yang dijangkakan. Perhatikan bahawa dua iterasi adalah optimum dalam kes ini. Walau bagaimanapun, kebarangkalian untuk mendapat jawapan yang betul bukan 100%, dan ini adalah perkara biasa dalam carian Grover.

Apa yang berlaku jika kita iterasi 3 kali?

Sekarang, jom cuba iterasi 3 kali.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 3

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc], shots=1024)
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0010': 88, '0001': 103, '0000': 94, '0111': 334, '0100': 112, '0110': 106, '0101': 99, '0011': 88}

$|0111\rangle$ masih diperhatikan dengan kebarangkalian tertinggi, walaupun kebarangkalian untuk mendapat jawapan yang betul telah sedikit berkurang.

Bagaimana pula dengan 4 kali?

Sekarang, jom cuba iterasi 4 kali.

n = 3
qr = QuantumRegister(n, "q")
anc = QuantumRegister(1, "ancillary")
grover_circuit = QuantumCircuit(qr, anc)

# the number of iterations
num_iterations = 4

# Let's do Grover search
initialization(grover_circuit)

for i in range(0, num_iterations):
    oracle(grover_circuit)
    diffusion(grover_circuit)

# Clear the ancilla bit
grover_circuit.h(n)
grover_circuit.x(n)

grover_circuit.draw(output="mpl", idle_wires=False, fold=-1, scale=0.5)

grover_circuit.measure_all()

# Define backend
backend = AerSimulator()

# Transpile to backend
pm = generate_preset_pass_manager(backend=backend, optimization_level=1)
isa_qc = pm.run(grover_circuit)

# Run the job
sampler = Sampler(backend)
job = sampler.run([isa_qc])
result = job.result()

# Print the results
counts = result[0].data.meas.get_counts()
print(counts)

# Plot the counts in a histogram
plot_histogram(counts)

{'0110': 127, '0000': 135, '0001': 150, '0101': 164, '0010': 153, '0011': 131, '0100': 150, '0111': 14}

$|0111\rangle$ diperhatikan dengan kebarangkalian terendah, dan kebarangkalian untuk mendapat jawapan yang betul telah berkurang lagi. Ini menunjukkan betapa pentingnya memilih bilangan iterasi yang optimum untuk algoritma Grover bagi mencapai keputusan terbaik.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'