שאלה 220832
למה למחשב קוונטי יכול להיות כח חישוב "החורג" מזה של מכונת טיורינג? למיטב הבנתי, ניתן לסמלץ מחשב קוונטי ע"י מחשב רגיל די בקלות.
שאלה 220846
אם הבנתי נכון, זה כמו בשיר של אריק איינשטיין- מחשב קלאסי עושה אותם הדברים אבל לאט.
שאלה 220847
נכון להיום לא ידועה דרך לסמלץ מחשב קוונטי ע''י מחשב רגיל כך שכל פעולה של המחשב הקוונטי תבוצע במספר פעולות קטן (פולינומיאלי) במחשב רגיל.
כאמור במאמר, אין שום הוכחה שלמחשב קוונטי יש כוח חישוב גדול משל מחשב רגיל, אבל ידועים כמה אלגוריתמים למחשב קוונטי שנכון להיום אין להם אלגוריתמים מקבילים במחשב רגיל.
שאלה 220875
האם ההסבר הבא נכון?
הטריק של המחשב הקוונטי הוא שהוא יכול לבצע הרבה מאוד פעולות בו זמנית. כשם שמכניקת הקוונטים מייצגת את האלקטרון ע"י "ענן הסתברות" המתאר את האפשרות של האלקטרון להיות בכל מקום בענן בהסתברות המתאימה, כך המחשב הקוונטי יכול לתאר כל משתנה ע"י "ענן הסתברות" המתאר את האפשרות של המשתנה להיות בעל ערך מסויים בהסתברות המתאימה. ביצוע מכפלה של משתנים כאלו שקול לביצוע כל המכפלות של כל הערכים האפשריים. הבעיה היא רק כיצד מתוך כל המכפלות האפשריות הקיימות בפוטנציה לגרום לפונקציית הגל לקרוס דוקא על המכפלה המעניינת אותנו.
שאלה 220901
כבר שמעתי את ההסבר הנ''ל יותר מפעם אחת ואפשר להגיד שיש בזה משהו. הבעיה היא למצוא דרך לגרום לפונקציית הגל לקרוס לתוצאה הרצויה, וזה בד''כ בלתי אפשרי.
מה שכן אפשרי זה לגרום לפונקציית הגל לקרוס קודם כל לתוך תת-מרחב של המצבים האפשריים, שכולל את התשובה הנכונה, ואז יש הסתברות לא רעה שבמדידה מלאה נקבל את התשובה הנכונה, ואם לא, נחזור על התהליך שוב. תהליך כזה דורש שבדיקת הנכונות של התשובה הוא קל - למשל פרוק נכון לגורמים קל לאימות.
שאלה 220903
כלומר, מחשב trial and error? משהו כמו מחשבי הירי בטנקים הצה"ליים?
שאלה 220906
האלגוריתם כולל בדיקה של נכונות וחזרה על החישוב במקרה הצורך. האלגוריתמים הידועים כיום הם כאלו שבזמן סביר יתנו תשובה נכונה בהסתברות יותר טובה מהסיכוי שלך לשרוד עד מתן התשובה.
(שמעתי כבר את ההשוואה - הסיכוי לתשובה שגויה הוא קטן מהסיכוי שיפול על המחשב אסטרואיד)
שאלה 220904
שוב אנחנו חוזרים לבעייה המקורית, תת-מרחב הפתרונות האפשריים הוא כל כך גדול שבדיקה שלהם תקח ימבה זמן ועד שנמצא את התשובה הנכונה כבר אפשר יהייה לצעוד לירח ובחזרה (עד אז יבנו שביל להולכי רגל).
שאלה 220949
כיום אין שום אלגוריתם למחשב קוונטי שיכול לפתור בעיה שידוע שהיא קשה (NP-Complete לאלו שמכירים את המינוח) וגם אין נימוק ממש טוב למה שיהיה כזה. כל האלגוריתמים הקוונטיים שידועים כיום ושהם יותר טובים מכל אלגוריתם קלאסי שידוע, הם לבעיות שיתכן שיש להן פתרון קל במחשב רגיל, רק שלא ידוע כזה.
הערה: 221530
עוד לא הוכח כי בעיות NP-complete הן באמת קשות על מחשב קלאסי. גם להן ייתכן פתרון קל במחשב רגיל.
הערה: 221532
אתה צודק, אבל הסיכוי שיתגלה פתרון פולינומיאלי לבעיות NP-complete הוא נמוך, לדעת רבים, מהסיכוי שרוזנקרנץ וגילדנשטרן חיים. יש משהו מפתיע, שלא לומר מסתורי, בעובדה שגם בחישוב קוונטי וגם בהצפנה ציבורית עוד לא הצליחו‏1 להתלבש על בעיות NP-complete, והלא יש כל כך הרבה כאלה.

1 ככל הידוע לי.
שאלה 220952
יש פה אי-הבנה. כשאומרים שכח חישוב של מודל X (מחשב רגיל) גדול מזה של מודל Y (מחשב קוונטי), אז בדרך כלל מתכוונים לכך ש-X יכול לפתור יותר בעיות מ-Y - בלי שום קשר למהירות. זה היה המובן שבו אני השתמשתי. זה די טריביאלי לסמלץ פעולה של מחשב קוונטי ע"י מספר אקספוננציאלי של פעולות. יש אפילו סימולטורים כאלו. לכן ברור שלכל אלג' למחשב קוונטי יש אלג' למחשב רגיל (עם נזק אקספונציאלי על זמן הריצה). היינו, למחשב קוונטי אין כח חישוב גדול יותר משל מחשב רגיל.

ברור שלא יודעים לסמלץ כל פעולה של מחשב קוונטי ע"י מספר פעולות פולינומיאלי - הרי זה היה כל הרעיון. מה שאתה (כנראה) מתכוון ב"כח חישוב גדול יותר" הוא ש-P (הבעיות שניתן לפתור בזמן סביר על מחשב רגיל) מוכל ב-QP (הבעיות שניתן לפתור בזמן סביר במחשב קוונטי) ואולי גם מוכל ממש.
שאלה 220953
אתה צודק.
אבל מצד שני 220958
בגודל של המחשבים הקוונטיים שוידעים לבנות היום, אין שום בעיה לסמלצם בזמן סביר :-(
שאלה 221576
תלוי למה אתה מתכוון ב''כח חישוב''. הם שקולים מבחינה חישובית, כלומר יכולים לפתור את אותן הבעיות, רק לא באותה המהירות.

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים