QAOA בקנה מידה שימושי

צפה בסרטון על QAOA בקנה מידה שימושי מאת Olivia Lanes, או פתח את הסרטון בחלון נפרד ב-YouTube.

סקירת השיעור:

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

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

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

הבעיה

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

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

1. סימולציה של הטבע
2. עיבוד נתונים עם מבנה מורכב
3. אופטימיזציה

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

בעיית האופטימיזציה שמעניינת אותנו היום נקראת Max-Cut, שאנחנו הולכים לפתור באמצעות אלגוריתם הנקרא Quantum Approximate Optimization Algorithm (QAOA).

מהי Max-Cut?

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

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

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

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

הפתרון

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

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

נשתמש במסגרת Qiskit patterns כדי למצוא את פתרונות Max-Cut לגרף הזה על המחשב הקוונטי שלנו.

מיפוי

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

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

כאשר $i$ ו-$j$ הם צמתים בגרף, ו-$x_i$ ו-$x_j$ הם 0 או 1, בהתאם לאיזה צד של החלוקה נמצא כל צומת (קבוצה אחת מסומנת "0" ואחת מסומנת "1"). כאשר $x_i$ ו-$x_j$ נמצאים באותו צד של החלוקה, הביטוי בסכום שווה לאפס. כאשר הם נמצאים בצדדים הנגדיים, כך שיש חיתוך ביניהם, הביטוי שווה לאחד. לכן, מיקסום מספר החיתוכים ימקסם את הסכום.

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

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

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

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

QUBO

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

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

כאשר $Q$ הוא מטריצה $n\times n$ של מספרים ממשיים, $n$ מתאים למספר הצמתים בגרף שלנו, כאן חמישה.

כדי להחיל QAOA, אנחנו צריכים לנסח את הבעיה שלנו כהמילטוניאן — שהוא פונקציה או מטריצה שמייצגת את האנרגיה הכוללת של מערכת. ספציפית, אנחנו רוצים ליצור המילטוניאן של פונקציית עלות שיש לו את התכונה שמצב הבסיס מתאים לערך המינימלי של הפונקציה. לכן, כדי לפתור את בעיית האופטימיזציה שלנו, ננסה להכין את מצב הבסיס של $H$ על מחשב קוונטי. אז, דגימה מהמצב הזה תניב את הפתרון ל-$\min 𝑓(𝑥)$ עם הסתברות גבוהה.

מיפוי להמילטוניאן של פונקציית עלות

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

כדי לכתוב את בעיית QUBO כהמילטוניאן של Ising, כל מה שעלינו לעשות הוא שינוי פשוט של משתנים:

$$x_i = \frac{1-z_i}{2}.$$

לא נעבור על כל השלבים כאן, אבל הם מוסברים ב-notebook המצורף. בסוף, המינימיזציה של ביטוי QUBO זהה למינימיזציה של הביטוי הזה:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

ניסוח מחדש שוב מעט ויש לנו את המילטוניאן של פונקציית העלות, כאשר המינימום של הביטוי מייצג את מצב הבסיס, Z הוא אופרטור Pauli Z, ו-$b$ הוא מקדם סקלרי ממשי:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

עכשיו שיש לנו את המילטוניאן שלנו, אנחנו צריכים לכתוב אותו מחדש במונחים של אופרטורי Pauli ZZ דו-מקומיים, שאנחנו יכולים להמיר בקלות לשערים דו-Qubit ב-Circuit הקוונטי שלנו. נגמור עם שישה אובייקטים — או מחרוזות Pauli — כאשר כל אחת מתאימה לכל אחת מהשש קשתות בגרף. כל אחד מחמשת האלמנטים במחרוזת מייצג פעולה על צומת — הזהות אם הצומת אינו מחובר לאותה קשת, ואופרטור Pauli Z אם הוא כן. ב-Qiskit, מחרוזות ביטים המייצגות Qubits מאונדקסות בסדר הפוך. לדוגמה, קשת בין צמתים 0 ו-1 מקודדת כ-IIIZZ, וקשת בין 2 ו-4 מקודדת כ-ZIZII.

בניית ה-Circuit הקוונטי

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

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

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

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

לכן, שלושת החלקים העיקריים של ה-QAOA Circuit הם:

1. מצב הניסוי ההתחלתי, באפור, שהוא מצב הבסיס של המערבב, שנוצר על ידי החלת Gate של Hadamard על כל Qubit
2. התפתחות פונקציית העלות, עליה דיברנו בעבר, בסגול כהה
3. ההתפתחות תחת המילטוניאן המערבב, שעדיין לא סקרנו, בסגול בהיר.

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

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

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

אופטימיזציה

בעוד ש-Circuit שיצרנו נראה פשוט למדי ושימושי לבניית הבנה אינטואיטיבית, זכור, שבב הקוונטום לא מבין מה Gate של QAOA הוא. אנחנו צריכים להפוך את זה לסדרה של Gates "מקוריים" של Qubit יחיד ושניים שניתן לבצע ישירות על החומרה. Gates מקוריים הם אלה שניתן לבצע ישירות על ה-Qubits. אמרים ש-Circuits כאלה כתובים בארכיטקטורת מערכת ההוראות (ISA) של ה-Backend.

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

