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

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

الخلفية

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

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

المتطلبات

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

• Qiskit SDK الإصدار 1.4 أو أحدث، مع دعم التصور البصري
• Qiskit Runtime (pip install qiskit-ibm-runtime) الإصدار 0.36 أو أحدث

الإعداد

# 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 متعددة التحكم.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(
    operational=True, simulator=False, min_num_qubits=127
)
backend.name

'ibm_brisbane'

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

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

marked_states = ["011", "100"]

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

marked_states = ["011", "100"]

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

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: تحسين المسألة لتنفيذها على العتاد الكمومي

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

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

الخطوة 3: التنفيذ باستخدام primitives في Qiskit

تضخيم السعة مسألة أخذ عينات تناسب التنفيذ باستخدام الـ primitive الخاص بـ Sampler في وقت التشغيل.

لاحظ أن طريقة run() الخاصة بـ Qiskit Runtime SamplerV2 تقبل متسلسلة من primitive unified blocks (PUBs). بالنسبة للـ Sampler، كل PUB عبارة عن متسلسلة بالصيغة (circuit, parameter_values). غير أنه يقبل كحد أدنى قائمةً من الدوائر الكمومية.

# To run on local simulator:
#   1. Use the StatevectorSampler from qiskit.primitives instead
sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

الخطوة 4: المعالجة اللاحقة وإرجاع النتيجة بالصيغة الكلاسيكية المطلوبة

plot_distribution(dist)

استبيان البرنامج التعليمي

يُرجى إكمال هذا الاستبيان القصير لتقديم ملاحظاتك حول هذا البرنامج التعليمي. ستساعدنا آراؤك في تحسين محتوانا وتجربة المستخدم.

رابط الاستبيان