ניתוח

עכשיו נבצע ניתוח של אלגוריתם גרובר כדי להבין כיצד הוא עובד. נתחיל ממה שאפשר לתאר כניתוח סמלי, שבו נחשב כיצד פעולת גרובר $G$ פועלת על מצבים מסוימים, ואז נקשור ניתוח סמלי זה לתמונה גאומטרית שעוזרת להמחיש כיצד האלגוריתם עובד.

פתרונות ולא-פתרונות

נתחיל בהגדרת שתי קבוצות של מחרוזות.

$$\begin{aligned} A_0 &= \bigl\{ x\in\Sigma^n : f(x) = 0\bigr\} \\ A_1 &= \bigl\{ x\in\Sigma^n : f(x) = 1\bigr\} \end{aligned}$$

הקבוצה $A_1$ מכילה את כל הפתרונות לבעיית החיפוש שלנו, ואילו $A_0$ מכילה את המחרוזות שאינן פתרונות (שנוכל לכנות לא-פתרונות כשנוח לנו). שתי הקבוצות הללו מקיימות $A_0 \cap A_1 = \varnothing$ ו-$A_0 \cup A_1 = \Sigma^n,$ כלומר זוהי חלוקה לשניים של $\Sigma^n.$

לאחר מכן נגדיר שני וקטורי יחידה המייצגים סופרפוזיציות אחידות על קבוצות הפתרונות והלא-פתרונות.

$$\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$ אינן ריקות. המקרים שבהם $A_0 = \varnothing$ או $A_1 = \varnothing$ קלים לטיפול בנפרד, ונעשה זאת בהמשך.

כהערת אגב, הסימון בשימוש כאן הוא מקובל: בכל פעם שיש לנו קבוצה סופית ולא ריקה $S,$ אפשר לכתוב $\vert S\rangle$ כדי לסמן את וקטור המצב הקוונטי האחיד על איברי $S.$

נגדיר גם את $\vert u \rangle$ כמצב קוונטי אחיד על כל המחרוזות בנות $n$ הסיביות:

$$\vert u\rangle = \frac{1}{\sqrt{N}} \sum_{x\in\Sigma^n} \vert x\rangle.$$

שימו לב ש-

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle.$$

כמו כן $\vert u\rangle = H^{\otimes n} \vert 0^n \rangle,$ ולכן $\vert u\rangle$ מייצג את המצב של הרגיסטר $\mathsf{Q}$ לאחר האתחול בשלב 1 של אלגוריתם גרובר.

מכך נובע שממש לפני האיטרציות של $G$ בשלב 2, המצב של $\mathsf{Q}$ נמצא במרחב הוקטורי הדו-ממדי הנפרש על ידי $\vert A_0\rangle$ ו-$\vert A_1\rangle,$ ויתר על כן מקדמי הוקטורים הללו הם מספרים ממשיים. כפי שנראה, למצב של $\mathsf{Q}$ תמיד יהיו תכונות אלו — כלומר המצב הוא צירוף לינארי ממשי של $\vert A_0\rangle$ ו-$\vert A_1\rangle$ — לאחר כל מספר של איטרציות של הפעולה $G$ בשלב 2.

תצפית על פעולת גרובר

עכשיו נפנה את תשומת לבנו לפעולת גרובר

$$G = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f,$$

ונתחיל עם תצפית מעניינת לגביה.

נדמיין לרגע שהחלפנו את הפונקציה $f$ בהרכבה של $f$ עם פונקציית ה-NOT — כלומר, הפונקציה שמתקבלת על ידי היפוך סיבית הפלט של $f.$ נקרא לפונקציה החדשה הזאת $g,$ ואפשר לבטא אותה בסמלים בכמה דרכים חלופיות.

$$g(x) = \neg f(x) = 1 \oplus f(x) = 1 - f(x) = \begin{cases} 1 & f(x) = 0\\[1mm] 0 & f(x) = 1 \end{cases}$$

שימו לב ש-

$$(-1)^{g(x)} = (-1)^{1 \oplus f(x)} = - (-1)^{f(x)}$$

לכל מחרוזת $x\in\Sigma^n,$ ולכן

$$Z_g = - Z_f.$$

משמעות הדבר היא שאם היינו מחליפים את הפונקציה $f$ בפונקציה $g,$ אלגוריתם גרובר לא היה פועל באופן שונה — כי המצבים שמתקבלים מהאלגוריתם בשני המקרים שקולים בהכרח עד לשלב גלובלי.

זה לא בעיה! באופן אינטואיטיבי, האלגוריתם לא מתחשב באילו מחרוזות הן פתרונות ואילו הן לא-פתרונות — הוא רק צריך להיות מסוגל להבחין בין פתרונות ולא-פתרונות כדי לפעול נכון.

פעולת פעולת גרובר

עכשיו נבחן את פעולת $G$ על וקטורי המצב הקוונטי $\vert A_0\rangle$ ו-$\vert A_1\rangle.$

