אלגוריתם גרובר

הערכת שימוש: פחות מדקה על מעבד Eagle r3 (הערה: זוהי הערכה בלבד. זמן הריצה בפועל עשוי להשתנות.)

תוצאות למידה

לאחר השלמת מדריך זה, אפשר לצפות שתבין את המידע הבא:

• כיצד לבנות אורקלים של גרובר המסמנים מצב אחד או יותר של בסיס חישובי
• כיצד להשתמש בפונקציה grover_operator() מספריית המעגלים של Qiskit
• כיצד לקבוע את מספר האיטרציות האופטימלי של גרובר לבעיה נתונה
• כיצד להפעיל את אלגוריתם גרובר באמצעות הפרימיטיב Sampler של Qiskit Runtime

דרישות קדם

מומלץ להתוודע לנושאים הבאים:

• יסודות האלגוריתמים הקוונטיים: אלגוריתם גרובר
• יסודות מידע קוונטי

רקע

הגברת משרעת (Amplitude Amplification) היא אלגוריתם קוונטי כללי, או שגרת עזר, שניתן להשתמש בה להשגת האצה ריבועית על פני מספר אלגוריתמים קלאסיים. אלגוריתם גרובר היה הראשון להדגים האצה זו על בעיות חיפוש לא-מובנות. ניסוח בעיית חיפוש של גרובר מצריך פונקציית אורקל המסמנת מצב אחד או יותר של בסיס חישובי כמצבים שאנו מעוניינים למצוא, ומעגל הגברה המגדיל את המשרעת של המצבים המסומנים תוך דיכוי שאר המצבים.

כאן, נדגים כיצד לבנות אורקלים של גרובר ולהשתמש ב-grover_operator() מספריית המעגלים של Qiskit להגדרה קלה של מופע חיפוש גרובר. הפרימיטיב Sampler של Runtime מאפשר ביצוע חלק של מעגלי גרובר.

דרישות מקדימות

לפני תחילת המדריך, ודא שהדברים הבאים מותקנים:

• Qiskit SDK גרסה 2.0 ומעלה, עם תמיכה ב-visualization
• Qiskit Runtime גרסה 0.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

דוגמת סימולטור בקנה מידה קטן

בסעיף זה, נעבור שלב אחר שלב על אלגוריתם גרובר בקנה מידה קטן באמצעות סימולטור מקומי, לפני הרצת אותה בעיה על חומרה קוונטית אמיתית.

שלב 1: מיפוי קלט קלאסי לבעיה קוונטית

אלגוריתם גרובר מצריך אורקל המציין מצב אחד או יותר של בסיס חישובי מסומן, כאשר "מסומן" משמעותו מצב עם פאזה של -1. שער Z-מבוקר, או הכללתו הרב-מבוקרת על $N$ קיוביטים, מסמן את המצב $2^{N}-1$ (מחרוזת הביטים '1'*$N$). סימון מצבי בסיס עם '0' אחד או יותר בייצוג הבינארי מצריך הפעלת שערי X על הקיוביטים המתאימים לפני ואחרי שער ה-Z-המבוקר; שקול לשליטה פתוחה על אותו קיוביט. בקוד הבא, אנחנו מגדירים אורקל שעושה בדיוק זאת, ומסמן מצב אחד או יותר של בסיס קלט המוגדרים דרך ייצוג מחרוזת הביטים שלהם. שער ה-MCMT משמש למימוש שער ה-Z הרב-מבוקר.

מופע ספציפי של גרובר

כעת שיש לנו את פונקציית האורקל, נוכל להגדיר מופע ספציפי של חיפוש גרובר. בדוגמה זו נסמן שני מצבים חישוביים מתוך שמונת המצבים הזמינים במרחב החישובי בן שלושת הקיוביטים:

marked_states = ["011", "100"]

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

אופרטור גרובר

הפונקציה המובנית grover_operator() של Qiskit מקבלת מעגל אורקל ומחזירה מעגל המורכב ממעגל האורקל עצמו ומעגל שמגביר את המצבים המסומנים על ידי האורקל. כאן, אנחנו משתמשים בשיטת decompose() על המעגל כדי לראות את השערים בתוך האופרטור:

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

