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

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

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

עקרון הפעולה של האלגוריתם מבוסס על ביצוע מחזורי של מספר פעולות בסיס כגון הפעלת הפונקציה הקוונטית המתארת את הגישה אל מבנה הנתונים, הפעלת שער אדמר ושער הפיכת פאזה. סט הפעולות ידוע בשם **איטרטור גרובר**, ויש להפעילו \frac{\pi\sqrt{N}}{4} פעמים על מנת לקבל הסתברות גבוהה ביותר לסיום האלגוריתם עם התשובה הנכונה.

## יישום האלגוריתם
כאמור, אלגוריתם גרובר נועד לחיפוש במבנה נתונים לא-ממוין. לייתר דיוק, הקלט של האלגוריתם היא פונקציית אוב כך שהפעלת הפונקציה על הערך המבוקש מחזירה 1, ועל כל שאר הערכים מחזירה 0. נניח, למשל, כי אנו מחפשים אינדקס מסוים מתוך המערך \left[1..N\right]. נסמן את האינדקס המבוקש (שערכו אינו ידוע לנו) ב \left.k\right.. מתקיים
f(x) = \begin{cases}1 & x=k \\ 0 & x \neq k\end{cases}
באופן קלאסי, הסתברותי, על מנת למצוא את האינדקס המבוקש, "ננחש" אינדקס כלשהו ונפעיל את f\left(x\right) עד לניחוש מוצלח עבורו הפונקציה החזירה את הערך 1. בממוצע, נצטרך להפעיל את הפונקציה N/2 פעמים.

## תיאור האלגוריתם הקוונטי
### אתחול
בעזרת הפונקציה f\left(x\right) ובעזרת שער אדמר נבנה מעגל המממש את האופרטור \left.U_f\right. עבורו U_f|x\rangle=(-1)^{f(x)}|x\rangle כלומר ערך הפונקציה משוקף בפאזה של האוגר.

אתחל אוגר קוונטי באורך n = \log\left(N\right) ואתחל אותו לסופרפוזיציה שווה של כל אברי בסיס החישוב (במילים אחרות, אתחל את האוגר למצב |0\rangle והפעל עליו את שער אדמר).

### איטרטור גרובר
{N}& & & \\-2\frac{\sqrt{N-1}}{N} &1-\frac{2}{N}& & & \\ & & -1 & & \\ & & & \ddots & \\ & & & & -1\end{pmatrix} 
בבסיס |k\rangle, |l\rangle המוגדר להלן.
|כיוון=שמאל|צבע=none}}
בצע את סט הפעולות הבאות \frac{\pi\sqrt{N}}{4} פעמים
:# הפעל את \left.U_f\right.
:# הפעל שער אדמר
:# הפעל שער המבצע הפיכת פאזה לאיבר |0\rangle בלבד
:# הפעל שער אדמר
:# הפוך את הפאזה הגלובלית. [צעד זה חסר משמעות מבחינה פיזיקלית, אך הוא נוח לשם האנליזה של האלגוריתם.]

### מדידה
לאחר הפעלת האיטרטור במספר הפעמים הנדרש, יש לבצע מדידה בבסיס החישוב. תוצאת המדידה יהיו האינדקס המבוקש \left.k\right. בהסתברות 1\approx.

## אנליזת האלגוריתם
נגדיר את הבסיס עבור המרחב אשר בו אבר בסיס אחד הוא |k\rangle, האינדקס אותו אנחנו מחפשים, ואבר שני הוא סופרפוזיציה שווה של כל שאר האינדקסים, |l\rangle = \frac{1}{\sqrt{N-1}}\sum_{i\neq k}|i\rangle. שני איברים אלו אורתוגונליים ולכן ניתן להרחיב אותם לבסיס של המרחב, למשל על ידי שימוש בתהליך גרם-שמידט.
פעולת איטרטור גרובר, Q, היא למעשה סיבוב ההטלה של המצב הקוונטי על המישור הנפרש על ידי |k\rangle, |l\rangle בזווית \omega המקיימת \cos \omega = 1-\frac{2}{N}.
באתחול האלגוריתם יוצרים אוגר שהוא סופרפוזיצה שווה של כלל האיברים, וניתן להציג אותו בבסיס החדש כ
\frac{1}{\sqrt{N}}\sum_i|i\rangle=\frac{1}{\sqrt{N}}|k\rangle+ \frac{\sqrt{N-1}}{\sqrt{N}}|l\rangle=\sin\phi|k\rangle+ \cos\phi|l\rangle
כאשר \phi = \arcsin \frac{1}{\sqrt{N}}. בכל פעם שמפעילים את Q, מתבצע סיבוב בזווית \omega, כך שלאחר ביצוע t הפעלות מתקבל המצב
\sin (\omega t+\phi)|k\rangle + \cos(\omega t + \phi)|l\rangle.

### סיכוי הצלחת האלגוריתם
אם נבצע מדידה לאחר t הפעלות של האלגוריתם, ההסתברות למדוד את האיבר המבוקש |k\rangle נתונה על ידי

Pr\left(t\right) = \sin^2 (\omega t+\phi).

הסתברות ההצלחה תלויה במספר ההפעלות של האיטרטור, ותהיה קרובה ל-1 ככל ש\left.\omega t+\phi\right. יתקרב ל-\left.\pi/2\right.. מספר ההפעלות המינימלי, t_{\min}, עבורו הסתברות ההצלחה היא גבוהה מקיים \left.\omega t+\phi\right.=\pi/2, כלומר t_\min=\frac{\pi-2\phi}{2\omega}.
עבור N גדול ושימוש בזהויות טריגונומטריות ובקרובים טריגונומטריים ניתן לבצע את הקרובים \omega \approx \frac{2}{\sqrt{N}}, \phi\approx \frac{1}{\sqrt{N}} ומתקבל
t_{\min} \approx \left(\frac{\pi\sqrt{N}}{4}-\frac{1}{2}\right).
יש לשים לב כי הפעלת האיטרטור במספר פעמים גבוה יותר עלול לפגום בהסתברות ההצלחה.

## קישורים חיצוניים

* 

## הערות שוליים

גרובר
גרובר