ראשית, נשים לב שלפעולה $Z_f$ יש פעולה פשוטה מאוד על $\vert A_0\rangle$ ו-$\vert A_1\rangle.$

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle \end{aligned}$$

שנית, יש לנו את הפעולה $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ הפעולה $Z_{\mathrm{OR}}$ מוגדרת כ-

$$Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[2mm] -\vert x\rangle & x \neq 0^n, \end{cases}$$

שוב לכל מחרוזת $x\in\Sigma^n,$ ודרך נוחה חלופית לבטא פעולה זו היא כך:

$$Z_{\mathrm{OR}} = 2 \vert 0^n \rangle \langle 0^n \vert - \mathbb{I}.$$

דרך פשוטה לאמת שביטוי זה מסכים עם ההגדרה של $Z_{\mathrm{OR}}$ היא להעריך את פעולתו על מצבי הבסיס הסטנדרטיים.

את הפעולה $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}$ אפשר לכתוב כך:

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 H^{\otimes n} \vert 0^n \rangle \langle 0^n \vert H^{\otimes n} - \mathbb{I} = 2 \vert u \rangle \langle u \vert - \mathbb{I},$$

תוך שימוש באותו הסימון, $\vert u \rangle,$ שהשתמשנו בו לעיל לסופרפוזיציה האחידה על כל המחרוזות בנות $n$ הסיביות.

ועכשיו יש בידינו את מה שדרוש לחישוב פעולת $G$ על $\vert A_0\rangle$ ו-$\vert A_1\rangle.$ ראשית נחשב את פעולת $G$ על $\vert A_0\rangle.$

$$\begin{aligned} G \vert A_0 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) Z_f \vert A_0\rangle \\ & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I}\bigr) \vert A_0\rangle \\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \vert u\rangle -\vert A_0 \rangle\\ & = 2 \sqrt{\frac{\vert A_0\vert}{N}} \biggl( \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) -\vert A_0 \rangle \\ & = \biggl( \frac{2\vert A_0\vert}{N} - 1\biggr) \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \\ & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle \end{aligned}$$

ושנית, נחשב את פעולת $G$ על $\vert A_1\rangle.$

$$\begin{aligned} G \vert A_1 \rangle & = \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) Z_f \vert A_1\rangle \\ & = - \bigl( 2 \vert u\rangle \langle u \vert - \mathbb{I} \bigr) \vert A_1\rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \vert u\rangle + \vert A_1 \rangle \\ & = - 2 \sqrt{\frac{\vert A_1\vert}{N}} \biggl(\sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle\biggr) + \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \biggl( 1 - \frac{2\vert A_1\vert}{N} \biggr) \vert A_1 \rangle \\ & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle \end{aligned}$$

בשני המקרים אנחנו משתמשים במשוואה

$$\vert u\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1 \vert}{N}} \vert A_1\rangle$$

יחד עם הביטויים

$$\langle u \vert A_0\rangle = \sqrt{\frac{\vert A_0 \vert}{N}} \qquad\text{and}\qquad \langle u \vert A_1\rangle = \sqrt{\frac{\vert A_1 \vert}{N}}$$

הנובעים ממנה.

לסיכום, יש לנו

$$\begin{aligned} G \vert A_0 \rangle & = \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_0 \rangle + \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} \vert A_1 \rangle\\[2mm] G \vert A_1 \rangle & = - \frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \vert A_0 \rangle + \frac{\vert A_0\vert - \vert A_1\vert}{N} \vert A_1 \rangle. \end{aligned}$$

כפי שכבר ציינו, המצב של $\mathsf{Q}$ ממש לפני שלב 2 נמצא במרחב הדו-ממדי הנפרש על ידי $\vert A_0\rangle$ ו-$\vert A_1\rangle,$ וכרגע הוכחנו ש-$G$ ממפה כל וקטור במרחב זה לוקטור אחר באותו המרחב. משמעות הדבר היא שלצורך הניתוח, נוכל להתמקד בנתח המשנה הזה בלבד.

כדי להבין טוב יותר מה קורה בתוך המרחב הדו-ממדי הזה, נבטא את פעולת $G$ על מרחב זה כמטריצה,

$$M = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix},$$

שהשורות/עמודות הראשונות והשניות שלה מתאימות ל-$\vert A_0\rangle$ ו-$\vert A_1\rangle,$ בהתאמה. עד כה בסדרה זו, תמיד קישרנו את השורות והעמודות של מטריצות למצבים הקלאסיים של מערכת, אך מטריצות יכולות לשמש גם לתיאור פעולות של העתקות לינאריות על בסיסים שונים כפי שיש לנו כאן.

אמנם זה כלל לא מובן ממבט ראשון, אך המטריצה $M$ היא מה שמתקבל כשמרבעים מטריצה פשוטה יותר.

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}^2 = \begin{pmatrix} \frac{\vert A_0\vert - \vert A_1\vert}{N} & -\frac{2 \sqrt{\vert A_1\vert \cdot \vert A_0\vert}}{N} \\[2mm] \frac{2 \sqrt{\vert A_0\vert \cdot \vert A_1\vert}}{N} & \frac{\vert A_0\vert - \vert A_1\vert}{N} \end{pmatrix} = M$$

