האלגוריתם של גרובר

למודול Qiskit in Classrooms הזה, הסטודנטים חייבים שיהיה להם סביבת Python עובדת עם החבילות הבאות מותקנות:

• qiskit v2.1.0 או חדש יותר
• qiskit-ibm-runtime v0.40.1 או חדש יותר
• qiskit-aer v0.17.0 או חדש יותר
• qiskit.visualization
• numpy
• pylatexenc

להגדרה והתקנת החבילות שלמעלה, ראו את המדריך התקנת Qiskit. כדי להריץ עבודות על מחשבים קוונטיים אמיתיים, הסטודנטים יצטרכו להגדיר חשבון ב-IBM Quantum® על ידי ביצוע הצעדים במדריך הגדרת חשבון IBM Cloud שלך.

המודול הזה נבדק והשתמש ב-12 שניות של זמן QPU. זוהי הערכה בתום לב; השימוש בפועל שלך עשוי להשתנות.

# Added by doQumentation — required packages for this notebook
!pip install -q qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

מבוא

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

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

האלגוריתם פועל בהקשר הבא:

• הגדרת הבעיה: יש לך פונקציה $f(x)$ שמחזירה 1 אם $x$ הוא הפריט שאתה רוצה, ו-0 אחרת. פונקציה זו נקראת לעיתים קרובות אורקל או קופסה שחורה, שכן ניתן ללמוד על הנתונים רק על ידי שאילתת $f(x)$.
• תועלת הקוונטי: בעוד שאלגוריתמים קלאסיים לבעיה זו דורשים, בממוצע, $N/2$ שאילתות, האלגוריתם של גרובר יכול למצוא את הפתרון בערך ב-$\pi\sqrt{N}/4$ שאילתות, שזה הרבה יותר מהיר עבור $N$ גדול.
• איך זה עובד (ברמה גבוהה):
  • המחשב הקוונטי קודם יוצר סופרפוזיציה של כל המצבים האפשריים, המייצגת את כל הפריטים האפשריים בו-זמנית.
  • לאחר מכן הוא מפעיל שוב ושוב רצף של פעולות קוונטיות (איטרציית גרובר) שמגבירה את ההסתברות לתשובה הנכונה ומדכאת את האחרות.
  • לאחר מספיק איטרציות, מדידת המצב הקוונטי מניבה את התשובה הנכונה בהסתברות גבוהה.

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

כמה דברים שכדאי לשים לב אליהם לגבי האלגוריתם של גרובר:

• הוא אופטימלי לחיפוש לא מובנה: אף אלגוריתם קוונטי לא יכול לפתור את הבעיה עם פחות מ-$O(\sqrt{N})$ שאילתות.
• הוא מספק רק האצה ריבועית, לא מעריכית — בניגוד לאלגוריתמים קוונטיים אחרים (למשל, האלגוריתם של שור לפירוק גורמים).
• יש לו השלכות מעשיות, כמו האצה פוטנציאלית של התקפות כוח גס על מערכות קריפטוגרפיות, אם כי ההאצה אינה מספיקה כדי לשבור את רוב ההצפנות המודרניות בעצמה.

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

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

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

תיאוריה

נניח שקיימת פונקציה $f$ שממפה מחרוזות בינאריות למשתנה בינארי יחיד, כלומר

$$f: \Sigma^n \rightarrow \Sigma$$

דוגמה אחת המוגדרת על $\Sigma^6$ היא

$$f(x)= \begin{cases} 1 \qquad \text{if }x=\{010101\}\\ 0 \qquad \text{otherwise } \end{cases}$$

דוגמה נוספת המוגדרת על $\Sigma^{2n}$ היא

$$f(x)= \begin{cases} 1 \qquad \text{if equal numbers of 1's and 0's in string}\\ 0 \qquad \text{otherwise } \end{cases}$$

אתם מתבקשים למצוא מצבים קוונטיים המתאימים לאותם ארגומנטים $x$ של $f(x)$ שממופים ל-1. במילים אחרות, מצאו את כל $\{x_1\}\in \Sigma^n$ כך ש-$f(x_1)=1$ (או אם אין פתרון, דווחו על כך). נתייחס לאי-פתרונות כ-$x_0$. כמובן, נעשה זאת על מחשב קוונטי, תוך שימוש במצבים קוונטיים, ולכן כדאי לבטא את המחרוזות הבינאריות הללו כמצבים:

$$\{|x_1\rangle\} \in |\Sigma^n\rangle$$

בשימוש בסימון המצב הקוונטי (Dirac), אנחנו מחפשים מצב מיוחד אחד או יותר $\{|x_1\rangle\}$ בתוך קבוצה של $N=2^n$ מצבים אפשריים, כאשר $n$ הוא מספר ה-Qubit, ועם אי-פתרונות המסומנים $\{|x_0\rangle\}.$

ניתן לחשוב על הפונקציה $f$ כמסופקת על ידי אורקל: קופסה שחורה שאנחנו יכולים לשאול אותה כדי לקבוע את השפעתה על מצב $|x\rangle.$ בפועל, לעיתים קרובות נדע את הפונקציה, אך היא עשויה להיות מסובכת מאוד ליישום, כלומר שהפחתת מספר השאילתות או היישומים של $f$ עשויה להיות חשובה. לחלופין, ניתן לדמיין פרדיגמה שבה אדם אחד שואל אורקל הנשלט על ידי אדם אחר, כך שאנחנו לא יודעים את פונקציית האורקל, אנחנו רק יודעים את פעולתה על מצבים מסוימים מהשאילתה.

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

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

