خوارزمية دويتش-جوزسا

لهذه الوحدة من برنامج Qiskit في الفصول الدراسية، يحتاج الطلاب إلى بيئة Python تعمل بشكل صحيح مع تثبيت الحزم التالية:

• qiskit v2.1.0 أو أحدث
• qiskit-ibm-runtime v0.40.1 أو أحدث
• qiskit-aer v0.17.0 أو أحدث
• qiskit.visualization
• numpy
• pylatexenc

لإعداد هذه الحزم وتثبيتها، راجع دليل تثبيت Qiskit. لتشغيل المهام على حواسيب كمية حقيقية، يحتاج الطلاب إلى إنشاء حساب على IBM Quantum® باتباع الخطوات الموضحة في دليل إعداد حساب IBM Cloud الخاص بك.

تم اختبار هذه الوحدة واستغرقت أربع ثوانٍ من وقت وحدة المعالجة الكمية (QPU). هذا تقدير فقط، وقد يختلف استخدامك الفعلي.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-aer qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

شاهد الشرح التفصيلي للوحدة من تقديم د. كيتي ماكورميك أدناه، أو انقر هنا لمشاهدتها على YouTube.

---

مقدمة

في مطلع الثمانينيات، كان لدى علماء الفيزياء الكمية وعلماء الحاسوب فكرة مبهمة مفادها أنه يمكن توظيف ميكانيكا الكم لإجراء عمليات حسابية أكثر قوةً بكثير مما تستطيع الحواسيب الكلاسيكية تحقيقه. كان منطقهم هكذا: يصعب على الحاسوب الكلاسيكي محاكاة الأنظمة الكمية، لكن الحاسوب الكمي ينبغي أن يكون قادراً على فعل ذلك بكفاءة أعلى. وإذا كان الحاسوب الكمي قادراً على محاكاة الأنظمة الكمية بكفاءة أكبر، فربما توجد مهام أخرى يمكنه أداؤها بكفاءة أعلى من الحاسوب الكلاسيكي أيضاً.

كان المنطق سليماً، لكن التفاصيل كانت بحاجة إلى معالجة. بدأ ذلك عام 1985، حين وصف ديفيد دويتش أول "حاسوب كمي عالمي". وفي الورقة ذاتها، قدّم أول مثال على مسألة يمكن للحاسوب الكمي حلها بكفاءة أعلى مما يستطيع الحاسوب الكلاسيكي. يُعرف هذا المثال الأولي اليوم بـ"خوارزمية دويتش". كان التحسن في خوارزمية دويتش متواضعاً، غير أن دويتش تعاون لاحقاً مع ريتشارد جوزسا لاتساع الفجوة بين الحواسيب الكلاسيكية والكمية أكثر.

هاتان الخوارزميتان — خوارزمية دويتش وامتداد دويتش-جوزسا — ليستا ذواتَي فائدة عملية كبيرة، إلا أنهما لا تزالان مهمتين جداً لأسباب عدة:

1. من الناحية التاريخية، كانتا من أوائل الخوارزميات الكمية التي أثبتت تفوقها على نظيراتها الكلاسيكية. إن فهمهما يساعدنا على استيعاب كيف تطور تفكير المجتمع العلمي في الحوسبة الكمية عبر الزمن.
2. تساعداننا على فهم بعض جوانب الإجابة عن سؤال دقيق بشكل لافت: ما الذي يمنح الحوسبة الكمية قوتها؟ أحياناً تُقارن الحواسيب الكمية بمعالجات متوازية ضخمة ذات توسع أسي. لكن هذا ليس دقيقاً تماماً. فبينما يكمن جزء من الإجابة في ما يُسمى "التوازي الكمي"، فإن استخلاص أكبر قدر ممكن من المعلومات في تشغيل واحد هو فن دقيق. تُظهر خوارزميتا دويتش ودويتش-جوزسا كيف يمكن تحقيق ذلك.

في هذه الوحدة، سنتعلم خوارزمية دويتش وخوارزمية دويتش-جوزسا، وما تعلّماننا إياه حول قوة الحوسبة الكمية.

التوازي الكمي وحدوده

جزء من قوة الحوسبة الكمية مصدره "التوازي الكمي"، وهو في جوهره القدرة على تنفيذ العمليات على مدخلات متعددة في آنٍ واحد، إذ يمكن أن تكون حالات الكيوبت المدخلة في تراكب من حالات كلاسيكية متعددة. بيد أنه، رغم أن الدائرة الكمية قد تستطيع تقييم حالات مدخلة متعددة دفعة واحدة، فإن استخلاص كل تلك المعلومات دفعةً واحدة أمرٌ مستحيل.

لتوضيح ما أقصده، لنفترض أن لدينا بتاً $x$ ودالةً مطبقة على ذلك البت، $f(x)$. توجد أربع دوال ثنائية ممكنة تأخذ بتاً واحداً وتُعطي بتاً واحداً:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

نريد معرفة أيٌّ من هذه الدوال (1-4) هي دالتنا $f(x)$. كلاسيكياً، سنحتاج إلى تشغيل الدالة مرتين — مرة عند $x=0$، ومرة عند $x=1$. لكن لنرَ إن كان بمقدورنا تحقيق نتائج أفضل باستخدام دائرة كمية. يمكننا التعرف على الدالة باستخدام البوابة التالية:

هنا، تحسب بوابة $U_f$ القيمة $f(x)$، حيث $x$ هي حالة الكيوبت 0، وتطبق ذلك على الكيوبت 1. لذا تصبح الحالة الناتجة $|x\rangle|y\oplus f(x)\rangle$ ببساطة $|x\rangle|f(x)\rangle$ حين $|y\rangle = |0\rangle$. هذا يحتوي على كل المعلومات التي نحتاجها لمعرفة الدالة $f(x)$: الكيوبت 0 يخبرنا ما هو $x$، والكيوبت 1 يخبرنا ما هو $f(x)$. لذا، إذا هيّأنا $|x\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$، فإن الحالة النهائية للكيوبتَين ستكون: $|y\rangle|x\rangle = \frac{1}{\sqrt{2}}(|f(0)\rangle|0\rangle+|f(1)\rangle|1\rangle)$. لكن كيف نصل إلى تلك المعلومات؟

2.1. جرّبها على Qiskit:

باستخدام Qiskit، سنختار عشوائياً إحدى الدوال الأربع الممكنة أعلاه ونشغّل الدائرة. مهمتك هي استخدام قياسات الدائرة الكمية لمعرفة الدالة في أقل عدد ممكن من التشغيلات.

في هذه التجربة الأولى وعلى مدار الوحدة بأكملها، سنستخدم إطار عمل للحوسبة الكمية يُعرف بـ"أنماط Qiskit"، الذي يقسّم سير العمل إلى الخطوات التالية:

• الخطوة 1: تحويل المدخلات الكلاسيكية إلى مسألة كمية
• الخطوة 2: تحسين المسألة للتنفيذ الكمي
• الخطوة 3: التنفيذ باستخدام Qiskit Runtime Primitives
• الخطوة 4: المعالجة اللاحقة والتحليل الكلاسيكي

لنبدأ بتحميل بعض الحزم الضرورية، بما فيها Qiskit Runtime primitives. وسنختار أيضاً الحاسوب الكمي الأقل ازدحاماً المتاح لنا.

يوجد في الأسفل كود لحفظ بياناتك عند الاستخدام الأول. احرص على حذف هذه المعلومات من الدفتر بعد حفظها في بيئتك، حتى لا تُشارَك بياناتك عن طريق الخطأ عند مشاركة الدفتر. راجع إعداد حساب IBM Cloud الخاص بك وتهيئة الخدمة في بيئة غير موثوقة لمزيد من التوجيهات.

# Load the Qiskit Runtime service
from qiskit_ibm_runtime import QiskitRuntimeService

# Load the Runtime primitive and session
from qiskit_ibm_runtime import SamplerV2 as Sampler

# Syntax for first saving your token.  Delete these lines after saving your credentials.
# QiskitRuntimeService.save_account(channel='ibm_quantum_platform', instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

# Use the least busy backend, or uncomment the loading of a specific backend like "ibm_brisbane".
# backend = service.least_busy(operational=True, simulator=False, min_num_qubits = 127)
backend = service.backend("ibm_brisbane")
print(backend.name)

sampler = Sampler(mode=backend)

ibm_brisbane

الخلية أدناه تتيح لك التبديل بين استخدام المحاكي أو الأجهزة الحقيقية على مدار الدفتر. نوصيك بتشغيلها الآن:

# Load the backend sampler
from qiskit.primitives import BackendSamplerV2

# Load the Aer simulator and generate a noise model based on the currently-selected backend.
from qiskit_aer import AerSimulator
from qiskit_aer.noise import NoiseModel

# Alternatively, load a fake backend with generic properties and define a simulator.

noise_model = NoiseModel.from_backend(backend)

# Define a simulator using Aer, and use it in Sampler.
backend_sim = AerSimulator(noise_model=noise_model)
sampler_sim = BackendSamplerV2(backend=backend_sim)

# You could also define a simulator-based sampler using a generic backend:
# backend_gen = GenericBackendV2(num_qubits=18)
# sampler_gen = BackendSamplerV2(backend=backend_gen)

الآن بعد أن حمّلنا الحزم الضرورية، يمكننا المتابعة مع سير عمل أنماط Qiskit. في خطوة التحويل أدناه، نبدأ أولاً بإنشاء دالة تختار من بين الدوال الأربع الممكنة التي تأخذ بتاً واحداً وتُعيد بتاً واحداً.

# Step 1: Map

from qiskit import QuantumCircuit

qc = QuantumCircuit(2)

def twobit_function(case: int):
    """
    Generate a valid two-bit function as a `QuantumCircuit`.
    """
    if case not in [1, 2, 3, 4]:
        raise ValueError("`case` must be 1, 2, 3, or 4.")

    f = QuantumCircuit(2)
    if case in [2, 3]:
        f.cx(0, 1)
    if case in [3, 4]:
        f.x(1)
    return f

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
# blackbox = twobit_function(2).to_gate()  # you may edit the number inside "twobit_function()" to select among the four valid functions
# blackbox.label = "$U_f$"

qc.h(0)
qc.barrier()
qc.compose(twobit_function(2), inplace=True)
qc.measure_all()

qc.draw("mpl")

في الدائرة أعلاه، بوابة هادامارد "H" تأخذ الكيوبت 0 — الذي يبدأ في الحالة $|0\rangle$ — وتحوّله إلى حالة التراكب $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$. بعدها، $U_f$ تحسب الدالة $f(x)$ وتطبّق النتيجة على الكيوبت 1.

الخطوة التالية هي تحسين الدائرة وتحويلها لتشغيلها على الحاسوب الكمومي:

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc)

وأخيرًا، ننفّذ الدائرة المحوّلة على الحاسوب الكمومي ونعرض النتائج:

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.meas.get_counts()

# Step 4: Visualize and analyze results

## Analysis
from qiskit.visualization import plot_histogram

plot_histogram(counts)

ما فوق هو رسم بياني لنتائجنا. بناءً على عدد اللقطات (shots) التي اخترتها لتشغيل الدائرة في الخطوة 3 أعلاه، ممكن تشوف شريطًا واحدًا أو اثنين، يمثّلان الحالات المقيسة للكيوبتين في كل لقطة. كالعادة في Qiskit وفي هذا الدفتر، نستخدم نظام "little endian"، يعني حالات الكيوبتات من 0 إلى n تُكتب بترتيب تصاعدي من اليمين لليسار، فالكيوبت 0 دائمًا في أقصى اليمين.

إذن، لأن الكيوبت 0 كان في حالة تراكب، الدائرة حسبت الدالة لـ كلا القيمتين $x=0$ و$x=1$ في نفس الوقت — وهذا شيء لا تقدر عليه الحواسيب الكلاسيكية! لكن المشكلة تظهر لما نريد نتعلم شيئًا عن الدالة $f(x)$ — لأنه عند قياس الكيوبتات، تنهار حالتها. لو اخترت "shots = 1" لتشغيل الدائرة مرة واحدة فقط، ستشوف شريطًا واحدًا فقط في الرسم البياني، ومعلوماتك عن الدالة ستكون ناقصة.

تحقق من فهمك

اقرأ السؤال (أو الأسئلة) أدناه، فكّر في الإجابة، ثم اضغط على المثلث لتكشف الحل.

كم مرة يجب علينا تشغيل الخوارزمية أعلاه لمعرفة الدالة $f(x)$؟ هل هذا أفضل من الحالة الكلاسيكية؟ هل تفضّل حاسوبًا كلاسيكيًا أم كموميًا لحل هذه المسألة؟

الجواب:

بما أن القياس سيجعل التراكب ينهار ويُعيد قيمة واحدة فقط، نحتاج إلى تشغيل الدائرة على الأقل مرتين لنحصل على كلا مخرجَي الدالة $f(0)$ و$f(1)$. في أحسن الأحوال، يكون الأداء مماثلًا للحالة الكلاسيكية، حيث نحسب كلًا من $f(0)$ و$f(1)$ في أول استعلامين. لكن هناك احتمال أننا قد نحتاج لأكثر من مرتين، لأن القياس النهائي احتمالي وقد يُعيد نفس قيمة $f(x)$ في المرتين الأوليين. في هذه الحالة، أفضّل الحاسوب الكلاسيكي.

إذن، رغم أن التوازي الكمومي قد يكون قويًا عند استخدامه بالشكل الصحيح، إلا أنه ليس صحيحًا القول بأن الحاسوب الكمومي يعمل مثل معالج متوازٍ كلاسيكي ضخم. عملية القياس تجعل الحالات الكمومية تنهار، لذا لا نستطيع أبدًا الوصول إلا لمخرج واحد من الحساب.

خوارزمية دويتش

بينما التوازي الكمومي وحده لا يمنحنا ميزة على الحواسيب الكلاسيكية، يمكننا دمجه مع ظاهرة كمومية أخرى وهي التداخل لتحقيق تسريع فعلي. الخوارزمية المعروفة الآن بـ"خوارزمية دويتش" هي أول مثال على خوارزمية تحقق هذا.

المسألة

كانت المسألة كالتالي:

بإعطاء بت مدخل $x = \{0,1\}$ ودالة مدخل $f(x) = \{0,1\}$، حدّد ما إذا كانت الدالة متوازنة أم ثابتة. يعني، لو كانت متوازنة، فمخرج الدالة يكون 0 نصف الوقت و1 النصف الآخر. أما لو كانت ثابتة، فمخرج الدالة يكون إما 0 دائمًا أو 1 دائمًا. تذكّر جدول الدوال الأربع الممكنة التي تأخذ بتًا واحدًا وتُعيد بتًا واحدًا:

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	1	1
1	0	1	0	1

الدالتان الأولى والأخيرة، $f_1(x)$ و$f_4(x)$، ثابتتان، بينما الدالتان الوسطيتان، $f_2(x)$ و$f_3(x)$، متوازنتان.

الخوارزمية

الطريقة التي تعامل بها دويتش مع هذه المسألة كانت من خلال "نموذج الاستعلام". في نموذج الاستعلام، الدالة المدخلة ($f_i(x)$ أعلاه) موجودة داخل "صندوق أسود" — ليس لدينا وصول مباشر لمحتواه، لكن يمكننا استعلامه وسيعطينا مخرج الدالة. أحيانًا نقول إن "أوراكل" يوفّر هذه المعلومات. راجع الدرس 1: خوارزميات الاستعلام الكمومية من دورة أساسيات الخوارزميات الكمومية لمزيد من التفاصيل حول نموذج الاستعلام.

لتحديد ما إذا كانت خوارزمية كمومية أكثر كفاءة من خوارزمية كلاسيكية في نموذج الاستعلام، يمكننا ببساطة مقارنة عدد الاستعلامات التي نحتاج إجراءها على الصندوق الأسود في كل حالة. في الحالة الكلاسيكية، لمعرفة ما إذا كانت الدالة في الصندوق الأسود متوازنة أم ثابتة، نحتاج لاستعلامه مرتين للحصول على كلٍّ من $f(0)$ و$f(1)$.

لكن في خوارزمية دويتش الكمومية، وجد طريقة للحصول على المعلومة باستعلام واحد فقط! أجرى تعديلًا واحدًا على دائرة "التوازي الكمومي" أعلاه، بحيث أعدّ حالة تراكب على كلا الكيوبتين بدلًا من الكيوبت 0 فحسب. بذلك، مخرجَا الدالة $f(0)$ و$f(1)$ تداخلا ليُعيدا 0 لو كانا كلاهما 0 أو كلاهما 1 (أي الدالة ثابتة)، ويُعيدان 1 لو كانا مختلفين (أي الدالة متوازنة). بهذه الطريقة، تمكّن دويتش من التمييز بين دالة ثابتة ودالة متوازنة باستعلام واحد.

لفهم كيفية عمل هذه الخوارزمية، دعنا نتفحص الحالات الكمية للكيوبتات عند النقاط الثلاث المشار إليها في المخطط أعلاه. حاول أن تستنتج الحالات بنفسك قبل أن تضغط لتشاهد الإجابات:

تحقق من فهمك

اقرأ الأسئلة التالية، فكّر في إجاباتك، ثم اضغط على المثلثات للكشف عن الحلول.

ما هي الحالة $|\pi_1\rangle$؟

الإجابة:

تطبيق بوابة هادامارد يحوّل الحالة $|0\rangle$ إلى $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ والحالة $|1\rangle$ إلى $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. إذن، تصبح الحالة الكاملة: $|\pi_1\rangle = [\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}]$

ما هي الحالة $|\pi_2\rangle$؟

الإجابة:

قبل أن نطبّق $U_f$، تذكّر ما تفعله. ستغيّر حالة الكيوبت 1 بناءً على حالة الكيوبت 0. لذا، من المنطقي أن نفصل حالة الكيوبت 0: $|\pi_1\rangle = \frac{1}{2} (|0\rangle-|1\rangle)|0\rangle+\frac{1}{2}(|0\rangle-|1\rangle)|1\rangle$. بعدها، إذا كان $f(0)=f(1)$، فإن الحدّين سيتحوّلان بنفس الطريقة وتبقى الإشارة النسبية بين الحدّين موجبة، أما إذا كان $f(0)\neq f(1)$، فهذا يعني أن الحدّ الثاني سيكتسب إشارة سالبة نسبةً إلى الحدّ الأول، مما يغيّر حالة الكيوبت 0 من $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ إلى $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$. إذن:

$$|\pi_2\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle+|1\rangle}{\sqrt{2}}] & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}][\frac{|0\rangle-|1\rangle}{\sqrt{2}}] &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

ما هي الحالة $|\pi_3\rangle$؟

الإجابة:

الآن، حالة الكيوبت 0 هي إما $\frac{1}{\sqrt{2}}(|0\rangle+|1\rangle)$ أو $\frac{1}{\sqrt{2}}(|0\rangle-|1\rangle)$، تبعاً للدالة. تطبيق هادامارد سيعطينا إما $|0\rangle$ أو $|1\rangle$ على التوالي.

$$|\pi_3\rangle = \begin{cases} \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|0\rangle & \text{if} & f(0) = f(1) \\ \pm[\frac{|0\rangle-|1\rangle}{\sqrt{2}}]|1\rangle &\text{if} & f(0) \neq f(1) \\ \end{cases}$$

بمراجعة إجاباتك على الأسئلة أعلاه، لاحظ أن شيئاً مثيراً للاهتمام يحدث. رغم أن $U_f$ لا تفعل شيئاً صريحاً لحالة الكيوبت 0، إلا أنه بما أنها تغيّر الكيوبت 1 بناءً على حالة الكيوبت 0، فقد يحدث أن هذا يتسبب في انزياح طوري في الكيوبت 0. يُعرف هذا بظاهرة "الارتداد الطوري" (phase-kickback)، ويُناقش بمزيد من التفصيل في الدرس 1: خوارزميات الاستعلام الكمي ضمن دورة أساسيات الخوارزميات الكمية.

الآن بعد أن فهمنا كيف تعمل هذه الخوارزمية، دعنا ننفّذها باستخدام Qiskit.

## Deutsch's algorithm:

## Step 1: Map the problem

# first, convert oracle circuit (above) to a single gate for drawing purposes. otherwise, the circuit is too large to display
blackbox = twobit_function(
    3
).to_gate()  # you may edit the number (1-4) inside "twobit_function()" to select among the four valid functions
blackbox.label = "$U_f$"

qc_deutsch = QuantumCircuit(2, 1)

qc_deutsch.x(1)
qc_deutsch.h(range(2))

qc_deutsch.barrier()
qc_deutsch.compose(twobit_function(2), inplace=True)
qc_deutsch.barrier()

qc_deutsch.h(0)
qc_deutsch.measure(0, 0)

qc_deutsch.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc_deutsch)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)
if "1" in counts:
    print("balanced")
else:
    print("constant")

{'1': 1}
balanced

خوارزمية دوتش-جوزسا

كانت خوارزمية دوتش خطوةً أولى مهمة في إثبات كيف يمكن لحاسوب كمي أن يكون أكثر كفاءة من الحاسوب الكلاسيكي، غير أنها كانت تحسيناً متواضعاً فحسب: كانت تحتاج إلى استعلام واحد فقط مقارنةً باستعلامين في الحالة الكلاسيكية. في عام 1992، قام دوتش وزميله ريتشارد جوزسا بتوسيع الخوارزمية الأصلية ذات الكيوبتين لتشمل عدداً أكبر من الكيوبتات. المسألة بقيت كما هي: تحديد ما إذا كانت الدالة متوازنة أم ثابتة. لكن هذه المرة، الدالة تمتد من $n$ بت إلى بت واحد. إما أن ترجع الدالة القيمتين 0 و1 بعدد متساوٍ من المرات (وهي متوازنة)، أو ترجع دائماً 1 أو دائماً 0 (وهي ثابتة).