המטריצה

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix}$$

היא מטריצת סיבוב, שאפשר לבטאה גם כ-

$$\begin{pmatrix} \sqrt{\frac{\vert A_0\vert}{N}} & - \sqrt{\frac{\vert A_1\vert}{N}} \\[2mm] \sqrt{\frac{\vert A_1\vert}{N}} & \sqrt{\frac{\vert A_0\vert}{N}} \end{pmatrix} = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}$$

עבור

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

הזווית $\theta$ הזו הולכת למלא תפקיד חשוב מאוד בניתוח שיבוא, ולכן כדאי להדגיש את חשיבותה כאן, כשאנו פוגשים אותה לראשונה.

לאור ביטוי זה של המטריצה, אנו מבחינים ש-

$$M = \begin{pmatrix} \cos(\theta) & -\sin(\theta) \\[2mm] \sin(\theta) & \cos(\theta) \end{pmatrix}^2 = \begin{pmatrix} \cos(2\theta) & -\sin(2\theta) \\[2mm] \sin(2\theta) & \cos(2\theta) \end{pmatrix}.$$

זאת מפני שסיבוב בזווית $\theta$ פעמיים שקול לסיבוב בזווית $2\theta.$ דרך נוספת לראות זאת היא להשתמש בביטוי החלופי

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

יחד עם נוסחאות הזווית הכפולה מהטריגונומטריה:

$$\begin{aligned} \cos(2\theta) & = \cos^2(\theta) - \sin^2(\theta)\\[1mm] \sin(2\theta) & = 2 \sin(\theta)\cos(\theta). \end{aligned}$$

לסיכום, המצב של הרגיסטר $\mathsf{Q}$ בתחילת שלב 2 הוא

$$\vert u\rangle = \sqrt{\frac{\vert A_0\vert}{N}} \vert A_0\rangle + \sqrt{\frac{\vert A_1\vert}{N}} \vert A_1\rangle = \cos(\theta) \vert A_0\rangle + \sin(\theta) \vert A_1\rangle,$$

ואפקט הפעלת $G$ על מצב זה הוא לסובב אותו בזווית $2\theta$ בתוך המרחב הנפרש על ידי $\vert A_0\rangle$ ו-$\vert A_1\rangle.$ כך למשל, יש לנו

$$\begin{aligned} G \vert u \rangle &= \cos(3\theta) \vert A_0\rangle + \sin(3\theta) \vert A_1\rangle\\[1mm] G^2 \vert u \rangle &= \cos(5\theta) \vert A_0\rangle + \sin(5\theta) \vert A_1\rangle\\[1mm] G^3 \vert u \rangle &= \cos(7\theta) \vert A_0\rangle + \sin(7\theta) \vert A_1\rangle \end{aligned}$$

ובאופן כללי

$$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.$$

תמונה גאומטרית

עכשיו נקשור את הניתוח שעברנו לתמונה גאומטרית. הרעיון הוא שהפעולה $G$ היא מכפלה של שתי השתקפויות, $Z_f$ ו-$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n}.$ והאפקט נטו של ביצוע שתי השתקפויות הוא ביצוע סיבוב.

נתחיל עם $Z_f.$ כפי שכבר הבחנו קודם לכן, יש לנו

$$\begin{aligned} Z_f \vert A_0\rangle & = \vert A_0\rangle \\[1mm] Z_f \vert A_1\rangle & = -\vert A_1\rangle. \end{aligned}$$

בתוך המרחב הוקטורי הדו-ממדי הנפרש על ידי $\vert A_0\rangle$ ו-$\vert A_1\rangle,$ זוהי השתקפות סביב הישר המקביל ל-$\vert A_0\rangle,$ שנקרא לו $L_1.$ הנה תרשים המדגים את פעולת ההשתקפות הזאת על וקטור יחידה היפותטי $\vert\psi\rangle,$ שאנחנו מניחים שהוא צירוף לינארי ממשי של $\vert A_0\rangle$ ו-$\vert A_1\rangle.$

שנית, יש לנו את הפעולה $H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n},$ שכבר ראינו שניתן לכתוב אותה כ-

$$H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} = 2 \vert u \rangle \langle u \vert - \mathbb{I}.$$

גם זוהי השתקפות, הפעם סביב הישר $L_2$ המקביל לוקטור $\vert u\rangle.$ הנה תרשים המדגים את פעולת ההשתקפות הזאת על וקטור יחידה $\vert\psi\rangle.$

כשמרכיבים את שתי ההשתקפויות הללו, מקבלים סיבוב — בפי שתיים מהזווית בין ישרי ההשתקפות — כפי שמדגים התרשים הבא.

זה מסביר, במונחים גאומטריים, מדוע האפקט של פעולת גרובר הוא לסובב צירופים לינאריים של $\vert A_0\rangle$ ו-$\vert A_1\rangle$ בזווית $2\theta.$