סקיצה של מעגלים באלגוריתם של גרובר

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

ניתן לחלק את האלגוריתם של גרובר לשלבים הבאים:

• הכנת סופרפוזיציה ראשונית (הפעלת Hadamard Gates על כל ה-Qubit)
• "סימון" המצב/מצבי המטרה עם היפוך פאזה
• שלב "דיפוזיה" שבו מוחלים Hadamard Gates והיפוך פאזה על כל ה-Qubit.
• חזרות אפשריות של שלבי הסימון והדיפוזיה כדי למקסם את ההסתברות למדידת מצב המטרה
• מדידה

לעיתים קרובות, שער הסימון $Z_f$ ושכבות הדיפוזיה המורכבות מ-$H,$ $Z_{\text{OR}},$ ו-$H$ מכונים ביחד "אופרטור גרובר". בדיאגרמה זו, מוצגת רק חזרה אחת של אופרטור גרובר.

Hadamard Gates $H$ ידועים היטב ומשמשים רבות בכל מחשוב קוונטי. ה-Hadamard Gate יוצר מצבי סופרפוזיציה. ספציפית, הוא מוגדר על ידי

$$H|0\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)\\ H|1\rangle = \frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)$$

פעולתו על כל מצב אחר מוגדרת דרך לינאריות. בפרט, שכבת Hadamard Gates מאפשרת לנו לעבור מהמצב הראשוני עם כל ה-Qubit ב-$|0\rangle$ (מסומן $|0\rangle^{\otimes n}$) למצב שבו לכל qubit יש הסתברות מסוימת להימדד ב-$|0\rangle$ או ב-$|1\rangle$; זה מאפשר לנו לבחון את מרחב כל המצבים האפשריים בצורה שונה ממחשוב קלאסי.

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

$$H\frac{1}{\sqrt{2}}\left(|0\rangle+|1\rangle\right)=|0\rangle\\ H\frac{1}{\sqrt{2}}\left(|0\rangle-|1\rangle\right)=|1\rangle$$

זה יהיה חשוב ממש בעוד רגע.

בדקו את ההבנה שלכם

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

תשובה

כאשר אנחנו מפעילים X על המצב $|+\rangle$, אנחנו מקבלים את הערך +1 ועל המצב $|-\rangle$ אנחנו מקבלים -1, ולכן אם היה לנו התפלגות 50-50, היינו מקבלים ערך ציפייה של 0.

ה-$Z_\text{OR}$ Gate פחות נפוץ, ומוגדר לפי

$$\text{Z}_\text{OR}|x\rangle = \begin{cases} |x\rangle & \text{if } x = 0^n \\ -|x\rangle & \text{if } x \neq 0^n \end{cases} \qquad \forall x \in \Sigma^n$$

לבסוף, ה-$Z_f$ Gate מוגדר על ידי

$$Z_f:|x\rangle \rightarrow (-1)^{f(x)}|x\rangle \qquad \forall x \in \Sigma^n$$

שימו לב שהשפעת זה היא ש-$Z_f$ הופך את הסימן על מצב מטרה שעבורו $f(x) = 1$ ומשאיר מצבים אחרים ללא שינוי.

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

• שכבת Hadamard הראשונה: שמה את ה-Qubit בסופרפוזיציה של כל המצבים האפשריים.
• $Z_f$: מסמן את המצב/מצבי המטרה על ידי הוספת סימן "-" לפניהם. זה לא משנה מיד את הסתברויות המדידה, אך משנה איך מצב המטרה יתנהג בצעדים הבאים.
• שכבת Hadamard נוספת: סימן "-" שהוצג בצעד הקודם ישנה את הסימן היחסי בין כמה מונחים. מכיוון ש-Hadamard Gates הופכים תערובת אחת של מצבים חישוביים $(|0\rangle+|1\rangle)/\sqrt{2}$ למצב חישובי אחד, $|0\rangle,$ ומהפכים $(|0\rangle-|1\rangle)/\sqrt{2}$ ל-$|1\rangle$ הבדל הסימן היחסי הזה יכול להתחיל לשחק תפקיד במה שנמדד.
• שכבה אחרונה של Hadamard Gates מופעלת, ולאחר מכן נעשות מדידות. נראה בפירוט גדול יותר איך זה עובד בחלק הבא.

דוגמה

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

הנה דיאגרמת המעגל עם המצבים הקוונטיים המסומנים בנקודות שונות לאורך הדרך. שימו לב שעם רק שני qubit, יש רק ארבעה מצבים אפשריים שיכולים להימדד בכל נסיבות: $|00\rangle$, $|01\rangle$, $|10\rangle$, ו-$|11\rangle$.

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

$$|\psi_0\rangle = |00\rangle$$

בשימוש בהגדרת Hadamard Gates, יש לנו

$$|\psi_1\rangle = \frac{1}{2}\left(|0\rangle+|1\rangle\right)\left(|0\rangle+|1\rangle\right)=\frac{1}{2}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)$$

עכשיו האורקל מסמן את מצב המטרה:

$$|\psi_2\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle+|11\rangle\right)$$

שימו לב שבמצב הזה, לכל ארבעת התוצאות האפשריות יש אותה הסתברות להימדד. לכולם יש משקל של גודל $1/2,$ כלומר לכל אחת יש סיכוי של $|1/2|^2=1/4$ להימדד. לכן, בעוד שהמצב $|01\rangle$ מסומן דרך הפאזה "-", זה עדיין לא הביא לעלייה כלשהי בהסתברות למדידת אותו מצב. ממשיכים על ידי הפעלת שכבת Hadamard Gates הבאה.

$$\begin{aligned} |\psi_3\rangle = &\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

כשמשלבים מונחים דומים, אנחנו מוצאים

$$|\psi_3\rangle = \frac{1}{2}\left(|00\rangle+|01\rangle-|10\rangle+|11\rangle\right)$$

עכשיו $Z_{\text{OR}}$ הופך את הסימן על כל המצבים חוץ מ-$|00\rangle$:

$$|\psi_4\rangle = \frac{1}{2}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)$$

ולבסוף, אנחנו מפעילים את שכבת Hadamard Gates האחרונה:

$$\begin{aligned} |\psi_5\rangle =&\frac{1}{4}\left(|00\rangle+|01\rangle+|10\rangle+|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle+|10\rangle-|11\rangle\right)\\ +&\frac{1}{4}\left(|00\rangle+|01\rangle-|10\rangle-|11\rangle\right)\\ -&\frac{1}{4}\left(|00\rangle-|01\rangle-|10\rangle+|11\rangle\right) \end{aligned}$$

כדאי לעבור דרך איחוד המונחים האלה כדי לשכנע את עצמכם שהתוצאה היא אכן:

$$|\psi_5\rangle =|01\rangle$$

כלומר, ההסתברות למדידת $|01\rangle$ היא 100% (בהיעדר רעש ושגיאות) וההסתברות למדידת כל מצב אחר היא אפס.

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

בחלק הבא, נשים את האלגוריתם הזה לפועל תוך שימוש במחשבים קוונטיים אמיתיים של IBM®.

התמונה הגיאומטרית

הדוגמה של שני qubit לעיל הראתה כיצד האלגברה עובדת עבור מקרה קטן, אך יש דרך הרבה יותר אינטואיטיבית להבין את האלגוריתם של גרובר: כרצף של השתקפויות גיאומטריות במישור דו-ממדי. להלן נתאר תמונה זו. ניתן גם לראות את הקורס של ג'ון ווטרוס Fundamentals of Quantum Algorithms לפרטים נוספים.

הגדרת המישור. ניתן לפרק את מצב הסופרפוזיציה הראשוני $|\psi\rangle$ לשני רכיבים. המצב הנכון — זה שאנחנו מחפשים — נקרא לו $|A_1\rangle$. כל מצב אחר, מאוחד יחד, נקרא לו $|A_0\rangle$. בהגדרה, $|A_1\rangle$ ו-$|A_0\rangle$ אורתוגונליים זה לזה, ולכן ניתן לשרטט אותם כצירים ניצבים במרחב מופשט דו-ממדי. מכיוון ש-$|\psi\rangle$ הוא צירוף לינארי של שני הרכיבים הללו, הוא נמצא בזווית קטנה $\theta$ לציר $|A_0\rangle$ — קרוב ל-$|A_0\rangle$, מפני שבתחילה, רק חלק קטן מאוד מהמצב נמצא ברכיב הנכון $|A_1\rangle$.

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

$$2|v\rangle\langle v| - I$$

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

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

האורקל כהשתקפות. האורקל הופך את הסימן של מצב $|A_1\rangle$ ומשאיר את כל השאר ללא שינוי. זהה להשתקפות סביב ציר $|A_0\rangle$.

דיפוזיה כהשתקפות. קצת יותר קשה לראות כיצד אופרטור הדיפוזיה הוא גם השתקפות. אופרטור הדיפוזיה הוא

$$H^{\otimes n}\, Z_{\text{OR}}\, H^{\otimes n}$$

$Z_{\text{OR}}$ כשלעצמו הוא השתקפות סביב מצב האפסים, מפני שהוא הופך את הסימן של כל מצב שאינו $|0\rangle^{\otimes n}$. ניתן לכתוב זאת כ-$2|0\rangle\langle 0| - I$. שכבות ה-Hadamard הסובבות מבצעות למעשה שינוי בסיס, ומשנות את ציר ההשתקפות. נזכור ש-$H^{\otimes n}$ ממפה את $|0\rangle^{\otimes n}$ לסופרפוזיציה האחידה $|u\rangle = \frac{1}{\sqrt{N}}\sum_{x}|x\rangle$. מכיוון ש-Hadamard הוא ההופכי של עצמו, הביטוי המלא הופך ל

$$H^{\otimes n}\left(2|0\rangle\langle 0| - I\right)H^{\otimes n} = 2|u\rangle\langle u| - I$$

שהיא השתקפות סביב $|u\rangle$. מכיוון ש-$|u\rangle$ קרוב מאוד ל-$|\psi\rangle$ (שניהם כמעט לאורך $|A_0\rangle$), ההשתקפות השנייה שולחת את המצב לזווית $2\theta$ ממקומו ההתחלתי.

סיבוב ב-$2\theta$. ההשפעה המשולבת של שתי ההשתקפויות הללו היא סיבוב ב-$2\theta$ לעבר $|A_1\rangle$. כל איטרציה עוקבת של אופרטור גרובר מסובבת את המצב ב-$2\theta$ נוסף.

מספר האיטרציות האופטימלי. המטרה שלנו היא לסובב את המצב כמה שיותר קרוב ל-$|A_1\rangle$, כלומר לסובב בסך הכל בערך $\pi/2$ רדיאנים (רבע סיבוב). אם כל איטרציה תורמת $2\theta$, מספר האיטרציות האופטימלי $t$ מקיים

$$(2t + 1)\theta \approx \frac{\pi}{2}$$

