הליך אמידת הפאזה

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

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

חימום: קירוב פאזות ברזולוציה נמוכה

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

שימוש ב-phase kickback

גישה פשוטה לבעיית אמידת הפאזה, שמאפשרת לנו ללמוד משהו על הערך $\theta$ שאנחנו מחפשים, מבוססת על תופעת ה-phase kick-back. כפי שנראה, זו בעצם גרסה של qubit יחיד של הליך אמידת הפאזה הכללי שיידון מאוחר יותר בשיעור.

כחלק מהקלט לבעיית אמידת הפאזה, יש לנו Circuit קוונטי לפעולה $U.$ אנחנו יכולים להשתמש בתיאור של Circuit זה כדי ליצור Circuit לפעולת controlled-$U$, שניתן לתאר אותה כפי שמציעה התמונה הזו (עם הפעולה $U,$ הנתפסת כ-Gate קוונטי, משמאל ופעולת controlled-$U$ מימין).

אנחנו יכולים ליצור Circuit קוונטי לפעולת controlled-$U$ על ידי הוספת qubit שליטה ל-Circuit עבור $U$, ולאחר מכן להחליף כל Gate ב-Circuit עבור $U$ בגרסה מבוקרת של אותו Gate — כך שה-Qubit השליטה החדש שלנו שולט בפועל בכל Gate יחיד ב-Circuit עבור $U.$ זה דורש שתהיה לנו גרסה מבוקרת של כל Gate ב-Circuit שלנו, אבל תמיד אפשר לבנות Circuits עבור פעולות מבוקרות אלה במקרה שהן לא נכללות בסט ה-Gate שלנו.

עכשיו שקלו את ה-Circuit הבא, שבו מצב הקלט $\vert\psi\rangle$ של כל ה-Qubits חוץ מהעליון הוא וקטור עצמי של המצב הקוונטי של $U.$

ההסתברויות לתוצאות המדידה של Circuit זה תלויות בערך העצמי של $U$ שמתאים לוקטור העצמי $\vert\psi\rangle.$ בואו ננתח את ה-Circuit בפירוט כדי לקבוע בדיוק איך.

המצב ההתחלתי של ה-Circuit הוא

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

וה-Gate הראשון של הדאמר מטפל במצב זה ומשנה אותו ל:

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

לאחר מכן, מתבצעת פעולת controlled-$U$, שמביאה למצב

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

בשימוש בהנחה ש-$\vert\psi\rangle$ הוא וקטור עצמי של $U$ עם ערך עצמי $\lambda = e^{2\pi i\theta},$ אנחנו יכולים לבטא את המצב הזה אחרת, כך:

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

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

לבסוף, מתבצע ה-Gate השני של הדאמר. לאחר פישוט קל, אנחנו מקבלים את הביטוי הזה עבור המצב הזה.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

המדידה מניבה לכן את התוצאות $0$ ו-$1$ עם ההסתברויות הבאות:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

הנה גרף של ההסתברויות לשתי התוצאות האפשריות, $0$ ו-$1,$ כפונקציות של $\theta.$

כמובן, שתי ההסתברויות תמיד מסתכמות ל-$1.$ שימו לב שכאשר $\theta = 0,$ תוצאת המדידה היא תמיד $0,$ וכאשר $\theta = 1/2,$ תוצאת המדידה היא תמיד $1.$ כלומר, למרות שתוצאת המדידה לא חושפת בדיוק מהו $\theta$, היא כן מספקת לנו מידע כלשהו עליו — ואם היה מובטח לנו שאחד מהם $\theta = 0$ או $\theta = 1/2,$ יכולנו ללמוד מה-Circuit איזה מהם נכון ללא שגיאה.

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

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

תוצאת המדידה ניתנת לראייה כניחוש עבור הסיבית $a.$ כאשר $\theta$ אינו $0$ ולא $1/2,$ יש הסתברות שאינה אפס שהניחוש יהיה שגוי — אבל הסתברות ביצוע השגיאה הולכת וקטנה ככל שמתקרבים ל-$0$ או ל-$1/2.$

טבעי לשאול מה תפקיד שני ה-Gate של הדאמר בהליך זה:

• ה-Gate הראשון של הדאמר מגדיר את ה-Qubit השליטה לסופרפוזיציה אחידה של $\vert 0\rangle$ ו-$\vert 1\rangle,$ כך שכאשר ה-phase kickback מתרחש, הוא קורה עבור המצב $\vert 1\rangle$ ולא עבור המצב $\vert 0\rangle,$ ויוצר הפרש פאזה יחסי שמשפיע על תוצאות המדידה. אם לא היינו עושים זאת ו-phase kickback היה מייצר פאזה גלובלית, זה לא היה משפיע על ההסתברויות לקבלת תוצאות מדידה שונות.

• ה-Gate השני של הדאמר מאפשר לנו ללמוד משהו על המספר $\theta$ דרך תופעת ההתאבכות. לפני ה-Gate השני של הדאמר, מצב ה-Qubit העליון הוא

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  ואם היינו מודדים מצב זה, היינו מקבלים $0$ ו-$1$ כל אחד עם הסתברות $1/2,$ ולא מספרים לנו כלום על $\theta.$ עם זאת, על ידי ביצוע ה-Gate השני של הדאמר, אנחנו גורמים למספר $\theta$ להשפיע על הסתברויות הפלט.

הכפלת הפאזה

ה-Circuit לעיל משתמש בתופעת ה-phase kickback כדי לקרב את $\theta$ לדיוק של סיבית בודדת. דיוק של סיבית אחת עשוי להיות כל מה שאנחנו צריכים במצבים מסוימים — אבל לפקטוריזציה נצטרך הרבה יותר דיוק מזה. שאלה טבעית היא, כיצד נוכל ללמוד יותר על $\theta?$

דבר פשוט מאוד שנוכל לעשות הוא להחליף את פעולת controlled-$U$ ב-Circuit שלנו בשני עותקים של פעולה זו, כמו ב-Circuit הזה:

שני עותקים של פעולת controlled-$U$ שקולים לפעולת controlled-$U^2$ אחת. אם $\vert\psi\rangle$ הוא וקטור עצמי של $U$ עם ערך עצמי $\lambda = e^{2\pi i \theta},$ אז מצב זה הוא גם וקטור עצמי של $U^2$, הפעם עם ערך עצמי $\lambda^2 = e^{2\pi i (2\theta)}.$

לכן, אם נריץ גרסה זו של ה-Circuit, אנחנו בעצם מבצעים את אותו חישוב כמו קודם, אלא שהמספר $\theta$ מוחלף ב-$2\theta.$ הנה גרף המדגים את הסתברויות הפלט כש-$\theta$ נע בין $0$ ל-$1.$

עשיית זאת אכן יכולה לספק לנו מידע נוסף על $\theta.$ אם הייצוג הבינארי של $\theta$ הוא

$$\theta = 0.a_1 a_2 a_3\cdots$$

אז הכפלת $\theta$ זזה בפועל את הנקודה הבינארית מיקום אחד ימינה:

$$2\theta = a_1. a_2 a_3\cdots$$

ומכיוון שאנחנו משווים $\theta = 1$ עם $\theta = 0$ כשאנחנו מסתובבים סביב מעגל היחידה, אנחנו רואים שלסיבית $a_1$ אין השפעה על ההסתברויות שלנו, ואנחנו בעצם מקבלים ניחוש עבור הסיבית השנייה אחרי הנקודה הבינארית אם נעגל את $\theta$ לשתי סיביות. לדוגמה, אם ידענו מראש ש-$\theta$ הוא $0$ או $1/4,$ נוכל לסמוך לחלוטין על תוצאת המדידה שתגיד לנו איזה.

עם זאת, לא ברור מיד כיצד יש לפייס אמידה זו עם מה שלמדנו מה-Circuit המקורי (ה-phase kickback הלא מוכפל) כדי לתת לנו את המידע המדויק ביותר האפשרי על $\theta.$ אז בואו נחזור צעד אחורה ונשקול כיצד להמשיך.

