בפוסטים קודמים [1] על מחשוב קוונטי סיפרנו לכם שאחת השאלות הפתוחות הלוהטות במדעי המחשב היא אם מחשבים קוונטיים הם אכן יותר חזקים מאבותיהם הקלאסיים. זו שאלה עמוקה, ואחד הדברים הראשונים שצריכים להבין הם מה בדיוק אנחנו שואלים. מה זה בעצם אומר להגיד על מחשב מסוג אחד שהוא "יותר חזק" ממחשב אחר?
הדרך הכי פשוטה להגדיר את זה היא להגיד שמחשב יותר חזק הוא מחשב שמסוגל לפתור יותר בעיות. כלומר, בעגה המקצועית אומרים שהוא "יותר חזק חישובית". הרי יש בעיות שידוע שמחשבים "רגילים" לא יכולים לפתור [2], אז אולי הגיוני להגדיר שמחשב הוא "יותר חזק" אם הוא יכול לפתור בעיות כאלו? הבעיה היא שאם נשתמש בהגדרה הזו, די סיימנו את הדיון. אין שום בעיה להריץ סימולציה של מחשב קוונטי על מחשב קלאסי [3], ולכן כל בעיה שמחשב קוונטי יכול לפתור גם מחשב קלאסי יכול לפתור. שימו לב שאנחנו לא מדברים על כמה זמן ייקח לפתור את הבעיה, או על איזה מחשב פותר אותה מהר יותר, פשוט על זה שמחשב אחד יודע לפתור אותה והשני לא. למעשה, עקרון פיזיקלי בשם התזה של צ'רצ' וטיורינג [4] טוען ששום מחשב שאפשר לבנות לא יהיה יותר חזק במובן הזה מהמחשב שיש לנו בבית. אכן, היו לא מעט ניסיונות להראות מודלים תאורטיים שיכולים לפתור בעיה שמחשב קלאסי לא מסוגל לפתור והיחידים שאולי הצליחו השתמשו בהנחות מאוד לא מציאותיות כמו האפשרות להשתמש בלולאות זמן חלל סגורות (כלומר מסלולים שאם נלך בהם נחזור בסוף לאותה נקודה שהתחלנו ממנה *באותו הזמן* שבו התחלנו [5]) או היכולת להתקרב ולהתרחק כרצוננו משפה של חור שחור [6].
אוקיי, אז אם מחשב קלאסי יכול לדמות לחלוטין מחשב קוונטי, למה צריכים מחשבים קוונטיים בכלל? פשוט תנו למחשבים קלאסיים לעשות כאילו ולפתור לנו את כל הבעיות, לא? אז לא. זה לא מספיק טוב. הבעיה ברעיון הזה היא שהסימולציות האלו איטיות. מאוד מאוד איטיות. הזמן שלוקח להריץ סימולציה כזו הוא מעריכי בגודל הקלט. זה אומר שכל קיוביט שאנחנו מוסיפים למערכת מכפיל לנו את כמות החישובים וכבר עבור מערכות יחסית קטנות כמות החישובים הדרושה היא מעבר ליכולות של כל כוח החישוב העולמי.
זה מוביל אותנו להגדרה יותר עדינה לכך שמחשב הוא "חזק יותר" ממחשב קלאסי. זה לא שמחשב קוונטי יכול לפתור בעיה שמחשב קלאסי לא יכול, אלא שהוא יכול לפתור "מהר" בעיות שמחשבים קלאסיים יכולים לפתור רק "לאט".  זה מה שנקרא מחשב "יותר חזק סיבוכית". יש תחום שלם במתמטיקה בשם תורת הסיבוכיות [7] שמגדיר במדוייק מה זה מהר ומה זה לאט ושואל שאלות לגבי איך אפשר להראות שבעיה יותר קשה מבעיה אחרת.
עם הגישה הזאת יש בעיה אחרת – היא פשוט מחוץ לגבולות היכולת התאורטית שלנו. להוכיח שמחשב קוונטי יכול לפתור בעיה כלשהי מהר זה "קל", "בסך הכל" צריך להראות אלגוריתם שפותר את הבעיה. להוכיח שמחשב קלאסי לא יכול לפתור אותה מהר זה הרבה יותר קשה, כי אנחנו בעצם צריכים להראות שכל אלגוריתם שניתן להעלות על הדעת לא יפתור אותה מהר. אין לנו מושג איך עושים דברים כאלו. למעשה, בעיות הרבה יותר בסיסיות בתורת החישוביות עדיין פתוחות וכנראה שיוותרו ללא מענה בעשורים הקרובים.
אז מה נעשה? נחכה למאה הבאה ונראה אם אולי התאוריה התפתחה מספיק כדי להוכיח משהו, ובינתיים נשים בצד את כל הנושא הזה של מחשוב קוונטי? מה פתאום! פשוט צריך גישה אחרת, פרקטית יותר. גישה אחת כזאת היא המחקר סביב המושג "עליונות קוונטית" [8]. החוקרים בתחום הזה שואלים את עצמם את השאלה הבאה: כמה גדולה ומסובכת צריכה להיות מערכת חישוב קוונטית כדי להראות שהיא יותר טובה מכל מחשב קלאסי שאנחנו מכירים היום?
כמובן שהגישה הזאת מביאה איתה המון שאלות מעניינות: איך אנחנו מודדים עד כמה מערכת חישוב כזו היא "טובה"? תחת אילו הנחות ננסה לעצב מערכת כזאת כדי שהיא תהיה מספיק פשוטה כדי שנצליח לבנות אותה, אבל מספיק מורכבת כדי שתוכל לעשות דברים מרשימים? אילו אלגוריתמים נריץ על המערכת הזו, ולמה?
לפני מספר ימים התפרסם במגזין היוקרתי Science מאמר של בראביי, גוסט וקוניג [9] שתואר כ"פריצת דרך", ואתרים כמו דה-מארקר הגדילו להכריז שנמצאה "הוכחה לעליונות של מחשב קוונטי" [8]. מה הם בעצם עשו שם? והאם זו אכן ההוכחה שהתקשורת טוענת שזו?
השאלה השנייה יותר קלה אז נתחיל בה. התשובה היא שממש לא. המאמר חשוב ומעניין, והוא צעד משמעותי בדרך לעליונות קוונטית. אבל הוא עדיין רק צעד אחד, והדרך לשם עוד מאוד ארוכה. אולי אפילו יותר ארוכה מהדרך לתקשורת מדע שאשכרה מתייעצת עם מדענים מהתחום במקום לפרסם שגיאות מביכות.
אז מה כן קרה במאמר הנ"ל, ומה המשמעויות של זה? כל זאת ועוד בפוסטים הבאים.
לחלק ב' >>>
הכתבה בדה-מארקר שהתחילה הכל

תמונה ראשית: Steve Jurvetson via flickr