خوارزمية غروفر
Grover's Search Algorithm
تجد خوارزمية غروفر عنصراً معلَّماً بين $N$ عنصراً بنحو $\frac{\pi}{4}\sqrt{N/M}$ استعلاماً بدلاً من $O(N/M)$ كلاسيكياً: تسريع تربيعي مُثبت أنه الأمثل.
Grover's algorithm finds a marked item among N with about (π/4)√(N/M) oracle queries instead of O(N/M): a provably optimal quadratic speed-up.
المسألة
بين $N=2^n$ عنصراً يوجد $M$ عنصراً معلَّماً يتعرّف عليها مُوحٍ؛ المطلوب إيجاد أحدها دون أي بنية مساعدة.
الفكرة الأساسية
تكرار (مُوحي الطور + الانعكاس حول المتوسط) يدير الحالة بزاوية $2\theta$ في كل مرة نحو تراكب العناصر المعلَّمة، فتتضخم سعتها.
المتطلبات
مُوحي طور قابل للتنفيذ دارةً، وبوابات متعددة التحكم (تتفكك إلى توفولي وCNOT)، ومعرفة $M$ أو استراتيجية لعدم معرفته.
الخطوات
- حضّر $|s\rangle=H^{\otimes n}|0\rangle^{\otimes n}$.
- طبّق مُوحي الطور: $|x\rangle\mapsto-|x\rangle$ للعناصر المعلَّمة.
- طبّق المنتشر: $H^{\otimes n}X^{\otimes n}(\text{MCZ})X^{\otimes n}H^{\otimes n}$.
- كرّر الخطوتين 2–3 نحو $k=\lfloor\pi/(4\theta)\rfloor$ مرة.
- قِس؛ وتحقق كلاسيكياً من أن النتيجة معلَّمة (وأعد عند الفشل).
خوارزمية غروفر (Grover's Algorithm) تحل مسألة البحث غير المهيكل (Unstructured Search): لدينا $N=2^n$ عنصراً، منها $M$ عناصر «معلَّمة» يتعرّف عليها مُوحٍ، ولا نعرف أي بنية تساعد في البحث. كلاسيكياً لا بد من فحص العناصر واحداً تلو الآخر، فالعدد المتوقع للاستعلامات $(N+1)/(M+1)$، أي $O(N/M)$. كمّياً يكفي نحو $\frac{\pi}{4}\sqrt{N/M}$ استعلاماً (Grover 1996).
الدارة: نبدأ بالتراكب المنتظم $|s\rangle=H^{\otimes n}|0\rangle$، ثم نكرّر «تكرار غروفر» $k$ مرات. كل تكرار من خطوتين: (1) مُوحي الطور يضرب سعات العناصر المعلَّمة في $-1$؛ (2) المنتشر (Diffuser) $2|s\rangle\langle s|-I$ يعكس كل السعات حول متوسطها. النتيجة هي «تضخيم السعة» (Amplitude Amplification): سعة العناصر المعلَّمة تكبر في كل تكرار.
الصورة الهندسية: الحالة تبقى في مستوى يحدده $|w\rangle$ (تراكب العناصر المعلَّمة) و$|w^\perp\rangle$. الحالة الابتدائية تصنع زاوية $\theta$ مع $|w^\perp\rangle$ حيث $\sin\theta=\sqrt{M/N}$، وكل تكرار يمثّل دوراناً بزاوية $2\theta$ نحو $|w\rangle$. بعد $k$ تكرارات:
$$P_{\text{success}}=\sin^2\big((2k+1)\theta\big).$$
العدد الأمثل $k=\lfloor\frac{\pi}{4\theta}\rfloor$. الزيادة بعد ذلك تعيد الاحتمال إلى الانخفاض («الإفراط في الدوران»)، ولهذا يرسم المختبر منحنى الاحتمال مقابل $k$ ويقارن قيم المحاكي بالصيغة. إذا كان $M$ مجهولاً تُستعمل استراتيجية عشوائية لاختيار $k$ تحافظ على كلفة $O(\sqrt{N/M})$ (Boyer وآخرون 1998)، الذين أثبتوا أيضاً حدوداً دنيا محكمة: لا توجد خوارزمية كمّية في نموذج المُوحي أفضل من $\Omega(\sqrt{N/M})$.
في المختبر: مُوحي الطور يقلب الكيوبتات التي قيمتها 0 في العنصر المعلَّم بـ $X$، ثم يطبّق $Z$ متعددة التحكم ($CZ$ لكيوبتين)، ثم يعيد $X$. لكل عنصر معلَّم كتلة مماثلة.
المقارنة الصادقة: التسريع تربيعي فقط وليس أسياً. والمُوحي يجب أن يُبنى دارةً؛ فالخوارزمية لا تسرّع البحث في قاعدة بيانات مخزنة كلاسيكياً ما لم تتوفر ذاكرة كمّية قابلة للعنونة، وهي غير متاحة عملياً اليوم. وعلى العتاد المتحمّل للأخطاء قد تلتهم كلفة تصحيح الأخطاء قسماً كبيراً من الفائدة التربيعية لمسائل ذات أحجام واقعية. لكن تضخيم السعة أداة عامة تُستعمل إجراءً فرعياً في خوارزميات أخرى.
المحاكاة التفاعلية والنتائج
المقارنة بالحل الكلاسيكي
| كلاسيكياً | $O(N/M)$ استعلاماً |
|---|---|
| كمّياً | $\approx\frac{\pi}{4}\sqrt{N/M}$ استعلاماً، $n$ كيوبت (إضافة إلى مساعدات المُوحي) |
كلاسيكياً: $(N+1)/(M+1)$ استعلاماً في المتوسط، أي $O(N/M)$. كمّياً: $O(\sqrt{N/M})$. التسريع تربيعي فقط، ومُثبت أنه الأفضل الممكن في نموذج المُوحي. لا يعني ذلك تسريع قواعد البيانات الكلاسيكية، وقد تقلّص كلفة تصحيح الأخطاء الفائدة العملية.
التسريع تربيعي لا أسي. المُوحي في المختبر يُبنى من قائمة العناصر المعلَّمة المعروفة مسبقاً، أي أنه توضيحي. بوابة Z متعددة التحكم تُطبَّق في المحاكي مباشرةً، بينما على العتاد تتطلب تفكيكاً عميقاً تتراكم فيه الأخطاء. المحاكاة تحتاج $2^n$ سعة، والحد الافتراضي في المتصفح 16 كيوبتاً.
شيفرة Qiskit
# Tested with Qiskit 2.6.2 / qiskit-aer 0.18.4; output shown was produced with: AerSimulator(seed_simulator=2024)
import math
from qiskit import QuantumCircuit, transpile
from qiskit_aer import AerSimulator
n, marked = 3, 5 # search space N = 8, marked |101>
N = 2 ** n
def mcz(qc): # multi-controlled Z on all n qubits
qc.h(n - 1)
qc.mcx(list(range(n - 1)), n - 1)
qc.h(n - 1)
def oracle(qc): # phase flip of |marked>
zeros = [i for i in range(n) if not (marked >> i) & 1]
if zeros: qc.x(zeros)
mcz(qc)
if zeros: qc.x(zeros)
def diffuser(qc): # 2|s><s| - I (up to global phase)
qc.h(range(n)); qc.x(range(n))
mcz(qc)
qc.x(range(n)); qc.h(range(n))
k = math.floor(math.pi / (4 * math.asin(math.sqrt(1 / N)))) # optimal iterations = 2
qc = QuantumCircuit(n)
qc.h(range(n))
for _ in range(k):
oracle(qc); diffuser(qc)
qc.measure_all()
sim = AerSimulator(seed_simulator=2024)
counts = sim.run(transpile(qc, sim, seed_transpiler=1), shots=1000).result().get_counts()
theta = math.asin(math.sqrt(1 / N))
print("iterations k =", k)
print("counts:", dict(sorted(counts.items(), key=lambda kv: -kv[1])))
print("theory P(success) = sin^2((2k+1)theta) =", round(math.sin((2 * k + 1) * theta) ** 2, 4))المخرجات الفعلية عند التشغيل
iterations k = 2
counts: {'101': 941, '001': 14, '000': 11, '110': 10, '100': 8, '111': 6, '011': 5, '010': 5}
theory P(success) = sin^2((2k+1)theta) = 0.9453تُشغَّل على جهازك بعد pip install qiskit qiskit-aer؛ لا تُنفَّذ داخل ووردبريس.
اختبر فهمك
يحتاج الاختبار إلى JavaScript.
موضوعات مرتبطة
المراجع
- Lov K. Grover (1996). A fast quantum mechanical algorithm for database search. Proc. 28th ACM STOC, pp. 212–219 doi:10.1145/237814.237866
- Michel Boyer; Gilles Brassard; Peter Høyer; Alain Tapp (1998). Tight Bounds on Quantum Searching. Fortschritte der Physik 46(4-5):493–505 doi:10.1002/(SICI)1521-3978(199806)46:4/53.0.CO;2-P
- 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
