בתשובה לאיזי נבו, 23/05/04 12:55
 |
|
 |
||
|
||||
 |
האם ההסבר הבא נכון? הטריק של המחשב הקוונטי הוא שהוא יכול לבצע הרבה מאוד פעולות בו זמנית. כשם שמכניקת הקוונטים מייצגת את האלקטרון ע"י "ענן הסתברות" המתאר את האפשרות של האלקטרון להיות בכל מקום בענן בהסתברות המתאימה, כך המחשב הקוונטי יכול לתאר כל משתנה ע"י "ענן הסתברות" המתאר את האפשרות של המשתנה להיות בעל ערך מסויים בהסתברות המתאימה. ביצוע מכפלה של משתנים כאלו שקול לביצוע כל המכפלות של כל הערכים האפשריים. הבעיה היא רק כיצד מתוך כל המכפלות האפשריות הקיימות בפוטנציה לגרום לפונקציית הגל לקרוס דוקא על המכפלה המעניינת אותנו. |
 |
 |
 |
|
|
|
||
|
||||
|
כבר שמעתי את ההסבר הנ''ל יותר מפעם אחת ואפשר להגיד שיש בזה משהו. הבעיה היא למצוא דרך לגרום לפונקציית הגל לקרוס לתוצאה הרצויה, וזה בד''כ בלתי אפשרי. מה שכן אפשרי זה לגרום לפונקציית הגל לקרוס קודם כל לתוך תת-מרחב של המצבים האפשריים, שכולל את התשובה הנכונה, ואז יש הסתברות לא רעה שבמדידה מלאה נקבל את התשובה הנכונה, ואם לא, נחזור על התהליך שוב. תהליך כזה דורש שבדיקת הנכונות של התשובה הוא קל - למשל פרוק נכון לגורמים קל לאימות. |
|
|
|
|
|
|
||
|
||||
|
כלומר, מחשב trial and error? משהו כמו מחשבי הירי בטנקים הצה"ליים? | |
|
|
|
|
|
||
|
||||
|
האלגוריתם כולל בדיקה של נכונות וחזרה על החישוב במקרה הצורך. האלגוריתמים הידועים כיום הם כאלו שבזמן סביר יתנו תשובה נכונה בהסתברות יותר טובה מהסיכוי שלך לשרוד עד מתן התשובה. (שמעתי כבר את ההשוואה - הסיכוי לתשובה שגויה הוא קטן מהסיכוי שיפול על המחשב אסטרואיד) |
|
|
|
|
|
|
||
|
||||
|
שוב אנחנו חוזרים לבעייה המקורית, תת-מרחב הפתרונות האפשריים הוא כל כך גדול שבדיקה שלהם תקח ימבה זמן ועד שנמצא את התשובה הנכונה כבר אפשר יהייה לצעוד לירח ובחזרה (עד אז יבנו שביל להולכי רגל). | |
|
|
|
|
|
||
|
||||
|
כיום אין שום אלגוריתם למחשב קוונטי שיכול לפתור בעיה שידוע שהיא קשה (NP-Complete לאלו שמכירים את המינוח) וגם אין נימוק ממש טוב למה שיהיה כזה. כל האלגוריתמים הקוונטיים שידועים כיום ושהם יותר טובים מכל אלגוריתם קלאסי שידוע, הם לבעיות שיתכן שיש להן פתרון קל במחשב רגיל, רק שלא ידוע כזה. | |
|
|
|
|
|
||
|
||||
|
עוד לא הוכח כי בעיות NP-complete הן באמת קשות על מחשב קלאסי. גם להן ייתכן פתרון קל במחשב רגיל. | |
|
|
|
|
|
||
|
||||
|
אתה צודק, אבל הסיכוי שיתגלה פתרון פולינומיאלי לבעיות NP-complete הוא נמוך, לדעת רבים, מהסיכוי שרוזנקרנץ וגילדנשטרן חיים. יש משהו מפתיע, שלא לומר מסתורי, בעובדה שגם בחישוב קוונטי וגם בהצפנה ציבורית עוד לא הצליחו1 להתלבש על בעיות NP-complete, והלא יש כל כך הרבה כאלה. 1 ככל הידוע לי. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |