خوارزمية دويتش–جوزا
Deutsch–Jozsa Algorithm
تحدّد خوارزمية دويتش–جوزا هل دالة على $n$ بت ثابتة أم متوازنة (مع ضمان أنها أحدهما) باستعلام واحد، بينما تحتاج الخوارزمية الكلاسيكية الحتمية $2^{n-1}+1$ استعلاماً في أسوأ الحالات.
Deutsch–Jozsa decides with one query whether an n-bit function promised to be constant or balanced is which, versus 2^{n−1}+1 queries for an exact classical algorithm.
المسألة
دالة $f:\{0,1\}^n\to\{0,1\}$ مضمون أنها ثابتة أو متوازنة؛ المطلوب تحديد النوع.
الفكرة الأساسية
ركلة الطور تكتب $(-1)^{f(x)}$ على كل حد من التراكب، وهادامارد النهائية تجمع هذه الإشارات في سعة $|0^n\rangle$: تداخل بنّاء كامل للدالة الثابتة وهدّام كامل للمتوازنة.
المتطلبات
$n+1$ كيوبت، مُوحٍ واحدي للدالة، ووعد صحيح بأن الدالة ثابتة أو متوازنة.
الخطوات
- هيّئ $n$ كيوبت مدخل في $|0\rangle$ والمساعد $q_n$ في $|1\rangle$.
- طبّق $H$ على كل الكيوبتات.
- استعلم المُوحي مرة واحدة: $|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$.
- طبّق $H$ على كيوبتات المدخل.
- قِس كيوبتات المدخل: $0\cdots0$ ⇒ ثابتة، وغير ذلك ⇒ متوازنة.
خوارزمية دويتش–جوزا (Deutsch–Jozsa Algorithm) تعمّم خوارزمية دويتش إلى $n$ بت. لدينا مُوحٍ لدالة $f:\{0,1\}^n\to\{0,1\}$ مع «وعد» (Promise) بأنها إما ثابتة (القيمة نفسها لكل المدخلات) أو متوازنة (تعطي 0 لنصف المدخلات و1 للنصف الآخر)، والمطلوب تحديد أيهما.
الدارة: $n$ كيوبت مدخل في $|0\rangle$ وكيوبت مساعد في $|1\rangle$؛ هادامارد على الجميع؛ استعلام واحد؛ هادامارد على كيوبتات المدخل؛ قياسها. بفضل ركلة الطور تصبح الحالة قبل القياس
$$\frac{1}{2^n}\sum_{y}\Big(\sum_x(-1)^{f(x)+x\cdot y}\Big)|y\rangle.$$
سعة النتيجة $y=0\cdots0$ هي $\frac{1}{2^n}\sum_x(-1)^{f(x)}$، وتساوي $\pm1$ إذا كانت $f$ ثابتة، و0 تماماً إذا كانت متوازنة لأن الحدود الموجبة والسالبة تلغي بعضها. إذن: النتيجة «كلها أصفار» تعني ثابتة، وأي نتيجة أخرى تعني متوازنة، بيقين ومن استعلام واحد.
مُوحي المختبر: الدالة الثابتة $f(x)=v$ (بوابة $X$ على المساعد إذا كان $v=1$)، والدالة المتوازنة $f(x)=s\cdot x\oplus v$ مع $s\neq0$، وتُبنى بوابات CNOT من كل كيوبت $i$ يكون فيه $s_i=1$ إلى المساعد. هذه الدوال الخطية متوازنة فعلاً، لكنها مجموعة جزئية صغيرة من كل الدوال المتوازنة الممكنة. في هذه الحالة يكون الناتج المقيس هو $s$ نفسه، وهذا هو جسر الانتقال إلى خوارزمية بيرنشتاين–فازيراني.
المقارنة الصادقة: الخوارزمية الكلاسيكية الحتمية التي يجب أن تكون صحيحة دائماً تحتاج في أسوأ الحالات $2^{n-1}+1$ استعلاماً، لأن أول $2^{n-1}$ إجابة قد تكون متساوية حتى لدالة متوازنة. لكن خوارزمية كلاسيكية احتمالية تختار $k$ مدخلات عشوائية تخطئ باحتمال لا يتجاوز $2^{-(k-1)}$، فبضعة استعلامات تكفي عملياً. لذلك فالفصل الأسي هنا هو مقابل الخوارزميات الحتمية الدقيقة وفي نموذج الاستعلام فقط، وليس دليلاً على تسريع عملي. قيمة الخوارزمية أنها أوضح مثال على قوة التداخل الكمّي، وكانت من أوائل الأمثلة على فصل أسي بين نموذجين حسابيين (Deutsch & Jozsa 1992). يعرض المختبر النتيجة المقيسة والحكم (ثابتة أو متوازنة) مع عدد الاستعلامات الكمّية، وهو 1، مقابل الحد الكلاسيكي الحتمي $2^{n-1}+1$، أي 5 استعلامات عندما $n=3$.
المحاكاة التفاعلية والنتائج
المقارنة بالحل الكلاسيكي
| كلاسيكياً | $2^{n-1}+1$ استعلاماً (حتمي)؛ $O(1)$ استعلامات لخطأ صغير ثابت (احتمالي) |
|---|---|
| كمّياً | استعلام واحد، $n+1$ كيوبت، $O(n)$ بوابة إضافة إلى كلفة المُوحي |
حتمياً وبيقين: $2^{n-1}+1$ استعلاماً في أسوأ الحالات. احتمالياً: $k$ استعلامات عشوائية تعطي خطأ لا يتجاوز $2^{-(k-1)}$، فالميزة الكمّية هنا ميزة في نموذج الاستعلام مقابل الخوارزميات الدقيقة، لا تسريع عملي.
إذا لم يتحقق الوعد فلا معنى للنتيجة. في المختبر تكون الدوال المتوازنة خطية فقط ($f(x)=s\cdot x\oplus v$)، ويُبنى المُوحي من معرفة مسبقة بالدالة؛ والمحاكاة مثالية بلا ضجيج وتكلفتها تنمو كـ $2^{n+1}$.
شيفرة Qiskit
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: StatevectorSampler(seed=7)
from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler
def dj_circuit(n, kind, s="1", v=0):
"""Deutsch-Jozsa: inputs q0..q_{n-1}, ancilla q_n.
constant: f(x) = v ; balanced: f(x) = s.x XOR v (s != 0)."""
qc = QuantumCircuit(n + 1, n)
qc.x(n)
qc.h(range(n + 1))
qc.barrier()
if kind == "balanced":
for i, bit in enumerate(reversed(s)): # s is written q_{n-1}...q_0
if bit == "1":
qc.cx(i, n)
if v:
qc.x(n)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))
return qc
sampler = StatevectorSampler(seed=7)
for kind, s, v in [("constant", "000", 0), ("constant", "000", 1), ("balanced", "101", 0), ("balanced", "011", 1)]:
qc = dj_circuit(3, kind, s, v)
counts = sampler.run([qc], shots=1000).result()[0].data.c.get_counts()
out = max(counts, key=counts.get)
print(f"{kind:8s} s={s} v={v}: {counts} -> {'constant' if out == '000' else 'balanced'}")المخرجات الفعلية عند التشغيل
constant s=000 v=0: {'000': 1000} -> constant
constant s=000 v=1: {'000': 1000} -> constant
balanced s=101 v=0: {'101': 1000} -> balanced
balanced s=011 v=1: {'011': 1000} -> balancedتُشغَّل على جهازك بعد pip install qiskit qiskit-aer؛ لا تُنفَّذ داخل ووردبريس.
اختبر فهمك
يحتاج الاختبار إلى JavaScript.
موضوعات مرتبطة
المراجع
- David Deutsch; Richard Jozsa (1992). Rapid solution of problems by quantum computation. Proc. R. Soc. Lond. A 439(1907):553–558 doi:10.1098/rspa.1992.0167
- Michael A. Nielsen; Isaac L. Chuang (2010). Quantum Computation and Quantum Information (10th Anniversary Edition). Cambridge University Press doi:10.1017/CBO9780511976667المرجع الأساسي للحوسبة الكمّية؛ سجل Crossref يذكر 2012 لنسخة Cambridge Core الإلكترونية.
- John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com