יישומים חוזרים של מעגל grover_op זה מגבירים את המצבים המסומנים, הופכים אותם למחרוזות הביטים בעלות הסבירות הגבוהה ביותר בהתפלגות הפלט מהמעגל. קיים מספר אופטימלי של יישומים כאלה הנקבע לפי יחס המצבים המסומנים למספר הכולל של המצבים החישוביים האפשריים:

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

מעגל גרובר המלא

ניסוי גרובר מלא מתחיל בשער Hadamard על כל קיוביט, ויוצר סופרפוזיציה אחידה של כל מצבי הבסיס החישובי, ולאחר מכן האופרטור grover_op מיושם מספר האיטרציות האופטימלי. כאן אנחנו עושים שימוש בשיטת QuantumCircuit.power(INT) להפעלה חוזרת של אופרטור גרובר.

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

שלב 2: אופטימיזציה של הבעיה לביצוע על חומרה קוונטית

לסימולציה בקנה מידה קטן, אנו מבצעים טרנספילציה של המעגל ללא מיקוד לחומרה ספציפית.

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

שלב 3: ביצוע באמצעות פרימיטיבים של Qiskit

הגברת משרעת היא בעיית דגימה המתאימה לביצוע עם הפרימיטיב SamplerV2. כאן אנחנו משתמשים ב-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)

דוגמת חומרה

שלבים 1–4

אלגוריתם גרובר הוא ביסודו אלגוריתם עמיד-לשגיאות — שערי ה-Z הרב-מבוקרים בלב האורקל ואופרטור ההפצה מובילים לעומקי שערים דו-קיוביטיים הגדלים במהירות רבה עם מספר הקיוביטים (כפי שנדגים בסעיף הבא). משמעות הדבר היא שהאלגוריתם אינו מתרחב היטב על חומרה רועשת כיום. מסיבה זו, אנו מדגימים את הביצוע על חומרה באותו קנה מידה קטן כמו דוגמת הסימולטור לעיל, במקום לנסות גודל בעיה גדול יותר.

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

דיון: סקלאביליות עומק השערים הדו-קיוביטיים

סיבה מרכזית לכך שאלגוריתם גרובר נחשב לאלגוריתם עמיד-לשגיאות היא הגידול המהיר בעומק השערים הדו-קיוביטיים של המעגל ככל שמספר הקיוביטים עולה. שער ה-Z הרב-מבוקר בלב האורקל ואופרטור ההפצה מתפרק למספר שערים דו-קיוביטיים הגדל בצורה אקספוננציאלית עם מספר קיוביטי הבקרה. בשילוב עם העובדה שמספר האיטרציות האופטימלי של גרובר עצמו גדל כ-$O(\sqrt{2^n})$, העומק הדו-קיוביטי הכולל הופך במהרה לבלתי מעשי עבור חומרה רועשת.

להלן אנו בונים מעגלי גרובר עבור מספרי קיוביטים עולים, מבצעים טרנספילציה, ומשרטטים את עומק השערים הדו-קיוביטיים המתקבל כדי להמחיש סקלאביליות זו.

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

כפי שמראה הגרף, עומק השערים הדו-קיוביטיים גדל במהירות רבה מאוד עם מספר הקיוביטים — בקירוב אקספוננציאלי. הדבר הופך את אלגוריתם גרובר לבלתי מעשי על חומרה קוונטית רועשת כיום מעבר לגדלי בעיה קטנים מאוד. האלגוריתם נשאר יעד חשוב עבור מחשבים קוונטיים עמידי-שגיאות עתידיים, שבהם תיקון שגיאות יאפשר ביצוע מעגלים עמוקים באופן אמין.

צעדים הבאים

המלצות

אם מצאת עבודה זו מעניינת, ייתכן שיעניינו אותך החומרים הבאים:

• ספריית מעגלים של Qiskit: תיעוד API של grover_operator()
• מדריך QAOA ושיעור QAOA בקנה מידה שימושי מציגים דוגמאות לטווח קצר של אופטימיזציה עם מחשבים קוונטיים
• להעמקה נוספת באלגוריתמים לטווח קצר, ראה את הקורס מחשוב קוונטי בפועל