בתשובה לסמילי, 20/02/03 21:12
 |
|
 |
||
|
||||
 |
אם יותר לי להעיר בנושא זה, מנסיוני המוגבל (קורס, ובסמסטר הבא סמינר), הגעתי למסקנות הבאות: א. אני ספקן מאד לגבי האפשרות למחשבים קוונטיים סבירים בזמן הקרוב, אם בכלל. במיוחד אם מגדירים סבירות על ידי היחס בין מספר ביטים קוונטיים לעומת ביטים קלאסיים בשימוש יומיומי, או בשימוש במפתחות קריפטוגרפיים. כלומר, האלגוריתם של שור נחמד, אבל לא מעשי, בגלל בעיות קוהרנטיות. ב. אף-על-פי-כן, לתחום שימושים אשר אינם דורשים מספר גדול מדי של ביטים קוונטיים, כמו בהחלפת מפתחות או בחישובים מבוזרים. ג. התחום מעניין מבחינה תיאורטית גרידא. בתחום של סיבוכיות קלאסית, למשל, יכולות להיות לו השלכות על שאלת ההכלה של P ב-PSPACE. ד. התחום יכול אולי להיות שימושי בכיוון ההפוך, למשל, שימוש בתורת האלגוריתמים הקוונטיים על מנת לבצע ניתוח רציני יותר של תהליכים קוהרנטיים מרובי-חלקיקים, גם אם איננו יכולים לשלוט בהם במידה מספקת. ה. אלגוריתם החיפוש הקוונטי של גרובר הוא פשוט אלגוריתם יפה. אולי הוא יעודד תכנון אלגוריתמים יפים בתחומים אחרים. |
 |
 |
 |
|
|
|
||
|
||||
|
אתה יכול לפרט יותר לגבי ג'? | |
|
|
|
|
|
||
|
||||
|
לא כליל, אבל לקחתי אותו קורס (אפילו היינו שותפים בשיעורי בית, אידיליה). מכיר קצת את הבולשיט הסיבוכי של מדעי המחשב? מכיר את הקבוצה BPP? (האלגוריתמים ההסתברותיים האלה?), אז אם נגדיר קבוצה חדשה, BQP, קבוצת האלגוריתמים הקוונטיים, אזי היא מקיימת אותם יחסי הכלה כמו BPP לP וPS. (ז"א: P מוכל שווה BQP מוכל שווה PS, לצורך העניין). אז כמו שאם היית מוצא אלגוריתם שהוא פולינומי בהסתברות (היינו, בBPP), אבל לא בPS היית יכול להסיק ש P מוכל ממש בPS, אז באותו אופן אם תמצא אלגוריתם בBQP שדורש מקום של יותר מP, תסיק אותה מסקנה. רק שעבור BQP יש יותר תקווה שזה יקרה. (והתנצלות מקרב לב למי שלא ראה פקולטה למדעי המחשב מבפנים ובטעות הגיע לסוף ההודעה הזו. אני בעצמי לא הייתי יודע לקרוא מה שכתבתי לפני סמסטר. למה, למה לקחתי עוד קורס במדעי המחשב? לא הספיק לי אחד שהייתי חייב לחזור לנסות שוב פעם? אהמ. כן.) |
|
|
|
|
|
|
||
|
||||
|
אח שלי הציע לי לקחת את הרעיון הזה כנושא לתזה - לנסות למצוא חסם פיזיקלי על BQP שיראה שהוא מוכל ממש בPS. סיפרתי על הרעיון לאחד משני המרצים היחידים בפקולטה שמכירים את המושג "חישוב קוונטי" והוא לא ממש התלהב להנחות אותי בכיוון. | |
|
|
|
|
|
||
|
||||
|
לפי מיטב ידיעתי, הסיבה היחידה ש עבור BQP יש יותר תקווה שזה יקרה, היא שלא השקיעו עדיין את הזמן הדרוש על השוואה בין BQP לבין שאר המשפחות, על מנת להגיע למסקנה (אליה הגיעו עבור המשפחות הקלאסיות), שכנראה לא נגיע להוכחה. עבור P ו-NP יש למשל רשימה גדולה של כיווני הוכחת שיוויון או אי-שיוויון, שניתן לפסול מסיבות שונות. אולי עוד כמה שנים יפרסם מישהו רשימה של כיווני הוכחה שניתן לפסול לגבי יחסה של BQP למשפחות השונות, ואז נוכל להתייאש גם ממנה. (אני מצטרף להתנצלות של גלעד, לאו דווקא לשאר הסוגריים שלו.) |
|
|
|
|
|
|
||
|
||||
|
תודה על ההסבר. לא ברור שיש באמת יותר תקווה להפריד בעזרת BQP, אבל אף פעם אסור לאבד תקווה.. ----------- למי שלא ראה פקולטה למדעי המחשב - השאלות האלה הם בין המענינות ביותר בכלל שיש במדע. לרוע המזל, אני לא מכיר לינק ממש מוצלח שמתאר את הבעיות הנ"ל (ובראשן הבעיה של P מול NP) בצורה ממש טובה. אפשר לנסות את למי שכן מהתחום, כדאי לקרוא את |
|
|
|
|
|
|
||
|
||||
|
ברור שאני מבין בתחום הרבה פחות ממך, מה זה הזמן הקרוב? | |
|
|
|
|
|
||
|
||||
|
יקשה עליך להבין הרבה פחות ממני - החתול הממוצע יודע רק במעט פחות. אשר לזמן הקרוב, אני מדבר על שני העשורים הקרובים. אם מגדירים סבירות לפי סדר הגודל של מחשבים קלאסיים בני-שימוש בזמן מקביל, אני מדבר על ארבעת העשורים הקרובים. אשמח להתבדות. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |