اختيار عدد التكرارات

أثبتنا أن متجه الحالة للسجل $\mathsf{Q}$ في خوارزمية غروفر يبقى في الفضاء الثنائي الأبعاد الممتد بين $\vert A_0\rangle$ و$\vert A_1\rangle$ بمجرد تنفيذ خطوة التهيئة.

الهدف هو إيجاد عنصر $x\in A_1$، وسيتحقق هذا الهدف إذا تمكنا من الحصول على الحالة $\vert A_1\rangle$ — لأنه إذا قسنا هذه الحالة، سنحصل بالتأكيد على نتيجة قياس $x\in A_1$. بما أن حالة $\mathsf{Q}$ بعد $t$ تكرار في الخطوة الثانية هي

$$G^t \vert u \rangle = \cos\bigl((2t + 1)\theta\bigr) \vert A_0\rangle + \sin\bigl((2t + 1)\theta\bigr) \vert A_1\rangle,$$

ينبغي اختيار $t$ بحيث يكون

$$\langle A_1 \vert G^t \vert u \rangle = \sin((2t + 1)\theta)$$

أقرب ما يمكن إلى $1$ بالقيمة المطلقة، لزيادة احتمالية الحصول على $x\in A_1$ من القياس. لأي زاوية $\theta \in (0,2\pi)$، تتذبذب قيمة $\sin((2t + 1)\theta)$ كلما زاد $t$، وإن لم تكن بالضرورة دورية — ولا ضمان بأن نحصل على القيمة نفسها مرتين.

بطبيعة الحال، إضافة إلى جعل احتمالية الحصول على عنصر $x\in A_1$ من القياس كبيرة، نريد أيضًا اختيار $t$ بأصغر قيمة ممكنة، لأن $t$ تطبيقات للعملية $G$ تتطلب $t$ استعلامًا للدالة $f$. نظرًا لأننا نسعى إلى جعل $\sin( (2t + 1) \theta)$ قريبة من $1$ بالقيمة المطلقة، طريقة طبيعية لذلك هي اختيار $t$ بحيث

$$(2t + 1) \theta \approx \frac{\pi}{2}.$$

حل هذه المعادلة لإيجاد $t$ يُعطي

$$t \approx \frac{\pi}{4\theta} - \frac{1}{2}.$$

بالطبع، $t$ يجب أن يكون عددًا صحيحًا، لذا لن نتمكن بالضرورة من الوصول إلى هذه القيمة تمامًا — لكن ما يمكننا فعله هو أخذ أقرب عدد صحيح لهذه القيمة، وهو

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor.$$

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

(ملاحظة جانبية: إذا كانت القيمة المستهدفة $\pi/(4\theta) - 1/2$ تقع بالضبط في منتصف المسافة بين عددين صحيحين، فإن هذا التعبير لـ$t$ ينتج بالتقريب للأعلى. يمكننا بدلًا من ذلك التقريب للأسفل، وهو أمر منطقي لأنه يعني استعلامًا أقل — لكن هذا ثانوي وغير مهم لأغراض هذا الدرس.)

بالتذكر أن قيمة الزاوية $\theta$ تُعطى بالصيغة

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{\vert A_1\vert}{N}}\biggr),$$

نرى أن عدد التكرارات الموصى به $t$ يعتمد على عدد السلاسل في $A_1$. هذا يطرح تحديًا إذا لم نعرف عدد الحلول كما سنناقش لاحقًا.

البحث الفريد

أولًا، لنركز على الحالة التي توجد فيها سلسلة واحدة فقط $x$ بحيث $f(x)=1$. بصيغة أخرى، نحن نأخذ بعين الاعتبار نسخة من مسألة البحث الفريد. في هذه الحالة لدينا

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr),$$

والذي يمكن تقريبه بشكل مناسب بـ

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{1}{N}} \biggr) \approx \sqrt{\frac{1}{N}}$$

عندما يصبح $N$ كبيرًا. إذا عوَّضنا $\theta = 1/\sqrt{N}$ في التعبير

$$t = \Bigl\lfloor \frac{\pi}{4\theta} \Bigr\rfloor$$

نحصل على

$$t = \Bigl\lfloor \frac{\pi}{4}\sqrt{N} \Bigr\rfloor.$$

بالتذكر أن $t$ ليس فقط عدد مرات تنفيذ العملية $G$، بل هو أيضًا عدد الاستعلامات للدالة $f$ التي تتطلبها الخوارزمية، نرى أننا في طريقنا نحو الحصول على خوارزمية تتطلب $O(\sqrt{N})$ استعلامًا.