אמידת פאזה עם שני qubits

במקום לשקול את שתי האפשרויות שתוארו לעיל בנפרד, בואו נשלב אותן ל-Circuit יחיד כך.

ה-Gate של הדאמר אחרי הפעולות המבוקרות הוסרו ואין כאן עדיין מדידות. נוסיף עוד ל-Circuit כשנשקול את האפשרויות שלנו ללמוד כמה שיותר על $\theta.$

אם נריץ Circuit זה כאשר $\vert\psi\rangle$ הוא וקטור עצמי של $U$, מצב ה-Qubits התחתונים יישאר $\vert\psi\rangle$ לאורך כל ה-Circuit, ופאזות "ייקרצו" למצב שני ה-Qubits העליונים. בואו ננתח את ה-Circuit בזהירות, באמצעות התמונה הבאה.

אנחנו יכולים לכתוב את המצב $\vert\pi_1\rangle$ כך:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

כאשר פעולת controlled-$U$ הראשונה מתבצעת, הערך העצמי $\lambda = e^{2\pi i\theta}$ נקרץ לפאזה כאשר $a_0$ (ה-Qubit העליון) שווה ל-$1,$ אבל לא כאשר הוא $0.$ לכן, אנחנו יכולים לבטא את המצב המתקבל כך:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

ה-Gate השני והשלישי של controlled-$U$ עושים משהו דומה, אלא עבור $a_1$ ולא $a_0$, וכאשר $\theta$ מוחלף ב-$2\theta.$ אנחנו יכולים לבטא את המצב המתקבל כך:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

אם נחשוב על המחרוזת הבינארית $a_1 a_0$ כמייצגת מספר שלם $x \in \{0,1,2,3\}$ בסימון בינארי, שהוא $x = 2 a_1 + a_0,$ נוכל לבטא את המצב הזה אחרת כך:

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

המטרה שלנו היא לחלץ כמה שיותר מידע על $\theta$ ממצב זה.

בשלב זה נשקול מקרה מיוחד, שבו מובטח לנו ש-$\theta = \frac{y}{4}$ עבור מספר שלם כלשהו $y\in\{0,1,2,3\}.$ במילים אחרות, $\theta\in \{0, 1/4, 1/2, 3/4\},$ כלומר אנחנו יכולים לבטא מספר זה בדיוק בסימון בינארי עם שתי סיביות, כ-$.$00,$.$01,$.$10,$או .$11.$באופן כללי,$\theta$עשוי שלא להיות אחד מארבעת הערכים הללו, אבל חשיבה על מקרה מיוחד זה תעזור לנו להבין כיצד לחלץ מידע על$\theta$ בצורה האפקטיבית ביותר באופן כללי.

ראשית נגדיר וקטור מצב של שני qubits לכל ערך אפשרי $y \in \{0, 1, 2, 3\}.$

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

לאחר פישוט האקספוננטים, אנחנו יכולים לכתוב וקטורים אלה כך:

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

וקטורים אלה אורתוגונליים: אם נבחר כל זוג מהם ונחשב את המכפלה הפנימית שלהם, נקבל $0.$ כל אחד מהם הוא גם וקטור יחידה, כך ש-$\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ הוא בסיס אורתונורמלי. לכן אנחנו יודעים מיד שקיימת מדידה שיכולה להבחין ביניהם בצורה מושלמת — כלומר, אם ניתן לנו אחד מהם אבל לא ידוע לנו איזה, נוכל לגלות איזה הוא ללא שגיאה.

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

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

כדי לכתוב את $V$ כמטריצה $4\times 4$, צריך פשוט לקחת את העמודות של $V$ להיות המצבים $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle.$

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

זוהי מטריצה מיוחדת, וסביר שחלק מהקוראים כבר נתקלו בה: זוהי המטריצה הקשורה לטרנספורם פורייה הדיסקרטי ממימד $4$. לאור עובדה זו, הבה נכנה אותה בשם $\mathrm{QFT}_4$ ולא $V.$ השם $\mathrm{QFT}$ הוא קיצור של טרנספורם פורייה הקוונטי — שהוא בעצם רק טרנספורם פורייה הדיסקרטי, הנתפס כפעולה יוניטרית. נדון בטרנספורם פורייה הקוונטי בפירוט ובכלליות רבה יותר בקרוב.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

