בתשובה לבועז, 19/05/03 17:48
 |
|
 |
||
|
||||
 |
הדיון הוא למעשה על הסיכוי של טכנולוגיה קוונטית להוליד מחשב, ולכן ה"קלאסיות" של האלגוריתם אינה רלוונטית. איפה צריך להעלות בריבוע את הסיבוכיות ב-Twinkle? |
 |
 |
 |
|
|
|
||
|
||||
|
אאז"נ ב TWINKLE יש k (כש k די גדול) מעבדים קטנטנים ומהירים כאשר לכל אחד מחוברת נורת LED שהוא דואג להדליק אותה מפעם לפעם. המטרה של התא הפוטו-אלקטרי הוא להרים דגל כאשר קורה האירוע הנדיר יחסית שבו "הרבה" מהנורות נדלקות (כלומר, כאשר סה"כ עצמת האור עוברת סף מסוים)1. זה לא אסון אם יהיו גם false alarms, כל זמן שאין יותר מדי כאלה. ברור שאם בכל יחידת זמן היינו עוצרים את המעבדים ועושים k פעולות ע"מ לסכם את התרומה של כל מעבד, היינו יכולים לדעת בדיוק מתי קורה האירוע. זה היה מגדיל את הזמן בפקטור של k. אם סופרים סיבוכיות כמס' מעבדים כפול זמן, אז מקסימום ההגדלה הוא ריבועי. עם זאת, למעשה מה שתארתי הוא overkill ובגלל שהאירוע נדיר ושרק צריך לדעת אם עובר סף מסוים אני די בטוח שאפשר לסמלץ את TWINKLE על ארכיטקטורה סטנדרטית ב overhead נמוך יותר. אני מתאר לעצמי שאפשר להפעיל את חלק מהרעיונות שנמצאים בתכנון מכשיר הTWIRL של שמיר וטרומר ע"מ לעשות סימולציה כזו. ---- בעיקרון אפשר לאמר שיש דיכוטומיה במדעי המחשב, וכל מכונת חישוב היא או קלאסית או קוואנטית2. זאת מאחר וקלאסית לא מתייחס דווקא למחשבי IBM על מצע סיליקון, אלא לכל מערכת שאפשר לסמלץ (עם overhead לא יותר מדי פרוע) ע"י מחשבים כאלה. -------- 1 שוב, אאז"נ, אז המטרה היא לבצע שלב מסוים באלגוריתם שבו אנחנו צריכים למצוא הרבה מספרים "חלקים". כלומר, מספרים שמתפרקים כמעט לגמרי מעל k המספרים הראשוניים הקטנים ביותר. כל מעבד i מתאים למספר הראשוני הi בגדלו p_i , ומדליק את הנורה שלו כל p_i יחידות זמן, כאשר עצמת הנורה היא log p_i . כאשר סה"כ האור גדול ביחידת הזמן ה n , סימן שn מספר חלק. 2 נדמה לי שהיו כמה הצעות למכונות שהם לא זה ולא זה, אבל בינתיים אין ממש מועמד רציני. דרך אגב, יש כאלה שחושבים שכל מכונת חישוב היא קלאסית, מאחר וגם מחשב קוואנטי הוא לא מועמד רציני (ראה http://www.cs.bu.edu/fac/lnd/misc/qc.html ). מחשב DNA דרך אגב, הוא קלאסי. |
|
|
|
|
|
|
||
|
||||
|
בקשר לקישור, כל הבעיות שהוא כתב תחת Small Difficulties הן באמת קטנות, קטנות עד כדי כך שהן טופלו. האיש לא שמע על NMR נוזלי? לא קרא את שור על תיקון שגיאות? או שפשוט הוא כתב את המאמר שלו לפני 1998. הבעייה שהוא מתאר תחת Remote Decimals היא באמת שאלה מעניינת, ואני לא יודע אם זו בעייה פתורה במחשוב הקוונטי. כשהוא כותב I doubt anything short of the most generic and direct use of these huge precisions would be easy to substitute, נראה לי שהוא צודק לגמרי, וזו טענה כבדת משקל. המחשוב הקוונטי אכן מחכה לפריצת דרך בנושא זה. הבעייה השלישית שהוא מעלה תחת Too Small Universe היא די בולשיט. אף אחד לא מנסה לממש אלגוריתמים קוונטיים בשיטה שהוא מציע. זה לא רדקציו אד אבסורדום, אלא סתם אבסורד. |
|
|
|
|
|
|
||
|
||||
|
אני לא מבין כמעט כלום ב quantum computing אז אני לא ממש יכול לענות לך. אני רק יכול להעיר שהוא מזכיר (ומכיר) את המושג error correcting codes, אבל טוען שהשגיאות יכולות להיות מצורה שבה הקוד לא יצליח לטפל. כמו כן, נראה שמה שהוא כתב הוא תמצית של דיון ב newsgroup משנת 2000 http://groups.google.com/groups?dq=&hl=en&lr... לגבי הבעיה השלישית, אני חושב שהוא רק מנסה לתאר מדוע מחשב קוואנטי ש*לא* יצליח לפקטר מספרים גדולים, לא ייתן לנו insight חדש על המכניקה הקוואנטית. כאמור, אין לי מושג ב QC, ולכן אין לי גם מושג אם הוא צודק או טועה. |
|
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |