ข้ามไปยังเนื้อหาหลัก

อัลกอริทึมของ Grover

ประมาณการใช้งาน: ไม่ถึงหนึ่งนาทีบน Eagle r3 processor (หมายเหตุ: นี่เป็นเพียงการประมาณเท่านั้น ระยะเวลาที่ใช้จริงอาจแตกต่างกันไป)

ผลลัพธ์การเรียนรู้​

หลังจากทำบทเรียนนี้แล้ว คุณจะสามารถเข้าใจข้อมูลต่อไปนี้:

  • วิธีสร้าง Grover oracles ที่ทำเครื่องหมาย computational basis states หนึ่งรายการหรือมากกว่า
  • วิธีใช้ฟังก์ชัน grover_operator() จาก Qiskit circuit library
  • วิธีกำหนดจำนวนรอบ Grover ที่เหมาะสมที่สุดสำหรับปัญหาที่กำหนด
  • วิธีรันอัลกอริทึมของ Grover ด้วย Qiskit Runtime Sampler primitive

ข้อกำหนดเบื้องต้น​

แนะนำให้ทำความคุ้นเคยกับหัวข้อเหล่านี้:

พื้นหลัง​

Amplitude amplification เป็นอัลกอริทึมหรือ subroutine เชิงควอนตัมอเนกประสงค์ที่สามารถใช้เพื่อให้ได้ความเร็วแบบ quadratic เหนืออัลกอริทึมคลาสสิกบางประเภท อัลกอริทึมของ Grover เป็นอัลกอริทึมแรกที่แสดงให้เห็นถึงความเร็วนี้สำหรับปัญหาการค้นหาแบบไม่มีโครงสร้าง การกำหนดปัญหาการค้นหาของ Grover ต้องการฟังก์ชัน oracle ที่ทำเครื่องหมาย computational basis states หนึ่งรายการขึ้นไปว่าเป็น states ที่เราต้องการค้นหา และ amplification circuit ที่เพิ่ม amplitude ของ states ที่ถูกทำเครื่องหมาย ส่งผลให้ states ที่เหลือถูกกดทับลง

ที่นี่เราจะสาธิตวิธีสร้าง Grover oracles และใช้ grover_operator() จาก Qiskit circuit library เพื่อตั้งค่า Grover's search instance ได้อย่างง่ายดาย Sampler primitive ของ runtime ช่วยให้รัน Grover circuits ได้อย่างราบรื่น

ความต้องการ​

ก่อนเริ่มบทเรียนนี้ โปรดตรวจสอบให้แน่ใจว่าติดตั้งสิ่งต่อไปนี้แล้ว:

  • Qiskit SDK v2.0 ขึ้นไป พร้อมรองรับ visualization
  • Qiskit Runtime v0.22 ขึ้นไป (pip install qiskit-ibm-runtime)

การตั้งค่า​

# Added by doQumentation — required packages for this notebook
!pip install -q matplotlib 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

ตัวอย่างด้วย simulator ขนาดเล็ก​

ในส่วนนี้เราจะอธิบายแต่ละขั้นตอนของอัลกอริทึมของ Grover ในระดับเล็กโดยใช้ local simulator ก่อนที่จะรันปัญหาเดียวกันบน quantum hardware จริง

ขั้นตอนที่ 1: แปลง input คลาสสิกให้เป็นปัญหาควอนตัม​

อัลกอริทึมของ Grover ต้องการ oracle ที่ระบุ computational basis states หนึ่งรายการขึ้นไปที่ถูกทำเครื่องหมาย โดย "ทำเครื่องหมาย" หมายถึง state ที่มี phase เป็น -1 controlled-Z gate หรือ multi-controlled generalization บน NN qubits จะทำเครื่องหมาย 2N−12^{N}-1 state ('1'*NN bit-string) การทำเครื่องหมาย basis states ที่มี '0' หนึ่งตัวขึ้นไปในการแทนแบบไบนารีต้องใช้ X-gates บน qubits ที่เกี่ยวข้องก่อนและหลัง controlled-Z gate ซึ่งเทียบเท่ากับการมี open-control บน qubit นั้น ในโค้ดต่อไปนี้เราจะกำหนด oracle ที่ทำเครื่องหมาย basis states หนึ่งรายการขึ้นไปตามที่กำหนดผ่าน bitstring representation ของพวกมัน MCMT gate ถูกใช้เพื่อสร้าง multi-controlled Z-gate

Grover's instance เฉพาะ​

เมื่อมีฟังก์ชัน oracle แล้ว เราสามารถกำหนด Grover search instance เฉพาะได้ ในตัวอย่างนี้เราจะทำเครื่องหมาย computational states สองรายการจากทั้งหมดแปดรายการที่มีใน three-qubit computational space:

marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

Output of the previous code cell

Grover operator​

grover_operator() ที่มีอยู่ใน Qiskit รับ oracle circuit แล้วคืน circuit ที่ประกอบด้วย oracle circuit เองและ circuit ที่ขยาย amplitude ของ states ที่ถูกทำเครื่องหมายโดย oracle ที่นี่เราใช้ method decompose() บน circuit เพื่อดู gates ภายใน operator:

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")

Output of the previous code cell

การนำ grover_op circuit นี้มาใช้ซ้ำหลายครั้งจะขยาย amplitude ของ states ที่ถูกทำเครื่องหมาย ทำให้กลายเป็น bit-strings ที่มีความน่าจะเป็นสูงสุดใน output distribution ของ circuit จำนวนครั้งที่ใช้ที่เหมาะสมที่สุดถูกกำหนดโดยอัตราส่วนของ states ที่ถูกทำเครื่องหมายต่อจำนวน computational states ทั้งหมดที่เป็นไปได้:

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

Full Grover circuit​

การทดลอง Grover ที่สมบูรณ์เริ่มต้นด้วย Hadamard gate บนแต่ละ qubit เพื่อสร้าง superposition ที่สม่ำเสมอของ computational basis states ทั้งหมด ตามด้วย Grover operator (grover_op) ที่ทำซ้ำตามจำนวนครั้งที่เหมาะสม ที่นี่เราใช้ method QuantumCircuit.power(INT) เพื่อนำ Grover operator มาใช้ซ้ำ

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

Output of the previous code cell

ขั้นตอนที่ 2: ปรับปัญหาให้เหมาะสมสำหรับการรันบน quantum hardware​

สำหรับการจำลองขนาดเล็กนี้ เราจะ transpile circuit โดยไม่กำหนด hardware เฉพาะ

pm = generate_preset_pass_manager(optimization_level=3)
circuit_isa = pm.run(qc)
circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

Output of the previous code cell

ขั้นตอนที่ 3: รันด้วย Qiskit primitives​

Amplitude amplification เป็นปัญหาแบบ sampling ที่เหมาะสำหรับการรันด้วย SamplerV2 primitive ที่นี่เราใช้ StatevectorSampler จาก qiskit.primitives สำหรับการจำลองในเครื่อง

from qiskit.primitives import StatevectorSampler

sampler = StatevectorSampler()
result = sampler.run([circuit_isa], shots=10_000).result()
dist = result[0].data.meas.get_counts()

ขั้นตอนที่ 4: ประมวลผลและแสดงผลลัพธ์ในรูปแบบคลาสสิกที่ต้องการ​

plot_distribution(dist)

Output of the previous code cell

ตัวอย่างบน Hardware​

ขั้นตอนที่ 1-4​

อัลกอริทึมของ Grover เป็นอัลกอริทึมที่ต้องการ fault tolerance โดยพื้นฐาน — multi-controlled Z gates ที่เป็นหัวใจของ oracle และ diffusion operator นำไปสู่ความลึกของ two-qubit gate ที่เพิ่มขึ้นอย่างรวดเร็วมากตามจำนวน qubits (ดังที่เราจะแสดงในส่วนถัดไป) ซึ่งหมายความว่าอัลกอริทึมไม่สามารถขยายขนาดได้ดีบน hardware ที่มีสัญญาณรบกวนในปัจจุบัน ด้วยเหตุนี้เราจึงสาธิตการรันบน hardware ในขนาดเล็กเดียวกับตัวอย่าง simulator ข้างต้น แทนที่จะพยายามแก้ปัญหาขนาดใหญ่กว่า

# -------------------------Step 1-------------------------
marked_states = ["011", "100"]

oracle = grover_oracle(marked_states)
grover_op = grover_operator(oracle)

optimal_num_iterations = math.floor(
    math.pi
    / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)

qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

# -------------------------Step 2-------------------------
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

# -------------------------Step 3-------------------------
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
sampler.options.environment.job_tags = ["TUT-GA"]
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# -------------------------Step 4-------------------------
plot_distribution(dist)

Output of the previous code cell

การอภิปราย: การขยายขนาดความลึกของ two-qubit gate​

เหตุผลสำคัญที่อัลกอริทึมของ Grover ถือเป็นอัลกอริทึมที่ต้องการ fault tolerance คือการเติบโตอย่างรวดเร็วของความลึกของ two-qubit gate ของ circuit เมื่อจำนวน qubits เพิ่มขึ้น multi-controlled Z gate ที่เป็นแกนกลางของทั้ง oracle และ diffusion operator จะแตกตัวเป็น two-qubit gates จำนวนหนึ่งที่เพิ่มขึ้นแบบ exponential ตามจำนวน control qubits รวมกับความจริงที่ว่าจำนวนรอบ Grover ที่เหมาะสมที่สุดเองก็เติบโตในลำดับ O(2n)O(\sqrt{2^n}) ทำให้ความลึกของ two-qubit โดยรวมกลายเป็นสิ่งที่ไม่สามารถปฏิบัติได้สำหรับ hardware ที่มีสัญญาณรบกวนอย่างรวดเร็ว

ด้านล่างนี้เราสร้าง Grover circuits สำหรับจำนวน qubit ที่เพิ่มขึ้น ทำการ transpile และ plot ความลึกของ two-qubit gate ที่ได้เพื่อแสดงการขยายขนาดนี้

import matplotlib.pyplot as plt

num_qubits_list = list(range(3, 10))
two_q_depths = []
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
for n in num_qubits_list:
    # Mark a single state for simplicity
    marked = ["1" * n]
    oracle_n = grover_oracle(marked)
    grover_op_n = grover_operator(oracle_n)

    # Optimal number of iterations
    num_iters = math.floor(
        math.pi / (4 * math.asin(math.sqrt(len(marked) / 2**n)))
    )

    # Build the full Grover circuit
    qc_n = QuantumCircuit(n)
    qc_n.h(range(n))
    qc_n.compose(grover_op_n.power(num_iters), inplace=True)
    qc_n.measure_all()

    # Transpile to a basis gate set and count 2Q depth
    pm_n = generate_preset_pass_manager(backend=backend, optimization_level=3)
    qc_transpiled = pm_n.run(qc_n)

    # Compute depth restricted to 2-qubit operations
    depth_2q = qc_transpiled.depth(lambda x: x.operation.num_qubits == 2)

    two_q_depths.append(depth_2q)
    print(f"n={n}: optimal_iters={num_iters}, 2Q depth={depth_2q}")

# Plot
fig, ax = plt.subplots(figsize=(8, 5))
ax.plot(
    num_qubits_list,
    two_q_depths,
    "o-",
    linewidth=2,
    markersize=8,
    color="#6929C4",
)
ax.set_xlabel("Number of qubits", fontsize=13)
ax.set_ylabel("Two-qubit gate depth", fontsize=13)
ax.set_title("Grover's algorithm: 2Q depth scaling", fontsize=14)
ax.set_yscale("log")
ax.grid(True, alpha=0.3)
ax.set_xticks(num_qubits_list)
plt.tight_layout()
plt.show()
n=3: optimal_iters=2, 2Q depth=39
n=4: optimal_iters=3, 2Q depth=111
n=5: optimal_iters=4, 2Q depth=466
n=6: optimal_iters=6, 2Q depth=1646
n=7: optimal_iters=8, 2Q depth=3550
n=8: optimal_iters=12, 2Q depth=7989
n=9: optimal_iters=17, 2Q depth=14824

Output of the previous code cell

ดังที่แสดงในกราฟ ความลึกของ two-qubit gate เติบโตอย่างรวดเร็วมากตามจำนวน qubits — โดยประมาณแบบ exponential ทำให้อัลกอริทึมของ Grover ไม่สามารถใช้งานได้จริงบน quantum hardware ที่มีสัญญาณรบกวนในปัจจุบันสำหรับขนาดปัญหาที่ใหญ่กว่าขนาดเล็กมาก อัลกอริทึมนี้ยังคงเป็นเป้าหมายสำคัญสำหรับ quantum computer ที่ทนทานต่อความผิดพลาดในอนาคต ซึ่งการแก้ไขข้อผิดพลาดจะช่วยให้สามารถรัน circuits ที่ลึกได้อย่างน่าเชื่อถือ

ขั้นตอนถัดไป​

คำแนะนำ

หากคุณพบว่าเนื้อหานี้น่าสนใจ คุณอาจสนใจเนื้อหาต่อไปนี้:

แหล่งที่มา: IBM Quantum docs — อัปเดตเมื่อ 8 พ.ค. 2569
เวอร์ชันภาษาอังกฤษ บน doQumentation — อัปเดตเมื่อ 8 พ.ค. 2569
การแปลนี้อิงตามเวอร์ชันภาษาอังกฤษวันที่ 9 เม.ย. 2569
ปัญหาเกี่ยวกับเว็บไซต์หรือการแปล?ปัญหาเกี่ยวกับเนื้อหา? แก้ไขที่ IBM Quantum docs