אלגוריתמים וריאציוניים

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

לאורך הקורס נחקור:

• כל שלב בזרימת עבודה של עיצוב אלגוריתמים וריאציוניים

• פשרות הקשורות לכל שלב

• כיצד להשתמש בפרימיטיבים של IBM Quantum לאופטימיזציה של מהירות ודיוק

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

זרימת עבודה היברידית מפושטת

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

1. אתחול בעיה: אלגוריתמים וריאציוניים מתחילים באתחול המחשב הקוונטי במצב ברירת המחדל $|0\rangle$, ולאחר מכן הופכים אותו למצב רצוי (בלתי-פרמטרי) $|\rho\rangle$, שנכנה מצב ייחוס.

   טרנספורמציה זו מיוצגת על ידי הפעלת אופרטור ייחוס אוניטרי $U_R$ על מצב ברירת המחדל, כך ש-$U_R|0\rangle = |\rho\rangle$.

2. הכנת אנזאץ': כדי להתחיל באופטימיזציה איטרטיבית ממצב ברירת המחדל $|0\rangle$ למצב המטרה $|\psi(\vec\theta)\rangle$, עלינו להגדיר צורה וריאציונית $U_V(\vec\theta)$ כדי לייצג אוסף של מצבים פרמטריים שהאלגוריתם הוריאציוני שלנו יחקור.

   אנחנו מכנים כל שילוב מסוים של מצב ייחוס וצורה וריאציונית אנזאץ', כך ש: $U_A(\vec\theta) := U_V(\vec\theta) U_R$. האנזאץ' ייקח בסופו של דבר את הצורה של מעגלים קוונטיים פרמטריים המסוגלים להעביר את מצב ברירת המחדל $|0\rangle$ למצב המטרה $|\psi(\vec\theta)\rangle$.

   בסך הכל יהיה לנו:

   $$\begin{aligned} |0\rangle \xrightarrow{U_R} U_R|0\rangle & = |\rho\rangle \xrightarrow{U_V(\vec{\theta})} U_A(\vec{\theta})|0\rangle \\[1mm] & = U_V(\vec{\theta})U_R|0\rangle \\[1mm] & = U_V(\vec{\theta})|\rho\rangle \\[1mm] & = |\psi(\vec{\theta})\rangle \\[1mm] \end{aligned}$$

3. הערכת פונקציית עלות: ניתן לקודד את הבעיה שלנו לפונקציית עלות $C(\vec\theta)$ כצירוף לינארי של אופרטורי Pauli, המורצת על מערכת קוונטית. בעוד שזה יכול להיות מידע על מערכת פיזיקלית, כגון אנרגיה או ספין, ניתן לקודד גם בעיות לא-פיזיקליות. ניתן להיעזר בפרימיטיבים של IBM Quantum לטיפול ברעש באמצעות דיכוי ומיתון שגיאות בעת הערכת פונקציית העלות.

4. אופטימיזציה של פרמטרים: ההערכות מועברות למחשב קלאסי, שבו מייעל קלאסי מנתח אותן ובוחר את הקבוצה הבאה של ערכים לפרמטרים הוריאציוניים. אם יש לנו פתרון אופטימלי קיים מראש, ניתן להגדיר אותו כנקודת התחלה $\vec\theta_0$ כדי לאתחל את האופטימיזציה שלנו. שימוש במצב ראשוני זה $|\psi(\vec\theta_0)\rangle$ יכול לעזור למייעל שלנו למצוא פתרון תקף מהר יותר.

5. התאמת פרמטרי האנזאץ' עם התוצאות והרצה מחדש: כל התהליך חוזר על עצמו עד שקריטריוני הסיום של המייעל הקלאסי מתקיימים, וקבוצה אופטימלית של ערכי פרמטרים $\vec\theta^*$ מוחזרת. מצב הפתרון המוצע לבעיה שלנו יהיה אז $|\psi(\vec\theta^*)\rangle = U_A(\vec\theta^*)|0\rangle$.

המשפט הוריאציוני

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

אינטואיציה מתמטית לאנרגיה ומצבי יסוד

במכניקת הקוונטים, האנרגיה מופיעה בצורת נצפה קוונטי המכונה בדרך כלל ההמילטוניאן, שנסמן אותו ב-$\hat{\mathcal{H}}$. נבחן את הפירוק הספקטרלי שלו:

$$\hat{\mathcal{H}} = \sum_{k=0}^{N-1} \lambda_k |\phi_k\rangle \langle \phi_k|$$

כאשר $N$ הוא מימד מרחב המצבים, $\lambda_{k}$ הוא הערך העצמי ה-$k$-י, או פיזיקלית, רמת האנרגיה ה-$k$-ית, ו-$|\phi_k\rangle$ הוא המצב עצמי המתאים: $\hat{\mathcal{H}}|\phi_k\rangle = \lambda_k |\phi_k\rangle$, תוחלת האנרגיה של מערכת במצב (המנורמל) $|\psi\rangle$ תהיה:

