מחשבים קוונטיים, המשתמשים בקיוביטים מגוונים, נמצאים בחזית הפתרון של בעיות אופטימיזציה מורכבות כמו דילמת איש המכירות הנוסע, הנגועה באופן מסורתי בחוסר יעילות חישובית. באמצעות ניתוח מתמטי קפדני, חוקרים הוכיחו כי מחשוב קוונטי יכול לשנות באופן מהותי את פתרון הבעיות, להציע עלייה פולינומית יעילה יותר בזמן החישוב בהשוואה לשיטות קלאסיות ולהניב פתרונות מעולים.
בעיית איש המכירות הנוסע נחשבת לדוגמא מצוינת לבעיית אופטימיזציה קומבינטורית. כעת, צוות ברלינאי בראשות הפיזיקאי התיאורטי פרופ' ד"ר ג'נס אייזרט מ-Freie Universität Berlin ו-HZB הראה שניתן לפתור סוג מסוים של בעיות כאלה בצורה טובה יותר ומהירה הרבה יותר עם מחשבים קוונטיים מאשר בשיטות קונבנציונליות.
מחשבים קוונטיים משתמשים במה שנקרא qubits, שהם לא אפס או אחד כמו במעגלים לוגיים קונבנציונליים, אבל יכולים לקבל כל ערך ביניהם. הקיוביטים הללו מתממשים על ידי אטומים, יונים או מעגלים מוליכים-על מקוררים מאוד, ועדיין זה מאוד מורכב מבחינה פיזיקלית לבנות מחשב קוונטי עם קיוביטים רבים. עם זאת, ניתן כבר להשתמש בשיטות מתמטיות כדי לחקור מה מחשבים קוונטיים סובלני תקלות יכולים להשיג בעתיד.
"יש הרבה מיתוסים על זה, ולפעמים כמות מסוימת של אוויר חם והייפ. אבל ניגשנו לנושא בקפדנות, תוך שימוש בשיטות מתמטיות, וסיפקנו תוצאות מוצקות בנושא. מעל לכל, הבהרנו באיזה מובן יכולים להיות יתרונות בכלל", אומר פרופ' ד"ר ינס אייזרט, העומד בראש קבוצת מחקר משותפת ב-Freie Universität Berlin וב-Helmholtz-Zentrum Berlin.
הבעיה של איש המכירות הנודד היא קלאסיקה במתמטיקה. על מטייל לבקר ב-N ערים במסלול הקצר ביותר ולחזור לנקודת ההתחלה. ככל שהמספר N עולה, מספר המסלולים האפשריים מתפוצץ. לאחר מכן ניתן לפתור בעיה זו באמצעות שיטות קירוב. מחשבים קוונטיים יכולים לספק פתרונות טובים משמעותית במהירות רבה יותר. קרדיט: HZB
טיפול בבעיות מורכבות
הבעיה הידועה של המוכר הנוסע משמשת דוגמה מצוינת: נוסע צריך לבקר במספר ערים ואז לחזור לעיר הולדתו. מהו המסלול הקצר ביותר? למרות שקל להבין את הבעיה הזו, היא הופכת מורכבת יותר ויותר ככל שמספר הערים גדל וזמן החישוב מתפוצץ.
בעיית אנשי המכירות הנוסעים היא קבוצה של בעיות אופטימיזציה בעלות חשיבות כלכלית עצומה, בין אם הן כוללות רשתות רכבת, לוגיסטיקה או אופטימיזציה של משאבים. ניתן למצוא פתרונות מספיק טובים באמצעות שיטות קירוב.
העבודה הנוכחית (חץ) מראה שניתן לפתור חלק מסוים מהבעיות הקומבינטוריות הרבה יותר טוב עם מחשבים קוונטיים, אולי אפילו בדיוק. קרדיט: HZB/Eisert
פתרונות קוונטיים והתקדמות
הצוות בראשות Jens Eisert ועמיתו ז'אן פייר סייפרט השתמש כעת בשיטות אנליטיות גרידא כדי להעריך כיצד מחשב קוונטי עם קיוביטים יכול לפתור סוג זה של בעיות. ניסוי מחשבתי קלאסי עם עט ונייר והרבה מומחיות.
"אנחנו פשוט מניחים, ללא קשר להבנה הפיזית, שיש מספיק קיוביטים ובוחנים את האפשרויות לבצע איתם פעולות מחשוב", מסביר וינסנט אוליטש, סטודנט לתואר שלישי באוניברסיטה הטכנית של ברלין. בכך הם חשפו קווי דמיון לבעיה ידועה בקריפטוגרפיה, כלומר הצפנת נתונים. "הבנו שאנחנו יכולים להשתמש באלגוריתם Shor כדי לפתור תת-סיווג של בעיות האופטימיזציה האלה", אומר Ulitzsch.
המשמעות היא שזמן המחשוב כבר לא "מתפוצץ" עם מספר הערים (מעריכי, 2נ), אבל רק גדל באופן פולינומי, כלומר עם Nאיקס, כאשר x הוא קבוע. הפתרון המתקבל בדרך זו הוא גם מבחינה איכותית הרבה יותר טוב מהפתרון המשוער באמצעות האלגוריתם המקובל.
"הראינו שלסוג ספציפי אך חשוב מאוד ורלוונטי מעשית של בעיות אופטימיזציה קומבינטורית, למחשבים קוונטיים יש יתרון מהותי על פני מחשבים קלאסיים למקרים מסוימים של הבעיה", אומר Eisert.
