Mga quantum algorithm: Grover Search at mga aplikasyon

tala

Atsushi Matsuo (Mayo 10, 2024)

I-download ang pdf ng orihinal na lektura. Tandaan na ang ilang code snippet ay maaaring maging deprecated dahil mga static na larawan ang mga ito.

Ang tinatayang QPU time para patakbuhin ang eksperimentong ito ay 2 segundo.

1. Panimula sa algoritmo ni Grover

Ang notebook na ito ang ikaapat sa isang serye ng mga lektura sa Path to Utility in Quantum Computing. Sa notebook na ito, matututunan natin ang tungkol sa algoritmo ni Grover.

Ang algoritmo ni Grover ay isa sa pinaka-kilalang quantum algorithm dahil sa quadratic speedup nito kumpara sa mga klasikal na paraan ng paghahanap. Sa klasikal na computing, ang paghahanap sa isang unsorted na database na may $N$ na elemento ay nangangailangan ng $O(N)$ na time complexity, ibig sabihin, sa pinakamasamang kaso, maaaring kailanganin pang suriin ang bawat elemento nang isa-isa. Gayunpaman, ang algoritmo ni Grover ay nagbibigay-daan sa atin na makamit ang paghahanap na ito sa loob ng $O(\sqrt{N})$ na oras, gamit ang mga prinsipyo ng quantum mechanics upang mas mahusay na matukoy ang target na elemento.

Gumagamit ang algoritmo ng amplitude amplification — isang proseso na nagpapataas ng probability amplitude ng tamang state sa isang quantum superposition, na nagbibigay-daan dito na masukat nang may mas mataas na posibilidad. Ang speedup na ito ay ginagawang mahalaga ang algoritmo ni Grover sa iba't ibang aplikasyon lampas sa simpleng paghahanap sa database, lalo na kapag malaki ang sukat ng dataset. Ang detalyadong paliwanag ng algoritmo ay makikita sa notebook ng algoritmo ni Grover.

Ang Pangunahing Estruktura ng Algoritmo ni Grover

Ang algoritmo ni Grover ay binubuo ng apat na pangunahing bahagi:

1. Initialization: Pag-set up ng superposition sa lahat ng posibleng estado.
2. Oracle: Pag-apply ng oracle function na nagtatanda sa target na estado sa pamamagitan ng pag-flip ng phase nito.
3. Diffusion Operator: Pag-apply ng serye ng mga operasyon upang palakasin ang posibilidad ng namarkahang estado.

Ang bawat isa sa mga hakbang na ito ay may mahalagang papel sa epektibong paggana ng algoritmo. Ang detalyadong paliwanag para sa bawat hakbang ay makikita sa ibaba.

2. Pag-implement ng Algoritmo ni Grover

2.1 Paghahanda

I-import ang mga kinakailangang library at i-set up ang kapaligiran para sa pagpapatakbo ng quantum circuit.

# 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

Hakbang 1: I-map ang problema sa mga quantum circuit at operator

Isaalang-alang ang isang listahan ng 4 na elemento, kung saan ang ating layunin ay tukuyin ang index ng elementong nakakatugon sa isang tiyak na kondisyon. Halimbawa, gusto nating hanapin ang index ng elementong katumbas ng 2. Sa halimbawang ito, ang quantum state na $|01\rangle$ ay kumakatawan sa index ng elementong nakakatugon sa kondisyong ito, dahil itinuturo nito ang posisyon kung saan matatagpuan ang value na 2.

Hakbang 2: I-optimize para sa target na hardware

1: Initialization

Sa hakbang ng initialization, gumagawa tayo ng superposition ng lahat ng posibleng estado. Nakamit ito sa pamamagitan ng pag-apply ng Hadamard gate sa bawat qubit sa isang n-qubit register, na magreresulta sa pantay na superposition ng $2^n$ na estado. Sa matematika, maaari itong ilarawan bilang:

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

