מחשב קוונטי

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

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

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

רקע[עריכת קוד מקור | עריכה]

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

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

קיוביט[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – קיוביט

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

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

שערים קוונטיים[עריכת קוד מקור | עריכה]

Postscript-viewer-shaded.png ערך מורחב – שער קוונטי

במחשב קלאסי, הפעולות הבסיסיות שניתן לבצע על ביטים מיוצגות באמצעות שערים לוגיים, ואלו יכולים לממש כל פונקציה בוליאנית שהקלט שלה הוא מספר כלשהו של ביטים, והפלט שלה יכול להיות כל מספר אחר של ביטים. המנגנון המקביל במחשב קוונטי נקרא שער קוונטי, שער כזה יכול לממש כל אופרטור יוניטרי על מספר קיוביטים, והתוצאה שלו תהיה בת מספר זהה של קיוביטים. נהוג לייצג שערים קוונטיים כמטריצות יוניטריות, כאשר שער קוונטי הפועל על n קיוביטים ייוצג על ידי מטריצה מגודל 2^n\times 2^n (כאמור, מצב אוגר קוונטי המכיל n קיוביטים מיוצג על ידי וקטור ממימד 2^n).

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

חיפוש[עריכת קוד מקור | עריכה]

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

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

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

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

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

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

ראו גם[עריכת קוד מקור | עריכה]

קישורים חיצוניים[עריכת קוד מקור | עריכה]