מחשב קוונטי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בוט: מעביר קישורי בינויקי לויקינתונים - d:q176555 |
מ ←חיפוש: הגהה |
||
שורה 25:
נניח שנרצה למצוא מספר העומד בקריטריון מסוים. לדוגמה, נאמר שקלטנו תשדורת המוצפנת בשיטת ההצפנה [[DES]], ואנו מחפשים את מפתח ההצפנה, שהוא מספר אקראי שאורכו 56 [[ביט|ביטים]]. קל לבדוק אם מספר נתון הוא המפתח הנכון, אבל כדי למצוא את המפתח הנכון (באופן ישיר) נאלץ לבדוק <math>2^{56}</math> אפשריות, וזהו תהליך ארוך מאד. אם ברשותנו מחשב קוונטי, נוכל לתכנת אותו לפתור את בעיית החיפוש באופן יעיל יותר. ניקח 56 [[קיוביט|קיוביטים]], ונפעיל עליהם פעולה אשר תביא אותם למצב של [[סופרפוזיציה]] אחידה של כל <math>2^{56}</math> האפשרויות. כעת נורה למחשב לבדוק את נכונות המפתח, ועפ"י עקרון הסופרפוזיציה הוא יעשה זאת ''במקביל'' עבור כל המפתחות האפשריים, באותו זמן שמחשב קלאסי היה דורש לביצוע בדיקה עבור מפתח בודד.
במבט ראשון נראה שהשגנו שיפור אדיר במהירות ([[פונקציה מעריכית|מעריכי]] באורך המפתח שמחפשים). ואולם, נשאר אתגר נוסף - כיצד נחלץ את המפתח הנכון, כלומר זה שעבורו הבדיקה הצליחה, מתוך הסופרפוזיציה? בשנת [[1996]] פיתח [[לוב גרובר]] [[אלגוריתם גרובר|אלגוריתם חיפוש קוונטי]] המאפשר לעשות זאת בעזרת כ-<math>2^{28}</math> פעולות קוונטיות (ובאופן כללי <math>2^{k/2}</math> פעולות, כאשר <math>k</math> הוא אורך המפתח). מסתבר שבאופן כללי, לא ניתן לבצע את החיפוש מהר יותר, כלומר, למחשב הקוונטי יש יתרון (ריבועי) על פני מחשב קלאסי בפתרון
=== מציאת גורמים ראשוניים ===
| |||