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

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

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

ניתן להציג את האיטרטור בתור האופרטור $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}}$ בבסיס $|k\rangle ,|l\rangle$ המוגדר להלן.

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

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

מדידה

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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