חיפוש לא מובנה

סיכום

נתחיל בתיאור הבעיה שאלגוריתם גרובר פותר. כמקובל, נסמן $\Sigma = \{0,1\}$ לאלפבית הבינארי לאורך הדיון הזה.

נניח ש-

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

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

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

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

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

דרך אחת לבצע משימת החיפוש הזאת קלאסית היא פשוט לעבור על כל המחרוזות $x\in\Sigma^n,$ ולהעריך את $f$ על כל אחת מהן כדי לבדוק אם היא פתרון. מכאן ואילך נכתוב

$$N = 2^n$$

לשם הנוחות. יש $N$ מחרוזות ב-$\Sigma^n,$ כך שמעבר על כולן דורש $N$ הערכות של $f.$ בהנחה שאנחנו מוגבלים להערכת $f$ על קלטים שנבחרו, זה הכי טוב שאפשר לעשות עם אלגוריתם דטרמיניסטי אם רוצים להבטיח הצלחה. עם אלגוריתם הסתברותי, אפשר לקוות לחסוך זמן על ידי בחירה אקראית של מחרוזות קלט ל-$f,$ אך עדיין נדרוש $O(N)$ הערכות של $f$ אם רוצים שהשיטה הזאת תצליח בהסתברות גבוהה.

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

הצהרת הבעיה הפורמלית

נפרמל את הבעיה שאלגוריתם גרובר פותר תוך שימוש במודל השאילתות של החישוב. כלומר, נניח שיש לנו גישה לפונקציה $f:\Sigma^n\rightarrow\Sigma$ דרך שער שאילתה המוגדר בדרך הרגילה:

$$U_f \bigl( \vert a\rangle \vert x\rangle \bigr) = \vert a \oplus f(x) \rangle \vert x \rangle$$

לכל $x\in\Sigma^n$ ו-$a\in\Sigma.$ זהו הפעולה של $U_f$ על מצבי בסיס סטנדרטיים, והפעולה שלו באופן כללי נקבעת על ידי לינאריות.

כפי שנדון בשיעור יסודות האלגוריתמיקה הקוונטית, אם יש לנו מעגל בוליאני לחישוב $f,$ אנחנו יכולים להמיר את תיאור המעגל הבוליאני למעגל קוונטי שמממש את $U_f$ (תוך שימוש במספר מסוים של Qubit-ים לעבודה שמתחילים ומסיימים את החישוב במצב $\vert 0\rangle$). לכן, למרות שאנחנו משתמשים במודל השאילתות לפרמול הבעיה שאלגוריתם גרובר פותר, הוא אינו מוגבל למודל זה; אנחנו יכולים להריץ את אלגוריתם גרובר על כל פונקציה $f$ שיש לנו עבורה מעגל בוליאני.

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

חיפוש

קלט: פונקציה $f:\Sigma^n\rightarrow\Sigma$
פלט: מחרוזת $x\in\Sigma^n$ המקיימת $f(x) = 1,$ או "אין פתרון" אם לא קיימת מחרוזת $x$ כזאת

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

חיפוש ייחודי

קלט: פונקציה מהצורה $f:\Sigma^n \rightarrow \Sigma$
הבטחה: יש בדיוק מחרוזת אחת $z\in\Sigma^n$ שעבורה $f(z) = 1,$ כאשר $f(x) = 0$ לכל המחרוזות $x\neq z$
פלט: המחרוזת $z$

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