Sunnyvale, קליפורניה - 26 באוקטובר 2022 - NTT Research הודיע כי מדען מטעם החברה מעבדת קריפטוגרפיה ואבטחת מידע (CIS). ועמית מה NTT מעבדות אינפורמטיקה חברתית (SIL) כתבו מאמר פורץ דרך על יתרון קוונטי. המאמר נבחר להצגה בסימפוזיון השנתי של IEEE על יסודות מדעי המחשב (FOCS), שמתקיים ב-31 באוקטובר עד נובמבר. 3 בדנבר.
המחברים השותפים של המאמר, שכותרתו "יתרון קוונטי ניתן לאימות ללא מבנה," הם ד"ר טאקאשי יאמאקאווה, חוקר מובהק ב-NTT SIL וד"ר מארק ז'אנדרי, מדען בכיר בתחום מחקר NTT מעבדת CIS. העבודה נעשתה בחלקה באוניברסיטת פרינסטון, שם ד"ר יאמאקאווה היה חוקר אורח וד"ר ז'אנדרי משמש גם כעוזר פרופסור למדעי המחשב.
הנושא של יתרון קוונטי (או מהירות קוונטית) מתייחס לסוגי הבעיות שמחשבים קוונטיים יכולים לפתור מהר יותר ממחשבים קלאסיים או לא קוונטיים ועד כמה הם מהירים יותר. הבעיות המדוברות מתוארות בדרך כלל כמחלקה פולינומית-זמן לא דטרמיניסטית (NP). כמה יתרון יכול להשתנות במידה רבה. מחשב קוונטי עשוי לפתור בעיה מסוימת בדקה או בשנייה שלוקח למחשב קלאסי בשבוע, או אולי פרק זמן אקספוננציאלי בלתי נתפס. במאמר זה, המחברים מתייחסים לאתגר של אימות עליונות זו, ולעשות זאת ביעילות. עד כה, הדגמות של יתרון קוונטי כללו "מבנה" משמעותי או תקשורת הלוך ושוב בין שני צדדים או יותר. פריצת הדרך של מאמר Yamakawa ו-Zhandry היא להדגים בעיה קשה של NP שבה אימות אפשרי ללא מבנה.
"זו הפעם הראשונה שראינו מהירות קוונטית אקספוננציאלית עבור בעיית חיפוש NP, שדורשת רק אורקל אקראי", אמר פרופסור למדעי המחשב באוניברסיטת טקסס באוסטין ד"ר סקוט אהרונסון, שהגיב על גרסה מוקדמת של המאמר במהלך סדנה ב-13 ביוני 2022, במכון סימונס לתורת המחשוב. על ידי דרישת אורקל אקראי בלבד, כלומר קופסה שחורה תיאורטית המייצרת תגובות אקראיות לכל שאילתה, Yamakawa וז'אנדרי בנו את הבעיה שלהם על הנחות חישוביות לא מובנות. ככזה, הבעיה שלהם מתיישרת יותר עם פונקציות חד-כיווניות במקום עם פונקציות מובנות, כמו אלו שנמצאות בהצפנת מפתח ציבורי. יישור חד-כיווני זה מאפשר אימות יעיל.
"מרגש לראות קריפטוגרפים הקשורים ל-NTT משתפים פעולה במחקר ששוב זוכה לתווית 'פריצת דרך', במיוחד במאמר המעשיר את ההבנה שלנו במחשוב קוונטי, תחום מיקוד נוסף עבורנו ב-NTT Research," אמר קזוהירו גומי. , נשיא ומנכ"ל NTT Research. "ברכות ואיחולים לכל המשתתפים בכנס IEEE היוקרתי הזה."
בעיית החיפוש של NP שיאמקאווה וז'אנדרי המציאו הייתה בעיה של שניים באחד שכרוכה במציאת 1) מחרוזת n-סמל שהיא מילת קוד של קוד נתון לתיקון שגיאות, ו-2) מחרוזת n-סמלים שבה כל הסמל ממופה לאפס מתחת לאורקל האקראי. כל בעיה בנפרד היא קלה. אבל למצוא מחרוזת אחת של סמלים שהיא גם מילת קוד וגם ממפה לאפס זה הרבה יותר קשה, לפחות באופן קלאסי. "אם אתה קוונטי, אתה יכול לפתור את זה בזמן פולינומי," אמר ד"ר ז'אנדרי, "אבל אם אתה קלאסי, לפחות אם אתה במודל הקופסה השחורה הזה, אתה צריך זמן אקספוננציאלי." מצד שני, בהינתן פתרון פוטנציאלי, קל לאמת אותו על ידי בדיקה שהוא פותר בנפרד כל אחת משתי הבעיות. שימו לב, כיאה למאמר עבור FOCS, עבודה זו היא בסיסית או בסיסית. כפי שצוין בהרצאתו של ד"ר אהרונסון במכון סימונס (שנדונה במחקר NTT זה בלוג המאמר), הטיעון Yamakawa-Zhandry נופל לסוג של העלאות מהירות שניתן לבדוק בקלות מתמטית, אך לא להדגים באופן מעשי על ידי מחשב קוונטי ממשי בזמן הקרוב. עם זאת, מעבר לתכנית האימות פורצת הדרך שלו, המאמר גם מצביע על משהו חדש הנוגע למידת המהירות הקוונטית.
"לפני העבודה שלנו, היו לנו דוגמאות ליתרון קוונטי לבעיות NP, כמו יצירת פקטורינג או, במסגרת הקופסה השחורה, מציאת תקופה. אבל מסתבר שהאלגוריתם הקוונטי שעמד בבסיס כל הדוגמאות הללו היה בעצם מציאת תקופה - אם כי המראה כיצד ליישם מציאת תקופה על דוגמאות אלו היה לרוב לא טריוויאלי", אמר ד"ר ז'אנדרי. "העיתון שלנו מראה שיש לפחות מקרה שני. אתה יכול לפרש את זה בצורה אופטימית כאילו יש תקווה שהיתרון הקוונטי נפוץ יותר ממה שאולי חשבנו קודם לכן".
בחסות הוועדה הטכנית של IEEE Computer Society on Mathematical Foundations of Computing (TCMF), FOCS הוא כנס מוביל בתחום מדעי המחשב התיאורטיים. הקריאה למסמכים עבור FOCS 2022, המפגש השנתי ה-63 כזה, רשמה את המחשוב הקוונטי כאחד מ-17 תחומי עניין כלליים. מאמר Yamakawa-Zhandry אמור להיות מוצג ב-31 באוקטובר 2022, בשעה 10:15 בבוקר MT. כדי ללמוד עוד על אירוע זה ולהירשם אליו, בקר באתר FOCS 2022 אתר אינטרנט.