עבור פתרון יחיד בין $N$ מצבים, הזווית הראשונית היא $\theta \approx \sin^{-1}(1/\sqrt{N}) \approx 1/\sqrt{N}$ (עבור $N$ גדול). בהצבה,

$$t \approx \frac{\pi}{4}\sqrt{N} - \frac{1}{2}$$

כאן טמון ההאצה המפורסמת של $\sqrt{N}$: אנחנו צריכים רק $O(\sqrt{N})$ איטרציות כדי להגיע למטרה, במקום $O(N)$ בדיקות שחיפוש קלאסי היה דורש.

באופן כללי יותר, אם יש $|A_1|$ מצבי פתרון מבין $N$ מצבים כולם, מספר האיטרציות האופטימלי הוא

$$t \approx \frac{\pi}{4}\sqrt{\frac{N}{|A_1|}} - \frac{1}{2}$$

שימו לב שאם מחילים יותר מדי איטרציות, מסתובבים מעבר ל-$|A_1\rangle$ וההסתברות למצוא את מצב המטרה תתחיל לרדת שוב. מציאת המספר הנכון של איטרציות חשובה, אם כי על חומרת קוונטים רועשת מספר האיטרציות האופטימלי ניסיונית עשוי להיות שונה מהנוסחה האידיאלית הזו.

למה האלגוריתם של גרובר שימושי?

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

זוהי שאלה הוגנת, ויש לה מספר תשובות טובות.

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

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

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

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

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

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

ייבוא כללי וגישה

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

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import grover_operator, MCMTGate, ZGate
from qiskit.visualization import plot_distribution
from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager

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

• צעד 1: מיפוי קלטים קלאסיים לבעיה קוונטית
• צעד 2: אופטימיזציה של הבעיה לביצוע קוונטי
• צעד 3: ביצוע תוך שימוש ב-Qiskit Runtime Primitives
• צעד 4: עיבוד לאחר המדידה וניתוח קלאסי

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

פעילות 1: מצא מצב מטרה יחיד נתון

צעד 1: מיפוי קלטים קלאסיים לבעיה קוונטית

אנחנו צריכים את שער שאילתת הפאזה כדי לשים פאזה כוללת (-1) על מצבי פתרון, ולהשאיר את המצבים שאינם פתרונות ללא שינוי. דרך נוספת לומר זאת היא שהאלגוריתם של גרובר דורש אורקל שמציין מצב בסיס חישובי אחד או יותר מסומן, כאשר "מסומן" פירושו מצב עם פאזה של -1. זה נעשה באמצעות controlled-Z gate, או הכללתו המרובת-שליטה על $N$ qubit. כדי לראות איך זה עובד, שקלו דוגמה ספציפית של מחרוזת ביטים {110}. נרצה מעגל שפועל על מצב $|\psi\rangle = |q_2,q_1,q_0\rangle$ ומחיל פאזה אם $|\psi\rangle = |011\rangle$ (כאשר הפכנו את סדר המחרוזת הבינארית, בגלל הסימון ב-Qiskit, שמשים את ה-Qubit הפחות משמעותי (לרוב 0) בצד ימין).

לפיכך, אנחנו רוצים מעגל $Z_f$ שמבצע

$$Z_f|\psi\rangle = \begin{cases} -|\psi\rangle \qquad \text{if} \qquad |\psi\rangle = |011\rangle \\ |\psi\rangle \qquad \text{if} \qquad |\psi\rangle \neq |011\rangle\end{cases}$$

ניתן להשתמש בשער multiple control multiple target (MCMTGate) כדי להחיל Z gate הנשלט על ידי כל ה-Qubit (להפוך את הפאזה אם כל ה-Qubit במצב $|1\rangle$). כמובן, חלק מה-Qubit במצב הרצוי שלנו עשויים להיות $|0\rangle$. לכן, עבור אותם qubit עלינו קודם להחיל X gate, ואז לעשות את Z gate המרובת-שליטה, ואז להחיל X gate נוסף כדי לבטל את השינוי שלנו. ה-MCMTGate נראה כך:

mcmt_ex = QuantumCircuit(3)
mcmt_ex.compose(MCMTGate(ZGate(), 3 - 1, 1), inplace=True)
mcmt_ex.draw(output="mpl", style="iqp")

שימו לב שייתכן שמעורבים qubit רבים בתהליך השליטה (כאן שלושה qubit מעורבים), אך אף qubit יחיד אינו מסומן כמטרה. זאת מכיוון שהמצב כולו מקבל סימן "-" כולל (היפוך פאזה); השער משפיע על כל ה-Qubit באופן שווה. זה שונה משערים רבים אחרים של qubit מרובים, כמו שער CX, שיש לו qubit שליטה יחיד ו-Qubit מטרה יחיד.

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

def grover_oracle(marked_states):
    """Build a Grover oracle for multiple marked states

    Here we assume all input marked states have the same number of bits

    Parameters:
        marked_states (str or list): Marked states of oracle

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle
    """
    if not isinstance(marked_states, list):
        marked_states = [marked_states]
    # Compute the number of qubits in circuit
    num_qubits = len(marked_states[0])

    qc = QuantumCircuit(num_qubits)
    # Mark each target state in the input list
    for target in marked_states:
        # Flip target bitstring to match Qiskit bit-ordering
        rev_target = target[::-1]
        # Find the indices of all the '0' elements in bitstring
        zero_inds = [
            ind for ind in range(num_qubits) if rev_target.startswith("0", ind)
        ]
        # Add a multi-controlled Z-gate with pre- and post-applied X-gates (open-controls)
        # where the target bitstring has a '0' entry
        qc.x(zero_inds)
        qc.compose(MCMTGate(ZGate(), num_qubits - 1, 1), inplace=True)
        qc.x(zero_inds)
    return qc

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

marked_states = ["1110"]
oracle = grover_oracle(marked_states)
oracle.draw(output="mpl", style="iqp")

אם qubit 1-3 במצב $|1\rangle$, ו-Qubit 0 נמצא במקור במצב $|0\rangle$, ה-X Gate הראשון יהפוך את qubit 0 ל-$|1\rangle$ וכל ה-Qubit יהיו ב-$|1\rangle.$ פירוש הדבר שה-MCMT Gate יחיל שינוי סימן כולל או היפוך פאזה, כרצוי. לכל מקרה אחר, או שה-Qubit 1-3 במצב $|0\rangle$, או ש-Qubit 0 הופך למצב $|0\rangle$, והיפוך הפאזה לא יוחל. אנחנו רואים שהמעגל הזה אכן מסמן את מצבנו הרצוי $|0111\rangle,$ או מחרוזת הביטים {1110}. אופרטור גרובר המלא מורכב משער שאילתת הפאזה (אורקל), שכבות Hadamard, ואופרטור $Z_\text{OR}$. ניתן להשתמש ב-grover_operator המובנה כדי לבנות זאת מהאורקל שהגדרנו לעיל.

grover_op = grover_operator(oracle)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

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

$$t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

כאשר $|A_1|$ הוא מספר מצבי הפתרון ו-$N=2^n$ הוא המספר הכולל של המצבים. על מחשבים קוונטיים רועשים מודרניים, מספר האיטרציות האופטימלי ניסיונית עשוי להיות שונה — אבל כאן אנחנו מחשבים ומשתמשים במספר התיאורטי האופטימלי הזה תוך שימוש ב-$|A_1|=1$.

optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(marked_states) / 2**grover_op.num_qubits)))
)
print(optimal_num_iterations)

3

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

qc = QuantumCircuit(grover_op.num_qubits)
# Create even superposition of all basis states
qc.h(range(grover_op.num_qubits))
# Apply Grover operator the optimal number of times
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
# Measure all qubits
qc.measure_all()
qc.draw(output="mpl", style="iqp")

בנינו את מעגל גרובר שלנו!

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

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

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

# To run on hardware, select the backend with the fewest number of jobs in the queue
from qiskit_ibm_runtime import QiskitRuntimeService

# Syntax for first saving your token.  Delete these lines after saving your credentials.

# QiskitRuntimeService.save_account(channel='ibm_quantum_platform',
# instance = '<YOUR_IBM_INSTANCE_CRN>', token='<YOUR_API_KEY>', overwrite=True, set_as_default=True)
# service = QiskitRuntimeService(channel='ibm_quantum_platform')

# Load saved credentials
service = QiskitRuntimeService()

backend = service.least_busy(operational=True, simulator=False)
backend.name

qiskit_runtime_service._resolve_cloud_instances:WARNING:2025-08-08 14:14:19,931: Default instance not set. Searching all available instances.

'ibm_brisbane'

עכשיו נשתמש במנהל pass מוגדר מראש כדי לאופטמז את ה-Circuit הקוונטי שלנו עבור ה-Backend שבחרנו.

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)

circuit_isa = pm.run(qc)
# The transpiled circuit will be very large. Only draw it if you are really curious.
# circuit_isa.draw(output="mpl", idle_wires=False, style="iqp")

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

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

The total depth is  439
The depth of two-qubit gates is  113

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

שלב 3: הרצה באמצעות פרימיטיבים של Qiskit

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

שים לב שמתודת run() של SamplerV2 של Qiskit Runtime מקבלת iterable של בלוקים אחודים פרימיטיביים (PUBs). עבור Sampler, כל PUB הוא iterable בפורמט (circuit, parameter_values). אולם, לכל הפחות, הוא מקבל רשימה של Circuit(s) קוונטיים.

# To run on a real quantum computer (this was tested on a Heron r2 processor and
# used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

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

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

שלב 4: עיבוד לאחר מעשה והחזרת התוצאה בפורמט קלאסי הרצוי

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

plot_distribution(dist)

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

בדוק את ההבנה שלך

חיפשנו פתרון יחיד בקבוצה של $2^4=16$ מצבים אפשריים. קבענו שמספר החזרות האופטימלי של אופרטור גרובר הוא $t=3$. האם מספר אופטימלי זה היה גדל או קטן אם חיפשנו (א) אחד ממספר פתרונות, או (ב) פתרון יחיד במרחב עם יותר מצבים אפשריים?

תשובה

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

$$(2t+1)\theta = (2t+1) \sin^{-1}{\sqrt{\frac{|\mathcal{A}_1|}{N}}}\approx (2t+1) \sqrt{\frac{|\mathcal{A}_1|}{N}} \approx \pi/2\\ t \approx \frac{\pi}{4}\sqrt{\frac{N}{|\mathcal{A}_1|}}-\frac{1}{2}$$

(א) מהביטוי לעיל אנחנו רואים שהגדלת מספר מצבי הפתרון תקטין את מספר האיטרציות. בהנחה שהשבר $\frac{|\mathcal{A}_1|}{N}$ עדיין קטן, אפשר לתאר איך $t$ יקטן: $t~\frac{1}{\sqrt{|\mathcal{A}_1|}}.$

(ב) ככל שמרחב הפתרונות האפשריים ($N$) גדל, מספר האיטרציות הדרושות גדל, אבל רק כמו $t~\sqrt{N}$.

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

