לדלג לתוכן

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

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

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

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

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

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

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

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

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

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

בעזרת הפונקציה ובעזרת שער הדמר נבנה מעגל המממש את האופרטור עבורו כלומר ערך הפונקציה משוקף בפאזה של האוגר[2].

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

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

[עריכת קוד מקור | עריכה]
ניתן להציג את האיטרטור בתור האופרטור


בבסיס המוגדר להלן.

בצע את סט הפעולות הבאות פעמים

  1. הפעל את
  2. הפעל שער הדמר
  3. הפעל שער המבצע הפיכת פאזה לאיבר בלבד
  4. הפעל שער הדמר
  5. הפוך את הפאזה הגלובלית. [צעד זה חסר משמעות מבחינה פיזיקלית, אך הוא נוח לשם האנליזה של האלגוריתם.]

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

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

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

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

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

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

אם נבצע מדידה לאחר t הפעלות של האלגוריתם, ההסתברות למדוד את האיבר המבוקש נתונה על ידי

.

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

הערות שוליים

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