Quantum algorithms: Grover Search และการประยุกต์ใช้

หมายเหตุ

Atsushi Matsuo (May 10, 2024)

ดาวน์โหลด pdf ของบรรยายต้นฉบับ โปรดทราบว่าโค้ดบางส่วนอาจล้าสมัยเนื่องจากเป็นภาพนิ่ง

เวลา QPU โดยประมาณในการรันการทดลองนี้คือ 2 วินาที

1. บทนำสู่อัลกอริทึมของ Grover

Notebook นี้เป็นบทที่สี่ในซีรีส์การบรรยายเรื่อง Path to Utility in Quantum Computing ในบทนี้เราจะเรียนรู้เกี่ยวกับอัลกอริทึมของ Grover

อัลกอริทึมของ Grover เป็นหนึ่งในอัลกอริทึมควอนตัมที่รู้จักกันดีที่สุดเนื่องจากความเร็วกำลังสองเหนือวิธีการค้นหาแบบคลาสสิก ในการประมวลผลแบบคลาสสิก การค้นหาฐานข้อมูลที่ไม่ได้เรียงลำดับขนาด $N$ รายการต้องใช้ time complexity $O(N)$ ซึ่งในกรณีเลวร้ายที่สุด อาจต้องตรวจสอบแต่ละรายการทีละรายการ อย่างไรก็ตาม อัลกอริทึมของ Grover ช่วยให้เราทำการค้นหานี้ได้ในเวลา $O(\sqrt{N})$ โดยใช้หลักการของกลศาสตร์ควอนตัมเพื่อระบุรายการเป้าหมายได้อย่างมีประสิทธิภาพมากขึ้น

อัลกอริทึมใช้ amplitude amplification ซึ่งเป็นกระบวนการที่เพิ่ม probability amplitude ของ state คำตอบที่ถูกต้องใน quantum superposition ทำให้สามารถวัดได้ด้วยความน่าจะเป็นที่สูงขึ้น ความเร็วนี้ทำให้อัลกอริทึมของ Grover มีคุณค่าในแอปพลิเคชันต่าง ๆ นอกเหนือจากการค้นหาฐานข้อมูลง่าย ๆ โดยเฉพาะเมื่อขนาดของ dataset ใหญ่ คำอธิบายโดยละเอียดของอัลกอริทึมมีให้ใน Grover's algorithm notebook

โครงสร้างพื้นฐานของอัลกอริทึมของ Grover

อัลกอริทึมของ Grover ประกอบด้วยส่วนประกอบหลักสี่อย่าง:

1. การ initialize: ตั้งค่า superposition บน states ที่เป็นไปได้ทั้งหมด
2. Oracle: ใช้ฟังก์ชัน oracle ที่ทำเครื่องหมาย target state โดยการพลิก phase ของมัน
3. Diffusion Operator: ใช้ชุดของการดำเนินการเพื่อขยาย probability ของ marked state

แต่ละขั้นตอนเหล่านี้มีบทบาทสำคัญในการทำให้อัลกอริทึมทำงานได้อย่างมีประสิทธิภาพ คำอธิบายโดยละเอียดสำหรับแต่ละขั้นตอนมีให้ในภายหลัง

2. การ implement อัลกอริทึมของ Grover

2.1 การเตรียมความพร้อม

Import libraries ที่จำเป็นและตั้งค่าสภาพแวดล้อมสำหรับรัน quantum circuit

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"qiskit": "qiskit", "qiskit_aer": "qiskit-aer", "qiskit_ibm_runtime": "qiskit-ibm-runtime"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

%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

ขั้นตอนที่ 1: แมปปัญหาไปยัง quantum circuits และ operators

พิจารณาลิสต์ที่มี 4 elements โดยเป้าหมายของเราคือระบุ index ของ element ที่ตรงตามเงื่อนไขเฉพาะ ตัวอย่างเช่น เราต้องการหา index ของ element ที่มีค่าเท่ากับ 2 ในตัวอย่างนี้ quantum state $|01\rangle$ แทน index ของ element ที่ตรงตามเงื่อนไขนี้ เนื่องจากมันชี้ไปยังตำแหน่งที่ค่า 2 อยู่

ขั้นตอนที่ 2: Optimize สำหรับ hardware เป้าหมาย

1: การ Initialize

