בעיית אמידת הפאזה

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

משפט הספקטרום

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

מטריצות נורמליות

מטריצה ריבועית $M$ עם ערכים מרוכבים נקראת מטריצה נורמלית אם היא מתחלפת עם הטרנספוז המצומד שלה: $M M^{\dagger} = M^{\dagger} M.$

כל מטריצה אוניטרית $U$ היא נורמלית, כי

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

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

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

ולכן $H$ היא נורמלית.

לא כל מטריצה ריבועית היא נורמלית. לדוגמה, המטריצה הבאה אינה נורמלית:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

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

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

בעוד ש

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

ניסוח המשפט

הנה ניסוח של משפט הספקטרום.

משפט

משפט הספקטרום: תהי $M$ מטריצה מרוכבת נורמלית מסדר $N\times N$. קיים בסיס אורתונורמלי של וקטורים מרוכבים ממימד $N$, $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$, ומספרים מרוכבים $\lambda_1,\ldots,\lambda_N$ כך ש

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

הביטוי של מטריצה בצורה

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

נקרא בדרך כלל פירוק ספקטרלי. שים לב שאם $M$ היא מטריצה נורמלית המבוטאת בצורה $(1)$, אז המשוואה

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

חייבת להתקיים לכל $j = 1,\ldots,N$. זוהי תוצאה של העובדה ש $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ הוא אורתונורמלי:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

כלומר, כל מספר $\lambda_j$ הוא ערך עצמי של $M$ ו-$\vert\psi_j\rangle$ הוא וקטור עצמי המתאים לאותו ערך עצמי.

• דוגמה 1. נגדיר

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  שהיא נורמלית. מהמשפט נובע שאת $\mathbb{I}$ ניתן לכתוב בצורה $(1)$ עבור בחירה כלשהי של $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ ו-$\vert\psi_2\rangle.$ ישנן מספר בחירות שעובדות, כולל

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  שים לב שהמשפט אינו אומר שהמספרים המרוכבים $\lambda_1,\ldots,\lambda_N$ הם שונים זה מזה — יכול להיות שאותו מספר מרוכב חוזר על עצמו, דבר הכרחי בדוגמה זו. בחירות אלה עובדות כי

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  למעשה, ניתן לבחור את $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ כ-כל בסיס אורתונורמלי והמשוואה תתקיים. לדוגמה,

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• דוגמה 2. נבחן פעולת הדמארד.

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

  זוהי מטריצה אוניטרית, לכן היא נורמלית. ממשפט הספקטרום נובע ש-$H$ ניתן לכתוב בצורה $(1)$, ובפרט מתקיים

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  כאשר

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  באופן מפורש יותר,

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  ניתן לבדוק שהפירוק נכון על ידי ביצוע החישובים הנדרשים:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

כפי שהדוגמה הראשונה לעיל מגלה, יש לעתים חופש בבחירת הוקטורים העצמיים. עם זאת, אין כלל חופש בבחירת הערכים העצמיים, פרט לסדרם: אותם $N$ מספרים מרוכבים $\lambda_1,\ldots,\lambda_N$, שיכולים לכלול חזרות של אותו מספר מרוכב, תמיד יופיעו במשוואה $(1)$ עבור בחירה נתונה של מטריצה $M$.

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

$$U\vert\psi\rangle = \lambda\vert\psi\rangle. \tag{2}$$

כלומר, $\lambda$ הוא ערך עצמי של $U$ ו-$\vert\psi\rangle$ הוא וקטור עצמי המתאים לערך עצמי זה.

מטריצות אוניטריות שומרות על הנורמה האוקלידית, ולכן אנחנו מסיקים את הדבר הבא מ-$(2)$.

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

מהתנאי ש-$\vert\psi\rangle$ הוא לא-אפס נובע ש-$\bigl\| \vert\psi\rangle \bigr\|\neq 0$, לכן ניתן לצמצם אותו משני הצדדים ולקבל

$$\vert \lambda \vert = 1.$$

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

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(הסימן $\mathbb{T}$ הוא שם נפוץ למעגל היחידה המרוכב. השם $S^1$ גם הוא נפוץ.)

ניסוח בעיית אמידת הפאזה

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

$$\lambda = e^{2\pi i \theta}$$

עבור מספר ממשי יחיד $\theta$ המקיים $0\leq\theta<1$. מטרת הבעיה היא לחשב או לקרב את המספר הממשי הזה $\theta$.

בעיית אמידת הפאזה

קלט: Circuit קוונטי אוניטרי לפעולה $U$ על $n$ קיוביטים, יחד עם מצב קוונטי $\vert\psi\rangle$ של $n$ קיוביטים
הבטחה: $\vert\psi\rangle$ הוא וקטור עצמי של $U$
פלט: קירוב למספר $\theta\in[0,1)$ המקיים $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

הנה כמה הערות על ניסוח הבעיה:

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

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

3. שים לב שכאשר אנחנו עוברים מ-$\theta = 0$ לכיוון $\theta = 1$ בבעיית אמידת הפאזה, אנחנו עוברים כל הדרך סביב מעגל היחידה, החל מ-$e^{2\pi i \cdot 0} = 1$ ונעים נגד כיוון השעון לכיוון $e^{2\pi i \cdot 1} = 1$. כלומר, כאשר אנחנו מגיעים ל-$\theta = 1$ אנחנו חוזרים לנקודת ההתחלה ב-$\theta = 0$. לכן, כאשר אנחנו שוקלים את דיוק הקירובים, ערכי $\theta$ קרובים ל-$1$ נחשבים כקרובים ל-$0$. לדוגמה, קירוב $\theta = 0.999$ נחשב כנמצא בטווח של $1/1000$ מ-$\theta = 0$.