אלגוריתם שור

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

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

בעיית מציאת הסדר

קצת תורת מספרים בסיסית

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

להתחלה, לכל מספר שלם חיובי נתון $N,$ נגדיר את הקבוצה $\mathbb{Z}_N$ כך:

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

לדוגמה, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ וכן הלאה.

אלו הן קבוצות של מספרים, אך אפשר לחשוב עליהן כיותר מסתם קבוצות. בפרט, אפשר לחשוב על פעולות חשבוניות על $\mathbb{Z}_N$ כגון חיבור וכפל — ואם נסכים תמיד לקחת את התוצאות מודולו $N$ (כלומר, לחלק ב-$N$ ולקחת את השארית כתוצאה), תמיד נישאר בתוך הקבוצה הזו כשנבצע פעולות אלו. שתי הפעולות הספציפיות של חיבור וכפל, שתיהן מודולו $N,$ הופכות את $\mathbb{Z}_N$ לחוג, שהוא סוג אובייקט חשוב ביסודו באלגברה.

לדוגמה, $3$ ו-$5$ הם איברים של $\mathbb{Z}_7,$ ואם נכפיל אותם יחד נקבל $3\cdot 5 = 15,$ שמשאיר שארית $1$ בחלוקה ב-$7.$ לפעמים אנו מביעים זאת כך:

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

אבל אפשר גם פשוט לכתוב $3 \cdot 5 = 1,$ בתנאי שהובהר שאנחנו עובדים ב-$\mathbb{Z}_7,$ כדי לשמור על הסימונים פשוטים ככל האפשר.

לדוגמה, הנה לוחות החיבור והכפל עבור $\mathbb{Z}_6.$

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

מבין $N$ האיברים של $\mathbb{Z}_N,$ האיברים $a\in\mathbb{Z}_N$ המקיימים $\gcd(a,N) = 1$ הם מיוחדים. לעתים קרובות הקבוצה המכילה איברים אלו מסומנת בכוכבית כך:

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

אם נתמקד בפעולת הכפל, הקבוצה $\mathbb{Z}_N^{\ast}$ יוצרת חבורה — ספציפית חבורה אבלית — שהיא גם כן סוג אובייקט חשוב באלגברה. עובדה בסיסית על קבוצות אלו (ועל חבורות סופיות בכלל) היא שאם נבחר איבר כלשהו $a\in\mathbb{Z}_N^{\ast}$ ונכפיל את $a$ בעצמו שוב ושוב, תמיד נגיע בסוף למספר $1.$

כדוגמה ראשונה, ניקח $N=6.$ $5\in\mathbb{Z}_6^{\ast}$ מכיוון ש-$\gcd(5,6) = 1,$ ואם נכפיל $5$ בעצמו נקבל $1,$ כפי שהלוח שלמעלה מאשר.

$$5^2 = 1 \quad \text{(working within $\mathbb{Z}_6$)}$$

כדוגמה שנייה, ניקח $N = 21.$ אם נעבור על המספרים מ-$0$ עד $20,$ אלו שיש להם מחלק משותף גדול ביותר שווה ל-$1$ עם $21$ הם:

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

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

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

כמובן שאנחנו עובדים בתוך $\mathbb{Z}_{21}$ בכל המשוואות האלה, דבר שלא טרחנו לכתוב — אנחנו רואים זאת כמשתמע כדי לא להעמיס. נמשיך לעשות כך לאורך שאר השיעור.

הצהרת הבעיה וקשר לאומדן פאזה

עכשיו נוכל להציג את בעיית מציאת הסדר.

מציאת סדר

קלט: מספרים שלמים חיוביים $N$ ו-$a$ המקיימים $\gcd(N,a) = 1$
פלט: המספר השלם החיובי הקטן ביותר $r$ כך ש-$a^r \equiv 1$ $(\textrm{mod } N)$

לחלופין, במונחי הסימון שהצגנו לעיל, ניתן לנו $a \in \mathbb{Z}_N^{\ast},$ ואנחנו מחפשים את המספר השלם החיובי הקטן ביותר $r$ כך ש-$a^r = 1.$ מספר זה $r$ נקרא הסדר של $a$ מודולו $N.$