$$\begin{aligned} \langle \psi | \hat{\mathcal{H}} | \psi \rangle & = \langle \psi |\bigg(\sum_{k=0}^{N-1} \lambda_k |\phi_k\rangle \langle \phi_k|\bigg) | \psi \rangle \\[1mm] & = \sum_{k=0}^{N-1} \lambda_k \langle \psi |\phi_k\rangle \langle \phi_k| \psi \rangle \\[1mm] & = \sum_{k=0}^{N-1} \lambda_k |\langle \psi |\phi_k\rangle|^2 \\[1mm] \end{aligned}$$

אם ניקח בחשבון ש-$\lambda_0\leq \lambda_k, \forall k$, נקבל:

$$\begin{aligned} \langle \psi | \hat{\mathcal{H}} | \psi \rangle & = \sum_{k=0}^{N-1} \lambda_k |\langle \psi |\phi_k\rangle|^2 \\[1mm] & \geq \sum_{k=0}^{N-1} \lambda_0 |\langle \psi |\phi_k\rangle|^2 \\[1mm] & = \lambda_0 \sum_{k=0}^{N-1} |\langle \psi |\phi_k\rangle|^2 \\[1mm] & = \lambda_0 \\[1mm] \end{aligned}$$

מכיוון ש-$\{|\phi_k\rangle \}_{k=0}^{N-1}$ הוא בסיס אורתונורמלי, ההסתברות למדידת $|\phi_{k} \rangle$ היא $p_k = |\langle \psi |\phi_{k} \rangle |^2$, וסכום כל ההסתברויות הוא $\sum_{k=0}^{N-1} |\langle \psi |\phi_k\rangle|^2 = \sum_{k=0}^{N-1}p_k = 1$. בקצרה, תוחלת האנרגיה של כל מערכת גבוהה מאנרגיית היסוד הנמוכה ביותר:

$$\langle \psi | \hat{\mathcal{H}} | \psi \rangle \geq \lambda_0.$$

הטיעון לעיל חל על כל מצב קוונטי תקף (מנורמל) $|\psi\rangle$, ולכן ניתן לשקול מצבים פרמטריים $|\psi(\vec\theta)\rangle$ התלויים בווקטור פרמטרים $\vec\theta$. כאן נכנס החלק ה"וריאציוני". אם נשקול פונקציית עלות הנתונה על ידי $C(\vec\theta) := \langle \psi(\vec\theta)|\hat{\mathcal{H}}|\psi(\vec\theta)\rangle$ ונרצה למזערה, המינימום יקיים תמיד:

$$\min_{\vec\theta} C(\vec\theta) = \min_{\vec\theta} \langle \psi(\vec\theta)|\hat{\mathcal{H}}|\psi(\vec\theta)\rangle \geq \lambda_0.$$

ערך המינימום של $C(\vec\theta)$ יהיה הקרוב ביותר שניתן להגיע ל-$\lambda_0$ באמצעות המצבים הפרמטריים $|\psi(\vec\theta)\rangle$, ושוויון יושג רק אם קיים ווקטור פרמטרים $\vec\theta^*$ כך ש-$|\psi(\vec\theta^*)\rangle = |\phi_0\rangle$.

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

אם המצב (המנורמל) $|\psi\rangle$ של מערכת קוונטית תלוי בווקטור פרמטרים $\vec\theta$, אז הקירוב האופטימלי של מצב היסוד (כלומר, המצב העצמי $|\phi_0\rangle$ עם הערך העצמי המינימלי $\lambda_0$) הוא זה הממזער את ערך הציפייה של ההמילטוניאן $\hat{\mathcal{H}}$:

$$\langle \hat{\mathcal{H}} \rangle(\vec\theta) := \langle \psi(\vec\theta) |\hat{\mathcal{H}}| \psi(\vec\theta) \rangle \geq \lambda_0$$

הסיבה שהמשפט הוריאציוני מנוסח במונחים של מינימום אנרגיה היא שהוא כולל מספר הנחות מתמטיות:

• מטעמים פיזיקליים, חייב להתקיים חסם תחתון סופי לאנרגיה $E \geq \lambda_0 > -\infty$, אפילו עבור $N\rightarrow\infty$.

• חסמים עליונים בדרך כלל אינם קיימים.

אולם, מבחינה מתמטית, אין שום דבר מיוחד בהמילטוניאן $\hat{\mathcal{H}}$ מעבר להנחות אלה, ולכן ניתן להכליל את המשפט לנצפים קוונטיים אחרים ולמצבים העצמיים שלהם, בתנאי שהם עומדים באותם אילוצים. כמו כן, שימו לב שאם קיימים חסמים עליונים סופיים, ניתן לבצע את אותם טיעונים מתמטיים למקסום ערכים עצמיים על ידי החלפת חסמים תחתונים בחסמים עליונים.

סיכום

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