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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

אלגוריתם גרובר הינו אלגוריתם קוונטי לחיפוש במבנה נתונים שאינו ממויין. האלגוריתם הומצא בשנת 1996 על ידי לוב גרובר[1]. בעוד אלגוריתם קלאסי מצריך \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 כלומר ערך הפונקציה משוקף בפאזה של האוגר‏‏[2].

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

הערות שוליים[עריכת קוד מקור | עריכה]

  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. ^ ‏ראה אלגוריתם דויטש-ג'וזה עבור שער הפולט את ערך הפונקציה על ידי שינוי פאזה‏