כדי לקשור את בעיית מציאת הסדר לאומדן פאזה, בואו נחשוב על הפעולה המוגדרת על מערכת שהמצבים הקלאסיים שלה מתאימים ל-$\mathbb{Z}_N,$ שבה אנחנו כופלים באיבר קבוע $a\in\mathbb{Z}_N^{\ast}.$

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(for each $x\in\mathbb{Z}_N$)}$$

להיות מדויק, אנחנו מבצעים את הכפל ב-$\mathbb{Z}_N,$ כך שמשתמע שאנחנו לוקחים את המכפלה מודולו $N$ בתוך ה-ket בצד ימין של המשוואה.

לדוגמה, אם ניקח $N = 15$ ו-$a=2,$ אז הפעולה של $M_2$ על הבסיס הסטנדרטי $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ היא כדלקמן:

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

זוהי פעולה אוניטרית בתנאי ש-$\gcd(a,N)=1;$ היא מערבבת את איברי הבסיס הסטנדרטי $\{\vert 0\rangle,\ldots,\vert N-1\rangle\},$ ולכן כמטריצה היא מטריצת תמורה. ברור מהגדרתה שפעולה זו היא דטרמיניסטית, ודרך פשוטה לראות שהיא הפיכה היא לחשוב על הסדר $r$ של $a$ מודולו $N,$ ולהכיר שההופכי של $M_a$ הוא $M_a^{r-1}.$

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

יש דרך נוספת לחשוב על ההופכי שאינה דורשת ידיעה של $r$ (שהרי זה מה שאנחנו מנסים לחשב). לכל איבר $a\in\mathbb{Z}_N^{\ast}$ יש תמיד איבר יחיד $b\in\mathbb{Z}_N^{\ast}$ המקיים $ab=1.$ אנחנו מסמנים איבר זה $b$ ב-$a^{-1},$ וניתן לחשב אותו ביעילות; הרחבה של אלגוריתם המחלק המשותף הגדול של אוקלידס עושה זאת בעלות ריבועית ב-$\operatorname{lg}(N).$ ולכן

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

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

עכשיו בואו נחשוב על הווקטורים העצמיים והערכים העצמיים של הפעולה $M_a,$ בהנחה ש-$a\in\mathbb{Z}_N^{\ast}.$ כפי שנטען זה עתה, הנחה זו אומרת לנו ש-$M_a$ היא אוניטרית.

יש $N$ ערכים עצמיים של $M_a,$ אפשרי שאותו ערך עצמי חוזר מספר פעמים, ובכלל יש חופש מסוים בבחירת הווקטורים העצמיים המתאימים — אבל לא נצטרך להתעסק עם כל האפשרויות. נתחיל בפשטות ונזהה ווקטור עצמי אחד של $M_a.$

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

המספר $r$ הוא הסדר של $a$ מודולו $N,$ כאן ולאורך שאר השיעור. הערך העצמי המשויך לווקטור עצמי זה הוא $1$ מכיוון שאינו משתנה כשכופלים ב-$a.$

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

זה קורה מכיוון ש-$a^r = 1,$ כך שכל מצב בסיס סטנדרטי $\vert a^k \rangle$ עובר ל-$\vert a^{k+1} \rangle$ עבור $k\leq r-1,$ ו-$\vert a^{r-1} \rangle$ עובר חזרה ל-$\vert 1\rangle.$ בצורה לא פורמלית, זה כאילו אנחנו מערבבים לאט את $\vert \psi_0 \rangle,$ אבל הוא כבר מעורבב לגמרי ולכן כלום לא משתנה.

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

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

לחלופין, אפשר לכתוב ווקטור זה באמצעות סכימה כך:

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

כאן אנחנו רואים את המספר המרוכב $\omega_r = e^{2\pi i/r}$ מופיע באופן טבעי, בשל האופן שבו כפל ב-$a$ עובד מודולו $N.$ הפעם הערך העצמי המתאים הוא $\omega_r.$ כדי לראות זאת, נוכל לחשב תחילה כך:

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

לאחר מכן, מכיוון ש-$\omega_r^{-r} = 1 = \omega_r^0$ ו-$\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle,$ אנחנו רואים ש-

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

ולכן $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle.$