נוכל לבצע את ההופכי של פעולה זו כדי ללכת בכיוון ההפוך, לטפל במצבים $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ למצבי הבסיס הסטנדרטי $\vert 0\rangle,\ldots,\vert 3\rangle.$ אם נעשה זאת, נוכל למדוד כדי ללמוד איזה ערך $y\in\{0,1,2,3\}$ מתאר את $\theta$ כ-$\theta = y/4.$ הנה תרשים של Circuit קוונטי שעושה זאת.

לסיכום, אם נריץ Circuit זה כאשר $\theta = y/4$ עבור $y\in\{0,1,2,3\},$ המצב מיד לפני ביצוע המדידות יהיה $\vert \psi\rangle \vert y\rangle$ (כאשר $y$ מקודד כמחרוזת בינארית של שתי סיביות), לכן המדידות יחשפו את הערך $y$ ללא שגיאה.

Circuit זה מונע על ידי המקרה המיוחד ש-$\theta \in \{0,1/4,1/2,3/4\}$ — אבל אנחנו יכולים להריצו עבור כל בחירה של $U$ ו-$\vert \psi\rangle,$ ולכן כל ערך של $\theta,$ שנרצה. הנה גרף של הסתברויות הפלט ש-Circuit מייצר עבור בחירות שרירותיות של $\theta.$

זוהי שיפור ברור על הגרסה של qubit בודד שתוארה קודם בשיעור. זה לא מושלם — הוא יכול לתת לנו תשובה שגויה — אבל התשובה נוטה מאוד לערכי $y$ עבורם $y/4$ קרוב ל-$\theta.$ בפרט, התוצאה הסבירה ביותר תמיד מתאימה לערך הקרוב ביותר של $y/4$ ל-$\theta$ (בשוות ערך $\theta = 0$ ו-$\theta = 1$ כמקודם), ומהגרף נראה שהערך הקרוב ביותר עבור $x$ מופיע תמיד עם הסתברות מעט מעל $40\%.$ כאשר $\theta$ נמצא בדיוק באמצע בין שני ערכים כאלה, כמו $\theta = 0.375$ לדוגמה, שני ערכי $y$ הקרובים באותה מידה הם בעלי שווה הסתברות.

הכנה להכללה לקראת qubits רבים

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

טרנספורמציית פורייה הקוונטית

טרנספורמציית פורייה הקוונטית היא פעולה יוניטרית שניתן להגדיר עבור כל מספר שלם חיובי $N.$ בחלק הזה נראה איך הפעולה הזו מוגדרת ואיך אפשר לממש אותה עם Circuit קוונטי על $m$ qubits בעלות $O(m^2)$ כאשר $N = 2^m.$

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

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

הגדרת טרנספורמציית פורייה הקוונטית

כדי להגדיר את טרנספורמציית פורייה הקוונטית, נגדיר קודם מספר מרוכב $\omega_N,$ לכל מספר שלם חיובי $N,$ כך:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

זה המספר על מעגל היחידה המרוכב שמתקבל אם מתחילים ב-$1$ וזזים נגד כיוון השעון בזווית של $2\pi/N$ רדיאנים, או שבריר של $1/N$ מהיקף המעגל. הנה כמה דוגמאות:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

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

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

כפי שכבר נאמר, זו המטריצה המשויכת לטרנספורמציית פורייה הדיסקרטית בממד $N.$ לעיתים קרובות הגורם המוביל $1/\sqrt{N}$ לא נכלל בהגדרה של המטריצה הזו, אבל צריך לכלול אותו כדי לקבל מטריצה יוניטרית.

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

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

שימו לב, בפרט, ש-$\mathrm{QFT}_2$ הוא שם נוסף לפעולת הדמארד.

יוניטריות

