|
||||
|
||||
אה, דובי, לא מדובר על פיתוח חישוב בעזרת כדורים כחולים ואדומים על חשבוניה, זו הייתה דוגמא לאיזי. כמה כסף? בינתיים לא המון. המעבדה בשלבי הקמה, ומדובר על רכישת ציוד בשווי של כמה עשרות אלפי דולרים, למיטב ידיעתי. לא יודע כמה עולים ארבעת האנשים שהזכרתי קודם. מה שכן, בעולם מוציא הכסף העיקרי על הנושא הוא הNSA, שכן מחשב קוונטי יכול לפקטר (למצוא את הגורמים הראשוניים) מספר בן n ביטים בסיבוכיות של ((n^2*log(n)*log(log(n, וזה מצויין, כי קלאסית היום הסיבוכיות אקספוננציאלית. ז"א שאם הNSA בונים מחשב קוונטי חלש למדי, ולאחרים אין מחשב קוונטי, אין קוד בעולם שבטוח בפניהם. |
|
||||
|
||||
בשביל סוגי המפתחות שקיימים כיום, צריך מחשב קוונטי בגודל של כמה אלפי ביטים קוונטיים. כיום הצליחו להפעיל בקושי מחשב קוונטי של שבעה ביטים קוונטיים. הייתי אומר שרוב הקודים בעולם בטוחים בפני ה-NSA מהבחינה הזו, אם כי שמיר פרסם לאחרונה תוכניות למכונת פריצת RSA קלאסית במאה מליון דולר. |
|
||||
|
||||
אלפי ביטים? מפיתום? ב500 ביטים אני כבר כותב מספר של 150 ספרות, כך שמחשב קוונטי של 1000 ביט יספיק לכל צורך מעשי. ותפסיק לבכות על זה ש1000>>7. יהיה בסדר. |
|
||||
|
||||
יש לי הרגשה אינטואיטיבית שמחשב קוואנטי אמור להיות גם טוב מאד בשחמט, ויוכל להסיר את החרפה מהתיקו 3:3 בין קאספארוב לג'וניור. מישהו יודע אם אני צודק? |
|
||||
|
||||
תלוי את מי אתה שואל. הסטנדרטים עולים כל שנה. עד כמה שאני זוכר, מספר הביטים המומלץ למספר שהוא הבסיס למפתח כיום 1024. והסיבות להחליף אותו אינן קשורות כלל למחשבים קוונטיים, אלא דווקא להתקפות קלאסיות. אלא אם כן תהיה פריצת דרך משמעותית בתחום של יישום, אני חושש שהחלק היותר מעניין של הקורס שלקחנו לא ייצא אל הפועל. ואני מתכוון לפריצת דרך עצומה, יותר גדולה מכל פריצות הדרך שהיו בתחום של המחשוב הקלאסי, מאז המצאת הטרנזיסטור. אני, אישית, ממליץ להשקיע במערכות שעטנזיות, עם רכיבים קוונטיים קטנים יחסית, ולראות עד כמה זה, כשלעצמו, מסייע. אבל מי שואל אותי? |
|
||||
|
||||
מפתחות RSA באורך 1024 ביט אכן נחשבים ע"י רבים לבטוחים בעשור או שניים הקרובים, אבל יתכן שידרשו עדכונים להערכה זו. נראה שאת שני השלבים העיקריים באלגוריתם ה-Number Field Sieve ניתן להשלים בשנה אחת בעלות של עשרות מליוני דולרים. |
|
||||
|
||||
שיטתכם היא ההתקפה הקלאסית אליה כיוונתי. תודה על הקישור. |
|
||||
|
||||
כי בדיוק היום פורסמה שם הכתבה הזו http://www.haaretz.co.il/hasite/pages/ShArtPE.jhtml?... |
|
||||
|
||||
רוצה לשנות קצת את הניסוח של תגובה 91686 ? וגם: מה פשר התעלמותך המתארכת מהאיזכורים שאני זורק בעניין הדוקרב קספרוב-צעיר עמוק? |
|
||||
|
||||
אני עדיין חושב שמיחשוב קוונטי הוא חלומות באספמיה. כרגע אין מועמדים טובים יותר לארכיטקטורות שבהן יבנו מחשבי-העתיד (אלא אם נשאר עם הזן הפון-ניומני), וההשקעה בבדיקת הכיוון הזה ברורה. עם זאת, לו הייתי דוקטורנט במדעי המחשב או פיזיקה, לא הייתי קושר את הקריירה שלי בהרפתקה הזו. (אל הדוקרב התייחסתי בדיון המתאים). |
|
||||
|
||||
בהנחה שמיחשוב קוונטי הוא חלומות באספמיה, למה לא היית קושר את הקריירה שלך בהרפתקה הזו (בהנחה שמדובר בקריירה אקדמית)? |
|
||||
|
||||
כי בעוד עשרים שנה, כשיהיה ברור שהענף הזה עומד להכרת, אני אשב בקצה שלו. |
|
||||
|
||||
מצד שני, יכול להיות שגם בעוד עשרים שנה הוא עדיין יראה כחלומות באספמיה, להבדיל דברים שנראים היום כעל סף מימוש יהיו בעוד עשרים שנה ממומשים ולכן חסרי עניין מחקרי, לא? |
|
||||
|
||||
אם יותר לי להעיר בנושא זה, מנסיוני המוגבל (קורס, ובסמסטר הבא סמינר), הגעתי למסקנות הבאות: א. אני ספקן מאד לגבי האפשרות למחשבים קוונטיים סבירים בזמן הקרוב, אם בכלל. במיוחד אם מגדירים סבירות על ידי היחס בין מספר ביטים קוונטיים לעומת ביטים קלאסיים בשימוש יומיומי, או בשימוש במפתחות קריפטוגרפיים. כלומר, האלגוריתם של שור נחמד, אבל לא מעשי, בגלל בעיות קוהרנטיות. ב. אף-על-פי-כן, לתחום שימושים אשר אינם דורשים מספר גדול מדי של ביטים קוונטיים, כמו בהחלפת מפתחות או בחישובים מבוזרים. ג. התחום מעניין מבחינה תיאורטית גרידא. בתחום של סיבוכיות קלאסית, למשל, יכולות להיות לו השלכות על שאלת ההכלה של 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) בצורה ממש טובה. אפשר לנסות את למי שכן מהתחום, כדאי לקרוא את |
|
||||
|
||||
ברור שאני מבין בתחום הרבה פחות ממך, מה זה הזמן הקרוב? |
|
||||
|
||||
יקשה עליך להבין הרבה פחות ממני - החתול הממוצע יודע רק במעט פחות. אשר לזמן הקרוב, אני מדבר על שני העשורים הקרובים. אם מגדירים סבירות לפי סדר הגודל של מחשבים קלאסיים בני-שימוש בזמן מקביל, אני מדבר על ארבעת העשורים הקרובים. אשמח להתבדות. |
|
||||
|
||||
1. אחרי מספיק זמן, לאנשים תגמר הסבלנות. אי-אפשר לסמוך על כך שהתחום ישאר בגדר חלומות לא ממומשים לעדי-עד. 2. דברים שהצליחו לעשות, אפשר לשפר. הסיכון שהעניין בתחום מסויים יאבד תמיד קיים, אבל דווקא תחומים שקרובים היום למימוש הם ביטוח לא רע מפני הסכנה הזו. שאלה לגבי 1: AI. (פירוש: אינטליגנציה מלאכותית היא חלום-רחוק כבר חמשים שנה, ועדיין לא נמאס; למה שמחשוב קוואנטי לא יהנה מאותה תופעה?). תשובה: אינטליגנציה מלאכותית, צריך. מחשבים מהירים יותר, צריך. מחשבים קוואנטיים דווקא - לא צריך. |
|
||||
|
||||
ברגע שמושגת התקדמות מסוימת בנושא, היא הופכת לתחום אחר- זיהוי-דיבור,לדוגמא. יש להניח כי תחומים שכיום נחשבים לא''מ יחשבו בעתיד לתחומים נפרדים שאף אחד לא יעלה על הדעת על הקשר בינם לבין א''מ. אם אני לא טועה, הסיבה לעניין הרב במחשוב קוונטי היא חוק מור. כמובן צריך לזכור את מחשבי הדנ''א ואת המחשבים האופטיים שגם הם חלופה(בינתיים, נראה שהמחשוב האופטי יחליף את המחשוב על בסיס סיליקון). |
|
||||
|
||||
1. נכון שנושאים כגון זיהוי דיבור או זיהוי תבניות התפתחו בתחילה בפריפריה של המחקר בבינה מלאכותית, אבל ההצלחה בתחומים האלה נובעת בעיקרה מהזמינות של חישוב מהיר ומאלגורתמים ש"הגיעו" ממדעי-המחשב הקונוונציונאליים או תחומים קרובים. דווקא הליבה של הבינה המלאכותית - הבנת טקסט - לא הגיעה להשגים מרשימים. 2. "חוק" מור הוא כלל אמפירי, ולא חוק הכולל סנקציות נגד תעשיית המחשבים במקרה של אי-עמידה בדרישות החוק. אני מבין את העניין הנוכחי במחשוב קוואנטי (וגם בתחליפים אפשריים אחרים), ומאחל הצלחה לעוסקים במלאכה. עם זאת, אני נשאר פסימי (לפחות לעשר השנים הקרובות). (תוקפה של הודעה זו פג ב- 21.2.2013 בחצות). |
|
||||
|
||||
תזכיר לי, לאיזה תחום בחרת לקשור את הקריירה שלך? היום, (כמעט) אף פיזיקאי לא חוקר ומנסה לשפר את מנוע הקיטור, או אפילו את מנוע הבנזין. פיזיקה זה לא תחום הנדסי אלא תחום מדעי. ואנשים שחוקרים את המחשב הקוונטי מקדמים את המחקר המדעי בכלל, אם ע"י שלילת האפשרות לממש אותו, ואם ע"י העלאת תחומים חדשים בפיזיקה. ובקשר לאינטליגנציה מלאכותית, תוך כדי סיכון הענף עליו אני יושב מדי פעם, למה באמת "צריך"? הרי כל כך קל לייצר ולהשתמש באינטליגנציה טבעית. |
|
||||
|
||||
לגבי הפסקה האחרונה, אני מסכים, אבל משום מה, כאשר התחלתי להציע את המתבקש, דהיינו, שיש להעביר את תקציבי המחקר מבינה מלאכותית לשטיפת מוח ותכנות בני אדם, במקום להתייחס אלי ברצינות, החלו לקרוא לי בשמות כמו ''מנגלה.'' אילו קיבעונות יש להם בממסד המדעי. ובקיצור, היתרון בבינה מלאכותית הוא שניתן לשלוט בה, בלי שארגוני זכויות האדם יעמדו לך על הראש. |
|
||||
|
||||
היתרון על מה? ז"א, מה בכלל המטרה של מחשב שיודע לקרוא טקסט (ואני שואל כמי שראה כמה תוכניות עסקיות שבנויות על מחשבים כאלה)? קח את המשאבים של מאה שנות מחקר (חמישים שעברו, ועוד חמישים שיעברו, עד שבסוף ירימו ידיים/ יעברו למחשב קוונטי) של מיטב מהמוחות של המין האנושי, ותשקיע את הכסף הזה בתחום מחקרי שתוחלת הכסף שבו גבוהה יותר (ז"א, תחומים עם תוכניות עסקיות שנשמעות קצת יותר רווחיות, זמן מחקר יותר קצר, סיכויי הצלחה גבוהים יותר, אפשרות לזיהוי נקודת כשל מהירה יותר וכו'), בכסף שתרוויח, תעסיק שני סינים במשכורת גדולה מהמשכורת שנייקי משלמת להם, כולל זכויות סוציאליות, והנה יש לך את האופציה של קריאת טקסטים, ללא בעיות של אירגוני זכויות אדם, ואפילו עם כמה דולרים להשקיע במשהו מופשט ואקדמי, כמו למשל, בינה מלאכותית. |
|
||||
|
||||
אבל סינים קוראים רק בסינית! |
|
||||
|
||||
1. מה רע בסינית? 2. תזכיר לי, באיזה שפה קוראים המתחרים שלהם (המחשבים)? 3. למד את הסיני אנגלית (או כל שפה שתרצה להשתמש בה), אם תתחיל בגיל שנתיים-שלוש הוא יוכל להגיע לרמת ידע מספקת עוד לפני שיתחיל לעבוד, בעלות שלא תעלה בהרבה על העלות של הלימודים שלו (שבכל מקרה היית צריך למד אותו). עדיין נראה לי זול. |
|
||||
|
||||
1. אני אמרתי רע? 2. בינתיים, שום שפה. Got me there. 3. או, אני הצעתי דברים כאלה, אבל משום מה לא נותנים למדענים מטורפים לגדל ילדים למטרות מחקר, סינים או אחרים. |
|
||||
|
||||
3. אבל זה (לימוד קריאה) מה שעושים עם (כמעט) הילדים, לא? |
|
||||
|
||||
לא, לא, לא! לחטוף ילדים סינים, ללמד אותם לקרוא, ולהעביד אותם בעיבוד נתונים! |
|
||||
|
||||
למה צריך לחטוף? |
|
||||
|
||||
לא משנה... בדיחה גרועה. |
|
||||
|
||||
אני לא בטוח שאני יכול לתת כאן תשובה מלאה לשאלה (הראשונה) שלך. תשובה חלקית אפשר למצוא כאן: |
|
||||
|
||||
לא כל הLaTeX תורגם שם טוב. אולי תסדר את זה? |
|
||||
|
||||
ואת התחום-שבחרת-לקשור-את-הקריירה-שלך-אליו1 צריך? אפשר לממש? הוא קרוב למימוש? ---------------------------------- 1 אפשר לקרוא לו "אלגברה"? "מתמטיקה"? או שזה יהווה עלבון? |
|
||||
|
||||
אפשר לקרוא לדברים שאני עושה "אלגברה" (למה שזה יהיה עלבון?). אפשר גם לדייק יותר, אבל לא נראה לי שזה המקום המתאים. האם "צריך" מתמטיקה? האם "צריך" מתמטיקאים? התשובה כמובן תלויה בפירוש השאלה, וזו עשויה להיות הזדמנות לשאול את אותה שאלה גם על תחומים אחרים. בכל מקרה, בהתחשב בסביבה רווית הסטודנטים והאוהדת, נראה לי שהמשחק מכור. אני לא יודע איזה סוג של נימוק אתה מחפש. יש כמה דברים שעשיתי שאפשר "לממש" (מחוץ למתמטיקה התאורטית); לרוב זה לא כך. אני לא מחפש את היישומים הפרקטיים האלה באופן יום יומי, וזה נכון לרוב המתמטיקאים שאני מכיר. המתמטיקה שואבת חלק משמעותי מן המוטיבציה שלה מתחומים קרובים (פיזיקה, מדעי המחשב, שאר מדעי הטבע, סטטיסטיקה), אבל כהרפתקה אנושית, היא עומדת יפה ברשות עצמה. אם התכוונת לעמת את התשובות שלי עם התשובות המקבילות לגבי מחשוב קוונטי (תגובה 128603), אני לא רואה מקום להשוואה. יש כמובן עניין תאורטי מסויים במודלים שונים לחישוב אבל ההצדקה העיקרית להתמקד דווקא במודל הקוונטי היא התקווה שיצא מזה משהו מעשי. אם לא יצא, הנושא יקבל את המעמד הראוי לו במסגרת התאורטית המתאימה, ותו לא. |
|
||||
|
||||
למה שאלגברה תהיה עלבון? לא יודע, פשוט לא הבנתי למה לא אמרת את השם המפורש, ופחדתי לפגוע שלא לצורך (זה הרי לא נושא הדיון). את שתי הפיסקאות האחרונות אפשר להעתיק כמו שהן ולכתוב על פיזיקה (חוץ מפירוט התחומים הקרובים, כמובן). אני לא חושב שמי שקושר את גורלו למיחשוב קוונטי עושה זאת מתוך תקווה שיצא מזה משהו מעשי בעתיד הקרוב, בטח לא ברמות האלה, כמו רוב מי שבוחר לקשור את גורלו לפיזיקה תיאורתית. |
|
||||
|
||||
מה שנחמד בנושא רב-תחומי כמו מחשוב קוונטי, הוא שאין בדיוק משמעות לעניין של לקשור את גורלך אליו --- אם יום אחד יתברר לך, שהתחום משעמם אותך, או שאין לו יותר עתיד פרקטי, בהנחה שרצית להתייחס לפרקטיקה, תמיד תוכל להשתמש בכלים שפיתחת והכרת במהלך המחקר בכיוון אחר, בין אם בפיסיקה הקוונטית, באופטיקה הלא-ליניארית, במדעי המחשב, או כל נושא אחר שיש בו אפליקציות מעשיות. |
|
||||
|
||||
השאלה היא אם יתנו לך הזדמנות לעבור לתחום אחר. חוקרים ותיקים מוצאים תמיד תחומי עניין חדשים, והנסיון שהם צברו הוא בעל ערך גם אם התוצאות עצמן כבר לא מעניינות במיוחד. לעומת זאת, אני לא חושב שלמי שפרסם כמה מאמרים בתחום שנפח את נשמתו1 יש סיכוי גדול להתקבל כחוקר במוסד טוב. 1 כרגע, "מחשוב קוונטי" הוא דוגמא לתחום חי ובועט. |
|
||||
|
||||
קשה ללמוד מן ההשוואה של נושא ששואב את ההצדקה הכמעט-יחידה לקיומו מן הסיכוי למימוש עתידי (גם אם בעתיד הרחוק), לבין מקצועות תאורטיים חובקי-כל (כמו מתמטיקה או פיזיקה). אגב, הנימוק בשורה הראשונה שלך פשוט מקסים... אני מקווה שלא יהיה צורך גם בהמשך. |
|
||||
|
||||
דוקטורנט לפיזיקה שחוקר את המחשב הקוונטי הוא עדיין דוקטורנט לפיזיקה (שהוא תחום תיאורתי חובק כל), לא? |
|
||||
|
||||
כן, אלא שבעוד ארבע-חמש שנים הוא עלול למצוא את עצמו במצב של המועמד מתגובה 135343. |
|
||||
|
||||
עוד לא השתכנעתי, אם המאמרים שהוא פירסם היו מאמרים בפיזיקה, שעסקו במחשב קוונטי כתחום מהמכניקה הקוונטית (או תורת האינפורמציה הקוונטית), ולא מאמרים בהנדסה של משהו רחוק ממימוש בתחום שנפח את נשמתו, הוא יוכל לחקור בתחומים אחרים במכניקת הקוונטים, ואם הוא חוקר טוב, יעסיקו אותו בגלל כישוריו כחוקר והידע שלו במכניקה קוונטית (או תורת האינפורמציה הקוונטית), ללא קשר לעובדה שהתחום שהוא עבד בו נפח את נשמתו. להבדיל, אם כל המכניקה הקוונטית תנפוח את נשמתה, מצבו יהיה עגום, אבל זו בעיה אפשרית של כמעט כל מי שחוקר במדעי הטבע (להבדיל, אני חושב, מפילוסופיה/ מתמטיקה/ מדעי החברה). |
|
||||
|
||||
1. כדי לחסוך אי-אילו מאות מלבנים, אני אמנע מלשאול מה ההגדרה של "חוקר טוב". הרשה לי רק להעיר שעוד לא מצאו לזה מבחנים אובייקטיביים. אם החוקר הטוב שלנו כתב מאמרים על פרטי הפרטים של תאוריה שכבר לא מתעניינים בה, הוא עלול להתקל בבעיה כשהוא מנסה להרשים אנשים בכישוריו כחוקר. 2. כל מה שכתבתי על מחשבים קוונטיים מבוסס על התרשמות שלי, כמי שאינו מומחה בתחום. אם מדובר בהלכה למעשה, דהיינו בחירת תחום מחקר לתואר שני או שלישי, המלצתי היא לבחור מנחה טוב, ולשמוע בקולו. |
|
||||
|
||||
1. מסכים. 2. אני חושב שכדאי להוסיף עניין אישי ויכולת אישית, אבל, מצד שני, אולי לא. |
|
||||
|
||||
מה שמזכיר לי את הסיפור על השפן שישב בפתח מערה וכתב במחברת. ניגש אליו שועל ושאלו לפשר מעשיו. ענה לו השפן כי הוא כותב תזה. "על מה" שאל השועל. "השפן הוא החזק שבחיות היער" ענה השפן ללא היסוס. "מעניין" ענה השועל, "אפשר לראות הוכחות?" "ודאי" ענה השפן "היכנס אחרי למערה והוכיח לך אחת שתיים". נכנסו השפן והשועל. אחרי כ-5 דקות יצא השפן שכל פרוותו אדומה - ולשועל אין כל זכר. כך היה גם עם הדוב והזאב. לבסוף, הינשוף, שעמד כל העת על גזע עץ סמוך למערה לא התאפק ושאל את השפן, כיצד ייתכן הדבר. השפן שרק ומן המערה יצא טיגריס. "תכיר" אמר השפן "זה המנחה שלי". מוסר השכל: (כפי שאמרת אתה) בחר מנחה טוב ושמע בקולו. |
|
||||
|
||||
|
||||
|
||||
אני מוחה על ההתעללות בשועלים! |
|
||||
|
||||
אני חושב על המרצה שלי בקורס "מבוא לעיבוד אינפורמציה קוונטית", שבהחלט קשר את גורלו במיחשוב הקוונטי, ודווקא מוצא שאני נוטה יותר לכיוון של עוזי. במה הוא מתעסק? על מה הוא מפרסם? על אלגוריתמים של הצפנה ותקיפה קוונטית. מה אם לא יהיה מימוש והתחום ידעך? במדעי המחשב, הוא לא עשה שום עבודה משמעותית. יש הבדל רציני בין התקפה קלאסית על אות מוצפן, ובין ניצול-הפוטון-השני-המופיע-כל-שליחה-עשירית בהתקפה הקוונטית שהוא פיתח. איזה דברים משמעותיים הוא (י)עשה במכניקה קוונטית? הרי לא צריך הבנה של יותר מקורס שני בתואר ראשון במכניקת הקוונטים כדי לדעת מה קורה, וכל התחום מבוסס על ניצול הידע הקיים, לא על פיתוח חדש. אז אם יכרת הענף, מה הוא שווה? הרי הוא כד"ר שכרגע יצא מהטקס. |
|
||||
|
||||
אני לא מכיר את המרצה שלך, ואני מעדיף לא לדבר עליו, אבל אני לא חושב שלאדם כמו איגור וולוביץ' (Igor Volovich, http://xxx.tau.ac.il/find/math-ph/1/Volovich/0/1/0/a...) תהיה בעיה כזו. |
|
||||
|
||||
אולי מכאן תבוא הישועה. |
|
||||
|
||||
לא קיבלתי כל-כך הרבה מתנות שאתה צריך לגזול גם את כבשת הרש שלי. רוצה התערבות שבעוד 20 שנה יצליחו לפקטר מספר בן 200 ספרות? (אגב, יש גם חידושים בתחום המחשב הdna'י שהגיע לכותרות לפני כשנה עקב מחקר של מכון ויצמן - עכשיו הוא גם מספק את האנרגיה של עצמו: http://www.sciencedaily.com/releases/2003/02/0302270...) ואת משטרו העריץ של פון-נוימן יש לה(כ)פיל. |
|
||||
|
||||
לפקטר מספר של של 200 ספרות תוך 20 שנה? אם מתחילים עכשיו, אז למה לא? צחוק בצד, רק שתדע שהנבואה שלך שמרנית למדי. אם נניח שהעוצמה החישובית תגדל לפי חוק מור, אז מספר של 308 ספרות (1024 ביט) יפוקטר עם מחשב קלאסי של 2023 תוך 38 שנה. אתה רוצה 200 ספרות, שזה 667 ביט, ואני לא מוכן לעבוד עם מספרים כאלה, אבל נגיד שזה בערך בחזקת 2/3 - 10 שנים. כלום, בהתחשב בזה שהיום לוקח בערך 6^10 שנה לעשות את זה. (כל החישובים נעשו בהנחה שיש רשת של 1000 מחשבים שעובדת של הפיקטור) אגב, למחשב קוונטי, אם נניח מהירות שעון של 100 מגה הרץ, יקח בערך 4.5 דקות לפקטר מספר של 1024 ביט. (ואתה קורא יקר, מוזמן לנחש: למי היה מועד ב' היום, ובאיזה מקצוע?) |
|
||||
|
||||
אני מנסה לנצל את הבורות המתמטית של אחד, עוזי ו., כדי לגרור אותו להתערבות שתוכל לממן לי את היאכטה, ואתה בא וטורף לי את הקלפים1 . מאז הפאדיחה שלי עם אלי והחייזרים לא נתקלתי בעוכר שמחות כמוך. הלואי שלא תקבל יותר מ 95 במבחן שלך. _________________ 1- אגב, מנסיוני אנטלופה הרבה יותר טעימה |
|
||||
|
||||
כבר פירקו (ב- 1999) מספר בן 155 ספרות1. בלי קוואנטים, בלי חומצות גרעין, בלי תאים פוטו-אלקטריים - מחשב מהוגן, עשוי מסיליקון (למעשה, רשת של כאלה). אבל אני כן מוכן להתערב באיזה סוג מחשב ישתמשו כדי למספר בן 200 ספרות בפעם הראשונה - הוא לא יהיה קוואנטי. |
|
||||
|
||||
הצב 400 במקום 200, ויש לנו התערבות (מה זה כבר פקטור 2 ביני לבינך?). ארוחה במסעדה כשרה? |
|
||||
|
||||
סדר צריך להיות. מדובר על פירוק של מספר "כללי" בן 400 ספרות עשרוניות, כלומר - מספר שהוא מכפלה של שני ראשוניים בני בערך 200 ספרות, ללא מבנה מיוחד. אני מעריך שהפירוק הראשון מהסוג הזה יעשה על מחשב קונוונציונאלי (מן הסתם, רשת מרובה מעבדים של מחשבים כאלה). אתה זוכה בכל מקרה אחר (הפירוק נעזר באופן מהותי במחשב general-purpose מסוג אחר). במקרה הביניים (מכונה יעודית לפירוק מספרים) אין הכרעה. נצטרך לחכות הרבה זמן לפירוק כזה; אני מצפה בקוצר רוח לראות את כרטיס האשראי על-שם Global Village Shote. |
|
||||
|
||||
למה במקרה של מכונה ייעודית אין הכרעה? השאלה היא האם המכונה היעודית תהיה מבית-ספרו של פון-ניומן. |
|
||||
|
||||
נדמה לי שפירוק מספרים נבחר רק כמבחן לטיב המחשב שישיג תוצאות חישוביות טובות יותר, ופירוק בעזרת מכונה יעודית לא עונה על השאלה הזו. |
|
||||
|
||||
מקובל עלי. (ואם הגב' ו. תחפוץ להצטרף לסעודה, אני מזמין את שניכם בלי קיטורים) |
|
||||
|
||||
סילחו לי שאני, בחור אנאלוגי מטבעי, מתערב בספֵירות של גדולי המתימטיקה והקריפטוגרפיה. על פי הבנתי, כל קרב המיחשוב שלכם נועד כדי למצוא שני מספרים ראשוניים גדולים מאד. האם זה נכון שאם תהיה נוסחא לחישוב מספר ראשוני כל הצורך הזה במיחשוב-על ייעלם? אם מה שרשמתי לעיל הוא נכון - מה בדיוק המכשולים העומדים בדרך להגעה לנוסחא שכזו? האם אנו יודעים שהדבר בלתי אפשרי? |
|
||||
|
||||
נדמה לי שהשאלה היא מה שני הגורמים הראשוניים (הגדולים מאד) של מספר גדול מאד נתון. בשביל לפצח מספר בן N ספרות תצטרך לבדוק מספרים ראשוניים בני כחצי N ספרות, וזה לוקח זמן. לבשל מספרים ראשוניים חדשים אפשר לעשות כך - כפול סדרה של מספרים ראשוניים עוקבים (2,3,5,7,11,13,17, וכו' עד שנמאס), הוסף אחד - וקיבלת ראשוני נוסף. אם המספר שקיבלת לא ראשוני, כנראה פספסת איזה ראשוני בדרך (למשל 2*3*5+1 = 31 ראשוני, אבל 3*5+1 = 16 לא ראשוני). |
|
||||
|
||||
אחרי לא מעט מחשבה, הגעתי למסקנה שהתהליך שהסברתי לבישול מספרים ראשוניים הוא שגוי. כלומר, לפעמים יתקבל ממנו מספר שאינו ראשוני. אאוקלידס השתמש בתהליך הזה כדי להוכיח בשלילה שיש אין-סוף מספרים ראשוניים. מניחים שיש מספר סופי של ראשוניים, כופלים את כולם זה בזה ומוסיפים אחד. מקבלים מספר שנותן שארית 1 בחלוקה בכל מספר ראשוני, משמע הוא בעצמו ראשוני - בסתירה להנחה - מש"ל. אין סיבה להניח שהמספר המתקבל בצורה זו לא יתחלק בזוג מספרים ראשוניים הגדולים מן המספרים ששימשו להכנתו. עליתי על הטעות רק כשניסיתי להבין למה *החסרת* אחד ממכפלת סדרה כזו של ראשוניים לא נותנת תמיד מספר ראשוני. טל"ח |
|
||||
|
||||
2*3*5*7*11*13*17 + 1= 510511 = 19 * 26869 סליחה ושלום |
|
||||
|
||||
1. כפי שציין ליאור, אנחנו מדברים על פירוק של מספר (נתון) לגורמיו הראשוניים, ולא על מציאת מספרים ראשוניים גדולים. הרבה יותר קשה לגלות את הגורמים הראשוניים של 2581, מאשר להכפיל 29 ב- 89. 2. לגבי "נוסחא" לחישוב ראשוניים: *שיטות* למצוא מספרים ראשוניים גדולים, יש. כל מה שצריך הוא מבחן יעיל לאישור הראשוניות של מועמד נתון, וסבלנות להפעיל אותו מספיק פעמים (הסיכוי של מספר בן 200 ספרות להיות ראשוני הוא כ- 1 ל- 460; אם נזהרים שהמספר לא יהיה זוגי, הסיכוי מוכפל). 3. *נוסחא* (פולינומית) לחישוב ראשוניים, דווקא אין. ליתר דיוק, לא קיים פולינום במקדמים שלמים (ומספר כלשהו של משתנים), שכל הערכים שהוא מקבל הם ראשוניים (עד כדי סימן). זהו משפט (די קל) שהוכיח גולדבך ב- 1752. 4. מצד שני, קיימים פולינומים (עם מקדמים שלמים) שכל ערך *חיובי* שהם מקבלים הוא ראשוני (הם מקבלים ערכים שליליים רוב הזמן). דוגמא אפשר למצוא כאן: |
|
||||
|
||||
כפי שענו לך, יש הרבה דרכים למצוא מספרים ראשוניים גדולים ככל שרוצים. בפרט, דרך אחת לעשות זאת היא להגריל מספר באקראי מבין כל המספרים שיש להם מספר ספרות מסוים ולבדוק אם הוא ראשוני. הסיכוי שמספר אקראי יהיה ראשוני הוא לא מאוד נמוך ויש שיטות יעילות לבדוק האם מספר הוא ראשוני או לא. השאלה היא, כפי שנאמר, כאשר אתה מקבל מספר גדול שאינו ראשוני (למשל בעל 100 ספרות), למצוא את הפירוק שלו לגורמים ראשוניים. דרך אחת לעשות זאת היא פשוט לעבור על כל האפשרויות לגורמים כאלה ולבדוק אותם. הבעיה היא שלמספר בן 100 ספרות, יש 10 בחזקת 100 גורמים אפשריים כאלה, וגם אם המחשב מבצע מיליארד פעולות בשנייה עדיין ייקח לו יותר זמן לעשות את זה ממה שייקח לשמש שלנו להפוך לחור שחור. מצאו דרכים יותר יעילות מזאת אבל לא באופן מספיק משמעותי, ובפרט עבור מספרים קצת יותר גדולים (למשל 1000 ספרות) הדרכים האלו עדיין יקחו בערך אותו זמן. שים לב שמחשב רגיל יכול להכפיל שני מספרים בני 1000 ספרות תוך פחות משנייה, תוך שימוש בכפל ארוך שלמדנו ביסודי. לא יודעים אם יש שיטה באמת יעילה לפרק מספר לגורמים. עד כמה שידוע לי, הסיבה היחידה להאמין שאולי אין שיטה כזו היא שזו אחת מהבעיות שנחקרו באופן אינטנסיבי במיוחד לאורך הרבה שנים ואף אחד לא הצליח למצוא כזו. |
|
||||
|
||||
הייתי מתחיל להתעניין במסעדות זולות http://www.urhome.umd.edu/newsdesk/sociss/release.cf... |
|
||||
|
||||
מתחיל בצעד קטן; אבל לא כל צעד קטן מתחיל אלף מילים של מסע. |
|
||||
|
||||
משום מה תמיד חשבתי שזה מסע של תמונה אחת. |
|
||||
|
||||
אני במקומך הייתי עושה את ההתערבות על מספר בגודל 2 ביטים, ולא 1300. דרך אגב, כמו טל, אני חושב שגם במקרה שהמספר יפורק באמצעות מכונה ייעודית, עדיין ניתן לשאול אם המכונה היא קוואנטית או קלאסית, ולכן צריכה להיות הכרעה גם במקרה זה. זה הדבר הנכון לעשות וגם יכול לחסוך לכם וויכוחים בסגנון "מיהו יעודי?" |
|
||||
|
||||
פוטואלקטרי (כמו Twinkle של שמיר מהטכניון) זה קוואנטי או קלאסי? לא כל מכונה יעודית נופלת לאחת משתי הקטגוריות האלה. |
|
||||
|
||||
TWINKLE = The *Weizmann INstitute* Key Locating Engine לא טכניון.
|
|
||||
|
||||
TWINKLE הוא קלאסי. הוא אינו משתמש בentanglement או בשום דבר אחר שלא ניתן לסמלץ ע"י מחשב סטנדרטי (במחיר של פקטור כפלי קבוע, או מקסימום העלאה בריבוע). |
|
||||
|
||||
הדיון הוא למעשה על הסיכוי של טכנולוגיה קוונטית להוליד מחשב, ולכן ה"קלאסיות" של האלגוריתם אינה רלוונטית. איפה צריך להעלות בריבוע את הסיבוכיות ב-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, ולכן אין לי גם מושג אם הוא צודק או טועה. |
|
||||
|
||||
יחד עם התינוק. |
|
||||
|
||||
אני חושב שאזמין סלט. (וארז ליבנה, אם אתה כאן במקרה, אודי שפירו עושה קולות של ארוחת חינם גם בהתערבות איתך). |
|
||||
|
||||
אני גם זוכר משהו מסלשדוט (אולי זה אותו דבר?) בחודשיים האחרונים. נדמה לי ששם דיברו על ישומים בהצפנה בשנתיים הקרובות. |
|
||||
|
||||
וגם הייתי מתחיל לחסוך: http://www.uni-bonn.de/en/News/52_2004.html |
|
||||
|
||||
מה "קוונטי" ברגיסטר שהם בנו? זה מתנהג כמו יחידת זכרון סטנדרטית לגמרי (של 5 ביטים). |
|
||||
|
||||
סתם כך "מה "קוונטי" ברגיסטר שהם בנו?" בלי שום התפעלות מהשוטה שחזר מן הכפור (הגלובלי)? |
|
||||
|
||||
גם אני מצטרף לחוסר ההתפעלות. כשיצליחו לבנות שער Controlled-Not על שני רגיסטרים של 8 QBits אני מבטיח להריע להישג. למעשה אם יצליחו לעשות את זה על רגיסטר של 2 QBits אני אתרשם מאוד. |
|
||||
|
||||
אני רואה שקשה להשביע את רצונך, אבל הנה עוד משהו בכל זאת: http://news.uns.purdue.edu/UNS/html4ever/2004/041013... (בשאלות וטרוניות נא לפנות למקור, אני רק השליח). |
|
||||
|
||||
מה שאני הבנתי, זה שהצליחו לבנות גלאי שטרן-גרלך ננוסקופי, הישג מרשים לכל הדעות, אבל אלא אם כן מישהו מתכוון ברצינות לבנות מחשב קוונטי מבוסס אלקטרונים (בתור QBits) זה לא ממש מקדם את הנושא. |
|
||||
|
||||
מתחיל? ממשיך! http://www.nist.gov/public_affairs/releases/quantum_... |
|
||||
|
||||
מישהו רוצה להמליץ על יין טוב? http://www.nist.gov/public_affairs/releases/fourier.... |
|
||||
|
||||
לא, מר וישנה, פלאפל בפיתה לא משביע את רצוני ואף לא את רעבוני. כלל וכלל לא. |
|
||||
|
||||
אז כבר הצליחו לפרק את 35 לגורמים ראשוניים בעזרת מחשב קוונטי, או שמשימות כאלה דורשות עדיין חשבוניה של חרוזים? |
|
||||
|
||||
עוד לא, אבל מזמן הבנתי שאם לא אתהלל כמפתח בעודי חוגר, לעולם לא אתהלל בכלל, וחבל. |
|
||||
|
||||
עוד צעד קטן, או לא כל-כך קטן, בדרך לארוחת החינם שלי: http://blogs.discovermagazine.com/80beats/2011/01/19... (דגדגן: כותרת התגובה הזאת) |
|
||||
|
||||
אני לא מודאג, מישהו עוד יטפל בזה רטרואקטיבית. |
|
||||
|
||||
מתמטיקאי מאונ. בר אילן הפנה את תשומת לבי למה שמתפרסם בידיעה הזאת. זהותו של המדליף שמורה עמי, מן הסתם יותר משהוא רצה לשמח אותי הוא רצה למרוט את עצביו של פרופ. וישנה. לקח צדדי הוא שאם לוקהיד משלמים משהו כמו עשרה מליון דולר עבור מכונה שלא ברור אם תעבוד כמצופה, הפרויקט של F35 באמת נמצא בצרות. |
|
||||
|
||||
עפ"י הסקירה (המצויינת) הזאת של מצב ההיתוך הגרעיני התכנון של לוקהיד מגוחך: "For example, Lockheed Martin claims that it will take them five years to build a prototype of a fusion power plant that will fit in a truck. They have yet to publish evidence that they have produced a fully ionized plasma. Maybe they're just being secretive, but their design has solid components in the plasma . That won't work." (הדגשה שלי). ("אכן," אמר מנהל הפרוייקט, יעקב מרידור שמו, "מחלקת חומרים חדשים עדיין צריכה לספק לנו חומר שנשאר מוצק ויציב בטמפ. מאה מליון מעלות קלוין, אבל הם מקבלים תמיכה מסיירת מטכ"ל כך שהכל יהיה בסדר"). |
|
||||
|
||||
פריצת דרך טכנולוגית? אני זוכר שמישהו כבר הזכיר את ה-Z-pinch כפריצת דרך טכנולוגית אפשרית בתחום כורי היתוך קטנים יותר. (אני רק מקווה שזה לא עוד פעם אתה). מדובר, ב-spin-off על גישת ה-TOKAMAK. במקום טורוס גדול של פלסמה לוהטת הכלואה ע"י שדות מגנטיים חיצונים חזקים, הפלסמה זורמת במקביל לציר הסימטריה והכליאה (היציבות) מושגת ע"י שדות אלקטרומגנטיים בתוך הפלסמה עצמה. ע"פ המתואר זה מאפשר כורים קטנים ביחס לשיטה המקורית. יחד עם זאת, מקריאת המאמר, התרשמתי שמדובר בכורי מחקר, רחוק מאד עדיין מפרוייקט של כור מסחרי. |
|
||||
|
||||
זה דיווח רציני יותר מאשר סתם הודעה לעיתונות של החברה (שבדיוק הצליחה לקבל מימון, או משהו כזה)? צריך לשנות את השם של החוקר שמצוטט שם מ־Shumlak ל־Shumlik ואז לתרגם לעברית כ„שומשום״. |
|
||||
|
||||
יש בעיה גדולה עם כתבות מהסוג הזה, שבהן המידע כולו מגיע ממקור אחד של בעלי עניין. |
חזרה לעמוד הראשי | המאמר המלא |
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש | © כל הזכויות שמורות |