אלגוריתם שור למחשב קוונטי
27/03/2022
מחשבים קוונטיים צפויים להיות שימושיים למחקר של מערכות קוונטיות, אך לא רק: נראה שהם יוכלו לבצע הרבה יותר מהר ממחשב רגיל גם פעולות שלכאורה אינן קשורות כלל לפיזיקה קוונטית, כמו שבירת צפנים.
מאת: נעה פלדמן, דוקטורנטית לפיזיקה באוניברסיטת תל-אביב
רבים מדברים על היתרונות של המחשב הקוונטי ועל כך שהוא יוכל לבצע פעולות שמחשב רגיל לא יוכל לבצע. גם כאן כתבנו בעבר על המחשב הקוונטי ועל יתרונותיו הצפויים [1]. אבל מהן הפעולות שהמחשב יוכל לבצע? איפה בדיוק טמונים היתרונות שלו?
פעולה טבעית ראשונה של מחשב קוונטי היא הדמיה (סימולציה) של מערכות קוונטיות בטבע - כמו גבישים, מולקולות מורכבות או הולכה חשמלית. מערכות בעלות תכונות קוונטיות הן קשות מאוד להדמיה באמצעות מחשב קלאסי. הדמיה היא כלי חשוב במחקר, לכן מחשבים קוונטיים צפויים לתרום רבות למחקר של חומרים חדשניים, תרופות סינתטיות ועוד. זוהי פעולה טבעית, או צפויה יחסית, של מחשבים קוונטיים.
אבל מתברר שמחשב קוונטי צפוי להיות שימושי גם בפעולות שלכאורה אינן קשורות כלל למערכות קוונטיות. היתרון של מחשב קוונטי שנתמקד בו כאן טמון בתכונות הגליות של חלקיקים קוונטיים [2]. מערכת קוונטית ניתנת לתיאור על ידי פונקציית גל, שנקראת כך משום שההתנהגות שלה מוכתבת על ידי משוואת גלים. אחת התכונות המעניינות של אותה משוואת גלים היא הלינאריות שלה, כלומר: עבור כל שני פתרונות של המשוואה, סכום, הפרש והכפלה שלהם בקבוע יהיו גם הם פתרונות למשוואה. אם ניקח שני גלים "ונחבר" אותם, אז במקומות מסוימים הגלים יחזקו זה את זה (התאבכות בונה), ואילו במקומות אחרים הגלים יחלישו זה את זה (התאבכות הורסת). התכונות הגליות מנוצלות, באופן מפתיע, לשבירת הצפנת RSA.
הצפנת RSA (ריבסט-שמיר-אדלמן) נמצאת כיום בשימוש נרחב, ובין השאר משמשת להצפנה של סיסמאות לאתרי אינטרנט, מיילים והודעות. ההצפנה מסתמכת על עיקרון פשוט: קל לכפול שני מספרים ראשוניים זה בזה, אבל לפרק מספר לגורמים הראשוניים שלו זו משימה קשה. המבנה המתמטי של מספרים טבעיים מאפשר לנו "להחביא" כך מפתחות הצפנה. ההצפנה מבוססת על תורה מתמטית שנקראת תורת החבורות, והיא מסתמכת על המחזוריות של פעולת כפל מיוחדת, שנקראת כפל-מודולו. בכפל-מודולו מכפילים שני מספרים זה בזה, מחלקים את התוצאה במספר שלישי, ולוקחים את השארית של התוצאה. לדוגמה, בשעון מחוגים אנו משתמשים בחשבון מודולו-12. אם ניקח את השעה חמש, ונכפיל אותה בשלוש (כלומר, נזיז את המחוג שלוש פעמים בחמש שעות), נקבל את השעה שלוש, שזאת בדיוק השארית של 15 כשמחלקים אותו ב-12. בהצפנה, המסרים המוצפנים מיוצגים כמספרים. אם נדע בדיוק באיזה מספר לכפול את ההודעה המוצפנת, נשלים מחזור שלם של פעולת כפל-מודולו ונקבל את ההודעה המקורית. כדי לדעת באיזה מספר צריך לכפול בדיוק, צריך לחלק מספר גדול לגורמים.
אפשר לתת דוגמה לכפל-מודולו: נניח שההודעה המקורית שלנו מקודדת כמספר 4, ופעולת המודולו מוגדרת על ידי 7. נבצע פעולות של כפל ב-4 ולקיחת שארית התוצאה מחלוקה ב-7.
צעד ראשון: 4x4=16. נחסיר את הכפולה הקרובה ביותר של 7, שהיא 14, ונקבל 2.
צעד שני: 2x4=8. נחסיר את הכפולה הקרובה ביותר של 7, שהיא 7, ונקבל 1.
צעד שלישי: 1x4=4. נחסיר את הכפולה הקרובה ביותר של 7, שהיא 0, ונקבל שוב 4.
קיבלנו מחזוריות של 3 כי אחרי שנחזור על הפעולה שלוש פעמים, נקבל את התוצאה שהייתה לנו בהתחלה. כך, אם קיבלנו מסר שהוצפן על ידי מכפלה אחת, נצטרך לכפול פעמיים כדי לקבל את התוצאה. כפל, כאמור, הוא משימה קלה, אז החלק הקשה הוא לדעת כמה פעמים לכפול כדי לפענח את המסר המוצפן. כשהמחזוריות גדולה מאוד (גדולה בהרבה מ-3), מציאת המספר המדויק הנדרש לכפל נעשית משימה מסובכת, ולכן אי אפשר למצוא את המספר שמייצג את ההודעה המקורית.
היכולת לפרק מספרים גדולים לגורמים תאפשר פענוח של כל ההודעות המוצפנות באמצעות RSA. הדרך היחידה הידועה כיום לעשות זאת דורשת כמות בלתי אפשרית של פעולות חישוב עבור מספרים גדולים מאוד.
פירוק מספר לגורמיו הראשוניים הוא פעולה קשה עבור מחשב רגיל, אבל נראה שהיא טבעית בהרבה עבור מחשב קוונטי. ב-1994 הציע מדען בשם פיטר שור אלגוריתם המאפשר פירוק של מספר גדול לגורמים שלו באמצעות מספר פעולות סביר למדי, שיעבוד קצת יותר משליש מהפעמים. העיקרון המרכזי של האלגוריתם הוא כזה: כמו שראינו למעלה, הצפנת RSA מתבססת על מחזוריות. מחשב רגיל אינו מתבסס על מחזוריות בפעולתו, אבל גלים, כלומר מערכות קוונטיות, דווקא כן. המחשב הקוונטי מוצלח מאוד בזיהוי של מחזוריות בפעולות מסוימות בגלל התכונות הגליות שלו. האלגוריתם משתמש בפעולה מתמטית שנקראת פירוק פורייה [3], שמפרקת פונקציה לרכיבים ה"גליים" שלה, כלומר לרכיבים שיש בהם מחזוריות. הפעולה הזו, מתברר, טבעית מאוד עבור מחשב קוונטי.
האלגוריתם של שור מדגים פעולה שלכאורה אינה קשורה לקוונטים בכלל, ובכל זאת מחשב קוונטי צפוי לעשות אותה בצורה טובה בהרבה מאשר מחשב רגיל. זוהי דוגמה מרכזית להבטחות הטמונות במחשב קוונטי ולאפשרויות שייפתחו באמצעותו.
אה, ואל דאגה - המחשבים הקוונטיים הקיימים היום הם קטנים מאוד, ויכולים אולי לפרק את 21 לגורמים שלו, 7 ו-3… ייקח זמן רב עד שנגיע למחשבים גדולים ומדוייקים מספיק בשביל לשבור את ההצפנות של המידע החשוב שלנו. שיטות הצפנה שיהיו חסינות גם למחשב קוונטי כבר נמצאות בפיתוח, כך שמבחינה זו אפשר לישון בשקט.
עריכה: שיר רוזנבלום-מן
מקורות לקריאה נוספת:
[2] פוסט על פונקציית הגל בבלוג שלי
