בשנת 1994, מתמטיקאי הבין איך לגרום למחשב קוונטי לעשות משהו שאף מחשב קלאסי רגיל לא יכול. העבודה חשפה כי באופן עקרוני, מכונה המבוססת על כללי מכניקת הקוונטים יכולה לפרק ביעילות מספר רב לגורמים העיקריים שלה - משימה כה קשה עבור מחשב קלאסי שהיא מהווה בסיס לחלק גדול מאבטחת האינטרנט של ימינו.
גל של אופטימיות הגיע בעקבותיו. אולי, חשבו החוקרים, נוכל להמציא אלגוריתמים קוונטיים שיכולים לפתור מגוון עצום של בעיות שונות.
אבל ההתקדמות נעצרה. "זה היה מסלול קצת מבאס," אמר ריאן אודונל מאוניברסיטת קרנגי מלון. "אנשים אמרו, 'זה מדהים, אני בטוח שנקבל כל מיני אלגוריתמים מדהימים אחרים'. לא." מדענים גילו העלאות מהירות דרמטיות רק עבור מחלקה אחת וצרה של בעיות מתוך מערכת סטנדרטית נקרא NP, כלומר היו להם פתרונות הניתנים לאימות ביעילות - כמו פקטורינג.
זה היה המצב במשך כמעט שלושה עשורים. ואז באפריל, חוקרים בדוי סוג חדש ביסודו של בעיה שמחשב קוונטי אמור להיות מסוגל לפתור באופן אקספוננציאלי מהר יותר ממחשב קלאסי. זה כרוך בחישוב התשומות לתהליך מתמטי מסובך, המבוסס רק על התפוקות המבולבלות שלו. טרם נקבע אם הבעיה עומדת בפני עצמה או שהיא הראשונה בגבול חדש של רבים אחרים.
"יש תחושה של התרגשות", אמר Vinod Vaikuntanathan, מדען מחשבים במכון הטכנולוגי של מסצ'וסטס. "הרבה אנשים חושבים על מה עוד יש שם בחוץ."
מדעני מחשב מנסים להבין מה מחשבים קוונטיים עושים טוב יותר על ידי לימוד מודלים מתמטיים המייצגים אותם. לעתים קרובות, הם מדמיינים מודל של מחשב קוונטי או קלאסי בשילוב עם מכונת חישוב אידיאלית הנקראת אורקל. אורקל הם כמו פונקציות מתמטיות פשוטות או תוכנות מחשב, הקולטות קלט ויורקות פלט שנקבע מראש. ייתכן שיש להם התנהגות אקראית, כשהם מוציאים "כן" אם הקלט נופל בטווח אקראי מסוים (נניח, 12 עד 67) ו"לא" אם לא. או שהם עשויים להיות תקופתיים, כך שקלט בין 1 ל-10 מחזיר "כן", 11 עד 20 מניב "לא", 21 עד 30 מייצר שוב "כן", וכן הלאה.
נניח שיש לך אחד מהאורקלים התקופתיים האלה ואתה לא יודע את התקופה. כל מה שאתה יכול לעשות הוא להזין אותו במספרים ולראות מה הוא מוציא. עם אילוצים אלה, באיזו מהירות יכול מחשב למצוא את המחזור? בשנת 1993, דניאל סיימון, אז באוניברסיטת מונטריאול, מצא שאלגוריתם קוונטי יכול לחשב את התשובה לבעיה הקשורה קרובה מהר יותר באופן אקספוננציאלי מכל אלגוריתם קלאסי.
התוצאה אפשרה לסיימון לקבוע את אחד הרמזים הראשונים היכן ניתן לצפות לעליונות דרמטית עבור מחשבים קוונטיים. אבל כשהגיש את מאמרו לכנס מוביל, הוא נדחה. עם זאת, העיתון עניין חבר זוטר בוועדת התוכנית של הכנס - פיטר שור, שבאותו זמן היה במעבדות בל בניו ג'רזי. שור המשיך ומצא שהוא יכול להתאים את האלגוריתם של סיימון לחישוב התקופה של אורקל, אם יש לו כזה. ואז הוא הבין שהוא יכול להתאים את האלגוריתם שוב, כדי לפתור משוואה שמתנהגת בדומה לאורקל מחזורי: המשוואה שמתארת פקטורינג, שהיא מחזורית.
התוצאה של שור הייתה היסטורית. האלגוריתם הקוונטי שגילה יכול לצמצם במהירות מספרים ענקיים לגורמים הראשוניים המרכיבים אותם, דבר שאף אלגוריתם קלאסי ידוע לא יכול לעשות. בשנים שלאחר מכן, חוקרים גילו אלגוריתמים קוונטיים יעילים אחרים. חלקם, כמו האלגוריתם של שור, אפילו סיפקו יתרון אקספוננציאלי, אבל אף אחד לא יכול היה להוכיח יתרון קוונטי דרמטי בכל בעיה NP שאינה תקופתית.
המחסור הזה בהתקדמות הוביל שני מדעני מחשבים, סקוט אהרונסון מאוניברסיטת טקסס, אוסטין, ו אנדריס אמביניס של אוניברסיטת לטביה, לבצע תצפית. הוכחות ליתרון קוונטי תמיד נראו תלויות באורקלים בעלי איזשהו מבנה לא אקראי, כגון מחזוריות. בשנת 2009, הם השערה שלא יכלו להיות מהירות דרמטית בבעיות NP שהן אקראיות או לא מובנות. אף אחד לא הצליח למצוא חריג.
ההשערה שלהם שמה גבול לכוחותיהם של מחשבים קוונטיים. אבל הוא אמר רק שלא היו מהירות דרמטית עבור סוג מסוים של בעיית NP לא מובנית - אלה עם תשובות כן או לא. אם בעיה הייתה כרוכה במציאת תשובות ספציפיות יותר, כמותיות, הידוע כבעיית חיפוש, ההשערה לא חלה.
עם זה בחשבון, חוקרים טאקאשי יאמאקאווה של NTT מעבדות אינפורמטיקה חברתית ו מארק ז'אנדרי מ-NTT Research ואוניברסיטת פרינסטון החליטו להתנסות בבעיית חיפוש ספציפית, שהוצגה ב-2005 על ידי עודד רגב.
תארו לעצמכם קבוצה של שבשבת מזג אוויר שכולן מצביעות לאותו כיוון. תן לכל אחד מהם דחיפה מדודה, ואז תן לרוח סוערת להשפיע על הכיוון שלו. רגב רצתה לקבוע, על סמך הכיוונים הסופיים שלהם, לאן כולם הצביעו בתחילה. בעיות כאלה נקראו "למידה עם שגיאות", מכיוון שהדחיפה והרוח פועלות כמקור לטעות אקראית בכיוון המקורי. ישנן עדויות לכך שקשה לפתור הן עבור אלגוריתמים קלאסיים והן עבור אלגוריתמים קוונטיים.
יאמאקאווה וז'אנדרי שיפרו את ההגדרה. הם שינו את החוזק של הדחיפות ההתחלתיות הללו, והפכו אותן לצפויות יותר. הם גם גרמו לכך שהרוח נקבעה על ידי אורקל אקראי, כך שהיא הייתה אפילו יותר אקראית במקרים מסוימים אך רדומה לחלוטין במקרים אחרים.
עם השינויים הללו, החוקרים גילו שאלגוריתם קוונטי יכול למצוא ביעילות את הכיוון הראשוני. הם גם הוכיחו שכל אלגוריתם קלאסי חייב להיות איטי יותר בגורם אקספוננציאלי. כמו שור, לאחר מכן הם התאימו את האלגוריתם שלהם כדי לפתור גרסה אמיתית של הבעיה, המחליפה את האורקל במשוואה מתמטית ממשית.
מדעני מחשבים עדיין עובדים כדי להבין ולבנות את הבעיה. Vaikuntanathan משווה אותו לאחד אחר שמתעורר בעת ביצוע דחיסת נתונים: כאשר מידע נדחס למטה, ניתן לסחוט בטעות שני ביטים לאותו מקום, ולדרוס אותם. הבעיה של חיזוי התנגשויות אלה מראש, כדי שתוכל להימנע מהן, מזכירה דמיון מסוים. "זה סוג של בעיות שבעצם נראות ככה", אמר. "אולי ניתן לפתור את הבעיות האלה באופן קוונטי."
היו תקוות שבעיה לא מובנית כמו זו החדשה עשויה להיות פתירה אפילו בגרסאות החדשות של מחשבים קוונטיים, ובכך לספק אמצעי לבחון אותם. המחשבה הייתה שבעיות לא מובנות עשויות לדרוש פחות משאבים לתכנת, או להיות פחות רגישות לרעש, מכיוון שהן כבר אקראיות. אבל עד כה, הבעיה החדשה עדיין נראית מתקדמת מכדי לפתור מחשבים קוונטיים קיימים. "זו בעיה מוזרה. לא חשבתי להגדיר את זה", אמר אהרונסון. "אבל בדיעבד, יש לו כמה תכונות נחמדות מאוד."
התוצאה מספקת דוגמה ראשונה ליתרון קוונטי דרמטי בבעיית NP לא מובנית. האם יכולות להיות בעיות רבות אחרות שהעולם הקוונטי משתנה מבלתי פתיר כמעט לפתיר? עכשיו יש עוד סיבה לחשוב כך.
"זה קצת הפך את האמונות שלנו לגבי סוגי הבעיות שבהם מחשבים קוונטיים יכולים להיות טובים", אמר אודונל.