באותו היגיון, אפשר לזהות זוגות ווקטור עצמי/ערך עצמי נוספים עבור $M_a.$ לכל בחירה של $j\in\{0,\ldots,r-1\}$ מתקיים ש-

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

הוא ווקטור עצמי של $M_a$ שהערך העצמי המשויך לו הוא $\omega_r^j.$

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

יש ווקטורים עצמיים נוספים של $M_a,$ אבל לא נצטרך להתעסק בהם — נתמקד אך ורק בווקטורים העצמיים $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ שזיהינו כרגע.

מציאת סדר באמצעות אומדן פאזה

כדי לפתור את בעיית מציאת הסדר עבור בחירה נתונה של $a\in\mathbb{Z}_N^{\ast},$ אפשר להפעיל את הליך אומדן הפאזה על הפעולה $M_a.$

לשם כך, עלינו לממש ביעילות לא רק את $M_a$ בעזרת Circuit קוונטי, אלא גם את $M_a^2,$ $M_a^4,$ $M_a^8,$ וכן הלאה, כמה שנצטרך כדי לקבל אומדן מדויק מספיק מהליך אומדן הפאזה. כאן נסביר כיצד ניתן לעשות זאת, ונגלה בדיוק כמה דיוק נחוץ בהמשך.

נתחיל עם הפעולה $M_a$ כשלעצמה. מטבע הדברים, מכיוון שאנחנו עובדים עם מודל ה-Circuit הקוונטי, נשתמש בייצוג בינארי לקידוד המספרים בין $0$ ל-$N-1.$ המספר הגדול ביותר שנצטרך לקודד הוא $N-1,$ כך שמספר הביטים שנצטרך הוא

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

לדוגמה, אם $N = 21$ יש לנו $n = \operatorname{lg}(N-1) = 5.$ הנה איך נראה הקידוד של איברי $\mathbb{Z}_{21}$ כמחרוזות בינאריות באורך $5$:

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

ועכשיו, הנה הגדרה מדויקת של כיצד $M_a$ מוגדרת כפעולה של $n$-Qubit.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

הנקודה היא שאמנם אכפת לנו רק מהאופן שבו $M_a$ פועלת על $\vert 0\rangle,\ldots,\vert N-1\rangle,$ אך עלינו לציין כיצד היא פועלת על $2^n - N$ מצבי הבסיס הסטנדרטי הנותרים — ועלינו לעשות זאת באופן שעדיין נותן לנו פעולה אוניטרית. הגדרת $M_a$ כך שלא תעשה כלום למצבי הבסיס הסטנדרטי הנותרים משיגה זאת.

באמצעות האלגוריתמים לכפל שלמים ולחלוקה שנדונו בשיעור הקודם, יחד עם המתודולוגיה למימושים הפיכים ונטולי-זבל שלהם, אפשר לבנות Circuit קוונטי המבצע את $M_a,$ לכל בחירה של $a\in\mathbb{Z}_N^{\ast},$ בעלות $O(n^2).$ הנה אחת הדרכים שניתן לעשות זאת:

1. בנה Circuit לביצוע הפעולה

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   כאשר

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   באמצעות השיטה שתוארה בשיעור הקודם. זה נותן לנו Circuit בגודל $O(n^2).$

2. החלף את שני המערכות של $n$-Qubit באמצעות $n$ שערי SWAP כדי להחליף את ה-Qubit-ים בנפרד.

3. בדומה לשלב הראשון, בנה Circuit לפעולה

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   כאשר $a^{-1}$ הוא ההופכי של $a$ ב-$\mathbb{Z}_N^{\ast}.$

על ידי אתחול ה-Qubit-ים התחתונים של $n$ וחיבור שלושת השלבים, מקבלים את הטרנספורמציה הבאה:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

השיטה דורשת Qubit-ים לסביבת עבודה, אך הם מוחזרים למצב האתחולי שלהם בסוף, מה שמאפשר לנו להשתמש ב-Circuit-ים אלו לאומדן פאזה. העלות הכוללת של ה-Circuit שאנחנו מקבלים היא $O(n^2).$

