מבוא

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

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

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

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

סרטון השיעור

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