”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה לא (וקצת מה כן)

השבוע קרה דבר שהוא תמיד משמח - עולם המתמטיקה עלה לכותרות בזכות תוצאה שקשורה לחישוב קוונטי - תחום שהופך לפופולרי יותר ויותר לאחרונה בעיתונות. “פריצת דרך: הוכחה ראשונה לעליונות מחשוב קוונטי” נאמר בכותרת בדה-מרקר, ובלועזית ראיתי כותרות אפילו מתלהבות יותר בסגנון “צוות מיבמ הוכיח שמחשבים קוונטיים יכולים לעשות דברים בלתי אפשריים”. ובכן, אני רוצה לעשות קצת סדר. ראשית, להסביר על מה בערך מדובר ומה בערך הוכיחו (התקציר: הוכיחו תוצאה מאוד יפה שהיא אכן פורצת דרך, אבל בואו לא נגזים עם הכותרות שנותנים לה), ושנית (ואת זה אעשה בפוסט נפרד) - להיכנס יותר לפרטים המתמטיים לטובת אלו שמעוניינים בכך (טוקבק זועם אצל דה-מרקר התלונן שלא סיפרו לו “איזו בעיה? גם השם מספיק” - ובכן חבר, להגיד 2D Hidden Linear Function Problem עוזר במשהו?)

מה זה חישוב קוונטי בכלל?

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

בואו נכניס טיפה סימון מתמטי לסיפור כי לדעתי זה יכול לעזור גם להדיוטות. פיזיקאים אוהבים להשתמש בסימון \( \left|0\right\rangle \) ו-\( \left|1\right\rangle \) כדי לתאר את הערכים הבסיסיים שקיוביט יכול להחזיק בהם; יש הגיון מאחורי הסימון המוזר הזה עם המשולש והכל, אבל נעזוב אותו כרגע. “תערובת” של שני המצבים הבסיסיים הללו היא משהו מהצורה \( a\left|0\right\rangle +b\left|1\right\rangle \) כאשר \( a,b \) הם מספרים. מה זה “מספרים” כאן? אני מרשה שברים כמו \( \frac{1}{2} \) וגם מספרים כמו \( \frac{\sqrt{2}}{2} \) ואפילו מספרים מרוכבים כמו \( i \) (מה זה \( i \)? זה מספר שמקיים \( i^{2}=-1 \), משהו שלא קורה במספרים שאנחנו מכירים מחיי היום יום). יש רק מגבלה אחת שאני דורש במפורש: שיתקיים \( \left|a\right|^{2}+\left|b\right|^{2}=1 \).

בחישוב קלאסי, לעומת זאת, עדיין אפשר לחשוב על כל מצב בתור משהו מהצורה \( a\left|0\right\rangle +b\left|1\right\rangle \), אבל עם מגבלה הרסנית הרבה יותר: הדרישה היא ש-\( a=1 \) ו-\( b=0 \) או ש-\( a=0 \) ו-\( b=1 \) וזהו. כלומר, ייצוג מידע קוונטי פותח לנו פתח לייצוג מורכב בצורה דרסטית יותר מאשר בייצוג מידע קלאסי. אבל זה אפילו לא סוף הסיפור, כי לא דיברנו (עדיין) על מה קורה במערכות שכוללות יותר מקיוביט בודד.

עכשיו, משהבנו מה זה בערך חישוב קוונטי, אפשר לתהות ממתי הדבר הזה קיים ולמה אנחנו שומעים עליו רק עכשיו. ובכן, תורת הקוונטים עצמה קיימת עוד מתחילת המאה ה-20, ומחשבים “קלאסיים” קיימים מאמצע המאה ה-20, אבל את ההצעה לבצע משהו כמו החישוב הקוונטי שמדברים עליו כיום הציע הפיזיקאי ריצ’ארד פיינמן רק ב-1982, מתוך כוונה להציע בניית מחשבים שיוכלו להתמודד יותר טוב עם בעיות של סימולציה של מערכות פיזיקליות “אמיתיות” (למה לעבוד קשה כדי לסמלץ מצבים קווונטיים בעזרת חישוב קלאסי כשאפשר לרתום את הטבע לעשות את העבודה בשבילנו). באופן די מרתק, עם הזמן התגלה שחישוב קוונטי יכול לסייע גם בכיוון “ההפוך” - לעזור לנו לפתור בעיות “קלאסיות” שמחשב קלאסי מתקשה להתמודד איתן. הדוגמא הידועה ביותר היא בעיית הפירוק לגורמים של מספרים; אנחנו לא מכירים כיום אלגוריתם קלאסי יעיל מספיק לפירוק לגורמים, למרות שהאלגוריתמים הקיימיים הם מתוחכמים בצורה יוצאת מן הכלל ומתבססים על מתמטיקה עמוקה למדי. התחושה הכללית היא שפירוק לגורמים היא בעיה “קשה מדי” ושכל אלגוריתם שפותר אותה ייקח כמות גדולה של זמן (“אקספוננציאלית” למי שזה אומר לו משהו).

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

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

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