כדי לבצע את $M_a^2,$ $M_a^4,$ $M_a^8,$ וכן הלאה, אפשר להשתמש בדיוק באותה שיטה, אלא שנחליף את $a$ ב-$a^2,$ $a^4,$ $a^8,$ וכן הלאה, כאיברים של $\mathbb{Z}_N^{\ast}.$ כלומר, לכל חזקה $k$ שנבחר, נוכל ליצור Circuit עבור $M_a^k$ לא על ידי איטרציה $k$ פעמים של ה-Circuit עבור $M_a,$ אלא במקום זאת על ידי חישוב $b = a^k \in \mathbb{Z}_N^{\ast}$ ואז שימוש ב-Circuit עבור $M_b.$

חישוב חזקות $a^k \in \mathbb{Z}_N$ הוא בעיית האקספוננציאציה המודולרית שהוזכרה בשיעור הקודם. חישוב זה ניתן לעשות קלאסית, באמצעות האלגוריתם לאקספוננציאציה מודולרית שהוזכר בשיעור הקודם (לעתים קרובות מכונה אלגוריתם החזקה בתורת המספרים החישובית). למעשה, אנחנו דורשים רק חזקות-של-$2$ של $a,$ ספציפית $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast},$ ואנחנו יכולים לקבל את החזקות האלה על ידי ריבוע איטרטיבי $m-1$ פעמים. כל ריבוע ניתן לביצוע על ידי Circuit בוליאני בגודל $O(n^2).$

בעיקרון, מה שאנחנו עושים כאן בפועל הוא להעביר את בעיית איטרציית $M_a$ עד $2^{m-1}$ פעמים לחישוב קלאסי יעיל. ומזל גדול שזה אפשרי! לבחירה שרירותית של Circuit קוונטי בבעיית אומדן הפאזה, זה כנראה לא יהיה אפשרי — ובמקרה כזה העלות המתקבלת לאומדן הפאזה גדלה אקספוננציאלית במספר Qubit-י הבקרה $m.$

פתרון בהינתן וקטור עצמי נוח

כדי להבין כיצד ניתן לפתור את בעיית מציאת הסדר בעזרת אמידת פאזה, נתחיל בהנחה שאנחנו מריצים את הליך אמידת הפאזה על הפעולה $M_a$ תוך שימוש בוקטור העצמי $\vert\psi_1\rangle.$ להשיג את הוקטור העצמי הזה זה לא דבר פשוט, כפי שנראה — אז זו לא תהיה סוף הסיפור — אבל מועיל להתחיל מכאן.

ערך העצמי של $M_a$ המתאים לוקטור העצמי $\vert \psi_1\rangle$ הוא

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

כלומר, $\omega_r = e^{2\pi i \theta}$ עבור $\theta = 1/r.$ לכן, אם נריץ את הליך אמידת הפאזה על $M_a$ תוך שימוש בוקטור העצמי $\vert\psi_1\rangle,$ נקבל קירוב ל-$1/r.$ על ידי חישוב ההופכי נוכל ללמוד את $r$ — בתנאי שהקירוב שלנו מדויק מספיק.

בפירוט רב יותר, כשמריצים את הליך אמידת הפאזה עם $m$ Qubit בקרה, מה שמתקבל הוא מספר $y\in\{0,\ldots,2^m-1\}.$ לאחר מכן לוקחים $y/2^m$ כניחוש עבור $\theta,$ שהוא $1/r$ במקרה שלנו. כדי לגלות מה הוא $r$ מהקירוב הזה, הדבר הטבעי הוא לחשב את ההופכי של הקירוב ולעגל למספר השלם הקרוב ביותר.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

לדוגמה, נניח ש-$r = 6$ ואנחנו מבצעים אמידת פאזה על $M_a$ עם הוקטור העצמי $\vert\psi_1\rangle$ תוך שימוש ב-$m = 5$ ביטי בקרה. הקירוב הטוב ביותר ב-$5$ ביטים ל-$1/r = 1/6$ הוא $5/32,$ ויש לנו סיכוי לא רע (כ-$68\%$ במקרה זה) לקבל את התוצאה $y=5$ מאמידת הפאזה. יש לנו

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

ועיגול למספר השלם הקרוב ביותר נותן $6,$ שהוא התשובה הנכונה.