إليك مخطط الدائرة الخاص بالخوارزمية:

تعمل هذه الخوارزمية بنفس الطريقة التي تعمل بها خوارزمية دويتش: يتيح لنا الـ phase-kickback قراءة حالة الكيوبت 0 لتحديد ما إذا كانت الدالة ثابتة أم متوازنة. الأمر أصعب قليلاً في الفهم مقارنةً بحالة خوارزمية دويتش ذات الكيوبتين، لأن الحالات ستتضمن مجاميع على $n$ كيوبت، لذا سيُترك حساب تلك الحالات كتمرين اختياري لك في نهاية الوحدة. ستُعيد الخوارزمية سلسلة بتات مكونة من أصفار فقط إذا كانت الدالة ثابتة، وسلسلة بتات تحتوي على واحد على الأقل إذا كانت الدالة متوازنة.

لنرى كيف تعمل الخوارزمية في Qiskit، علينا أولاً توليد الـ oracle الخاص بنا: وهو الدالة العشوائية التي تكون إما ثابتة أو متوازنة بالضرورة. الكود التالي سيولّد دالة متوازنة بنسبة 50% من الوقت، ودالة ثابتة بنسبة 50% من الوقت. لا داعي للقلق إن لم تتابع الكود بالكامل — إنه معقد وليس ضرورياً لفهمنا للخوارزمية الكمومية.

from qiskit import QuantumCircuit
import numpy as np

def dj_function(num_qubits):
    """
    Create a random Deutsch-Jozsa function.
    """

    qc_dj = QuantumCircuit(num_qubits + 1)
    if np.random.randint(0, 2):
        # Flip output qubits with 50% chance
        qc_dj.x(num_qubits)
    if np.random.randint(0, 2):
        # return constant circuit with 50% chance.
        return qc_dj

    # If the "if" statement above was "TRUE" then we've returned the constant
    # function and the function is complete. If not, we proceed in creating our
    # balanced function. Everything below is to produce the balanced function:

    # select half of all possible states at random:
    on_states = np.random.choice(
        range(2**num_qubits),  # numbers to sample from
        2**num_qubits // 2,  # number of samples
        replace=False,  # makes sure states are only sampled once
    )

    def add_cx(qc_dj, bit_string):
        for qubit, bit in enumerate(reversed(bit_string)):
            if bit == "1":
                qc_dj.x(qubit)
        return qc_dj

    for state in on_states:
        # qc_dj.barrier()  # Barriers are added to help visualize how the functions are created. They can safely be removed.
        qc_dj = add_cx(qc_dj, f"{state:0b}")
        qc_dj.mcx(list(range(num_qubits)), num_qubits)
        qc_dj = add_cx(qc_dj, f"{state:0b}")

    # qc_dj.barrier()

    return qc_dj

n = 3  # number of input qubits

oracle = dj_function(n)

display(oracle.draw("mpl"))

هذه هي دالة الـ oracle، والتي إما أن تكون متوازنة أو ثابتة. هل يمكنك من خلال النظر إليها تحديد ما إذا كان الناتج على الكيوبت الأخير يعتمد على القيم المُدخَلة في الكيوبتات الأولى $n$؟ إذا كان الناتج على الكيوبت الأخير يعتمد على الكيوبتات الأولى $n$، هل يمكنك معرفة ما إذا كان ذلك الناتج المعتمد متوازناً أم لا؟

يمكننا تحديد ما إذا كانت الدالة متوازنة أم ثابتة بالنظر إلى الدائرة أعلاه، لكن تذكّر، لأغراض هذه المسألة، نتعامل مع هذه الدالة باعتبارها "صندوقاً أسود". لا يمكننا الاطلاع داخل الصندوق لرؤية مخطط الدائرة. بدلاً من ذلك، نحتاج إلى الاستعلام منه.

للاستعلام من الصندوق، نستخدم خوارزمية دويتش-جوزا ونحدد ما إذا كانت الدالة ثابتة أم متوازنة:

blackbox = oracle.to_gate()
blackbox.label = "$U_f$"

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(blackbox, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 1: Map the problem

qc_dj = QuantumCircuit(n + 1, n)
qc_dj.x(n)
qc_dj.h(range(n + 1))
qc_dj.barrier()
qc_dj.compose(oracle, inplace=True)
qc_dj.barrier()
qc_dj.h(range(n))
qc_dj.measure(range(n), range(n))

qc_dj.decompose().decompose()

qc_dj.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc_dj)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

if (
    "0" * n in counts
):  # The D-J algorithm returns all zeroes if the function was constant
    print("constant")
else:
    print("balanced")  # anything other than all zeroes means the function is balanced.

{'110': 1}
balanced

في الأعلى، السطر الأول من المخرجات هو سلسلة البتات الناتجة عن القياس. أما السطر الثاني، فيُخرج ما إذا كانت هذه السلسلة تدل على أن الدالة متوازنة أم ثابتة. إذا احتوت سلسلة البتات على أصفار فقط، فالدالة ثابتة؛ وإن لم تكن كذلك، فهي متوازنة. إذن، بتشغيل واحد فقط للدائرة الكمومية أعلاه، يمكننا تحديد ما إذا كانت الدالة ثابتة أم متوازنة!