האם המאמר הנוכחי שעלה לכותרות עושה את זה?

ובכן, לא.

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

מה המאמר אומר?

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

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

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

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

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

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

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

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

המאמר הנוכחי לוקח שני מחלקות סיבוכיות אחרות: אחת “קלאסית” שנקראת \( \text{NC}^{0} \) והשניה קוונטית שנקראת \( \text{SQC} \) (השם הזה הוא לדעתי חידוש של המאמר הנוכחי ולא תמצאו אותו בגוגל) ומראה שהן כן שונות, כלומר שיש בעיה ששייכת ל-SQC אבל לא שייכת ל-\( \text{NC}^{0} \). ההוכחה שהבעיה שייכת ל-SQC היא החלק הפשוט יותר של המאמר; עיקר העבודה היא בלהוכיח ש-\( \text{NC}^{0} \) לא כוללת את הבעיה - כלומר, עיקר המאמר הוא תוצאה “קלאסית” בתורת הסיבוכיות שאפשר היה לדבר עליה גם בלי לדבר על חישוב קוונטי.

התוצאה הזו, של הפרדה בין שתי מחלקות סיבוכיות מקבילות שאחת מהן קלאסית ואחת מהן קוונטית, היא באמת משהו חדש (לפחות למיטב ידיעתי). אבל לומר שזו “הוכחה ראשונה לעליונות מחשב קוונטי” זה לא באמת נכון, וכדי להסביר למה אני רוצה להכניס לתמונה את האלגוריתם של גרובר. יש לי פוסט עליו, אבל הנה התקציר: האלגוריתם של גרובר מטפל בבעיה של חיפוש. תחשבו שאתם בספריה ועל המדף יש \( N \) ספרים, ואתם מחפשים ספר אחד ספציפי. והמדף לא ממוין בשום צורה - או ליתר דיוק, גם אם הוא ממוין, אתם לא יודעים את זה ואתם לא יודעים על פי איזו שיטת מיון. איך תמצאו את הספר? תצטרכו לדגום: לקחת ספר מהמדף, לבדוק אם הוא הספר שלכם, ואם לא אז להחזיר אותו ולעבור לספר אחר. אפשר להוכיח מתמטית שבחישוב רגיל, תצטרכו במקרה הגרוע לדגום את כל \( N \) הספרים לפני שתמצאו את הספר שלכם.

והנה, בחישוב קוונטי קורה קסם מדהים ואתם יכולים למצוא את הספר שלכם ב-\( \sqrt{N} \) דגימות. זה אפשרי בגלל שבחישוב קוונטי, גם “דגימה” היא קוונטית - במקום לדגום את \( \left|0\right\rangle \) או את \( \left|1\right\rangle \) אתם מסוגלים לדגום את \( a\left|0\right\rangle +b\left|1\right\rangle \) “בבת אחת”. התיאור הפשטני הזה יוצר תחושה שהרעיון בחישוב קוונטי הוא המקביליות הזו - היכולת לפעול בו זמנית על \( \left|0\right\rangle \) ו-\( \left|1\right\rangle \) ולקבל עליהם אינפורמציה ביחד. זה אמנם מה שקורה אבל זה לא סוף הסיפור, ויש לחישוב קוונטי גם קשיים (אין לנו דרך פשוט “לקרוא” את התשובה לדגימה שביצענו; בסוף החישוב הקוונטי כל מה שנקבל הוא את הכתובת של ספר בודד שמוגרל איכשהו מבין כל הספרים, וצריך לעבוד קשה כדי לוודא שההסתברות של הספר “שלנו” תהיה גבוהה).

מה שמעניין באלגוריתם גרובר הוא שמדובר על הוכחה חד משמעית לכך שמחשב קוונטי מסוגל להשיג “קיצורי דרך” שמחשב קלאסי לא מסוגל להן - \( \sqrt{N} \) דגימות מול \( N \) דגימות. יש עוד דוגמאות ל”שיפור במספר הדגימות” והמאמר הנוכחי מאזכר אחת מהן ומתבסס עליה חלקית, אבל הדיבור על “מספר דגימות” הוא שונה מהדיבור על “זמן ריצה” שהזכרנו קודם. גרובר בהחלט משפר את זמן הריצה של אלגוריתמים מסויימים, אבל לא ברמה שמספיקה כדי לטעון ששתי מחלקות סיבוכיות כמו BQP ו-BPP הן שונות זו מזו. מה שהמאמר הנוכחי עושה, ועושה בצורה יפה מאוד, הוא להיפטר מכל הנושא הזה של דגימה ובמקום זה לדבר על בעיה שנתונה בצורה מפורשת לחלוטין; אני אסביר את זה בפוסט הבא.

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

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