מצד שני, אם לא נשתמש בדיוק מספיק, ייתכן שלא נקבל את התשובה הנכונה. למשל, אם ניקח $m = 4$ Qubit בקרה באמידת הפאזה, נוכל לקבל את הקירוב הטוב ביותר ב-$4$ ביטים ל-$1/r = 1/6,$ שהוא $3/16.$ נטילת ההופכי נותנת

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

ועיגול למספר השלם הקרוב ביותר נותן תשובה שגויה — $5.$

אז כמה דיוק אנחנו צריכים כדי לקבל את התשובה הנכונה? אנחנו יודעים ש-$r$ הוא מספר שלם, ובאופן אינטואיטיבי מה שצריך הוא דיוק מספיק כדי להבדיל בין $1/r$ לבין אפשרויות סמוכות, כולל $1/(r+1)$ ו-$1/(r-1).$ המספר הקרוב ביותר ל-$1/r$ שצריך להדאיג אותנו הוא $1/(r+1),$ והמרחק בין שני המספרים הללו הוא

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

לכן, אם נרצה לוודא שלא נטעה בין $1/r$ ל-$1/(r+1),$ מספיק להשתמש בדיוק מספיק כדי להבטיח שהקירוב הטוב ביותר $y/2^m$ ל-$1/r$ קרוב יותר ל-$1/r$ מאשר ל-$1/(r+1).$ אם נשתמש בדיוק מספיק כדי להבטיח ש

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

כך שהשגיאה קטנה מחצי המרחק בין $1/r$ ל-$1/(r+1),$ אז $y/2^m$ יהיה קרוב יותר ל-$1/r$ מאשר לכל אפשרות אחרת, כולל $1/(r+1)$ ו-$1/(r-1).$

ניתן לאמת זאת באופן הבא. נניח ש

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

עבור $\varepsilon$ המקיים

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

כשנוטלים את ההופכי מקבלים

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

על ידי מקסום המונה ומינום המכנה, ניתן לחסום את המרחק מ-$r$ כך:

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

אנחנו פחות מ-$1/2$ רחוקים מ-$r,$ ולכן כצפוי נקבל $r$ כשנעגל.

לרוע המזל, מכיוון שעדיין לא ידוע לנו מה הוא $r,$ אנחנו לא יכולים להשתמש בו כדי לדעת כמה דיוק אנחנו צריכים. מה שניתן לעשות במקום זאת הוא להשתמש בעובדה ש-$r$ חייב להיות קטן מ-$N$ כדי להבטיח שנשתמש בדיוק מספיק. בפרט, אם נשתמש בדיוק מספיק כדי להבטיח שהקירוב הטוב ביותר $y/2^m$ ל-$1/r$ מקיים

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

אז יהיה לנו דיוק מספיק לקבוע נכון את $r$ כשנחשב את ההופכי. נטילת $m = 2\operatorname{lg}(N)+1$ מבטיחה שיש לנו סיכוי גבוה לקבל אמידה ברמת דיוק זו בשיטה שתוארה קודם. (נטילת $m = 2\operatorname{lg}(N)$ מספיקה אם מסתפקים בחסם תחתון של 40% על הסתברות ההצלחה.)

פתרון כללי

כפי שראינו זה עתה, אם יש לנו את הוקטור העצמי $\vert \psi_1 \rangle$ של $M_a,$ אנחנו יכולים ללמוד את $r$ דרך אמידת פאזה, כל עוד משתמשים במספר מספיק של Qubit בקרה לביצוע זאת עם דיוק מספיק. לרוע המזל, לא קל להשיג את הוקטור העצמי $\vert\psi_1\rangle,$ ולכן צריך לגלות כיצד להמשיך.

נניח לרגע שאנחנו ממשיכים בדיוק כמו לעיל, אך עם הוקטור העצמי $\vert\psi_k\rangle$ במקום $\vert\psi_1\rangle,$ לכל בחירה של $k\in\{0,\ldots,r-1\}$ שנבחר לחשוב עליה. התוצאה שנקבל מהליך אמידת הפאזה תהיה קירוב

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

