خوارزمية سايمون
Simon's Algorithm
تجد خوارزمية سايمون الدور المخفي $s$ لدالة تحقق $f(x)=f(y)\iff y\in\{x,x\oplus s\}$ بنحو $O(n)$ استعلاماً، بينما تحتاج الخوارزميات الكلاسيكية الاحتمالية عدداً أسياً $\Omega(2^{n/2})$.
خوارزمية سايمون (Simon's Algorithmخوارزمية سايمون: تجد خوارزمية سايمون الدور المخفي s لدالة تحقق f(x)=f(y) y∈\x,x⊕ s\ بنحو O(n) استعلاماً، بينما تحتاج الخوارزميات الكلاسيكية الاحتمالية عدداً أسياً Ω(2^n/2).) كانت أول مثال على فصل أسي في نموذج المُوحي بين الحاسوب الكمّي والحاسوب الكلاسيكي الاحتمالي، وألهمت مباشرةً خوارزمية شور (Simon 1997).
المسألة: دالة $f:\{0,1\}^n\to\{0,1\}^n$ مع وعد بوجود سلسلة $s\neq0$ بحيث $f(x)=f(y)$ إذا وفقط إذا كان $y=x$ أو $y=x\oplus s$، أي أن الدالة «اثنان إلى واحد» ودورية بالنسبة إلى XOR. المطلوب إيجاد $s$.
كلاسيكياً، الطريقة الوحيدة هي البحث عن «تصادم» $f(x)=f(y)$ ثم حساب $s=x\oplus y$، ووفق مفارقة أعياد الميلاد يحتاج ذلك نحو $2^{n/2}$ استعلاماً، وقد أُثبت أن أي خوارزمية احتمالية تحتاج $\Omega(2^{n/2})$.
كمّياً نستعمل سجلّين من $n$ كيوبت. نضع الأول في تراكب كامل، نستعلم المُوحي $|x\rangle|0\rangle\mapsto|x\rangle|f(x)\rangle$، ثم نتجاهل السجل الثاني (أو نقيسه). يبقى السجل الأول في $\frac{1}{\sqrt2}(|x_0\rangle+|x_0\oplus s\rangle)$ لقيمة عشوائية $x_0$. بعد هادامارد تصبح سعة كل $y$ متناسبة مع $(-1)^{x_0\cdot y}\big(1+(-1)^{s\cdot y}\big)$، فلا تظهر إلا القيم $y$ التي تحقق $y\cdot s=0 \pmod 2$، وبتوزيع منتظم بينها. كل تشغيل يعطي معادلة خطية واحدة على $s$. بعد نحو $n-1$ معادلة مستقلة خطياً (عادةً $O(n)$ تشغيلاً) نحل النظام بحذف غاوس على الحقل $\mathrm{GF}(2)$ فنحصل على $s$ الوحيدة غير الصفرية.
بناء المُوحي في المختبر: نسخ السجل الأول إلى الثاني بـ CNOT ($f(x)=x$)، ثم إذا كان $j$ أدنى بت يساوي 1 في $s$ نضيف CNOT من الكيوبت $j$ إلى كل كيوبت $n+i$ يكون فيه $s_i=1$. النتيجة $f(x)=x\oplus x_j s$، وهي فعلاً تحقق $f(x)=f(x\oplus s)$ واثنان إلى واحد. يأخذ المختبر افتراضياً $3n+4$ عينة ثم يتحقق من أن كل $y$ مقيسة تحقق $y\cdot s=0$ ويحل النظام كلاسيكياً.
المقارنة الصادقة: الفصل الأسي مُثبت في نموذج المُوحي فقط؛ ولا توجد مسألة عملية معروفة تُحل بخوارزمية سايمون مباشرة. والجزء الكلاسيكي (حذف غاوس) جزء أساسي من الخوارزمية، فهي خوارزمية هجينة بطبيعتها.
الصياغة الرياضية
مثال محلول
لتكن $s=110$ ($n=3$). القيم $y$ التي تحقق $y\cdot s=y_2\oplus y_1=0$ هي $\{000,001,110,111\}$، وكلٌّ منها يظهر باحتمال $\tfrac14$.
افترض أننا قسنا $001$ و$110$ (مستقلتان خطياً). المعادلتان: $s_0=0$ و$s_2\oplus s_1=0$. الحلول غير الصفرية: $s_2=s_1=1, s_0=0$، أي $s=110$. النتيجة $000$ لا تفيد، و$111$ تعطي $s_2\oplus s_1\oplus s_0=0$ وهي تابعة للمعادلتين السابقتين.
جرّب بنفسك: مستكشف الخوارزميات الكمّية
اختبر فهمك
يحتاج الاختبار إلى JavaScript.
المراجع
- Daniel R. Simon (1997). On the Power of Quantum Computation. SIAM J. Comput. 26(5):1474–1483 doi:10.1137/S0097539796298637
- 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