kung saan ang $N = 2^n$ ang kabuuang bilang ng mga posibleng estado. Binabago rin natin ang estado ng ancilla bit sa $|-\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

Ang oracle ay isang pangunahing bahagi ng algoritmo ni Grover. Tinatanda nito ang target na estado sa pamamagitan ng pag-apply ng phase shift, na karaniwang inii-flip ang tanda ng amplitude na nauugnay sa estado na iyon. Ang oracle ay madalas na spesipiko sa problema at itinayo batay sa pamantayan para sa pagtukoy ng target na estado. Sa matematika, inaaplika ng oracle ang sumusunod na transpormasyong:

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

Ang phase flip na ito ay nakamit sa pamamagitan ng pag-apply ng negatibong tanda sa amplitude ng target na estado gamit ang 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: Diffusion Operator

Ang proseso ng amplitude amplification ang nagtatangi sa algoritmo ni Grover mula sa klasikal na paghahanap. Pagkatapos markahan ng oracle ang target na estado, nag-a-apply tayo ng serye ng mga operasyon na nagpapataas ng amplitude ng namarkahang estado na ito, na ginagawa itong mas malamang na maobserbahan kapag sinukat. Ang prosesong ito ay nakamit sa pamamagitan ng Diffusion operator, na epektibong gumaganap ng inversion tungkol sa average amplitude. Ang operasyong matematika ay ang sumusunod:

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

kung saan ang $D$ ang diffusion operator, ang $I$ ang identity matrix, at ang $|\psi\rangle$ ang pantay na superposition state. Ang kombinasyon ng oracle at ng diffusion operator ay inilalapat nang humigit-kumulang $\sqrt{N}$ na beses upang makamit ang pinakamataas na posibilidad sa pagsukat ng namarkahang estado.

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 Isang halimbawa ng 2-qubit Grover search.

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 Eksperimento gamit ang mga Simulator

Hakbang 3: Pagpapatakbo ng 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()

Hakbang 4: Post-processing ng mga resulta.

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

Nakuha natin ang tamang sagot na $|01\rangle$. Tandaan na mag-ingat sa pagkakasunud-sunod ng mga qubit.

3. Eksperimento gamit ang Tunay na Device

Hakbang 2: I-optimize para sa target na hardware

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)

Sa pag-transpile ng circuit, na-convert ito sa isang circuit gamit ang native basis gates ng device.

Hakbang 3: Pagpapatakbo ng 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}

Hakbang 4: Post-processing ng mga resulta.

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

4. Isang 3-qubit Grover Search

Ngayon, subukan natin ang isang halimbawa ng 3-qubit Grover search.

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

Sa pagkakataong ito, ang $|111\rangle$ ang "tamang" estado.

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

Ang $|0111\rangle$ ay naobserbahan na may pinakamataas na posibilidad, gaya ng inaasahan. Tandaan na ang dalawang iteration ay optimal sa kasong ito. Gayunpaman, ang posibilidad ng pagkuha ng tamang sagot ay hindi 100%, na karaniwan sa Grover's search.

Ano ang mangyayari kung mag-iterate tayo nang 3 beses?

Ngayon, subukan nating mag-iterate nang 3 beses.

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}

Ang $|0111\rangle$ ay nananatiling naobserbahan na may pinakamataas na posibilidad, bagaman ang posibilidad ng pagkuha ng tamang sagot ay bahagyang bumaba.

Paano naman kung 4 na beses?

Ngayon, subukan nating mag-iterate nang 4 na beses.

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}

Ang $|0111\rangle$ ay naobserbahan na may pinakamababang posibilidad, at ang posibilidad ng pagkuha ng tamang sagot ay lalo pang bumaba. Ipinapakita nito ang kahalagahan ng pagpili ng tamang bilang ng mga iteration para sa algoritmo ni Grover upang makamit ang pinakamahusay na resulta.

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'