בהנחה שאנחנו לא יודעים לא את $k$ ולא את $r,$ ייתכן שיאפשר לנו לזהות את $r$ ואולי לא. למשל, אם $k = 0$ נקבל קירוב $y/2^m$ לאפס, שלמרבה הצער אינו מלמד אותנו כלום. אולם מדובר במקרה יוצא דופן; עבור ערכים אחרים של $k,$ נוכל לפחות ללמוד משהו על $r.$

ניתן להשתמש באלגוריתם הידוע בשם אלגוריתם השברים המשורשרים כדי להפוך את הקירוב $y/2^m$ לשברים קרובים — כולל $k/r$ אם הקירוב מדויק מספיק. לא נסביר כאן את אלגוריתם השברים המשורשרים. במקום זאת, הנה פירוט של עובדה ידועה על אלגוריתם זה.

עובדה

בהינתן מספר שלם $N\geq 2$ ומספר ממשי $\alpha\in(0,1),$ קיים לכל היותר מספר שלם אחד $u,v\in\{0,\ldots,N-1\}$ עם $v\neq 0$ ו-$\gcd(u,v)=1$ המקיים $\vert \alpha - u/v\vert < \frac{1}{2N^2}.$ בהינתן $\alpha$ ו-$N,$ אלגוריתם השברים המשורשרים מוצא את $u$ ואת $v,$ או מדווח שאינם קיימים. ניתן לממש אלגוריתם זה כמעגל בוליאני בגודל $O((\operatorname{lg}(N))^3).$

אם יש לנו קירוב קרוב מאוד $y/2^m$ ל-$k/r,$ ונריץ את אלגוריתם השברים המשורשרים עבור $N$ ו-$\alpha = y/2^m,$ נקבל את $u$ ואת $v$ כפי שמתוארים בעובדה. ניתוח העובדה מאפשר לנו להסיק ש

$$\frac{u}{v} = \frac{k}{r}.$$

שימו לב בפרט שאנחנו לא בהכרח לומדים את $k$ ואת $r,$ אנחנו רק לומדים את $k/r$ בצורה מצומצמת.

לדוגמה, וכפי שכבר ציינו, לא נלמד כלום מ-$k=0.$ אבל זה הערך היחיד של $k$ שבו זה קורה. כאשר $k$ אינו אפס, יתכן שיש לו מחלקים משותפים עם $r,$ אבל המספר $v$ שנקבל מאלגוריתם השברים המשורשרים חייב לפחות לחלק את $r.$

זה לא מובן מאליו, אבל אכן נכון שאם יש לנו יכולת ללמוד את $u$ ואת $v$ עבור $u/v = k/r$ עבור $k\in\{0,\ldots,r-1\}$ שנבחר אחיד אקראית, אז סביר מאוד שנוכל לשחזר את $r$ לאחר מספר קטן של דגימות. בפרט, אם הניחוש שלנו ל-$r$ הוא המכפל המשותף הקטן ביותר של כל ערכי המכנה $v$ שאנחנו צופים בהם, נהיה צודקים עם הסתברות גבוהה. בצורה אינטואיטיבית, ערכים מסוימים של $k$ אינם טובים מפני שיש להם מחלקים משותפים עם $r,$ והמחלקים הללו נסתרים ממנו כשאנחנו לומדים את $u$ ואת $v.$ אבל בחירות אקראיות של $k$ אינן צפויות להסתיר מחלקים של $r$ לאורך זמן, וההסתברות שלא ניחש נכון את $r$ על ידי נטילת המכפל המשותף הקטן ביותר של המכנים שאנחנו צופים בהם יורדת בצורה מעריכית במספר הדגימות.

נותר לטפל בשאלה כיצד להשיג וקטור עצמי $\vert\psi_k\rangle$ של $M_a$ עליו להריץ את הליך אמידת הפאזה. כפי שמסתבר, בכלל לא צריך ליצור אותם!

מה שנעשה במקום זאת הוא להריץ את הליך אמידת הפאזה על המצב $\vert 1\rangle,$ כלומר על הקידוד הבינארי של $n$ ביטים של המספר $1,$ במקום וקטור עצמי $\vert\psi\rangle$ של $M_a.$ עד כה דיברנו רק על הרצת הליך אמידת הפאזה על וקטור עצמי מסוים, אבל שום דבר לא מונע אותנו מלהריץ את ההליך על מצב כניסה שאינו וקטור עצמי של $M_a,$ וזה בדיוק מה שאנחנו עושים כאן עם המצב $\vert 1\rangle.$ (זהו וקטור עצמי של $M_a$ רק אם $a=1,$ שזה לא בחירה שתעניין אותנו.)

ההנמקה לבחירה במצב $\vert 1\rangle$ במקום וקטור עצמי של $M_a$ היא שהמשוואה הבאה נכונה.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

דרך אחת לאמת משוואה זו היא להשוות את המכפלות הפנימיות של שני הצדדים עם כל מצב בסיס סטנדרטי, תוך שימוש בנוסחאות שהוזכרו קודם בשיעור כדי לעזור בהערכת התוצאות עבור הצד הימני. כתוצאה מכך, נקבל בדיוק את אותן תוצאות מדידה כאילו בחרנו $k\in\{0,\ldots,r-1\}$ אחיד אקראית והשתמשנו ב-$\vert\psi_k\rangle$ כוקטור עצמי.

בפירוט רב יותר, בואו נדמיין שאנחנו מריצים את הליך אמידת הפאזה עם המצב $\vert 1\rangle$ במקום אחד מהוקטורים העצמיים $\vert\psi_k\rangle.$ לאחר ביצוע התמרת פורייה הקוונטית ההפוכה, נקבל את המצב

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

כאשר

$$\vert\gamma_k\rangle = \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (k/r - y/2^m)} \vert y\rangle.$$

הוקטור $\vert\gamma_k\rangle$ מייצג את המצב של $m$ ה-Qubit העליונים לאחר שהתמרת פורייה הקוונטית ההפוכה בוצעה עליהם.

לכן, מתוך העובדה ש-$\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ הוא קבוצה אורתונורמלית, מוצאים שמדידה של $m$ ה-Qubit העליונים נותנת קירוב $y/2^m$ לערך $k/r$ כאשר $k\in\{0,\ldots,r-1\}$ נבחר אחיד אקראית. כפי שכבר דיברנו, זה מאפשר לנו ללמוד את $r$ ברמת ביטחון גבוהה לאחר מספר הרצות עצמאיות, וזה היה המטרה שלנו.

עלות כוללת

עלות המימוש של כל יחידה מבוקרת $M_a^k$ היא $O(n^2).$ יש $m$ פעולות יחידה מבוקרת, ו-$m = O(n),$ ולכן העלות הכוללת של פעולות היחידה המבוקרת היא $O(n^3).$ בנוסף, יש לנו $m$ שערי הדאמארד (שתורמים $O(n)$ לעלות), והתמרת פורייה הקוונטית ההפוכה תורמת $O(n^2)$ לעלות. לכן, עלות פעולות היחידה המבוקרת שולטת בעלות של כל ההליך — שהיא לכן $O(n^3).$

בנוסף למעגל הקוונטי עצמו, יש כמה חישובים קלאסיים שצריך לבצע בדרך. זה כולל חישוב החזקות $a^k$ ב-$\mathbb{Z}_N$ עבור $k = 2, 4, 8, \ldots, 2^{m-1},$ הנדרשות ליצירת שערי היחידה המבוקרת, וכן אלגוריתם השברים המשורשרים שממיר קירובים של $\theta$ לשברים. ניתן לבצע חישובים אלה במעגלים בוליאניים בעלות כוללת של $O(n^3).$

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

פירוק לגורמים באמצעות מציאת סדר

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

הנה הרעיון הבסיסי. אנחנו רוצים לפרק את המספר $N,$ ואפשר לעשות זאת רקורסיבית. ספציפית, אפשר להתמקד במשימת פיצול $N,$ כלומר למצוא שני מספרים שלמים $b,c\geq 2$ כך ש-$N = bc.$ זה לא אפשרי אם $N$ הוא מספר ראשוני, אבל אפשר לבדוק ביעילות אם $N$ ראשוני באמצעות אלגוריתם בדיקת ראשוניות תחילה, ואם $N$ אינו ראשוני ננסה לפצל אותו. ברגע שמפצלים את $N,$ אפשר פשוט להמשיך רקורסיבית על $b$ ו-$c$ עד שכל הגורמים שלנו יהיו ראשוניים ונקבל את הפירוק לגורמים ראשוניים של $N.$