בואו נוודא ש-$\mathrm{QFT}_N$ הוא יוניטרי, לכל בחירה של $N.$ דרך אחת לעשות זאת היא להראות שהעמודות שלו יוצרות בסיס אורתונורמלי. אפשר להגדיר וקטור המתאים לעמודה מספר $y,$ החל מ-$y = 0$ עד $y = N-1,$ כך:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

לקיחת המכפלה הפנימית בין כל שניים מהוקטורים האלה נותנת לנו את הביטוי הבא:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

אפשר לחשב סכומים כאלה באמצעות הנוסחה הבאה לסכום $N$ האיברים הראשונים של סדרה הנדסית.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

ספציפית, אפשר להשתמש בנוסחה הזו כאשר $\alpha = \omega_N^{y-z}.$ כאשר $y = z,$ מתקבל $\alpha = 1,$ ולכן שימוש בנוסחה וחלוקה ב-$N$ נותן

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

כאשר $y\neq z,$ מתקבל $\alpha \neq 1,$ ולכן הנוסחה מגלה:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

זה קורה כי $\omega_N^N = e^{2\pi i} = 1,$ ולכן $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ מה שהופך את המונה לאפס, בעוד שהמכנה שונה מאפס כי $\omega_N^{y-z} \neq 1.$ באופן אינטואיטיבי, מה שעושים כאן הוא לסכום קבוצת נקודות שמפוזרות על מעגל היחידה, והן מתבטלות ומשאירות $0$ בסכום.

הוכחנו אם כך ש-$\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ הוא קבוצה אורתונורמלית,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

מה שמגלה ש-$\mathrm{QFT}_N$ הוא יוניטרי.

שערי פאזה מבוקרים

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

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

לכל מספר ממשי $\alpha.$ לגרסה המבוקרת של Gate הזה יש המטריצה הבאה:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

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

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

כדי לבצע את טרנספורמציית פורייה הקוונטית כאשר $N = 2^m$ ו-$m\geq 2,$ נצטרך לבצע פעולה על $m$ qubits שפעולתה על וקטורי הבסיס הסטנדרטיים ניתנת לתיאור כ

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

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

באופן כללי, לכל בחירה שרירותית של $m\geq 2,$ ה-Qubit העליון המתאים לביט $a$ יכול להיחשב כשליטה, כשגייטי הפאזה $P_{\alpha}$ נעים מ-$\alpha = \pi/2^{m-1}$ על ה-Qubit המתאים לביט הכי פחות משמעותי של $y$ עד $\alpha = \frac{\pi}{2}$ על ה-Qubit המתאים לביט הכי משמעותי של $y.$ שערי הפאזה המבוקרים האלה כולם מתחלפים זה עם זה וניתן לבצע אותם בכל סדר.

מימוש Circuit של ה-QFT

עכשיו נראה איך אפשר לממש את טרנספורם פורייה הקוונטי עם Circuit כאשר הממד $N = 2^m$ הוא חזקה של $2.$ בעצם, יש כמה דרכים לממש את טרנספורם פורייה הקוונטי, אבל זו כנראה השיטה הפשוטה ביותר שידועה. ברגע שיודעים לממש את טרנספורם פורייה הקוונטי עם Circuit קוונטי, קל לממש גם את ההופכי שלו: אפשר להחליף כל Gate בהופכי שלו (או, בשורה אחרת, בטרנספוז המצומד) ולהפעיל את ה-Gates בסדר הפוך. כל Circuit קוונטי שמורכב אך ורק מ-Gates יוניטריים ניתן להפוך בצורה כזו.

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

כדי לבצע את טרנספורם פורייה הקוונטי על $m$ qubits כאשר $m \geq 2,$ ניתן לבצע את הצעדים הבאים, שנתאר את פעולתם על מצבי בסיס סטנדרטיים מהצורה $\vert x \rangle \vert a\rangle,$ כאשר $x\in\{0,\ldots,2^{m-1} - 1\}$ הוא מספר שלם מקודד כ-$m-1$ ביטים בסימון בינארי ו-$a$ הוא ביט בודד.

