בחירת מספר האיטרציות

קבענו שוקטור המצב של הרגיסטר $\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$ איטרציות בשלב 2 הוא

$$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{Success probability}\\ \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.$