ในขั้นตอนการ initialize เราสร้าง superposition ของ states ที่เป็นไปได้ทั้งหมด ทำได้โดยการใช้ Hadamard gate กับแต่ละ Qubit ใน n-qubit register ซึ่งจะให้ equal superposition ของ $2^n$ states ในทางคณิตศาสตร์ สามารถแสดงได้ดังนี้:

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

โดยที่ $N = 2^n$ คือจำนวน states ที่เป็นไปได้ทั้งหมด นอกจากนี้เราเปลี่ยน state ของ ancilla bit เป็น $|-\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 เป็นส่วนสำคัญของอัลกอริทึมของ Grover มันทำเครื่องหมาย target state โดยการใช้ phase shift โดยทั่วไปจะพลิก sign ของ amplitude ที่เกี่ยวข้องกับ state นั้น Oracle มักเฉพาะปัญหาและสร้างขึ้นตามเกณฑ์ในการระบุ target state ในทางคณิตศาสตร์ oracle ใช้การแปลงต่อไปนี้:

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

การพลิก phase นี้ทำได้โดยการใช้ negative sign กับ amplitude ของ target state ผ่าน 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

กระบวนการ amplitude amplification คือสิ่งที่ทำให้อัลกอริทึมของ Grover แตกต่างจากการค้นหาแบบคลาสสิก หลังจาก oracle ทำเครื่องหมาย target state แล้ว เราใช้ชุดของการดำเนินการที่เพิ่ม amplitude ของ marked state ทำให้มีโอกาสถูกสังเกตเห็นเมื่อวัดมากขึ้น กระบวนการนี้ทำได้ผ่าน Diffusion operator ซึ่งดำเนินการ inversion about the average amplitude อย่างมีประสิทธิภาพ การดำเนินการทางคณิตศาสตร์เป็นดังนี้:

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

โดยที่ $D$ คือ diffusion operator, $I$ คือ identity matrix และ $|\psi\rangle$ คือ equal superposition state การรวมกันของ oracle และ diffusion operator ถูกใช้ประมาณ $\sqrt{N}$ ครั้งเพื่อให้ได้ probability สูงสุดสำหรับการวัด marked state

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 ตัวอย่าง Grover search แบบ 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 ทดลองกับ Simulators

ขั้นตอนที่ 3: รัน 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()

ขั้นตอนที่ 4: Post-processing ผลลัพธ์

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

# Plot the counts in a histogram
plot_histogram(counts)

{'001': 1024}

เราได้คำตอบที่ถูกต้อง $|01\rangle$ โปรดระวังลำดับของ qubits

3. ทดลองกับอุปกรณ์จริง

ขั้นตอนที่ 2: Optimize สำหรับ 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)

โดยการ transpile circuit มันถูกแปลงเป็น circuit ที่ใช้ native basis gates ของอุปกรณ์

ขั้นตอนที่ 3: รัน 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}

ขั้นตอนที่ 4: Post-processing ผลลัพธ์

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

4. Grover Search แบบ 3-qubit

มาลองตัวอย่าง Grover search แบบ 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()

คราวนี้ $|111\rangle$ คือ state "ดี"

# 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$ ถูกสังเกตเห็นด้วยความน่าจะเป็นสูงสุดตามที่คาดไว้ โปรดทราบว่าสองรอบนั้น optimal ในกรณีนี้ อย่างไรก็ตาม ความน่าจะเป็นของการได้คำตอบที่ถูกต้องไม่ใช่ 100% ซึ่งเป็นเรื่องปกติใน Grover's search

จะเกิดอะไรขึ้นถ้าทำซ้ำ 3 ครั้ง?

มาลองทำซ้ำ 3 ครั้งกัน

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$ ยังคงถูกสังเกตเห็นด้วยความน่าจะเป็นสูงสุด แต่ความน่าจะเป็นของการได้คำตอบที่ถูกต้องลดลงเล็กน้อย

แล้ว 4 ครั้งล่ะ?

มาลองทำซ้ำ 4 ครั้งกัน

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$ ถูกสังเกตเห็นด้วยความน่าจะเป็นต่ำสุด และความน่าจะเป็นของการได้คำตอบที่ถูกต้องลดลงอีก สิ่งนี้แสดงให้เห็นถึงความสำคัญของการเลือกจำนวนรอบที่ optimal สำหรับอัลกอริทึมของ Grover เพื่อให้ได้ผลลัพธ์ที่ดีที่สุด

# See the version of Qiskit
import qiskit

qiskit.__version__

'2.0.2'