בתשובה לכליל החורש נאורי, 21/02/03 11:43
 |
|
 |
||
|
||||
 |
אתה יכול לפרט יותר לגבי ג'? |  |
 |
 |
|
|
|
||
|
||||
|
לא כליל, אבל לקחתי אותו קורס (אפילו היינו שותפים בשיעורי בית, אידיליה). מכיר קצת את הבולשיט הסיבוכי של מדעי המחשב? מכיר את הקבוצה 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 מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |