خوارزمية سايمون
Simon's Algorithm
دائرة سايمون لـ $s=110$: كل النتائج $y$ تحقق $y\cdot s=0$ (بترديد 2)، ومنها يُستخرج $s$ كلاسيكياً.
Simon's circuit for s = 110: every outcome y satisfies y·s = 0 mod 2, from which s is recovered classically.
الأوراكل ينسخ المدخل إلى سجل المخرج ثم يضيف $s$ عندما يكون البت $j$ (أدنى بت غير صفري في $s$) مساوياً 1؛ فتصبح $f(x)=f(x\oplus s)$. بعد H وقياس سجل المدخل فقط تظهر أربع قيم $y$ متساوية الاحتمال، كلها متعامدة مع $s$ بترديد 2. السطر الأخير يتحقق من ذلك لكل نتيجة.
المتطلبات: pip install qiskit qiskit-aer. تُشغَّل الشيفرة على جهازك أو في Colab، لا داخل ووردبريس.
الشيفرة
from qiskit import QuantumCircuit
from qiskit.primitives import StatevectorSampler
s = "110"
n = len(s)
qc = QuantumCircuit(2 * n, n)
qc.h(range(n))
for i in range(n):
qc.cx(i, n + i)
j = s[::-1].index("1")
for i, bit in enumerate(reversed(s)):
if bit == "1":
qc.cx(j, n + i)
qc.h(range(n))
qc.measure(range(n), range(n))
counts = StatevectorSampler(seed=6).run([qc], shots=400).result()[0].data.c.get_counts()
print(dict(sorted(counts.items())))
def dot(a, b):
return sum(int(x) * int(y) for x, y in zip(a, b)) % 2
print({y: dot(y, s) for y in sorted(counts)})
شرح الشيفرة سطراً بسطر
| السطر | الشرح |
|---|---|
| 1-2 | الاستيراد. |
| 4-5 | السر وطوله. |
| 6 | سجلان من n كيوبت: مدخل ومخرج. |
| 7 | تراكب على المدخل. |
| 8-9 | نسخ المدخل إلى المخرج. |
| 10 | أدنى موضع فيه s_j = 1. |
| 11-13 | إضافة s إلى المخرج مشروطة بالبت j. |
| 14 | H على المدخل. |
| 15 | قياس المدخل فقط. |
| 17 | 400 عينة ببذرة 6. |
| 18 | طباعة العدّات مرتبة. |
| 21-22 | حاصل الضرب النقطي بترديد 2. |
| 25 | التحقق: y·s = 0 لكل نتيجة. |
المخرجات المتوقعة (من تشغيل فعلي)
{'000': 101, '001': 92, '110': 90, '111': 117}
{'000': 0, '001': 0, '110': 0, '111': 0}
العدّات من StatevectorSampler(seed=6)؛ القيم الأربع متساوية الاحتمال نظرياً.
جرّب بنفسك
موضوعات مرتبطة
المراجع
- 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 الإلكترونية.
