كتب الذكاء الاصطناعيمشاريع الذكاء الاصطناعيمقالات الذكاء الاصطناعيمعجم الذكاء الاصطناعياسئلة واجوبة في الذكاء الاصطناعيأكاديمية الذكاء الاصطناعي للأطفالأكاديمية الذكاء الاصطناعيمدرسة رياضيات الذكاء الاصطناعيمختبر الذكاء الاصطناعيمختبر الخوارزميات المستوحاة من الطبيعةأطلس نماذج الذكاء الاصطناعيموسوعة تطبيقات الذكاء الاصطناعيمستكشف مجموعات البيانات للذكاء الاصطناعياختبارات الذكاء الاصطناعيالفايب كودينغدليل البرمجة بالذكاء الاصطناعيمولّد مشاريع الذكاء الاصطناعيمرصد الذكاء الاصطناعيدليل أدوات الذكاء الاصطناعي البحث والنشر الأكاديميمكتبة البرومبتات الأكاديميةمستودع الرسائل والأطاريح في الذكاء الاصطناعيحاسبة الترقية العلميةأكاديمية الوكلاء الذكيينمختبر أخلاقيات الذكاء الاصطناعي والعدالةساحة ألعاب الذكاء الاصطناعيمختبر التنبؤ بالسلاسل الزمنيةمتحف الذكاء الاصطناعيمختبر الرؤية الحاسوبيةمختبر الشبكات العصبية البيانيةمختبر معالجة اللغة الطبيعيةمختبر الحوسبة الكمّيةخرائط طريق الذكاء الاصطناعيمصمم الشبكات العصبية
خوارزميةمتقدمخوارزميات فورييه والطور

خوارزمية شور

Shor's Factoring Algorithm

تحلّل خوارزمية شور عدداً صحيحاً $N$ إلى عوامله في زمن حدودي في $\log N$ عبر إيجاد رتبة $a$ بمقياس $N$ كمّياً؛ لكنها تتطلب حاسوباً كمّياً كبيراً متحمّلاً للأخطاء غير متاح اليوم.

Shor's algorithm factors N in time polynomial in log N via quantum order finding, but needs a large fault-tolerant quantum computer that does not yet exist.

المسألة

إيجاد عامل غير بديهي لعدد صحيح مركّب $N$.

الفكرة الأساسية

اختزال التحليل كلاسيكياً إلى إيجاد رتبة $a$ بمقياس $N$، وإيجاد الرتبة كمّياً بتقدير طور بوابة الضرب النمطي ثم الكسور المستمرة.

المتطلبات

دارات ضرب نمطي عكوسة ومتحكَّم بها، $\mathrm{QFT}^\dagger$، آلاف الكيوبتات المنطقية لأعداد ذات حجم تشفيري، وتصحيح أخطاء كمّي.

الخطوات

  1. اختر $1<a<N$ عشوائياً؛ إذا كان $\gcd(a,N)>1$ فقد وجدت عاملاً.
  2. حضّر سجل عدّ ($t$ كيوبت) في تراكب، وسجل عمل في $|1\rangle$.
  3. طبّق الضرب في $a^{2^j}\bmod N$ على سجل العمل متحكَّماً به من كيوبت العدّ $j$.
  4. طبّق $\mathrm{QFT}^\dagger$ على سجل العدّ وقِسه فتحصل على $m$.
  5. استخرج $r$ من $m/2^t$ بالكسور المستمرة وتحقق أن $a^r\equiv1$.
  6. إذا كانت $r$ زوجية و$a^{r/2}\not\equiv-1$ احسب $\gcd(a^{r/2}\pm1,N)$؛ وإلا كرّر.

