מחשב קוונטי – הבדלי גרסאות

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

סופרפוזיציה של קיוביט בודד מיוצגת על ידי - <math>\alpha |0\rangle + \beta |1\rangle</math> כאשר המשמעות היא שבעת [[בעיית המדידה|מדידה קוונטית]] יש הסתברות של <math>|\alpha |^2</math> למצוא את הקיוביט במצב 0 והסתברות של <math>|\beta |^2</math> למצוא את הקיוביט במצב 1. כיוון שניתן למצוא את הקיוביט רק באחד מבין שני המצבים, <math>\alpha,\ \beta</math> שהם [[מספר מרוכב|מספרים מרוכבים]], מקיימים <math>|\alpha |^2 + |\beta |^2 = 1</math>. קיוביט בודד מיוצג לצרכים תאורטיים על ידי שני מספרים מרוכבים, ולכן יכול לכאורה לייצג כמות אינסופית של מידע. אכן ניתן לבצע חישובים ומניפולציות שונות על קיוביט המייצג סופרפוזיציה בין מספר מצבים, אך בסופו של דבר [[בעיית המדידה|מדידה קוונטית]] שלו תגרום לקריסה של [[פונקציית גל|פונקציית הגל]] ולאחריה במקום סופרפוזיציה של שני המצבים יתקבל מצב אחד ויחיד. תכונה זו של סופרפוזיציה מאפשרת לבצע חישובים בצורה שונה מהאופן שבו הם מתבצעים במחשב קלאסי, ועם זאת קריסת פונקציית הגל בעת המדידה מגבילה את העצמה החישובית.

== הכח החישובי של מודלים קוונטיים ==

נניח שנרצה למצוא מספר העומד בקריטריון מסוים. לדוגמה, נאמר שקלטנו תשדורת המוצפנת בשיטת ההצפנה [[DES]], ואנו מחפשים את מפתח ההצפנה, שהוא מספר אקראי שאורכו 56 [[סיבית|ביטים]]. קל לבדוק אם מספר נתון הוא המפתח הנכון, אבל כדי למצוא את המפתח הנכון (באופן ישיר) נאלץ לבדוק <math>2^{56}</math> אפשריות, וזהו תהליך ארוך מאד. אם ברשותנו מחשב קוונטי, נוכל לתכנת אותו לפתור את בעיית החיפוש באופן יעיל יותר. ניקח 56 [[קיוביט|קיוביטים]]ים, ונפעיל עליהם פעולה אשר תביא אותם למצב של [[סופרפוזיציה]] אחידה של כל <math>2^{56}</math> האפשרויות. כעת נורה למחשב לבדוק את נכונות המפתח, ועפ"י עקרון הסופרפוזיציה הוא יעשה זאת '''במקביל''' עבור כל המפתחות האפשריים, באותו זמן שמחשב קלאסי היה דורש לביצוע בדיקה עבור מפתח בודד.

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

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