Algoritma kuantum: Pencarian Grover dan aplikasinya

catatan

Atsushi Matsuo (10 Mei 2024)

Unduh pdf dari kuliah aslinya. Perhatikan bahwa beberapa cuplikan kode mungkin sudah tidak berlaku karena ini adalah gambar statis.

Perkiraan waktu QPU untuk menjalankan eksperimen ini adalah 2 detik.

1. Pengenalan algoritma Grover

Notebook ini adalah yang keempat dalam serangkaian kuliah tentang Jalur Menuju Utilitas dalam Komputasi Kuantum. Di notebook ini, kita akan belajar tentang algoritma Grover.

Algoritma Grover adalah salah satu algoritma kuantum yang paling terkenal karena percepatan kuadratiknya dibanding metode pencarian klasik. Dalam komputasi klasik, mencari database tak terurut dengan $N$ item membutuhkan kompleksitas waktu $O(N)$, artinya dalam kasus terburuk, seseorang mungkin harus memeriksa setiap item satu per satu. Namun, algoritma Grover memungkinkan kita mencapai pencarian ini dalam waktu $O(\sqrt{N})$, memanfaatkan prinsip-prinsip mekanika kuantum untuk mengidentifikasi item target secara lebih efisien.

Algoritma ini menggunakan amplifikasi amplitudo, yaitu proses yang meningkatkan amplitudo probabilitas dari state jawaban yang benar dalam superposisi kuantum, sehingga bisa diukur dengan probabilitas lebih tinggi. Percepatan ini membuat algoritma Grover berharga dalam berbagai aplikasi di luar pencarian database sederhana, terutama ketika ukuran dataset besar. Penjelasan rinci tentang algoritma ini tersedia di notebook algoritma Grover.

Struktur Dasar Algoritma Grover

Algoritma Grover terdiri dari empat komponen utama:

1. Inisialisasi: Menyiapkan superposisi atas semua state yang mungkin.
2. Oracle: Menerapkan fungsi oracle yang menandai state target dengan membalik fasenya.
3. Operator Difusi: Menerapkan serangkaian operasi untuk memperkuat probabilitas state yang ditandai.

Setiap langkah ini memainkan peran penting dalam membuat algoritma bekerja secara efisien. Penjelasan rinci untuk setiap langkah diberikan di bagian selanjutnya.

2. Mengimplementasikan Algoritma Grover

2.1 Persiapan

Impor library yang diperlukan dan siapkan lingkungan 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 ke Circuit dan operator kuantum

Pertimbangkan daftar 4 elemen, di mana tujuan kita adalah mengidentifikasi indeks elemen yang memenuhi kondisi tertentu. Misalnya, kita ingin menemukan indeks elemen yang sama dengan 2. Dalam contoh ini, state kuantum $|01\rangle$ mewakili indeks elemen yang memenuhi kondisi ini, karena menunjuk ke posisi di mana nilai 2 berada.

Langkah 2: Optimalkan untuk hardware target

1: Inisialisasi

Pada langkah inisialisasi, kita membuat superposisi dari semua state yang mungkin. Ini dicapai dengan menerapkan Gate Hadamard ke setiap Qubit dalam register n-Qubit, yang akan menghasilkan superposisi setara dari $2^n$ state. Secara matematis, ini bisa direpresentasikan sebagai:

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

di mana $N = 2^n$ adalah jumlah total state yang mungkin. Kita juga mengubah state bit ancilla menjadi $|-\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 bagian kunci dari algoritma Grover. Ia menandai state target dengan menerapkan pergeseran fase, biasanya membalik tanda amplitudo yang terkait dengan state tersebut. Oracle seringkali spesifik terhadap masalah dan dikonstruksi berdasarkan kriteria untuk mengidentifikasi state target. Secara matematis, oracle menerapkan transformasi berikut:

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

Pembalikan fase ini dicapai dengan menerapkan tanda negatif pada amplitudo state target melalui phase kickback.

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 Difusi

Proses amplifikasi amplitudo adalah yang membedakan algoritma Grover dari pencarian klasik. Setelah oracle menandai state target, kita menerapkan serangkaian operasi yang meningkatkan amplitudo state yang ditandai ini, membuatnya lebih mungkin untuk diamati saat pengukuran. Proses ini dicapai melalui Operator Difusi, yang secara efektif melakukan inversi di sekitar amplitudo rata-rata. Operasi matematisnya adalah sebagai berikut:

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

di mana $D$ adalah operator difusi, $I$ adalah matriks identitas, dan $|\psi\rangle$ adalah state superposisi setara. Kombinasi oracle dan operator difusi diterapkan sekitar $\sqrt{N}$ kali untuk mencapai probabilitas maksimum dalam mengukur state 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 pencarian Grover dengan 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: Pemrosesan hasil.

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Kita mendapatkan jawaban yang benar $|01\rangle$. Perhatikan bahwa hati-hati dengan urutan Qubit

3. Eksperimen dengan Perangkat Nyata

Langkah 2: Optimalkan untuk hardware target

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 men-transpile Circuit, Circuit tersebut dikonversi menjadi Circuit menggunakan Gate basis native dari perangkat.

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: Pemrosesan hasil.

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

4. Pencarian Grover dengan 3 Qubit

Sekarang, mari kita coba contoh pencarian Grover dengan 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 state "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$ diamati dengan probabilitas tertinggi, seperti yang diharapkan. Perhatikan bahwa dua iterasi adalah optimal dalam kasus ini. Namun, probabilitas mendapatkan jawaban yang benar tidak 100%, yang memang biasa dalam pencarian Grover.

Apa yang terjadi jika kita iterasi 3 kali?

Sekarang, mari kita coba iterasi sebanyak 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 diamati dengan probabilitas tertinggi, meski probabilitas mendapatkan jawaban yang benar sedikit berkurang.

Bagaimana kalau 4 kali?

Sekarang, mari kita coba iterasi sebanyak 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$ diamati dengan probabilitas terendah, dan probabilitas mendapatkan jawaban yang benar semakin berkurang. Ini menunjukkan pentingnya memilih jumlah iterasi yang optimal untuk algoritma Grover agar mendapatkan hasil terbaik.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'