الآن سنتحقق من مدى نجاح الاختيار الموصى به لـ$t$. يمكن التعبير بصورة صريحة عن احتمالية أن يكشف القياس النهائي عن الحل الفريد على النحو التالي:

$$p(N,1) = \sin^2 \bigl( (2t + 1) \theta \bigr).$$

الوسيطة الأولى، $N$، تشير إلى عدد العناصر التي نبحث بينها، والوسيطة الثانية، وهي $1$ هنا، تشير إلى عدد الحلول. بعد قليل سنستخدم نفس التدوين بصورة أعم، حيث تتعدد الحلول.

فيما يلي جدول لاحتمالات النجاح مع تزايد القيم $N = 2^n$.

$$\begin{array}{ll} N & p(N,1)\\ \hline 2 & 0.5000000000\\ 4 & 1.0000000000\\ 8 & 0.9453125000\\ 16 & 0.9613189697\\ 32 & 0.9991823155\\ 64 & 0.9965856808\\ 128 & 0.9956198657\\ 256 & 0.9999470421\\ 512 & 0.9994480262\\ 1024 & 0.9994612447\\ 2048 & 0.9999968478\\ 4096 & 0.9999453461\\ 8192 & 0.9999157752\\ 16384 & 0.9999997811\\ 32768 & 0.9999868295\\ 65536 & 0.9999882596 \end{array}$$

لاحظ أن هذه الاحتمالات ليست في تزايد صارم. بالتحديد، نلاحظ ظاهرة مثيرة للاهتمام عند $N=4$، حيث نحصل على الحل بيقين تام. غير أنه يمكن إثبات بصفة عامة أن

$$p(N,1) \geq 1 - \frac{1}{N}$$

لجميع قيم $N$، لذا فإن احتمالية النجاح تتجه نحو $1$ في النهاية مع تكبُّر $N$، كما توحي القيم أعلاه. هذا جيد!

لكن لاحظ أن حتى حدًا ضعيفًا كـ$p(N,1) \geq 1/2$ يُثبت فائدة خوارزمية غروفر. لأيِّ نتيجة قياس $x$ نحصل عليها من تشغيل الإجراء، يمكننا دائمًا التحقق من أن $f(x) = 1$ باستعلام واحد لـ$f$. وإذا فشلنا في الحصول على السلسلة الفريدة $x$ التي يحقق $f(x) = 1$ باحتمالية على الأكثر $1/2$ من تشغيل الإجراء مرة واحدة، فإنه بعد $m$ تشغيل مستقل للإجراء سيكون احتمالية فشلنا في الحصول على هذه السلسلة الفريدة $x$ على الأكثر $2^{-m}$. أي باستخدام $O(m \sqrt{N})$ استعلامًا لـ$f$، سنحصل على الحل الفريد $x$ باحتمالية لا تقل عن $1 - 2^{-m}$. استخدام الحد الأفضل $p(N,1) \geq 1 - 1/N$ يكشف أن احتمالية إيجاد $x\in A_1$ باستخدام هذه الطريقة هي في الواقع لا تقل عن $1 - N^{-m}$.

حلول متعددة

مع تغيُّر عدد العناصر في $A_1$، تتغير الزاوية $\theta$ كذلك، مما قد يؤثر تأثيرًا كبيرًا على احتمالية نجاح الخوارزمية. للإيجاز، لنكتب $s = \vert A_1 \vert$ لتدل على عدد الحلول، وكما في السابق سنفترض أن $s\geq 1$.

كمثال تحفيزي، لنفترض أن لدينا $s = 4$ حلول بدلًا من حل واحد كما تناولنا أعلاه. هذا يعني أن

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{4}{N}} \biggr),$$

وهو تقريبًا ضعف الزاوية في حالة $\vert A_1 \vert = 1$ عندما يكون $N$ كبيرًا. لنفترض أننا لم ننتبه لذلك، واخترنا نفس قيمة $t$ كما في حالة الحل الفريد:

$$t = \Biggl\lfloor \frac{\pi}{4\sin^{-1}\bigl(1/\sqrt{N}\bigr)}\Biggr\rfloor.$$

ستكون النتيجة كارثية كما يكشف الجدول التالي للاحتمالات.

