באילו מקרים ספציפיים מחשבים קוונטיים עולים על מקביליהם הקלאסיים? זו שאלה שקשה לענות עליה, בין השאר משום שהמחשבים הקוונטים של היום הם דברים קפדניים, נגועים בשגיאות שעלולות להיערם ולקלקל את החישובים שלהם.
לפי מידה אחת, כמובן, הם כבר עשו את זה. בשנת 2019, פיזיקאים בגוגל הודיע שהם השתמשו במכונה של 53 קיוביטים כדי להשיג עליונות קוונטית, אבן דרך סמלית המסמנת את הנקודה שבה מחשב קוונטי עושה משהו מעבר להישג ידו של כל אלגוריתם קלאסי מעשי. דומה הפגנות על ידי פיזיקאים מאוניברסיטת המדע והטכנולוגיה של סין הגיעו בקרוב.
אבל במקום להתמקד בתוצאה ניסיונית עבור מכונה מסוימת אחת, מדעני מחשבים רוצים לדעת האם אלגוריתמים קלאסיים יוכלו לעמוד בקצב ככל שמחשבים קוונטיים הולכים וגדלים. "התקווה היא שבסופו של דבר הצד הקוונטי פשוט מתרחק לגמרי עד שלא תהיה תחרות יותר", אמר סקוט אהרונסון, מדען מחשבים באוניברסיטת טקסס, אוסטין.
עדיין קשה לענות על השאלה הכללית הזו, שוב בין היתר בגלל הטעויות המציקות הללו. (מכונות קוונטיות עתידיות יפצו על חוסר השלמות שלהן באמצעות טכניקה הנקראת תיקון שגיאה קוונטית, אבל היכולת הזו עדיין רחוקה.) האם ניתן להשיג את היתרון הקוונטי המיוחל גם עם שגיאות לא מתוקנות?
רוב החוקרים חשדו שהתשובה שלילית, אבל הם לא הצליחו להוכיח זאת בכל המקרים. עכשיו, ב מאמר פורסם בשרת ה-preprint arxiv.org, צוות של מדעני מחשב עשה צעד גדול לקראת הוכחה מקיפה לכך שתיקון שגיאות נחוץ ליתרון קוונטי מתמשך בדגימת מעגלים אקראית - הבעיה המותאמת שגוגל השתמשה בה כדי להראות עליונות קוונטית. הם עשו זאת על ידי פיתוח אלגוריתם קלאסי שיכול לדמות ניסויי דגימת מעגלים אקראיים כאשר קיימות שגיאות.
"זו תוצאה תיאורטית יפה", אמר אהרונסון תוך שהוא מדגיש שהאלגוריתם החדש אינו שימושי באופן מעשי להדמיית ניסויים אמיתיים כמו זה של גוגל.
בניסויים של דגימת מעגלים אקראיים, החוקרים מתחילים עם מערך של קיוביטים, או ביטים קוונטיים. לאחר מכן הם מבצעים מניפולציות אקראית על הקיוביטים הללו עם פעולות הנקראות שערים קוונטיים. שערים מסוימים גורמים לזוגות של קיוביטים להסתבך, כלומר הם חולקים מצב קוונטי ואי אפשר לתאר אותם בנפרד. שכבות חוזרות ונשנות של שערים מביאות את הקיוביטים למצב סבוך יותר מסובך.
כדי ללמוד על המצב הקוונטי הזה, החוקרים מודדים את כל הקיוביטים במערך. זה גורם למצב הקוונטי הקולקטיבי שלהם לקרוס למחרוזת אקראית של ביטים רגילים - 0 ו-1. מספר התוצאות האפשריות גדל במהירות עם מספר הקיוביטים במערך: עם 53 קיוביטים, כמו בניסוי של גוגל, זה כמעט 10 קוואדריליונים. ולא כל המיתרים סבירים באותה מידה. דגימה ממעגל אקראי פירושה לחזור על מדידות כאלה פעמים רבות כדי לבנות תמונה של התפלגות ההסתברות שבבסיס התוצאות.
שאלת היתרון הקוונטי היא פשוט זו: האם קשה לחקות את התפלגות ההסתברות הזו עם אלגוריתם קלאסי שלא משתמש בשום הסתבכות?
ב 2019, חוקרים הוכיח שהתשובה היא כן עבור מעגלים קוונטיים נטולי שגיאות: אכן קשה לדמות קלאסית ניסוי דגימת מעגל אקראי כאשר אין שגיאות. החוקרים עבדו במסגרת תיאוריית המורכבות החישובית, המסווגת את הקושי היחסי של בעיות שונות. בתחום זה, החוקרים לא מתייחסים למספר הקיוביטים כמספר קבוע כמו 53. "תחשוב על זה כעל n, שזה מספר שהולך לגדול", אמר ארם הארו, פיזיקאי במכון הטכנולוגי של מסצ'וסטס. "אז אתה רוצה לשאול: האם אנחנו עושים דברים שבהם המאמץ הוא אקספוננציאלי n או פולינום ב n?" זוהי הדרך המועדפת לסווג את זמן הריצה של אלגוריתם - מתי n גדל מספיק, אלגוריתם שהוא אקספוננציאלי n מפגר הרבה מאחורי כל אלגוריתם שיש בו פולינום n. כאשר תיאורטיקנים מדברים על בעיה שקשה למחשבים קלאסיים אבל קלה למחשבים קוונטיים, הם מתכוונים להבחנה הזו: האלגוריתם הקלאסי הטוב ביותר לוקח זמן אקספוננציאלי, בעוד שמחשב קוונטי יכול לפתור את הבעיה בזמן פולינומי.
עם זאת, מאמר 2019 הזה התעלם מההשפעות של שגיאות שנגרמו משערים לא מושלמים. זה השאיר את המקרה פתוח של יתרון קוונטי עבור דגימת מעגל אקראית ללא תיקון שגיאות.
אם אתה מדמיין להגדיל ללא הרף את מספר הקיוביטים כפי שעושים תיאורטיקנים של מורכבות, ואתה גם רוצה לקחת בחשבון שגיאות, אתה צריך להחליט אם אתה גם הולך להמשיך להוסיף עוד שכבות של שערים - להגדיל את עומק המעגל, כפי שחוקרים אומרים. נניח שאתה שומר על עומק המעגל קבוע, למשל, בשלוש שכבות רדודות יחסית, ככל שאתה מגדיל את מספר הקיוביטים. אתה לא תקבל הרבה הסתבכות, והפלט עדיין יהיה זמין לסימולציה קלאסית. מצד שני, אם תגדיל את עומק המעגל כדי לעמוד בקצב הגדל והולך של קיוביטים, ההשפעות המצטברות של שגיאות שער ישטפו את ההסתבכות, והפלט יהפוך שוב לקל לדמות קלאסית.
אבל בין לבין שוכן אזור זהבה. לפני המאמר החדש, עדיין הייתה אפשרות שהיתרון הקוונטי יוכל לשרוד כאן, גם כשמספר הקיוביטים גדל. במקרה של עומק ביניים זה, אתה מגדיל את עומק המעגל באיטיות רבה ככל שמספר הקיוביטים גדל: למרות שהפלט יתדרדר בהתמדה על ידי שגיאות, עדיין עלול להיות קשה לדמות קלאסית בכל שלב.
העיתון החדש סוגר את הפרצה הזו. המחברים גזרו אלגוריתם קלאסי להדמיית דגימת מעגלים אקראית והוכיחו שזמן הריצה שלו הוא פונקציה פולינומית של הזמן הנדרש להפעלת הניסוי הקוונטי המתאים. התוצאה יוצרת קשר תיאורטי הדוק בין מהירות הגישות הקלאסיות והקוונטיות לדגימת מעגלים אקראית.
האלגוריתם החדש עובד עבור מחלקה עיקרית של מעגלי עומק בינוניים, אך ההנחות הבסיסיות שלו מתקלקלות עבור חלקים רדודים יותר, ומשאירים פער קטן שבו שיטות סימולציה קלאסיות יעילות אינן ידועות. אך מעטים החוקרים שמחזיקים בתקווה שדגימת מעגלים אקראית תתגלה כקשה לדמות קלאסית בחלון הדק שנותר הזה. "אני נותן לזה סיכויים די קטנים," אמר ביל פפרמן, מדען מחשבים באוניברסיטת שיקגו ואחד ממחבריו של מאמר התיאוריה משנת 2019.
התוצאה מרמזת שדגימת מעגלים אקראית לא תניב יתרון קוונטי לפי הסטנדרטים המחמירים של תיאוריית המורכבות החישובית. יחד עם זאת, זה ממחיש את העובדה שאלגוריתמים פולינומיים, שתיאורטיקנים של מורכבות מכנים אותם ללא הבחנה יעילים, אינם בהכרח מהירים בפועל. האלגוריתם הקלאסי החדש נהיה איטי יותר בהדרגה ככל ששיעור השגיאות יורד, ובשיעורי השגיאות הנמוכים שהושגו בניסויי עליונות קוונטית, הוא איטי מכדי להיות מעשי. ללא שגיאות, הוא מתקלקל לחלוטין, כך שתוצאה זו אינה סותרת שום דבר שחוקרים ידעו על כמה קשה לדמות קלאסית דגימת מעגלים אקראית במקרה האידיאלי, נטול שגיאות. סרג'יו בוישו, הפיזיקאי המוביל את מחקר העליונות הקוונטית של גוגל, אומר שהוא רואה במאמר "יותר אישור נחמד לדגימת מעגל אקראי מאשר כל דבר אחר".
בנקודה אחת, כל החוקרים מסכימים: האלגוריתם החדש מדגיש עד כמה תיקון שגיאות קוונטי יהיה מכריע להצלחה ארוכת הטווח של מחשוב קוונטי. "זה הפתרון, בסופו של יום", אמר פפרמן.
