خوارزمية سايمون
Simon's Algorithm
تجد خوارزمية سايمون الدور المخفي $s$ لدالة تحقق $f(x)=f(y)\iff y\in\{x,x\oplus s\}$ بنحو $O(n)$ استعلاماً، بينما تحتاج الخوارزميات الكلاسيكية الاحتمالية عدداً أسياً $\Omega(2^{n/2})$.
Simon's algorithm finds the hidden period s of a two-to-one function with O(n) queries, whereas classical randomized algorithms need Ω(2^{n/2}).
المسألة
دالة $f:\{0,1\}^n\to\{0,1\}^n$ مضمون أنها تحقق $f(x)=f(y)\iff y\in\{x,x\oplus s\}$؛ المطلوب إيجاد $s\neq0$.
الفكرة الأساسية
الاستعلام على تراكب ثم هادامارد يجعل النتائج المقيسة $y$ تحقق دائماً $y\cdot s=0$؛ جمع $n-1$ معادلة مستقلة يحدد $s$ بالجبر الخطي على $\mathrm{GF}(2)$.
المتطلبات
$2n$ كيوبت، مُوحٍ يحقق الوعد، ومعالجة كلاسيكية لحل نظام خطي على $\mathrm{GF}(2)$.
الخطوات
- هيّئ سجلين من $n$ كيوبت في $|0\rangle$.
- طبّق $H$ على السجل الأول.
- استعلم المُوحي: $|x\rangle|0\rangle\mapsto|x\rangle|f(x)\rangle$.
- طبّق $H$ على السجل الأول وقِسه فتحصل على $y$ مع $y\cdot s=0$.
- كرّر حتى تحصل على $n-1$ معادلة مستقلة خطياً.
- حلّ النظام بحذف غاوس على $\mathrm{GF}(2)$ كلاسيكياً.
خوارزمية سايمون (Simon's Algorithm) كانت أول مثال على فصل أسي في نموذج المُوحي بين الحاسوب الكمّي والحاسوب الكلاسيكي الاحتمالي، وألهمت مباشرةً خوارزمية شور (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$ ويحل النظام كلاسيكياً.
المقارنة الصادقة: الفصل الأسي مُثبت في نموذج المُوحي فقط؛ ولا توجد مسألة عملية معروفة تُحل بخوارزمية سايمون مباشرة. والجزء الكلاسيكي (حذف غاوس) جزء أساسي من الخوارزمية، فهي خوارزمية هجينة بطبيعتها.
المحاكاة التفاعلية والنتائج
المقارنة بالحل الكلاسيكي
| كلاسيكياً | $\Theta(2^{n/2})$ استعلاماً |
|---|---|
| كمّياً | $O(n)$ استعلاماً، $2n$ كيوبت، و$O(n^3)$ عمليات كلاسيكية لحذف غاوس |
أي خوارزمية كلاسيكية احتمالية تحتاج $\Omega(2^{n/2})$ استعلاماً (البحث عن تصادم). الكمّية تحتاج $O(n)$ استعلاماً مع معالجة كلاسيكية حدودية: فصل أسي مُثبت في نموذج المُوحي.
الفصل مُثبت في نموذج المُوحي وليس لمسألة عملية. مُوحي المختبر نوع واحد خاص من الدوال الدورية ($f(x)=x\oplus x_j s$)، ويُبنى بمعرفة $s$. عدد العينات الافتراضي $3n+4$ قد لا يكفي أحياناً لتحديد $s$ بتفرّد (يبلغ المختبر عن رتبة النظام والمرشحين). المحاكاة تحتاج $2^{2n}$ سعة.
شيفرة Qiskit
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: StatevectorSampler(seed=3)
from itertools import product
from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler
s = "110" # hidden period, printed q2 q1 q0
n = len(s)
sb = [int(b) for b in reversed(s)] # sb[i] = bit of qubit i
# Oracle f(x) = x XOR (x_j * s), j = lowest set bit of s -> f(x) = f(x XOR s)
qc = QuantumCircuit(2 * n, n)
qc.h(range(n))
qc.barrier()
for i in range(n):
qc.cx(i, n + i)
j = sb.index(1)
for i in range(n):
if sb[i]:
qc.cx(j, n + i)
qc.barrier()
qc.h(range(n))
qc.measure(range(n), range(n))
counts = StatevectorSampler(seed=3).run([qc], shots=12).result()[0].data.c.get_counts()
print("measured y:", counts)
dot = lambda a, b: sum(int(x) * int(y) for x, y in zip(a, b)) % 2
print("all y satisfy y.s = 0 (mod 2):", all(dot(y, s) == 0 for y in counts))
# classical post-processing: non-zero candidates orthogonal to every observed y
cands = ["".join(c) for c in product("01", repeat=n) if "1" in c and all(dot(y, "".join(c)) == 0 for y in counts)]
print("candidates for s:", cands)المخرجات الفعلية عند التشغيل
measured y: {'000': 5, '111': 1, '110': 3, '001': 3}
all y satisfy y.s = 0 (mod 2): True
candidates for s: ['110']تُشغَّل على جهازك بعد pip install qiskit qiskit-aer؛ لا تُنفَّذ داخل ووردبريس.
اختبر فهمك
يحتاج الاختبار إلى 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
