البحث غير المنظم

ملخص

سنبدأ بوصف المشكلة التي تحلها خوارزمية Grover. كالمعتاد، سنستخدم $\Sigma = \{0,1\}$ للدلالة على الأبجدية الثنائية طوال هذا النقاش.

لنفترض أن

$$f:\Sigma^n \rightarrow \Sigma$$

هي دالة من السلاسل الثنائية بطول $n$ إلى البتات. سنفترض أننا نستطيع حساب هذه الدالة بكفاءة، لكنها فيما عدا ذلك اعتباطية ولا يمكننا الاعتماد على وجود بنية خاصة أو تنفيذ محدد يلائم احتياجاتنا.

ما تفعله خوارزمية Grover هو البحث عن سلسلة $x\in\Sigma^n$ تُحقق $f(x) = 1.$ سنُسمي مثل هذه السلاسل حلولًا لمسألة البحث. إذا وُجدت حلول متعددة، يُعدّ أيٌّ منها إجابةً صحيحة، وإذا لم يوجد أي حل فإن الإجابة الصحيحة تستلزم التصريح بعدم وجود حلول.

تُوصف هذه المهمة بمسألة بحث غير منظم (unstructured search) لأننا لا يمكننا الاعتماد على وجود أي بنية خاصة في $f$ تجعل المهمة سهلة. نحن لا نبحث في قائمة مرتبة أو داخل هيكل بيانات مُصمَّم خصيصًا لتسهيل البحث، بل نبحث في جوهره عن إبرة في كومة قش.

بشكل حدسي، يمكننا تخيّل أن لدينا دائرة بوليانية بالغة التعقيد تحسب $f$، ويمكننا بسهولة تشغيل هذه الدائرة على سلسلة مُدخَلة مختارة. لكن لأن الدائرة بالغة التعقيد، لا أمل لنا في فهمها بفحصها (سوى امتلاك القدرة على تقييمها على سلاسل مُدخَلة مختارة).

إحدى طرق أداء مهمة البحث هذه كلاسيكيًا هي ببساطة المرور عبر جميع السلاسل $x\in\Sigma^n$، وتقييم $f$ على كل منها للتحقق من كونها حلًا أم لا. من الآن فصاعدًا، لنكتب

$$N = 2^n$$

لاختصار العبارة. يوجد $N$ سلسلة في $\Sigma^n$، ويستلزم المرور عبرها جميعًا $N$ تقييمًا لـ $f$. انطلاقًا من افتراض أننا مقيّدون بتقييم $f$ على مدخلات مختارة، هذا أفضل ما يمكننا تحقيقه بخوارزمية حتمية إذا أردنا ضمان النجاح. مع خوارزمية احتمالية، يمكن الأمل في توفير الوقت باختيار سلاسل مُدخَلة عشوائية لـ $f$، لكننا سنحتاج كذلك إلى $O(N)$ تقييمًا لـ $f$ إذا أردنا لهذه الطريقة أن تنجح باحتمال مرتفع.

تحل خوارزمية Grover مسألة البحث هذه باحتمال مرتفع بـ $O(\sqrt{N})$ تقييمًا فقط لـ $f$. وللتوضيح، يجب أن تتم تقييمات الدالة هذه في تراكب (in superposition)، على غرار خوارزميات الاستعلام الكمومي التي نوقشت في درس خوارزميات الاستعلام الكمومي، بما فيها خوارزمية Deutsch، وخوارزمية Deutsch-Jozsa، وخوارزمية Simon. على خلاف تلك الخوارزميات، تتبنى خوارزمية Grover نهجًا تكراريًا: تُقيِّم $f$ على تراكبات سلاسل المُدخَلات وتتخلل هذه التقييمات بعمليات أخرى ذات تأثير في إنشاء أنماط تداخل (interference patterns)، مما يُفضي إلى حل باحتمال مرتفع (إذا وُجد) بعد $O(\sqrt{N})$ تكرارًا.

صياغة رسمية للمسألة

سنُصوِّغ المسألة التي تحلها خوارزمية Grover بشكل رسمي باستخدام نموذج الحساب بالاستعلام (query model). أي سنفترض أن بإمكاننا الوصول إلى الدالة $f:\Sigma^n\rightarrow\Sigma$ عبر بوابة استعلام مُعرَّفة بالطريقة المعتادة:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

لكل $x\in\Sigma^n$ و $a\in\Sigma$. هذا هو تأثير $U_f$ على حالات الأساس القياسية، ويُحدَّد تأثيرها عمومًا بالخطية.

كما نُوقش في درس أسس الخوارزميات الكمومية، إذا كان لدينا دائرة بوليانية لحساب $f$، يمكننا تحويل وصف تلك الدائرة إلى دائرة كمومية تُنفِّذ $U_f$ (باستخدام عدد من كيوبتات مساحة العمل التي تبدأ وتنتهي الحساب في حالة $\vert 0\rangle$). لذا، رغم استخدامنا نموذج الاستعلام لتصوير المسألة التي تحلها خوارزمية Grover، فإنها ليست مقتصرة على هذا النموذج؛ يمكن تشغيل خوارزمية Grover على أي دالة $f$ تتوفر لها دائرة بوليانية.

إليك صياغة دقيقة للمسألة، التي تُسمى بحث (Search) لأننا نبحث عن حل، أي عن سلسلة $x$ تجعل $f$ تُقيَّم بـ $1$.

بحث (Search)

المُدخَل: دالة $f:\Sigma^n\rightarrow\Sigma$
المُخرَج: سلسلة $x\in\Sigma^n$ تُحقق $f(x) = 1$، أو "لا حل" إذا لم توجد سلسلة $x$ كهذه

لاحظ أن هذه ليست مسألة وعد (promise problem) — الدالة $f$ اعتباطية. سيكون مفيدًا مع ذلك تناول النوع التالي من المسألة مع وعد، حيث يُضمن وجود حل واحد فقط. ظهرت هذه المسألة كمثال على مسألة وعد في درس خوارزميات الاستعلام الكمومي.

بحث فريد (Unique search)

المُدخَل: دالة من النوع $f:\Sigma^n \rightarrow \Sigma$
الوعد: توجد سلسلة فريدة $z\in\Sigma^n$ تُحقق $f(z) = 1$، مع $f(x) = 0$ لجميع السلاسل $x\neq z$
المُخرَج: السلسلة $z$

لاحظ أيضًا أن مسألة Or المذكورة في الدرس نفسه وثيقة الصلة بمسألة البحث. في تلك المسألة، الهدف هو تحديد ما إذا كان يوجد حل أم لا، في مقابل إيجاد الحل فعليًا.