מחשב קוונטי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 רקע
2 יישומים
- 2.1 חיפוש
- 2.2 מציאת גורמים ראשוניים
3 מגבלות עקרוניות
4 ראו גם

[עריכה] רקע

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

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

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

[עריכה] יישומים

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

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

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

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

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

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

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