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

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

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

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

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

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

תיאור האלגוריתם הקוונטי

אתחול

בעזרת הפונקציה ${\displaystyle f\left(x\right)}$ ובעזרת שער הדמר נבנה מעגל המממש את האופרטור ${\displaystyle \left.U_{f}\right.}$ עבורו ${\displaystyle U_{f}|x\rangle =(-1)^{f(x)}|x\rangle }$ כלומר ערך הפונקציה משוקף בפאזה של האוגר^[2].

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

איטרטור גרובר

ניתן להציג את האיטרטור בתור האופרטור ${\displaystyle Q={\begin{pmatrix}1-{\frac {2}{N}}&2{\frac {\sqrt {N-1}}{N}}&&&\\-2{\frac {\sqrt {N-1}}{N}}&1-{\frac {2}{N}}&&&\\&&-1&&\\&&&\ddots &\\&&&&-1\end{pmatrix}}}$ בבסיס ${\displaystyle |k\rangle ,|l\rangle }$ המוגדר להלן.

בצע את סט הפעולות הבאות ${\displaystyle {\frac {\pi {\sqrt {N}}}{4}}}$ פעמים

1. הפעל את ${\displaystyle \left.U_{f}\right.}$
2. הפעל שער הדמר
3. הפעל שער המבצע הפיכת פאזה לאיבר ${\displaystyle |0\rangle }$ בלבד
4. הפעל שער הדמר
5. הפוך את הפאזה הגלובלית. [צעד זה חסר משמעות מבחינה פיזיקלית, אך הוא נוח לשם האנליזה של האלגוריתם.]

מדידה

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

אנליזת האלגוריתם

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

סיכוי הצלחת האלגוריתם

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

${\displaystyle Pr\left(t\right)=\sin ^{2}(\omega t+\phi )}$.

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

הערות שוליים

1. Grover L.K.: A fast quantum mechanical algorithm for database search, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212
2. ראו אלגוריתם דויטש-ג'וזה עבור שער הפולט את ערך הפונקציה על ידי שינוי פאזה