זכור משיעורנו הקודם שתהליך ה-transpilation כולל מספר שלבים:

• מיפוי ראשוני של ה-Qubits ב-Circuit (כלומר, משתני ההחלטה) ל-Qubits פיזיים על המכשיר.
• פתיחת ההוראות ב-Circuit הקוונטי להוראות המקוריות של החומרה שה-Backend מבין.
• ניתוב של כל Qubits ב-Circuit שמקיימים אינטראקציה ל-Qubits פיזיים שסמוכים זה לזה.

וכתמיד, פרטים נוספים על כך ניתן למצוא בתיעוד.

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

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

ועם זאת, יש לנו Circuit מתורגם שמוכן לביצוע על חומרה!

הרצה

עד כה, תרגמנו את ה-Circuit ושמרנו את הפרמטרים gamma ו-beta בצד — אבל אנחנו לא יכולים להריץ את ה-Circuit בלי לציין פרמטרים אלה. בתהליך העבודה של QAOA, הפרמטרים האופטימליים של QAOA נמצאים בלולאת אופטימיזציה איטרטיבית, שבה אנחנו מריצים סדרה של הערכות Circuit ואז משתמשים במאפטם קלאסי כדי למצוא את הפרמטרים האופטימליים 𝛽 ו-𝛾. אלא שאנחנו צריכים להתחיל איפשהו, אז אנחנו עושים ניחוש ראשוני של $\gamma=\pi/2$ ו-$\beta=\pi$.

מצבי הרצה

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

• מצב Job: בקשה בודדת של ה-Estimator או ה-Sampler נשלחת ללא context manager. Circuits וקלטים ארוזים כ-primitive unified blocs (PUBs) ומוגשים כמשימת הרצה על המחשב הקוונטי.

• מצב Batch: מנהל רב-עבודות להרצה יעילה של ניסוי המורכב מחבילה של עבודות עצמאיות. השתמש במצב Batch כדי להגיש מספר עבודות primitive בו-זמנית.

• מצב Session: חלון ייעודי להרצת עומס עבודה רב-עבודות. זה מאפשר למשתמשים להתנסות עם אלגוריתמים וריאציוניים בדרך צפויה יותר, ואפילו להריץ מספר ניסויים בו-זמנית, תוך ניצול מקביליות ב-stack. השתמש ב-Sessions לעומסי עבודה איטרטיביים או ניסויים שדורשים גישה ייעודית. ראה הרצת עבודות ב-Session לדוגמאות.

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

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

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

עכשיו שהצלחנו להפחית את פונקציית העלות שלנו על ידי מציאת ערכים טובים יותר לפרמטרים שלנו, נריץ את ה-Circuit שלנו באמצעות הערכים החדשים שמצאנו עבור gamma ו-beta. ציינתי את הערכים הספציפיים שאני משתמש בהם כאן, אבל זכור, כשתנסה את ידך בזה או אפילו רק תריץ מחדש את אותו tutorial notebook, הערכים האלה עלולים להשתנות מעט. עכשיו נריץ את ה-Circuit האופטימלי שלנו עם הערכים האלה ונמצא את פתרון המועמד שלנו לבעיית ה-Max-Cut.

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

לאחר עיבוד

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

מחרוזות הביטים מייצגות כיצד כל אחד מהצמתים חולק לשתי קבוצות (מסומנות "0" ו-"1") על ידי החיתוך. אמורים להיות ארבעה פתרונות שכולם נותנים את הערך המקסימלי של קשתות שנחתכו. ארבעת אלה מוצגים בסגול. אפשר לראות מיד ש-4 פתרונות הרבה יותר סבירים מכל האחרים. מחרוזת הביטים הגבוהה ביותר, ולכן הסבירה ביותר, היא 0,1,0,1,1. (זכור — סדר ה-Qubits הפוך במחרוזות הביט של גרף!)

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

אז, זה אכן פתרון Max-Cut. אבל זה לא הפתרון היחיד! בגלל הסימטריה של גרף זה, יש מספר פתרונות נכונים. במקום שהצמתים 0 ו-3 יהיו בתוך החיתוך, יכולנו לכלול את הצמתים 2 ו-4. אפשר לראות שכל מה שהיה עלי לעשות הוא לסובב את החיתוך שלי כדי לכלול את הנקודות החדשות האלה. מספר הקשתות הנחתכות נשאר חמש. מסתבר שיש ארבעה פתרונות max cut, מכיוון שלכל אחד משני הפתרונות שציינו יש גם "שותף הפוך", שבו הצמתים הסגולים הם אפורים והצמתים האפורים הם סגולים — כך שהחיתוך נשאר זהה, אבל כל צומת עובר למעשה לצד ההפוך של החלוקה.

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

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

השגיאה הזו יכולה לנבוע ממספר מקומות:

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

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

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

בקנה מידה שימושי

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