חישוב קוונטי - מה זה אומר ומה זה לא אומר?

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

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

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

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

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

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

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

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

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

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

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

אבל גם זה עדיין לא מספיק טוב, כי זה לא מבהיר עד כמה מושג ה”תערובת” הזה הוא מוזר! אז הנה המחשה: תחת בחירה מתאימה של התנהגות של המערכת הקוונטית שמתארת את החתול, אנחנו מסוגלים להגיע למצב שבו החתול הוא \( \frac{1}{2} \) “חי” ו-\( -\frac{\sqrt{3}}{2} \) “מת”. כן, אתם רואים נכון - יש שם מינוס. זה כמובן שונה לגמרי מהאינטואיציה של “חצי-חצי” שבדרך כלל יש לנו. ואפשרי גם שהחתול יהיה \( \frac{\sqrt{2}}{2}i \) “חי” ו-\( -\frac{\sqrt{2}}{2}i \) “מת”, כאשר \( i \) הוא מספר מדומה. כל הדברים הללו הם לגיטימיים לחלוטין מבחינת תורת הקוונטים; אבל מה המשמעות שלהם בעולם האמיתי? מה זה אומר בכלל שהחתול הוא \( \frac{\sqrt{2}}{2}i \) “חי”? איך זה נראה? איך זה מתנהג? אין לנו מושג.

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

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

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

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

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

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