1. ראשית, מפעילים את טרנספורם פורייה הקוונטי ממימד $2^{m-1}$ על $m-1$ ה-Qubits התחתונים/השמאליים ביותר כדי לקבל את המצב הבא:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   הדבר נעשה על ידי הפעלה רקורסיבית של השיטה המתוארת עבור qubit אחד פחות, תוך שימוש בפעולת הדמארד על qubit בודד כמקרה הבסיסי.

2. משתמשים ב-Qubit העליון/הימני ביותר כשליטה כדי להזריק את הפאזה $\omega_{2^m}^y$ עבור כל מצב בסיס סטנדרטי $\vert y\rangle$ של $m-1$ ה-Qubits הנותרים (כפי שתואר לעיל) כדי לקבל את המצב הבא:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. מבצעים Hadamard Gate על ה-Qubit העליון/הימני ביותר כדי לקבל את המצב הבא:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. מסדרים מחדש את סדר ה-Qubits כך שהביט הפחות משמעותי הופך לביט המשמעותי ביותר, כשכל האחרים מוזזים למעלה/ימינה:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

לדוגמה, הנה ה-Circuit שמתקבל עבור $N = 32 = 2^5.$ בדיאגרמה זו, ה-Qubits נקראים בשמות התואמים לוקטורי הבסיס הסטנדרטיים $\vert x\rangle \vert a\rangle$ (עבור הקלט) ו-$\vert b\rangle \vert y\rangle$ (עבור הפלט) לשם בהירות.

ניתוח

הנוסחה המרכזית שצריך לאמת שה-Circuit שתואר מממש את טרנספורם פורייה הקוונטי ממימד $2^m$ היא זו:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

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

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

כאשר השוויון השני משתמש בתצפית ש

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

טרנספורם פורייה הקוונטי ממימד $2^m$ מוגדר כדלקמן עבור כל $u\in\{0,\ldots,2^m - 1\}.$

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

אם נכתוב את $u$ ו-$v$ בתור

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

עבור $a,b\in\{0,1\}$ ו-$x,y\in\{0,\ldots,2^{m-1} - 1\},$ נקבל

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

לבסוף, על ידי חשיבה על מצבי הבסיס הסטנדרטיים $\vert x \rangle \vert a\rangle$ ו-$\vert b \rangle \vert y \rangle$ כקידוד בינארי של מספרים שלמים בתחום $\{0,\ldots,2^m-1\},$

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

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

לבסוף, בואו נספור כמה Gates משמשים ב-Circuit שתואר. ה-Gates של שלב מבוקר אינם בסט ה-Gates הסטנדרטי שדנו בו בשיעור הקודם, אבל לצורך ההתחלה נתעלם מכך ונספור כל אחד מהם כ-Gate בודד.

נסמן ב-$s_m$ את מספר ה-Gates שנדרשים עבור כל בחירה אפשרית של $m.$ אם $m=1,$ טרנספורם פורייה הקוונטי הוא פשוט פעולת הדמארד, ולכן

$$s_1 = 1.$$

אם $m\geq 2,$ אז ב-Circuit לעיל נצטרך $s_{m-1}$ Gates עבור טרנספורם פורייה הקוונטי על $m-1$ qubits, בתוספת $m-1$ Gates של שלב מבוקר, בתוספת Hadamard Gate, בתוספת $m-1$ gates של החלפה, ולכן

$$s_m = s_{m-1} + (2m - 1).$$

ניתן לקבל ביטוי בצורה סגורה על ידי סכימה:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

בעצם אין צורך בכמה gates של החלפה כפי שהשיטה מתארת. אם נסדר מחדש את ה-Gates קצת, נוכל לדחוף את כל gates ההחלפה ימינה ולהפחית את מספרם הנדרש ל-$\lfloor m/2\rfloor.$ מבחינה אסימפטוטית זה לא שיפור משמעותי: עדיין מקבלים Circuits בגודל $O(m^2)$ לביצוע $\mathrm{QFT}_{2^m}.$

