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

למודול 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®.

הסתייגות ברורה

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

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

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

(3) האלגוריתם של גרובר לא מחזיר רק נתונים קלאסיים. נכון, אם נבצע מדידה של המצב הסופי לאחר $t$ חזרות של אופרטור גרובר, נקבל כנראה מידע קלאסי שמזהה את מצב הפתרון. אבל מה אם אנחנו לא רוצים מידע קלאסי; מה אם אנחנו רוצים מצב פתרון מוכן על מחשב קוונטי לשימוש נוסף באלגוריתם אחר? האלגוריתם של גרובר למעשה מייצר מצב קוונטי עם הפתרונות ממושקלים בכבדות. לכן אתם עשויים לצפות למצוא את האלגוריתם של גרובר כתת-שגרה באלגוריתמים קוונטיים מסובכים יותר.

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

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

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

# Built-in modules
import math

# Imports from Qiskit
from qiskit import QuantumCircuit
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,$ למיקסום האמפליטודה של מצב המטרה בהיעדר רעש ניתן מהביטוי הזה:

$$(2t+1)\theta = (2t+1)\sin^{-1}\left( \sqrt{\frac{|A_1|}{N}}\right) \approx (2t+1)\sqrt{\frac{|A_1|}{N}} \approx \frac{\pi}{2}\\ t\approx \frac{\pi}{4} \sqrt{\frac{N}{|A_1|}}-\frac{1}{2}$$

כאן $A_1$ הוא מספר הפתרונות או מצבי המטרה. על מחשבים קוונטיים רועשים מודרניים, מספר האיטרציות האופטימלי ניסיונית עשוי להיות שונה - אבל כאן אנחנו מחשבים ומשתמשים במספר התיאורטי האופטימלי הזה תוך שימוש ב-$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 לא יהיו בעלי ביצועים גבוהים במיוחד. בוא נראה איך אלה מתפקדים.

הרצה באמצעות פרימיטיבים של 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: קריטריון שאינו מחרוזת ביטים ספציפית

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

שלב 1:

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

from qiskit import QuantumCircuit

def grover_oracle_hamming_weight(num_qubits, target_weight):
    """
    Build a Grover oracle that marks all states with Hamming weight == target_weight.

    Parameters:
        num_qubits (int): Number of qubits in the circuit.
        target_weight (int): The Hamming weight to mark.

    Returns:
        QuantumCircuit: Quantum circuit representing Grover oracle.
    """
    qc = QuantumCircuit(num_qubits)
    marked_count = 0
    marked_list = []
    for x in range(2**num_qubits):
        bitstr = format(x, f"0{num_qubits}b")
        if bitstr.count("1") == target_weight:
            # Count the number of target states
            marked_count = marked_count + 1
            marked_list.append(bitstr)
            # Reverse for Qiskit bit order (qubit 0 is rightmost)
            rev_target = bitstr[::-1]
            zero_inds = [i for i, b in enumerate(rev_target) if b == "0"]
            # Apply X gates to 'open' controls (where bit is 0)
            qc.x(zero_inds)
            # Multi-controlled Z (as MCX conjugated by H)
            if num_qubits == 1:
                qc.z(0)
            else:
                qc.h(num_qubits - 1)
                qc.mcx(list(range(num_qubits - 1)), num_qubits - 1)
                qc.h(num_qubits - 1)
            # Undo X gates
            qc.x(zero_inds)
    return qc, marked_count, marked_list

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(3, 2)
print(marked_states)
oracle.draw(output="mpl", style="iqp")

['011', '101', '110']

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

from qiskit_ibm_runtime import SamplerV2 as Sampler

# Completing step 1
oracle, num_marked_states, marked_states = grover_oracle_hamming_weight(4, 2)
oracle.draw(output="mpl", style="iqp")

grover_op = grover_operator(oracle)
grover_op.decompose().draw(output="mpl", style="iqp")
optimal_num_iterations = math.floor(
    math.pi / (4 * math.asin(math.sqrt(len(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()
qc.draw(output="mpl", style="iqp")

# Step 2: Optimize for running on real quantum computers

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)

# Step 3: Execute using Qiskit primitives
# To run on a real quantum computer (this was tested on a Heron r2 processor and used 4 seconds of QPU time)

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()

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

ibm_brisbane

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  502
The depth of two-qubit gates is  130

num_marked_states

6

plot_distribution(dist)

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

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

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

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

שאלות

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

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. אילו תנאים אחרים אפשר להשתמש ב-oracle קוונטי? שקול תנאים שקל לנסח או להטיל על מחרוזת ביטים אך אינם סתם כתיבת מחרוזות הביטים המסומנות.