خوارزمية شور (Shor's Algorithm) تحل مسألة تحليل الأعداد الصحيحة إلى عواملها الأولية، وهي المسألة التي يقوم عليها أمان تشفير RSA. نشرها شور عام 1994 (والنسخة الموسّعة في 1997)، وتعمل في زمن حدودي في عدد بتات $N$، بينما أفضل خوارزمية كلاسيكية معروفة، وهي غربال حقل الأعداد العام (General Number Field Sieve)، تعمل في زمن دون أسي $\exp\!\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$. لا يوجد برهان على أن التحليل صعب كلاسيكياً؛ الفرق هو مع أفضل خوارزمية كلاسيكية معروفة.

الاختزال الكلاسيكي: اختر $a$ عشوائياً مع $1<a1$ فقد وجدنا عاملاً دون أي حوسبة كمّية. وإلا نبحث عن الرتبة $r$، أصغر عدد موجب يحقق $a^r\equiv1 \pmod N$. إذا كانت $r$ زوجية و$a^{r/2}\not\equiv-1$ فإن $\gcd(a^{r/2}\pm1,N)$ يعطي عاملاً غير بديهي. هذا يحدث باحتمال لا يقل عن النصف لـ $a$ العشوائي عندما يكون $N$ فردياً وليس قوة لعدد أولي.

الجزء الكمّي هو إيجاد الرتبة، وهو تقدير طور لبوابة الضرب النمطي $U|y\rangle=|ay\bmod N\rangle$، التي قيمها الذاتية $e^{2\pi i s/r}$. سجل عدّ من $t\approx2\log_2N$ كيوبت في تراكب، وتطبيق $U^{2^j}$ المتحكَّم بها (الضرب في $a^{2^j}\bmod N$)، ثم $\mathrm{QFT}^\dagger$ وقياس. النتيجة $m$ تحقق $m/2^t\approx s/r$، وخوارزمية الكسور المستمرة (Continued Fractions) تستخرج $r$ من هذا التقريب.

ماذا يفعل المختبر؟ يقبل $N\in\{15,21,33,35\}$ فقط. يأخذ $L=\lceil\log_2(N+1)\rceil$ كيوبت عمل و$t=2L$ كيوبت عدّ، ويطبّق الضرب النمطي تبديلاً (Permutation) لسجل العمل مبنياً بالحساب النمطي الكلاسيكي. لـ $N=15,a=7$ تكون $r=4$، وتظهر القمم عند $m\in\{0,64,128,192\}$ باحتمال $\tfrac14$ لكلٍّ منها. القمتان 64 و192 تعطيان $r=4$ ثم العاملين 3 و5؛ بينما 128 تعطي $r=2$ خاطئة و0 لا تعطي شيئاً، فالخوارزمية احتمالية وتُكرَّر.

المقارنة الصادقة: (1) بناء التبديلات كلاسيكياً في المختبر يعني أن المحاكاة ليست دليلاً على أي تسريع؛ إنها تحاكي رياضيات الدارة بأمانة فقط. (2) التنفيذ الحقيقي يحتاج دارات حسابية نمطية عكوسة بآلاف أو ملايين البوابات وتصحيح أخطاء، أي حاسوباً كمّياً متحمّلاً للأخطاء غير موجود اليوم. (3) التجارب المنشورة حلّلت أعداداً صغيرة جداً مثل 15 (Vandersypen وآخرون 2001 بالرنين المغناطيسي النووي)، وغالباً بدارات مبسّطة تستفيد من معرفة الجواب مسبقاً.

$$a^r\equiv1\pmod N,\qquad \frac{m}{2^t}\approx\frac{s}{r},\qquad \{p,q\}=\gcd\!\big(a^{r/2}\pm1,\,N\big)$$

المحاكاة التفاعلية والنتائج

جارٍ تحميل المحاكي…

المقارنة بالحل الكلاسيكي

كلاسيكياً$\exp\big(O((\log N)^{1/3}(\log\log N)^{2/3})\big)$ (GNFS، أفضل معروف)
كمّياً$O((\log N)^3)$ بوابة تقريباً بالحساب المدرسي، و$O(\log N)$ كيوبت منطقي

أفضل خوارزمية كلاسيكية معروفة (غربال حقل الأعداد العام) دون أسية: $\exp(O((\log N)^{1/3}(\log\log N)^{2/3}))$. شور حدودية في $\log N$. الفرق أسي مقابل أفضل خوارزمية معروفة، لا مقابل حد أدنى مُثبت. ويتطلب حاسوباً كمّياً كبيراً متحمّلاً للأخطاء.

حدود الخوارزمية والمحاكاة

المختبر يقبل $N\in\{15,21,33,35\}$ فقط، ويبني الضرب النمطي تبديلاً بالحساب الكلاسيكي، فهو ليس دليلاً على تسريع. النتيجة احتمالية وبعض القياسات تعطي رتبة خاطئة أو صفراً. تكلفة المحاكاة $2^{t+L}$ سعة (لـ $N=35$: $t=12$ و$L=6$، أي $2^{18}$ سعة). لا توجد اليوم أجهزة قادرة على تحليل أعداد ذات أهمية تشفيرية.

شيفرة Qiskit

Qiskit ≥ 1.0
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: AerSimulator(seed_simulator=1)
import math
from fractions import Fraction
import numpy as np
from qiskit import QuantumCircuit, transpile
from qiskit.circuit.library import QFTGate, UnitaryGate
from qiskit_aer import AerSimulator

N, a = 15, 7
L = math.ceil(math.log2(N + 1))  # work register: 4 qubits
t = 2 * L                        # counting register: 8 qubits

def mult_gate(m):
    """U|y> = |m*y mod N> for y < N, |y> otherwise (a permutation matrix).
    NOTE: built with classical modular arithmetic - fine for a demo, not a scalable circuit."""
    U = np.zeros((2 ** L, 2 ** L))
    for y in range(2 ** L):
        U[(m * y) % N if y < N else y, y] = 1
    return UnitaryGate(U, label=f"x{m} mod {N}")

qc = QuantumCircuit(t + L, t)
qc.x(t)                          # work register = |1>
qc.h(range(t))
for j in range(t):               # controlled-U^(2^j) = multiplication by a^(2^j) mod N
    qc.append(mult_gate(pow(a, 2 ** j, N)).control(1), [j] + list(range(t, t + L)))
qc.append(QFTGate(t).inverse(), range(t))
qc.measure(range(t), range(t))

sim = AerSimulator(seed_simulator=1)
counts = sim.run(transpile(qc, sim, seed_transpiler=1), shots=256).result().get_counts()
print("counts:", dict(sorted(counts.items(), key=lambda kv: -kv[1])))

for bits in sorted(counts, key=counts.get, reverse=True):
    m = int(bits, 2)
    r = Fraction(m, 2 ** t).limit_denominator(N).denominator   # continued fractions
    ok = pow(a, r, N) == 1
    msg = f"m={m:3d} phase={m / 2**t:.4f} -> r={r} (a^r mod N == 1: {ok})"
    if ok and r % 2 == 0 and pow(a, r // 2, N) != N - 1:
        h = pow(a, r // 2, N)
        msg += f" -> factors {math.gcd(h - 1, N)} x {math.gcd(h + 1, N)}"
    print(msg)

المخرجات الفعلية عند التشغيل

counts: {'11000000': 69, '01000000': 66, '10000000': 66, '00000000': 55}
m=192 phase=0.7500 -> r=4 (a^r mod N == 1: True) -> factors 3 x 5
m= 64 phase=0.2500 -> r=4 (a^r mod N == 1: True) -> factors 3 x 5
m=128 phase=0.5000 -> r=2 (a^r mod N == 1: False)
m=  0 phase=0.0000 -> r=1 (a^r mod N == 1: False)

تُشغَّل على جهازك بعد pip install qiskit qiskit-aer؛ لا تُنفَّذ داخل ووردبريس.

اختبر فهمك

يحتاج الاختبار إلى JavaScript.

موضوعات مرتبطة

المراجع

  1. Peter W. Shor (1997). Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 26(5):1484–1509 doi:10.1137/S0097539795293172
  2. L. M. K. Vandersypen; M. Steffen; G. Breyta; C. S. Yannoni; M. H. Sherwood; I. L. Chuang (2001). Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance. Nature 414:883–887 doi:10.1038/414883a
  3. Don Coppersmith (1994). An approximate Fourier transform useful in quantum factoring. IBM Research Report RC19642 (arXiv:quant-ph/0201067, 2002) doi:10.48550/arXiv.quant-ph/0201067
  4. 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 الإلكترونية.
  5. John Watrous / IBM Quantum (2025). Fundamentals of Quantum Algorithms (course). IBM Quantum Learning quantum.cloud.ibm.com