תשובה

לא. נניח שחזרנו על הפעילות הראשונה עם 20 qubits, ואנחנו מריצים את ה-Circuit הקוונטי מספר פעמים num_shots = 10,000. התפלגות הסתברות אחידה תאמר שלכל מצב יש הסתברות של $10,000/2^{20}=0.00954$ למדוד אפילו פעם אחת. אם ההסתברות למדוד את מצב היעד הייתה פי 10 מאשר לא-פתרונות (והסתברות כל לא-פתרון הייתה פוחתת בהתאמה), הייתה רק כ-10% סיכוי למדוד את מצב היעד אפילו פעם אחת. מאוד לא סביר למדוד את מצב היעד מספר פעמים, מה שיהפוך אותו לבלתי ניתן להבחנה ממצבי הלא-פתרון הרבים שהתקבלו באקראי. החדשות הטובות הן שאפשר לקבל תוצאות עם פידליות גבוהה יותר על ידי שימוש בדיכוי ובהפחתת שגיאות.

פעילות 2: תהליך עבודה מדויק של אלגוריתם שאילתות

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

שלב 1: מיפוי קלטים קלאסיים לבעיה קוונטית

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

# Modify the marked states to mark those you wish to target.
marked_states = ["1000"]
oracle = grover_oracle(marked_states)

עכשיו יצרת Circuit קוונטי שהופך את הפאזה של מצב היעד שלך. אפשר לשמור את ה-Circuit הזה כ-my_circuit.qpy באמצעות התחביר מטה.

from qiskit import qpy

# Save to a QPY file at a location where you can easily find it.
# You might want to specify a global address.
with open("C:\\Users\\...put your own address here...\\my_circuit.qpy", "wb") as f:
    qpy.dump(oracle, f)

עכשיו שלח את הקובץ הזה לשותפך (דרך אימייל, שירות הודעות, repo משותף וכן הלאה). בקש מהשותף לשלוח לך גם את ה-Circuit שלו. הקפד לשמור את הקובץ במקום שקל לך למצוא. כשיש לך את ה-Circuit של שותפך, אפשר לצייר אותו — אבל זה שובר את מודל השאילתות. כלומר, אנחנו מדמים מצב שבו אפשר לבצע שאילתות ל-oracle (להשתמש ב-Circuit של ה-oracle) אבל לא לבדוק אותו כדי לקבוע לאיזה מצב הוא מכוון.

from qiskit import qpy

# Load the circuit from your partner's qpy file from the folder where you saved it.
with open("C:\\Users\\...file location here...\\my_circuit.qpy", "rb") as f:
    circuits = qpy.load(f)

# qpy.load always returns a list of circuits
oracle_partner = circuits[0]

# You could visualize the circuit, but this would break the model of a query algorithm.
# oracle_partner.draw("mpl")

שאל את שותפך כמה מצבי יעד הוא קידד והזן זאת מטה.

# Update according to your partner's number of target states.
num_marked_states = 1

זה משמש בביטוי הבא לקביעת מספר האיטרציות האופטימלי של גרובר.

grover_op = grover_operator(oracle_partner)
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(num_marked_states / 2**grover_op.num_qubits)))
)
qc = QuantumCircuit(grover_op.num_qubits)
qc.h(range(grover_op.num_qubits))
qc.compose(grover_op.power(optimal_num_iterations), inplace=True)
qc.measure_all()

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

זה ממשיך בדיוק כמו קודם.

# To run on hardware, select the backend with the fewest number of jobs in the queue
service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
backend.name

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_partner_isa = pm.run(qc)

שלב 3: הרצה באמצעות פרימיטיבים של Qiskit

זה גם זהה לתהליך בפעילות הראשונה.

# To run on a real quantum computer (this was tested on a Heron r2 processor and used
# 4 seconds of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_partner_isa]).result()
dist = result[0].data.meas.get_counts()

שלב 4: עיבוד לאחר מעשה והחזרת התוצאה בפורמט קלאסי הרצוי

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

plot_distribution(dist)

בדוק את ההבנה שלך

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

רמזים

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

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

רמזים

• נזכור שתפקיד ה-oracle הוא להפוך את הסימן על מצב היעד.
• נזכור שה-MCMTGate הופך את הסימן על מצב אם ורק אם כל ה-Qubits המעורבים בשליטה נמצאים במצב $|1\rangle$.
• אם מצב היעד שלך כבר יהיה עם $|1\rangle$ על qubit מסוים, אז לא צריך לעשות שום דבר ל-Qubit הזה. אם ליעד שלך יש $|0\rangle$ על qubit מסוים ואתה רוצה שה-MCMTGate יהפוך את הסימן, אתה צריך להחיל Gate X על אותו qubit ב-oracle שלך (ולאחר מכן לבטל את ה-X Gate אחרי ה-MCMTGate).

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

הנחיה

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

למה מישהו עשוי לרצות להשתמש בפחות איטרציות גרובר מה"מספר האופטימלי" שזוהה כאן?

תשובה

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

פעילות 3: פתרון רשת Minesweeper עם האלגוריתם של גרובר

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

הוכח ש-Minesweeper הוא NP-שלם: קשה לפתור אך קל לאמת. זה הופך אותו למועמד טבעי לאלגוריתם של גרובר. כמובן, עדיין לא ניתן לפתור רשת מלאה של $9\times9$ על מחשב קוונטי רועש — ה-Circuits יהיו עמוקים מדי. במקום זאת, נשתמש ברשת קטנה כהדגמת צעצוע של כיצד ניתן לגשת ללוח גדול יותר על מכונה עמידה לפגמים בעתיד.

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

הרשת

הנה רשת ה-Minesweeper הקטנה שלנו:

כל תא ריק ניתן לייצוג על ידי משתנה בינארי המציין האם הוא מכיל מוקש. נסמן אותם $x_0$, $x_1$, ו-$x_2$, כאשר $x_i = 1$ אומר שיש מוקש בתא זה ו-$x_i = 0$ אומר שאין:

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

קידוד האילוצים

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

התא "1" הסמוך ל-$x_0$ ו-$x_1$ אומר שבדיוק אחד מהם מכיל מוקש. זוהי בדיוק פעולת ה-XOR הבלעדי (XOR), $\oplus$, שמחזירה אמת כאשר בדיוק אחד מהקלטים שלה הוא אמת:

$$(x_0 \oplus x_1)$$

בדומה לכך, התא "1" האחר (הסמוך ל-$x_1$ ו-$x_2$) נותן לנו:

$$(x_1 \oplus x_2)$$

התא "2" אומר ששניים מתוך שלושת התאים הריקים חייבים להכיל מוקשים. מכיוון ש-XOR הוא פעולת זוגיות, $x_0 \oplus x_1 \oplus x_2$ מחזיר אמת כאשר מספר אי-זוגי של המשתנים הם אמת. אנחנו רוצים מספר זוגי (ספציפית שניים) שיהיו אמת, לכן אנחנו שוללים עם $\lnot$:

$$\lnot(x_0 \oplus x_1 \oplus x_2)$$

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

על שלושת התנאים להתקיים בו-זמנית, לכן אנחנו מצרפים אותם עם סמלי AND $\land$:

$$(x_0 \oplus x_1) \;\land\; (x_1 \oplus x_2) \;\land\; \lnot(x_0 \oplus x_1 \oplus x_2)$$

שלב 1: מיפוי קלטים קלאסיים לבעיה קוונטית

עכשיו עלינו לקדד ביטוי בוליאני זה למעגל קוונטי שמשמש כאורקל. הגרסה הקוונטית של XOR ניתנת לביצוע עם שערי CX (CNOT): החלת שני שערי CX מ-Qubits הנתונים ל-Qubit עזר (ancilla) מחשבת למעשה את ה-XOR שלהם ומאחסנת את התוצאה ב-ancilla.

אנחנו מציגים שלושה qubits של עבודה — אחד לכל פסוקית. אנחנו מאחסנים את תוצאת כל ביטוי בוליאני ב-Qubit העבודה המתאים לו, ואז משתמשים בשער Z מרובת-שליטה כדי להפוך את הפאזה של מצב שלושת ה-Qubits שגורם לכל שלושת qubits העבודה להיות $|1\rangle$ (כלומר כל הפסוקיות מתקיימות בו-זמנית).

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

x = QuantumRegister(3, "x")
a = QuantumRegister(3, "a")
qc = QuantumCircuit(x, a)

# Clause 1: x0 XOR x1 -> stored in a[0]
qc.cx(x[0], a[0])
qc.cx(x[1], a[0])

# Clause 2: x1 XOR x2 -> stored in a[1]
qc.cx(x[1], a[1])
qc.cx(x[2], a[1])

# Clause 3: NOT(x0 XOR x1 XOR x2) -> stored in a[2]
qc.cx(x[0], a[2])
qc.cx(x[1], a[2])
qc.cx(x[2], a[2])
qc.x(a[2])  # The NOT

qc.draw("mpl", style="iqp")

בשלב זה, תוצאת כל פסוקית מאוחסנת ב-Qubit העבודה המתאים לה. עכשיו אנחנו צריכים שמצב נתוני שלושת ה-Qubits שגורם לכל שלושת qubits העבודה להיות $|1\rangle$ יקבל סימן מינוס. אנחנו עושים זאת עם שער Z מרובת-שליטה (מיושם כשער MCX המוקף בשערי Hadamard על המטרה).

לאחר החלת היפוך הפאזה, עלינו לבטל חישוב — לבטל את כל שלבי הערכת הפסוקיות בסדר הפוך — כדי לאפס את qubits העבודה חזרה ל-$|0\rangle.$ זה חיוני כך שה-Qubits עבודה יהיו נקיים לאיטרציות עוקבות של אופרטור גרובר.

# Multi-controlled Z: flip phase if all workspace qubits are |1>
qc.h(a[2])
qc.mcx([a[0], a[1]], a[2])
qc.h(a[2])

# Uncompute clause 3: NOT(x0 XOR x1 XOR x2)
qc.x(a[2])
qc.cx(x[2], a[2])
qc.cx(x[1], a[2])
qc.cx(x[0], a[2])

# Uncompute clause 2: x1 XOR x2
qc.cx(x[2], a[1])
qc.cx(x[1], a[1])

# Uncompute clause 1: x0 XOR x1
qc.cx(x[1], a[0])
qc.cx(x[0], a[0])

qc.draw("mpl", style="iqp")

מעגל זה הוא האורקל שלנו: הוא הופך את הפאזה של מצב ה-Qubit הנתוני שמקיים את שלושת אילוצי Minesweeper, ומשאיר את qubits העבודה חזרה ב-$|0\rangle.$

עכשיו אנחנו בונים את אופרטור גרובר המלא מאורקל זה. שימו לב לארגומנט reflection_qubits: אנחנו מעבירים רק את qubits הנתונים x, מפני ש-Qubits העבודה אינם חלק ממרחב החיפוש. תפקידם הסתיים לאחר שהאורקל הוחל.

