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