פיצול מספרים זוגיים הוא פשוט: פשוט מוציאים $2$ ו-$N/2.$

קל גם לפצל חזקות שלמות, כלומר מספרים מהצורה $N = s^j$ עבור מספרים שלמים $s,j\geq 2,$ פשוט על ידי קירוב השורשים $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ וכן הלאה, ובדיקת מספרים שלמים קרובים כמועמדים עבור $s.$ אין צורך להרחיק יותר מ-$\log(N)$ צעדים בסדרה הזו, כי בנקודה הזו השורש יורד מתחת ל-$2$ ולא יחשוף מועמדים נוספים.

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

אלגוריתם הסתברותי לפיצול מספר שלם אי-זוגי ומורכב N שאינו חזקת ראשוני

1. בחר אקראית $a\in\{2,\ldots,N-1\}.$

2. חשב $d=\gcd(a,N).$

3. אם $d > 1$ אז הוצא $b = d$ ו-$c = N/d$ ועצור. אחרת המשך לשלב הבא בידיעה ש-$a\in\mathbb{Z}_N^{\ast}.$

4. יהי $r$ הסדר של $a$ מודולו $N.$ (כאן נזדקק למציאת סדר.)

5. אם $r$ זוגי:

   5.1 חשב $x = a^{r/2} - 1$ מודולו $N$
   5.2 חשב $d = \gcd(x,N).$
   5.3 אם $d>1$ אז הוצא $b=d$ ו-$c = N/d$ ועצור.

6. אם הגעת לנקודה הזו, האלגוריתם נכשל במציאת גורם של $N.$

הרצה של האלגוריתם הזה עשויה להיכשל במציאת גורם של $N.$ ספציפית, זה קורה בשני מצבים:

• הסדר של $a$ מודולו $N$ הוא אי-זוגי.
• הסדר של $a$ מודולו $N$ הוא זוגי ו-$\gcd\bigl(a^{r/2} - 1, N\bigr) = 1.$

תורת המספרים הבסיסית מוכיחה שעבור בחירה אקראית של $a,$ בהסתברות של לפחות $1/2$ אף אחד מהמקרים הללו לא קורה. למעשה, ההסתברות שאחד מהאירועים הללו מתרחש היא לכל היותר $2^{-(m-1)}$ כאשר $m$ הוא מספר הגורמים הראשוניים השונים של $N,$ ולכן נדרשת ההנחה ש-$N$ אינו חזקת ראשוני. (גם ההנחה ש-$N$ אי-זוגי נדרשת כדי שעובדה זו תהיה נכונה.)

משמעות הדבר היא שלכל הרצה יש סיכוי של לפחות 50% לפצל את $N.$ לכן, אם נריץ את האלגוריתם $t$ פעמים, בכל פעם עם בחירה אקראית של $a,$ נצליח לפצל את $N$ בהסתברות של לפחות $1 - 2^{-t}.$

הרעיון הבסיסי שעומד מאחורי האלגוריתם הוא כדלקמן. אם יש לנו בחירה של $a$ שעבורה הסדר $r$ של $a$ מודולו $N$ הוא זוגי, אז $r/2$ הוא מספר שלם ואפשר לבחון את המספרים

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{and} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

תוך שימוש בנוסחה $Z^2 - 1 = (Z+1)(Z-1),$ אנחנו מסיקים ש-

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

כעת, אנחנו יודעים ש-$a^r \; (\textrm{mod}\; N) = 1$ לפי הגדרת הסדר — דרך אחרת לומר ש-$N$ מחלק ללא שארית את $a^r - 1.$ כלומר $N$ מחלק ללא שארית את המכפלה

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

כדי שזה יתאפשר, כל הגורמים הראשוניים של $N$ חייבים להיות גם גורמים ראשוניים של $a^{r/2} - 1$ או $a^{r/2} + 1$ (או שניהם) — ועבור בחירה אקראית של $a$ מתברר שלא סביר שכל הגורמים הראשוניים של $N$ יחלקו אחד מהאיברים בלבד ואף אחד לא יחלק את האחר.