אם רוצים לממש את טרנספורם פורייה הקוונטי תוך שימוש רק ב-Gates מסט ה-Gates הסטנדרטי שלנו, צריך לבנות או לקרב כל אחד מ-Gates השלב המבוקר עם gates מהסט שלנו. המספר הנדרש תלוי בדיוק הנדרש, אבל כפונקציה של $m$ העלות הכוללת נשארת ריבועית.

למעשה, ניתן לקרב את טרנספורם פורייה הקוונטי בצורה קרובה מאוד עם מספר תת-ריבועי של gates על ידי שימוש בעובדה ש-$P_{\alpha}$ קרובה מאוד לפעולת הזהות כאשר $\alpha$ קטן מאוד — מה שאומר שניתן פשוט להשמיט את רוב gates השלב המבוקר מבלי לסבול מאובדן גדול מדי מבחינת דיוק.

הפרוצדורה הכללית והניתוח

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

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

הדרך הפשוטה ביותר לממש פעולת controlled-$U^k$ עבור בחירה כלשהי של $k$ היא פשוט לחזור על פעולת controlled-$U$ $k$ פעמים. אם זוהי אכן המתודולוגיה שבשימוש, יש להכיר בכך שהוספת qubits שליטה תורמת באופן משמעותי לגודל ה-Circuit: אם יש לנו $m$ qubits שליטה, כפי שהדיאגרמה מציגה, נדרש סך כולל של $2^m - 1$ עותקים של פעולת controlled-$U$. משמעות הדבר היא שעלות חישובית משמעותית נוצרת ככל ש-$m$ גדל — אבל כפי שנראה, הדבר גם מוביל לקירוב משמעותית יותר מדויק של $\theta.$

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

עכשיו בואו ננתח את ה-Circuit שתואר. המצב מיד לפני טרנספורם פורייה הקוונטי ההפוך נראה כך:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

מקרה מיוחד

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

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

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

$$\vert\psi\rangle \vert y\rangle$$

והמדידות מגלות את $y$ (מקודד בבינארי).

חסימת ההסתברויות

עבור ערכים אחרים של $\theta,$ כלומר כאלה שאינם בצורה $y/2^m$ עבור מספר שלם $y,$ תוצאות המדידה לא יהיו וודאיות, אבל ניתן להוכיח חסמים על ההסתברויות עבור תוצאות שונות. להמשך, נבחן בחירה שרירותית של $\theta$ המקיימת $0\leq \theta < 1.$

לאחר ביצוע טרנספורם פורייה הקוונטי ההפוך, מצב ה-Circuit הוא:

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

לכן, כאשר מבצעים את המדידות על $m$ ה-Qubits העליונים, רואים כל תוצאה $y$ עם הסתברות

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

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

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

ניתן לפשט את הסכום המופיע בנוסחה של $p_y$ על ידי לקיחת $\alpha = e^{2\pi i (\theta - y/2^m)}.$ הנה מה שמתקבל.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

אז, במקרה ש-$\theta = y/2^m,$ מוצאים ש-$p_y = 1$ (כפי שכבר ידענו מהבחינה של המקרה המיוחד), ובמקרה ש-$\theta \neq y/2^m,$ מוצאים ש

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

ניתן ללמוד יותר על ההסתברויות האלה על ידי חשיבה על הקשר בין אורכי קשתות ואורכי מיתרים על מעגל היחידה. הנה איור שממחיש את הקשרים הדרושים לנו עבור כל מספר ממשי $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

ראשית, אורך המיתר (המצויר בכחול) לא יכול להיות גדול מאורך הקשת (המצויר בסגול):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

כשמשווים את האורכים בכיוון ההפוך, רואים שהיחס בין אורך הקשת לאורך המיתר הוא הגדול ביותר כאשר $\delta = \pm 1/2,$ ובמקרה זה היחס הוא מחצית היקף המעגל חלקי הקוטר, שהוא $\pi/2.$ לכן, מתקיים

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

ולכן

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

ניתוח המבוסס על קשרים אלה מגלה שני עובדות חשובות.