تحقق من فهمك

اقرأ الأسئلة أدناه، وفكّر في إجاباتك، ثم انقر على المثلثات للاطلاع على الحلول.

كم استعلامًا سيحتاجه حاسوب كلاسيكي ليحدد بيقين 100% ما إذا كانت دالة ما ثابتة أم متوازنة؟ تذكّر أنه كلاسيكيًا، يُتيح لك الاستعلام الواحد تطبيق الدالة على سلسلة بتات واحدة فقط.

الجواب:

هناك $2^n$ سلسلة بتات محتملة للفحص، وفي أسوأ الحالات، ستحتاج إلى اختبار $2^n/2+1$ منها. على سبيل المثال، إذا كانت الدالة ثابتة وظللت تقيس "1" كمخرج للدالة، فلن تستطيع التأكد من أنها ثابتة فعلًا حتى تتحقق من أكثر من نصف النتائج. قبل ذلك، ربما كنت محظوظًا جدًا وتقيس "1" على دالة متوازنة. الأمر يشبه قلب عملة معدنية مرارًا وتكرارًا وظهور الوجه في كل مرة — هذا مستبعد، لكنه ليس مستحيلًا.

كيف سيتغير جوابك السابق إذا احتجت فقط إلى القياس حتى تصبح إحدى النتيجتين (متوازنة أم ثابتة) أكثر احتمالًا من الأخرى؟ كم استعلامًا ستحتاج في هذه الحالة؟

الجواب:

في هذه الحالة، يكفيك القياس مرتين فقط. إذا كانت القياستان مختلفتين، فأنت تعلم أن الدالة متوازنة. وإذا كانتا متساويتين، فقد تكون متوازنة أو ثابتة. احتمال أن تكون متوازنة بهذه المجموعة من القياسات هو: $\frac{1}{2}\frac{2^n /2 - 1}{2^n-1}$. هذا أقل من 1/2، لذا فمن الأرجح أن الدالة ثابتة في هذه الحالة.

إذن، أثبت خوارزمية دويتش-جوزسا تسريعًا أسيًا مقارنةً بالخوارزمية الكلاسيكية الحتمية (التي تعيد الإجابة بيقين 100%)، لكنها لم تُقدّم تسريعًا يُذكر مقارنةً بالخوارزمية الكلاسيكية الاحتمالية (التي تعيد نتيجة يُرجَّح أنها صحيحة).

مسألة برنشتاين - فازيراني

في عام 1997، استخدم إيثان برنشتاين وأوميش فازيراني خوارزمية دويتش-جوزسا لحل مسألة أكثر تحديدًا وتقييدًا مقارنةً بمسألة دويتش-جوزسا. بدلًا من مجرد التمييز بين فئتين مختلفتين من الدوال كما في حالة D-J، استخدم برنشتاين وفازيراني خوارزمية دويتش-جوزسا لاستخراج سلسلة مشفّرة داخل دالة ما. إليك المسألة:

الدالة $f:\{0,1\}^n \rightarrow \{0,1\}$ لا تزال تأخذ سلسلة بتات من $n$ بت وتُخرج بتًا واحدًا. لكن الآن، بدلًا من الوعد بأن الدالة متوازنة أو ثابتة، نُعطى وعدًا بأن الدالة هي حاصل الضرب النقطي بين سلسلة الإدخال $x$ وسلسلة سرية $s$ من $n$ بت، بقسمة مودولو 2. (يُسمى هذا الضرب النقطي مودولو 2 بـ"الضرب النقطي الثنائي".) والمطلوب هو معرفة ما هي السلسلة السرية من $n$ بت.

بصياغة أخرى، لدينا دالة صندوق أسود $f: {0,1}^n \rightarrow {0,1}$ تحقق $f(x) = s \cdot x$ لسلسلة ما $s$، ونريد معرفة السلسلة $s$.

لنرَ كيف تحل خوارزمية D-J هذه المسألة:

1. أولًا، يُطبَّق بوابة هادامار على $n$ كيوبت من المدخلات، وتُطبَّق بوابة NOT مع هادامار على كيوبت المخرج، مما يجعل الحالة:

$$|\Psi\rangle = |-\rangle_{n} \otimes |+\rangle_{n-1} \otimes |+\rangle_{n-2} \otimes ... \otimes |+\rangle_0$$

يمكن كتابة حالة الكيوبتات من 1 إلى $n$ بشكل أبسط كمجموع على جميع $2^n$ من حالات الأساس ذات $n$ كيوبت $|00...00\rangle, |00...01\rangle, |000...11\rangle, ..., |111...11\rangle$. نسمي مجموعة هذه الحالات الأساسية $\Sigma^n$. (راجع أساسيات الخوارزميات الكمومية لمزيد من التفاصيل.)

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{|x\rangle}$$

2. بعد ذلك، تُطبَّق بوابة $U_f$ على الكيوبتات. ستأخذ هذه البوابة أول n كيوبتات كمدخل (التي هي الآن في تراكب متساوٍ لجميع سلاسل البتات الممكنة من n بت) وتطبّق الدالة $f(x)=s \cdot x$ على كيوبت المخرج، بحيث يصبح هذا الكيوبت في الحالة: $|- \oplus f(x)\rangle$. بفضل آلية الرفس الطوري، تبقى حالة هذا الكيوبت دون تغيير، لكن بعض الحدود في حالة كيوبتات الإدخال تكتسب إشارة سالبة:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{\sqrt{2^n}}\sum\limits_{x \in \Sigma^n}{(-1)^{f(x)}|x\rangle}$$

