דלג לתוכן הראשי

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

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

שערי שאילתת פאזה​

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

Zf∣x⟩=(−1)f(x)∣x⟩Z_f \vert x\rangle = (-1)^{f(x)} \vert x\rangle

עבור כל מחרוזת x∈Σn.x\in\Sigma^n.

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

A quantum circuit implementing a Z_f gate using one query gate together with the phase kickback phenomenon

מימוש זה מנצל את תופעת ה-phase kickback, ודורש Qubit סביבה אחד שמאותחל למצב ∣−⟩\vert -\rangle. Qubit זה נשאר במצב ∣−⟩\vert - \rangle לאחר סיום המימוש, וניתן לעשות בו שימוש חוזר (למשל, למימוש שערי ZfZ_f נוספים) או פשוט להשליכו.

בנוסף לפעולה Zf,Z_f, נשתמש גם בשער שאילתת פאזה עבור פונקציית ה-OR בת nn סיביות, המוגדרת כך עבור כל מחרוזת x∈Σn.x\in\Sigma^n.

OR(x)={0x=0n1x≠0n\mathrm{OR}(x) = \begin{cases} 0 & x = 0^n\\[0.5mm] 1 & x \neq 0^n \end{cases}

באופן מפורש, שער שאילתת הפאזה עבור פונקציית ה-OR בת nn סיביות פועל כך:

ZOR∣x⟩={∣x⟩x=0n−∣x⟩x≠0n.Z_{\mathrm{OR}} \vert x\rangle = \begin{cases} \vert x\rangle & x = 0^n \\[0.5mm] - \vert x\rangle & x \neq 0^n. \end{cases}

כדי להיות מדויקים, כך פועל ZORZ_{\mathrm{OR}} על מצבי הבסיס הסטנדרטיים; התנהגותו על מצבים כלליים נגזרת מביטוי זה על ידי לינאריות.

ניתן לממש את הפעולה ZORZ_{\mathrm{OR}} כמעגל קוונטי על ידי התחלה ממעגל בוליאני עבור פונקציית ה-OR, בניית פעולת UORU_{\mathrm{OR}} (כלומר, שער שאילתה סטנדרטי עבור פונקציית ה-OR בת nn סיביות) תוך שימוש בנוהל המתואר בשיעור יסודות האלגוריתמיקה הקוונטית, ולבסוף בניית פעולת ZORZ_{\mathrm{OR}} באמצעות תופעת ה-phase kickback כמתואר לעיל. שימו לב שלפעולה ZORZ_{\mathrm{OR}} אין תלות בפונקציה ff ולכן ניתן לממש אותה על ידי מעגל קוונטי ללא שערי שאילתה.

תיאור האלגוריתם​

עכשיו שיש לנו את שתי הפעולות ZfZ_f ו-ZOR,Z_{\mathrm{OR}}, נוכל לתאר את האלגוריתם של גרובר.

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

האלגוריתם של גרובר
  1. אתחל רגיסטר nn Qubit בשם Q\mathsf{Q} למצב האפסים ∣0n⟩\vert 0^n \rangle ואז הפעל פעולת Hadamard על כל Qubit ב-Q.\mathsf{Q}.
  2. הפעל tt פעמים את הפעולה האוניטרית G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f על הרגיסטר Q\mathsf{Q}
  3. מדוד את ה-Qubit-ים של Q\mathsf{Q} ביחס למדידות הבסיס הסטנדרטי ופלוט את המחרוזת המתקבלת.

הפעולה G=H⊗nZORH⊗nZfG = H^{\otimes n} Z_{\mathrm{OR}} H^{\otimes n} Z_f שחוזרת בשלב 2 תיקרא פעולת גרובר לאורך שאר השיעור. הנה ייצוג מעגל קוונטי של פעולת גרובר כאשר n=7 ⁣:n=7\!:

A quantum circuit representation of the Grover operation

בתרשים זה, פעולת ZfZ_f מצוירת גדולה יותר מ-ZORZ_{\mathrm{OR}} כרמז ויזואלי בלתי פורמלי המרמז שסביר שזו הפעולה היקרה יותר. בפרט, כאשר אנו עובדים במודל השאילתות, ZfZ_f דורשת שאילתה אחת בעוד ZORZ_{\mathrm{OR}} לא דורשת שאילתות כלל. אם לעומת זאת יש לנו מעגל בוליאני עבור הפונקציה ff ואז ממירים אותו למעגל קוונטי עבור Zf,Z_f, ניתן לצפות באופן סביר שהמעגל הקוונטי המתקבל יהיה גדול ומסובך יותר מזה של ZOR.Z_{\mathrm{OR}}.

הנה תרשים של מעגל קוונטי עבור האלגוריתם השלם כאשר n=7n=7 ו-t=3.t=3. עבור ערכים גדולים יותר של tt ניתן פשוט להוסיף מופעים נוספים של פעולת גרובר מיד לפני המדידות.

A quantum circuit for Grover's algorithm when t=3

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

  • בחר את המספר tt בשלב 2. (נושא זה נדון בהמשך השיעור.)
  • הרץ את האלגוריתם של גרובר על הפונקציה f,f, תוך שימוש בכל בחירה שעשינו עבור t,t, כדי לקבל מחרוזת x∈Σn.x\in\Sigma^n.
  • שאל את הפונקציה ff על המחרוזת xx כדי לבדוק אם היא פתרון תקין:
    • אם f(x)=1,f(x) = 1, אז מצאנו פתרון, ולכן נוכל לעצור ולפלוט את x.x.
    • אחרת, אם f(x)=0,f(x) = 0, נוכל לרוץ את הנוהל שוב, אפשר עם בחירה שונה עבור t,t, או שנוכל להחליט לוותר ולפלוט "אין פתרון."

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