1. נניח ש-$\theta$ הוא מספר ממשי ו-$y\in \{0,\ldots,2^m-1\}$ מקיים

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

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

   נוכיח ש-$p_y$ חייב להיות גדול למדי במקרה זה. מהנחת היסוד שאנחנו שוקלים, נובע ש-$\vert 2^m \theta - y \vert \leq 1/2,$ ולכן ניתן להשתמש בתצפית השנייה לעיל בנוגע לקשת ומיתר כדי להסיק ש

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

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

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   שימוש בשתי אי-השוויונות האלה על $p_y$ מגלה

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   זה מסביר את התצפית שלנו שהתוצאה הטובה ביותר מתרחשת עם הסתברות גדולה מ-$40\%$ בגרסת $m=2$ של אמידת הפאזה שנדונה קודם. זה לא ממש 40%, אלא $4/\pi^2,$ ולמעשה חסם זה תקף עבור כל בחירה של $m.$

2. עכשיו נניח ש-$y\in \{0,\ldots,2^m-1\}$ מקיים

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   משמעות הדבר היא שיש קירוב טוב יותר $z/2^m$ ל-$\theta$ בין $\theta$ ל-$y/2^m.$

   הפעם נוכיח ש-$p_y$ לא יכול להיות גדול מדי. ניתן להתחיל מהתצפית הפשוטה ש

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   הנובעת מהעובדה שכל שתי נקודות על מעגל היחידה יכולות להבדל בערך מוחלט לכל היותר ב-$2.$

   ניתן גם להשתמש בתצפית השנייה בנוגע לקשת ומיתר מלעיל, הפעם תוך עבודה עם המכנה של $p_y$ ולא עם המונה, כדי להסיק

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   שילוב שני אי-השוויונות יחד מגלה

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   שימו לב שלמרות שחסם זה מספיק לצרכינו, הוא גס למדי — בדרך כלל ההסתברות נמוכה בהרבה מ-$1/4.$

המסקנה החשובה מניתוח זה היא שקירובים קרובים מאוד ל-$\theta$ צפויים להתרחש — נקבל קירוב טוב ביותר ב-$m$ ביטים עם הסתברות גדולה מ-$40\%$ — בעוד שקירובים שסוטים ביותר מ-$2^{-m}$ פחות סבירים, עם הסתברות חסומה מלמעלה ב-$25\%.$

בהינתן ערובות אלה, ניתן להגביר את הביטחון שלנו על ידי חזרה על פרוצדורת אמידת הפאזה מספר פעמים, כדי לאסוף ראיות סטטיסטיות לגבי $\theta.$ חשוב לציין שהמצב $\vert\psi\rangle$ של אוסף ה-Qubits התחתון אינו משתנה על ידי פרוצדורת אמידת הפאזה, ולכן ניתן להשתמש בו להרצת הפרוצדורה כמה פעמים שרוצים. בפרט, בכל פעם שמריצים את ה-Circuit, מקבלים קירוב טוב ביותר ב-$m$ ביטים ל-$\theta$ עם הסתברות גדולה מ-$40\%,$ בעוד שהסתברות לסטות ביותר מ-$2^{-m}$ חסומה ב-$25\%.$ אם מריצים את ה-Circuit מספר פעמים ולוקחים את התוצאה הנפוצה ביותר, הסיכוי גבוה מאוד שהתוצאה שמופיעה הכי הרבה לא תהיה כזו שמתרחשת לכל היותר $25\%$ מהזמן. כתוצאה מכך, סביר מאוד לקבל קירוב $y/2^m$ שנמצא בתוך $1/2^m$ מהערך $\theta.$ אכן, הסיכוי הנמוך שנסטה ביותר מ-$1/2^m$ יורד באופן אקספוננציאלי עם מספר הפעמים שמריצים את הפרוצדורה.

הנה שתי גרפים המציגים את ההסתברויות עבור שלושה ערכים עוקבים של $y$ כאשר $m = 3$ ו-$m=4$ כפונקציות של $\theta.$ (רק שלוש תוצאות מוצגות לשם בהירות. ההסתברויות עבור תוצאות אחרות מתקבלות על ידי הזזה מחזורית של אותה פונקציה בסיסית.)