grover_op = grover_operator(qc, reflection_qubits=x)
grover_op.decompose(reps=0).draw(output="mpl", style="iqp")

עם שלושה qubits נתונים ומצב פתרון אחד, מספר האיטרציות האופטימלי של גרובר הוא $t \approx \frac{\pi}{4}\sqrt{8} - \frac{1}{2} \approx 1.7$, לכן אנחנו משתמשים בשתי איטרציות. אנחנו מחילים שערי Hadamard על qubits הנתונים כדי ליצור את הסופרפוזיציה הראשונית, מרכיבים את אופרטור גרובר פעמיים, ומודדים רק את qubits הנתונים.

x = QuantumRegister(3, "x")
a = QuantumRegister(4, "a")
meas = ClassicalRegister(3, "meas")

qc = QuantumCircuit(x, a, meas)
# Create superposition over the data qubits only
qc.h(x)
# Apply 2 iterations of the Grover operator
qc.compose(grover_op.power(2), inplace=True)
# Measure only the data qubits
qc.measure(x, meas)
qc.decompose().draw(output="mpl", style="iqp")

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

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

service = QiskitRuntimeService()
backend = service.least_busy(operational=True, simulator=False)
print(backend.name)

target = backend.target
pm = generate_preset_pass_manager(target=target, optimization_level=3)
circuit_isa = pm.run(qc)

עכשיו ניתן לבדוק את עומק המעגל המטורנספל. מכיוון שאורקל Minesweeper משתמש ב-Qubits עבודה ובשערי CX מרובים, המעגל המטורנספל יהיה עמוק יותר מאלה שבפעילויות הקודמות.

print("The total depth is ", circuit_isa.depth())
print(
    "The depth of two-qubit gates is ",
    circuit_isa.depth(lambda instruction: instruction.operation.num_qubits == 2),
)

שלב 3: הרצה באמצעות פרימיטיבים של Qiskit

# To run on a real quantum computer (this was tested on a Heron r2 processor and
#  used 4 sec. of QPU time)

from qiskit_ibm_runtime import SamplerV2 as Sampler

sampler = Sampler(mode=backend)
sampler.options.default_shots = 10_000
result = sampler.run([circuit_isa]).result()
dist = result[0].data.meas.get_counts()

# To run on local simulator:
# from qiskit.primitives import StatevectorSampler as Sampler
# sampler = Sampler()
# result = sampler.run([qc]).result()
# dist = result[0].data.meas.get_counts()

שלב 4: עיבוד לאחר מעשה והחזרת התוצאה בפורמט קלאסי הרצוי

plot_distribution(dist)

המצב 101 אמור להופיע בהסתברות גבוהה הרבה יותר מכל מצב אחר, מה שמצביע על כך שמוקשים נמצאים ב-$x_0$ וב-$x_2$. השתמשנו במחשב קוונטי כדי לפתור משחק Minesweeper זעיר!

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

שאלות ומושגים מרכזיים:

מושגים מרכזיים:

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

• בעוד שאלגוריתמי חיפוש קלאסי לא-מובנה דורשים מספר שאילתות שגדל לינארית בגודל המרחב, $N,$ אלגוריתם גרובר דורש מספר שאילתות שגדל כמו $\sqrt{N}.$
• אלגוריתם גרובר כולל חזרה על סדרת פעולות (שנקראת בדרך כלל "אופרטור גרובר") מספר פעמים $t,$ שנבחר כדי לגרום למצבי היעד להיות סבירים ביותר למדידה.
• אפשר להריץ את אלגוריתם גרובר עם פחות מ-$t$ איטרציות ועדיין להגביר את מצבי היעד.
• אלגוריתם גרובר מתאים למודל השאילתות של חישוב והגיוני ביותר כשאדם אחד שולט בחיפוש ואחר שולט/בונה את ה-oracle. הוא עשוי גם להיות שימושי כ-subroutine בחישובים קוונטיים אחרים.
• ניתן לבנות אורקל מאילוצי בעיה ולא מידיעת הפתרון, כפי שהודגם בדוגמת Minesweeper.

שאלות נכון/לא נכון:

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

2. נ/ל אלגוריתם גרובר פועל על ידי הגדלה איטרטיבית של ההסתברות שמצב פתרון יימדד.

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

שאלות רב-ברירה:

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

• א. פעם אחת בלבד.
• ב. תמיד $t$ פעמים, כדי למקסם את אמפליטודת ההסתברות של מצב(י) הפתרון.
• ג. עד $t$ פעמים, אם כי פחות עשוי להספיק כדי שמצבי הפתרון יבלטו.
• ד. לא פחות מ-10 פעמים.

2. כאן מוצג Circuit של שאילתת פאזה שמתפקד כ-oracle לסימון מצב מסוים עם היפוך פאזה. אילו מהמצבים הבאים מסומנים על ידי ה-Circuit הזה?

• א. $|0000\rangle$
• ב. $|0101\rangle$
• ג. $|0110\rangle$
• ד. $|1001\rangle$
• ה. $|1010\rangle$
• ו. $|1111\rangle$

3. נניח שאתה רוצה לחפש שלושה מצבים מסומנים מתוך קבוצה של 128. מהו מספר האיטרציות האופטימלי של אופרטור גרובר כדי למקסם את האמפליטודות של המצבים המסומנים?

• א. 1
• ב. 3
• ג. 5
• ד. 6
• ה. 20
• ו. 33

שאלות לדיון:

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