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