$$\begin{array}{ll} N & \text{احتمالية النجاح}\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 0.2500000000\\ 32 & 0.0122070313\\ 64 & 0.0203807689\\ 128 & 0.0144530758\\ 256 & 0.0000705058\\ 512 & 0.0019310741\\ 1024 & 0.0023009083\\ 2048 & 0.0000077506\\ 4096 & 0.0002301502\\ 8192 & 0.0003439882\\ 16384 & 0.0000007053\\ 32768 & 0.0000533810\\ 65536 & 0.0000472907 \end{array}$$

هذه المرة تتجه احتمالية النجاح نحو $0$ كلما اتجه $N$ نحو اللانهاية. يحدث هذا لأننا في الواقع ندور بسرعة ضعف ما كنا ندور في حالة الحل الفريد، فنتخطى الهدف $\vert A_1\rangle$ وننتهي قرب $-\vert A_0\rangle$.

لكن إذا استخدمنا بدلًا من ذلك الاختيار الموصى به لـ$t$، وهو

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor$$

من أجل

$$\theta = \sin^{-1}\biggl( \sqrt{\frac{s}{N}} \biggr),$$

فإن الأداء سيكون أفضل. بدقة أكبر، هذا الاختيار لـ$t$ يؤدي إلى النجاح باحتمالية مرتفعة.

$$\begin{array}{ll} N & p(N,4)\\ \hline 4 & 1.0000000000\\ 8 & 0.5000000000\\ 16 & 1.0000000000\\ 32 & 0.9453125000\\ 64 & 0.9613189697\\ 128 & 0.9991823155\\ 256 & 0.9965856808\\ 512 & 0.9956198657\\ 1024 & 0.9999470421\\ 2048 & 0.9994480262\\ 4096 & 0.9994612447\\ 8192 & 0.9999968478\\ 16384 & 0.9999453461\\ 32768 & 0.9999157752\\ 65536 & 0.9999997811 \end{array}$$

تعميمًا لما ادُّعي سابقًا، يمكن إثبات أن

$$p(N,s) \geq 1 - \frac{s}{N},$$

حيث نستخدم التدوين المقترح سابقًا: $p(N,s)$ تدل على احتمالية أن تكشف خوارزمية غروفر المُشغَّلة لـ$t$ تكرارًا عن حل عندما يوجد $s$ حلًا من بين $N$ احتمالًا.

هذا الحد الأدنى $1 - s/N$ لاحتمالية النجاح غريب قليلًا من حيث إن كثرة الحلول تعني حدًا أدنى أضعف — لكن بافتراض أن $s$ أصغر بكثير من $N$، نستنتج مع ذلك أن احتمالية النجاح مرتفعة بشكل معقول. وكما من قبل، مجرد كون $p(N,s)$ كبيرًا بشكل معقول يُثبت فائدة الخوارزمية.

يصادف أيضًا أن

$$p(N,s) \geq \frac{s}{N}.$$

هذا الحد الأدنى يصف احتمالية أن تكون سلسلة $x\in\Sigma^n$ مختارة عشوائيًا بتوزيع منتظم حلًا — لذا فإن خوارزمية غروفر دائمًا تؤدي أداءً أفضل على الأقل من التخمين العشوائي. (في الواقع، عندما $t=0$، خوارزمية غروفر هي تخمين عشوائي.)

الآن لنلقِ نظرة على عدد التكرارات (ومن ثمَّ عدد الاستعلامات)

$$t = \Bigl\lfloor \frac{\pi}{4\theta}\Bigr\rfloor,$$

من أجل

$$\theta = \sin^{-1}\biggl(\sqrt{\frac{s}{N}}\biggr).$$

لكل $\alpha \in [0,1]$، يصح أن $\sin^{-1}(\alpha)\geq \alpha$، وبالتالي

$$\theta = \sin^{-1}\left(\sqrt{\frac{s}{N}}\right) \geq \sqrt{\frac{s}{N}}.$$

هذا يستلزم أن

$$t \leq \frac{\pi}{4\theta} \leq \frac{\pi}{4}\sqrt{\frac{N}{s}}.$$

وهذا يُترجَم إلى توفير في عدد الاستعلامات كلما زاد $s$. بالتحديد، عدد الاستعلامات المطلوبة هو

$$O\biggl(\sqrt{\frac{N}{s}}\biggr).$$

عدد الحلول غير المعروف

إذا كان عدد الحلول $s = \vert A_1 \vert$ غير معروف، فمطلوب نهج مختلف، إذ ليس لدينا في هذه الحالة معرفة بـ$s$ تُرشدنا في اختيار $t$. في الواقع، توجد عدة نهج.