3. الآن، تُطبَّق مجموعة هادامار التالية على الكيوبتات من 0 إلى $n-1$. تتبّع الإشارات السالبة في هذه الحالة قد يكون أمرًا صعبًا. من المفيد معرفة أن تطبيق طبقة من بوابات هادامار على $n$ كيوبت في حالة أساسية قياسية $|x\rangle$ يمكن كتابته كـ:

$$H^{\otimes n} |x\rangle = \frac{1}{\sqrt{2^n}}\sum\limits_{y \in \Sigma^n}{(-1)^{x \cdot y}|y\rangle}$$

فتصبح الحالة:

$$|\Psi\rangle = |-\rangle \otimes \frac{1}{2^n}\sum\limits_{x \in \Sigma^n}\sum\limits_{y \in \Sigma^n}{(-1)^{(s \cdot x) + (x \cdot y)}|y\rangle}$$

4. الخطوة التالية هي قياس أول $n$ بت. لكن ماذا سنقيس؟ تبيّن أن الحالة أعلاه تُبسَّط إلى: $|\Psi\rangle = |-\rangle \otimes |s\rangle$، لكن هذا ليس واضحًا على الإطلاق. إذا أردت تتبّع الرياضيات، راجع دورة جون واتروس أساسيات الخوارزميات الكمومية. والنقطة الأساسية هي أن آلية الرفس الطوري تجعل كيوبتات الإدخال في الحالة $|s\rangle$. لذا، لمعرفة ما هي السلسلة السرية $s$، ما عليك سوى قياس الكيوبتات!

تحقق من فهمك

اقرأ الأسئلة أدناه، وفكّر في إجاباتك، ثم انقر على المثلثات للاطلاع على الحلول.

تحقق من أن الحالة من الخطوة 3 أعلاه هي فعلًا الحالة $|s\rangle$ للحالة الخاصة $n=1$.

الجواب:

عندما تكتب المجموعتين صراحةً، يجب أن تحصل على حالة ذات أربعة حدود (لنحذف حالة المخرج $|-\rangle$ لهذا الغرض):

$$|\Psi\rangle = \frac{1}{2}[|0\rangle + (-1)^s |0\rangle + |1\rangle + (-1)^{(s+1)} |1\rangle]$$

إذا كان $s=0$، يتجمّع الحدّان الأولان بشكل بنّاء ويتلاشى الحدّان الأخيران، تاركًا لنا $|\Psi\rangle = |0\rangle$. وإذا كان $s=1$، يتجمّع الحدّان الأخيران بشكل بنّاء ويتلاشى الحدّان الأولان، تاركًا لنا $|\Psi\rangle = |1\rangle$. إذن، في كلتا الحالتين، $|\Psi\rangle = |s\rangle$. نأمل أن هذه الحالة الأبسط تعطيك فكرة عن كيفية عمل الحالة العامة مع $n$ كيوبت: كل الحدود التي ليست $|s\rangle$ تتلاشى بالتداخل، تاركةً فقط الحالة $|s\rangle$.

كيف يمكن للخوارزمية نفسها حل مسألتَي برنشتاين-فازيراني ودويتش-جوزسا؟ لفهم ذلك، فكّر في دوال برنشتاين-فازيراني التي هي من الشكل $f(x) = s \cdot x$. هل هذه الدوال دوال دويتش-جوزسا أيضًا؟ أي، حدّد ما إذا كانت الدوال بهذا الشكل تفي بوعد مسألة دويتش-جوزسا: أنها إما ثابتة أو متوازنة. كيف يساعدنا هذا على فهم كيفية حل الخوارزمية نفسها لمسألتين مختلفتين؟

الجواب:

كل دالة برنشتاين-فازيراني من الشكل $f(x) = s \cdot x$ تفي أيضًا بوعد مسألة دويتش-جوزسا: إذا كان s=00...00، فالدالة ثابتة (تعيد دائمًا 0 لكل سلسلة x). وإذا كانت s أي سلسلة أخرى، فالدالة متوازنة. لذا، تطبيق خوارزمية دويتش-جوزسا على إحدى هذه الدوال يحل المسألتين في آنٍ واحد! فهي تعيد السلسلة، وإذا كانت هذه السلسلة 00...00 فنعلم أنها ثابتة؛ وإذا كان في السلسلة "1" واحد على الأقل، نعلم أنها متوازنة.

يمكننا أيضًا التحقق من أن هذه الخوارزمية تحل مسألة برنشتاين-فازيراني بنجاح عن طريق اختبارها تجريبيًا. أولًا، نُنشئ دالة B-V التي تعيش داخل الصندوق الأسود:

# Step 1: Map the problem

def bv_function(s):
    """
    Create a Bernstein-Vazirani function from a string of 1s and 0s.
    """
    qc = QuantumCircuit(len(s) + 1)
    for index, bit in enumerate(reversed(s)):
        if bit == "1":
            qc.cx(index, len(s))
    return qc

display(bv_function("1000").draw("mpl"))

string = "1000"  # secret string that we'll pretend we don't know or have access to
n = len(string)

qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
# qc.compose(oracle, inplace = True)
qc.compose(bv_function(string), inplace=True)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))

qc.draw("mpl")

# Step 2: Transpile
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

qc_isa = pm.run(qc)

# Step 3: Run the job on a real quantum computer

