מחשב קוונטי

מחשב קוונטי הוא מחשב המבצע עיבוד נתונים על "ביטים קוונטים" - qubits ומשתמש בתכונות של מכניקת הקוונטים על מנת לבצע עיבוד נתונים מקביל (מקביל, במובן של סופרפוזיציה) יעיל יותר. הוכח שישנן בעיות שמחשב קוונטי פותר במהירות ויעילות גבוהה יותר מאשר כל מחשב קלאסי רגיל.

תוכן עניינים

1 רקע
2 הכח החישובי של מודלים קוונטיים
3 ראו גם
4 קישורים חיצוניים

[עריכה] רקע

מקור מושג המחשב הקוונטי הוא בהבחנה הבאה, אשר הועלתה על ידי הפיזיקאי ריצ'רד פיינמן בשנת 1981. כאשר מנסים לחשב את חיזויי מכניקת הקוונטים עבור מערכות פיזיקליות גדולות, נראה שמחשב רגיל (הבנוי על פי מכניקה קלאסית) לא יכול לעשות זאת ביעילות בגלל המשאבים המעריכיים הנדרשים לייצוג פונקציית הגל. ואולם, הטבע עצמו הרי מבצע חישובים אלו, במובלע, כאשר המערכת הפיזיקאלית מתקיימת במציאות. מכאן, נראה שלטבע, הפועל על פי מכניקת הקוונטים, יש יתרון ביכולת החישוב שלו מול מחשב "קלאסי" (כלומר, מופרת תזת צ'רץ'-טיורינג הפיזיקאלית בגירסתה החזקה). אם כך, נוכל אולי לבנות סוג חדש של מחשב, המנצל אפקטים קוונטיים לביצוע חישוב באופן יעיל יותר. מחשב כזה יוכל לחשב את חיזויי מכניקת הקוונטים ביעילות - ואולי אף לבצע חישובים אחרים באופן יעיל יותר מכל מחשב "קלאסי".

על בסיס זה הוגדרו מודלים מדויקים של מחשבים קוונטים אשר פעולתם היא על פי חוקי מכניקת הקוונטים, ואשר התקווה היא כי ניתן יהיה לבנות מכונות העובדות לפי עקרונותיהם. כמו כן, נבחנה יכולת החישוב של מודלים חישוביים אלו, ונמצא כי הם אכן חזקים יותר מהמודלים ה-"קלאסיים" במובנים מסוימים.

המחשב הקוונטי מבוסס על איכסון של קיוביטים ופעולה עליהם, באנלוגיה למחשב קלאסי הפועל על ביטים. השוני בין השניים, ומקור הכוח הנוסף של המחשב הקוונטי, נובעים מתופעות הסופרפוזיציה והשזירה המתקיימות עבור קיוביטים.

[עריכה] הכח החישובי של מודלים קוונטיים

[עריכה] חיפוש

נניח שנרצה למצוא מספר העומד בקריטריון מסוים. לדוגמה, נאמר שקלטנו תשדורת המוצפנת בשיטת ההצפנה DES, ואנו מחפשים את מפתח ההצפנה, שהוא מספר אקראי שאורכו 56 ביטים. קל לבדוק אם מספר נתון הוא המפתח הנכון, אבל כדי למצוא את המפתח הנכון (באופן ישיר) נאלץ לבדוק $256$ אפשריות, וזהו תהליך ארוך מאד. אם ברשותנו מחשב קוונטי, נוכל לתכנת אותו לפתור את בעיית החיפוש באופן יעיל יותר. ניקח 56 קיוביטים, ונפעיל עליהם פעולה אשר תביא אותם למצב של סופרפוזיציה אחידה של כל $256$ האפשרויות. כעת נורה למחשב לבדוק את נכונות המפתח, ועפ"י עקרון הסופרפוזיציה הוא יעשה זאת במקביל עבור כל המפתחות האפשריים, באותו זמן שמחשב קלאסי היה דורש לביצוע בדיקה עבור מפתח בודד.

במבט ראשון נראה שהשגנו שיפור אדיר במהירות (מעריכי באורך המפתח שמחפשים). ואולם, נשאר אתגר נוסף - כיצד נחלץ את המפתח הנכון, כלומר זה שעבורו הבדיקה הצליחה, מתוך הסופרפוזיציה? בשנת 1996 גילה לוב גרובר אלגוריתם המאפשר לעשות זאת בעזרת כ- $228$ פעולות קוונטיות (ובאופן כללי $2 k / 2$ פעולות, כאשר $k$ הוא אורך המפתח). מסתבר שבאופן כללי, לא ניתן לבצע את החיפוש מהר יותר, כלומר, למחשב הקוונטי יש יתרון (ריבועי) על פני מחשב קלאסי בפתרון בעייות חיפוש כלליות, אך לא יותר מכך.

[עריכה] מציאת גורמים ראשוניים

אחת הבעיות החשובות שניתנות לפתרון באמצעות מחשב קוונטי היא מציאת הגורמים הראשוניים של מספר גדול. הדבר חשוב בין השאר כי משמעו שמי שברשותו מחשב קוונטי יוכל לפצח את שיטת ההצפנה RSA: בהצפנת RSA המפתח הסודי הוא שני מספרים ראשוניים גדולים מאוד $p$ ו- $q$ , ורק מכפלתם $N = p \times q$ מתפרסמת. השערה מקובלת היא שהחישוב ההפוך, כלומר מציאת הגורמים הסודיים $p$ ו- $q$ בהינתן מכפלתם N, מהווה בעיה שאינו ניתנת לפתרון יעיל במחשב קלאסי. בטיחות שיטת ההצפנה מסתמכת על קושי זה. ב-1994 פיתח מדען המחשב פיטר שור אלגוריתם למציאת גורמים ראשוניים של מספר נתון. הוא עשה זאת על ידי המרה של בעיית הפירוק לגורמים לבעיה של מציאת מחזור עבור פונקציה מסוימת, והראה שמחשב קוונטי יכול למצוא את המחזור ביעילות רבה (בעזרת גרסה קוונטית של התמרת פורייה). הרעיון הוא שמחשב קוונטי "רואה" בו זמנית את כל נקודות הפונקציה ולכן יכול לבצע התאבכות על מנת לקבל את המחזור של הפונקציה.

[עריכה] מגבלות עקרוניות

למרות שידועות בעיות שמחשב הקוונטי יכול לפתור ביעילות גדולה יותר ממחשב קלאסי, יכולתו של מחשב קוונטי אינה בלתי מוגבלת והוא אינו "פתרון קסם" לכל בעיה חישובית. בראש ובראשונה, ידוע כי ההבדל העקרוני בין מחשבים קוונטיים וקלאסיים הוא ביעילות (דהיינו, סיבוכיות) בלבד; כלומר, כל בעיה הניתנת לפתרון על מחשב קוונטי ניתנת לפתרון גם כל מחשב רגיל, אם כי ייתכן שהדבר ידרוש משאבים גדולים יותר. גם הפרש היעילות אינו שרירותי - הוא לכל היותר מעריכי, וישנן בעיות אותן מחשב קוונטי אינו יכול לפתור באופן יעיל הרבה יותר ממחשב קלאסי. לא ידוע אם מחשב קוונטי מסוגל לפתור בעיות NP-שלמות בזמן ריצה פולינומי, ומדענים רבים משערים שאין כך הדבר.