מבוא

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

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

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

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

וידאו השיעור

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