نهج بسيط هو اختيار

$$t \in \Bigl\{ 1,\ldots,\bigl\lfloor\pi\sqrt{N}/4\bigr\rfloor \Bigr\}$$

بشكل عشوائي منتظم. اختيار $t$ بهذه الطريقة يجد دائمًا حلًا (إذا وُجد) باحتمالية تزيد على 40%، وإن كان هذا غير واضح ويستلزم تحليلًا لن نُدرجه هنا. لكنه منطقي بالنظر إلى الصورة الهندسية: تدوير حالة $\mathsf{Q}$ عددًا عشوائيًا من المرات يشبه اختيار متجه وحدة عشوائي في الفضاء الممتد بـ$\vert A_0\rangle$ و$\vert A_1\rangle$، حيث من المرجح أن يكون معامل $\vert A_1\rangle$ كبيرًا بشكل معقول. بتكرار هذا الإجراء والتحقق من النتيجة بنفس الطريقة المذكورة سابقًا، يمكن جعل احتمالية إيجاد الحل قريبة جدًا من $1$.

يوجد طريقة مُحسَّنة تجد حلًا حين يوجد باستخدام $O(\sqrt{N/s})$ استعلامًا، حتى حين يكون عدد الحلول $s$ غير معروف، وتتطلب $O(\sqrt{N})$ استعلامًا لتحديد أنه لا توجد حلول حين $s=0$.

الفكرة الأساسية هي اختيار $t$ بشكل منتظم عشوائي من المجموعة $\{1,\ldots,T\}$ بصورة تكرارية مع زيادة قيم $T$. بالتحديد، يمكننا البدء بـ$T = 1$ وزيادتها أسيًا، مع إنهاء العملية فور العثور على حل وتقييد $T$ لتجنب إضاعة الاستعلامات حين لا يوجد حل. تستفيد هذه العملية من حقيقة أنه كلما زادت الحلول، قلَّت الاستعلامات اللازمة. غير أن الأمر يستلزم بعض الدقة في الموازنة بين معدل زيادة $T$ واحتمالية النجاح في كل تكرار. (أخذ $T \leftarrow \lceil \frac{5}{4}T\rceil$ يجدي مثلًا، كما يُبيِّن التحليل. أما مضاعفة $T$ فلا يجدي — وهذا يبيَّن أنها زيادة سريعة جدًا.)

الحالات البديهية

طوال التحليل الذي مررنا به، افترضنا أن عدد الحلول غير صفري. في الواقع، بالإشارة إلى المتجهات

$$\begin{aligned} \vert A_0\rangle &= \frac{1}{\sqrt{\vert A_0\vert}} \sum_{x\in A_0} \vert x\rangle \\ \vert A_1\rangle &= \frac{1}{\sqrt{\vert A_1\vert}} \sum_{x\in A_1} \vert x\rangle \end{aligned}$$

افترضنا ضمنيًا أن $A_0$ و$A_1$ كلتيهما غير فارغتين. هنا سنتناول باختصار ما يحدث حين تكون إحدى هاتين المجموعتين فارغة.

قبل الخوض في التحليل، دعنا نلاحظ الأمر الجلي: إذا كانت كل سلسلة $x\in\Sigma^n$ حلًا، فسنرى حلًا عند القياس؛ وحين لا توجد أي حلول، لن نرى أيًا منها. لا حاجة في بعض الأحيان للذهاب أبعد من هذا.

يمكننا مع ذلك التحقق سريعًا من الرياضيات لهذه الحالات البديهية. الحالة التي تكون فيها إحدى $A_0$ و$A_1$ فارغة تحدث حين تكون $f$ ثابتة؛ $A_1$ فارغة حين $f(x) = 0$ لكل $x\in\Sigma^n$، و$A_0$ فارغة حين $f(x) = 1$ لكل $x\in\Sigma^n$. هذا يعني أن

$$Z_f \vert u\rangle = \pm \vert u\rangle,$$

وبالتالي

$$\begin{aligned} G \vert u \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f\vert u\rangle \\ & = \pm \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert u\rangle \\ & = \pm \vert u\rangle. \end{aligned}$$

إذن، بصرف النظر عن عدد التكرارات $t$ التي نُجريها في هذه الحالات، ستكشف القياسات دائمًا عن سلسلة عشوائية منتظمة $x\in\Sigma^n$.