خوارزمية غروفر

تقدير الاستخدام: أقل من دقيقة على معالج Eagle r3 (ملاحظة: هذا تقدير فحسب. قد يختلف وقت التشغيل الفعلي لديك.)

نتائج التعلم

بعد إتمام هذا البرنامج التعليمي، يُتوقع منك فهم المعلومات التالية:

• كيفية بناء oracle لغروفر تُعلّم حالة أو أكثر من حالات قاعدة الحساب
• كيفية استخدام دالة grover_operator() من مكتبة دوائر Qiskit
• كيفية تحديد العدد الأمثل من تكرارات غروفر لمسألة معينة
• كيفية تنفيذ خوارزمية غروفر باستخدام الـ primitive الخاص بـ Sampler في Qiskit Runtime

المتطلبات الأساسية

يُوصى بالتعرف على هذه الموضوعات:

• أساسيات الخوارزميات الكمومية: خوارزمية غروفر
• أساسيات المعلومات الكمومية

الخلفية

تضخيم السعة (Amplitude amplification) هو خوارزمية كمومية عامة الأغراض، أو روتين فرعي، يمكن استخدامه لتحقيق تسريع تربيعي مقارنةً بعدد من الخوارزميات الكلاسيكية. كانت خوارزمية غروفر الأولى التي تُظهر هذا التسريع في مسائل البحث غير المنظمة. تتطلب صياغة مسألة بحث غروفر دالة oracle تُعلّم حالة أو أكثر من حالات قاعدة الحساب بوصفها الحالات التي نسعى إلى إيجادها، ودائرة تضخيم ترفع سعة الحالات المعلَّمة، مما يُخفّض سعة الحالات المتبقية بالتبعية.

نوضّح هنا كيفية بناء oracle لغروفر واستخدام grover_operator() من مكتبة دوائر Qiskit لإعداد نسخة من بحث غروفر بسهولة. يتيح الـ primitive الخاص بـ Sampler في وقت التشغيل تنفيذ دوائر غروفر بسلاسة.

المتطلبات

قبل البدء في هذا البرنامج التعليمي، تأكد من تثبيت ما يلي:

• Qiskit SDK الإصدار 2.0 أو أحدث، مع دعم التصور البصري
• 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: تحويل المدخلات الكلاسيكية إلى مسألة كمومية

تتطلب خوارزمية غروفر oracle يُحدد حالة أو أكثر من حالات قاعدة الحساب المعلَّمة، حيث تعني "المعلَّمة" حالةً ذات طور يساوي -1. تُعلّم بوابة controlled-Z، أو تعميمها متعدد التحكم على $N$ كيوبت، الحالة $2^{N}-1$ (سلسلة البتات '1'*$N$). يتطلب تعليم حالات قاعدة الحساب التي تحتوي على '0' واحدة أو أكثر في التمثيل الثنائي تطبيق بوابات X على الكيوبتات المقابلة قبل بوابة controlled-Z وبعدها، وهو ما يُعادل وجود تحكم مفتوح (open-control) على ذلك الكيوبت. في الكود التالي، نُعرّف oracle يُعلّم حالة أو أكثر من حالات قاعدة المدخلات المُعرَّفة عبر تمثيلها بسلسلة البتات. تُستخدم بوابة MCMT لتنفيذ بوابة Z متعددة التحكم.

نسخة محددة من بحث غروفر

بعد أن أصبح لدينا دالة oracle، يمكننا تعريف نسخة محددة من بحث غروفر. في هذا المثال، سنُعلّم حالتين حسابيتين من أصل الحالات الثماني المتاحة في فضاء حساب ثلاثي الكيوبتات:

marked_states = ["011", "100"]

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

معامل غروفر

تأخذ الدالة المُدمجة grover_operator() في Qiskit دائرة oracle وتُعيد دائرة مكوَّنة من دائرة oracle ذاتها ودائرة تُضخّم الحالات التي علّمها oracle. نستخدم هنا طريقة 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: التنفيذ باستخدام primitives في Qiskit

تضخيم السعة مسألة أخذ عينات تناسب التنفيذ باستخدام الـ primitive الخاص بـ 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 متعددة التحكم التي تقع في قلب oracle ومشغّل الانتشار إلى أعماق من بوابات ثنائية الكيوبت تتزايد بسرعة بالغة مع عدد الكيوبتات (كما سنوضح في القسم التالي). هذا يعني أن الخوارزمية لا تتوسع جيداً على العتاد الضوضائي الحالي. لهذا السبب، نُظهر تنفيذ العتاد على نفس النطاق الصغير كمثال المحاكاة أعلاه، بدلاً من محاولة نطاق مسألة أكبر.

# -------------------------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 متعددة التحكم في قلب كل من oracle ومشغّل الانتشار إلى عدد من البوابات ثنائية الكيوبت يتزايد أسياً مع عدد كيوبتات التحكم. ومع الأخذ بعين الاعتبار أن العدد الأمثل من تكرارات غروفر نفسه يتزايد بترتيب $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 على نطاق الاستخدام يقدّمان أمثلة قريبة المدى على تحسين المسائل بالحواسيب الكمومية
• للتعمق أكثر في الخوارزميات قريبة المدى، راجع دورة الحوسبة الكمومية في التطبيق