job = sampler.run([qc_isa], shots=1)
# job = sampler_sim.run([qc_isa],shots=1) # uncomment this line to run on simulator instead
res = job.result()
counts = res[0].data.c.get_counts()

# Step 4: Visualize and analyze results

## Analysis
print(counts)

{'0000': 1}

إذاً، بمجرد استعلام واحد فقط، سيعيد خوارزمية دويتش-يوزسا السلسلة $s$ المستخدمة في الدالة: $f(x)=x \cdot s$ حين نطبّقها على مسألة برنشتاين-فازيراني. أما الخوارزمية الكلاسيكية، فستحتاج إلى $n$ استعلامًا لحل المسألة نفسها.

الخلاصة

نأمل أن هذه الأمثلة البسيطة قد منحتك حدسًا أفضل حول الكيفية التي تستغل بها الحواسيب الكمية التراكب والتشابك والتداخل لتحقيق تفوقها على الحواسيب الكلاسيكية.

تمتلك خوارزمية دويتش-يوزسا أهمية تاريخية بالغة لأنها كانت أول خوارزمية تُثبت أي تسريع على الخوارزميات الكلاسيكية، وإن كان تسريعًا متعدد الحدود فحسب. وخوارزمية دويتش-يوزسا ليست سوى بداية القصة.

بعد أن استخدم برنشتاين وفازيراني الخوارزمية لحل مسألتهما، اتخذاها أساسًا لمسألة أكثر تعقيدًا وتعاودية تُعرف بـ مسألة أخذ عينات فورييه التعاودية. وقد أتاح حلّهما تسريعًا فائق التعدد الحدودي مقارنةً بالخوارزميات الكلاسيكية. وحتى قبل برنشتاين وفازيراني، كان بيتر شور قد توصّل بالفعل إلى خوارزميته الشهيرة التي تمكّن الحواسيب الكمية من تحليل الأعداد الكبيرة إلى عوامل بصورة أسرع أسيًا من أي خوارزمية كلاسيكية. أثبتت هذه النتائج مجتمعةً الوعد المثير لمستقبل الحواسيب الكمية، ودفعت الفيزيائيين والمهندسين إلى تحويل هذا المستقبل إلى واقع.

الأسئلة

يمكن للمدرّسين طلب نسخ من هذه الدفاتر مع مفاتيح الإجابات وإرشادات حول موضعها في المناهج الدراسية الشائعة، وذلك بتعبئة هذا الاستبيان السريع حول طريقة استخدام الدفاتر.

المفاهيم الأساسية

• تستخدم خوارزميتا دويتش ودويتش-يوزسا التوازي الكمي مقترنًا بالتداخل للوصول إلى إجابة المسألة بشكل أسرع مما تستطيعه الحاسوب الكلاسيكي.
• آلية الرفس الطوري هي ظاهرة كمية غير حدسية تنقل العمليات على كيوبت واحد إلى طور كيوبت آخر. وتستفيد خوارزميتا دويتش ودويتش-يوزسا من هذه الآلية.
• تقدّم خوارزمية دويتش-يوزسا تسريعًا متعدد الحدود على أي خوارزمية كلاسيكية حتمية.
• يمكن تطبيق خوارزمية دويتش-يوزسا على مسألة مختلفة تُسمى مسألة برنشتاين-فازيراني، للعثور على سلسلة مخفية مُشفَّرة داخل دالة.

صح أم خطأ

1. ص/خ خوارزمية دويتش هي حالة خاصة من خوارزمية دويتش-يوزسا حيث المدخل كيوبت واحد.
2. ص/خ تستخدم خوارزميتا دويتش ودويتش-يوزسا التراكب الكمي والتداخل لتحقيق كفاءتهما.
3. ص/خ تتطلب خوارزمية دويتش-يوزسا تقييمات متعددة للدالة لتحديد ما إذا كانت ثابتة أم متوازنة.
4. ص/خ "خوارزمية برنشتاين-فازيراني" هي في الواقع خوارزمية دويتش-يوزسا نفسها مطبَّقة على مسألة مختلفة.
5. ص/خ يمكن لخوارزمية برنشتاين-فازيراني إيجاد سلاسل سرية متعددة في آنٍ واحد.

إجابات قصيرة

1. كم من الوقت تحتاجه الخوارزمية الكلاسيكية لحل مسألة دويتش-يوزسا في أسوأ الحالات؟

2. كم من الوقت تحتاجه الخوارزمية الكلاسيكية لحل مسألة برنشتاين-فازيراني؟ وما مقدار التسريع الذي تقدمه خوارزمية DJ في هذه الحالة؟

3. صِف آلية الرفس الطوري وكيف تعمل لحل مسألتَي دويتش-يوزسا وبرنشتاين-فازيراني.

مسألة تحدٍّ

1. خوارزمية دويتش-يوزسا: تذكّر أن لديك سؤالًا أعلاه يطلب منك اشتقاق حالات الكيوبت الوسيطة $\pi_1$ و $\pi_2$ في خوارزمية دويتش. افعل الشيء ذاته لحالات الكيوبت الوسيطة $\pi_1$ و $\pi_2$ المؤلفة من $n+1$ كيوبت في خوارزمية دويتش-يوزسا، للحالة الخاصة $n=2$. ثم تحقق من أن $\pi_3 = |-\rangle \otimes \sum\limits_{x_0...x_n}(-1)^{f(x_0...x_n)}|x_0 ... x_n\rangle$، مرة أخرى للحالة الخاصة $n=2$.