מודלים חדשים של חישוב
במושג חישוב חבויות שתי רמות. האחת מתמטית והאחת פיזיקאלית. בד"כ אנו חושבים על בעיה מתמטית נתונה כמו למצוא ערך של פונקציה מסויימת, ועל כלי עזר פיזיקאלי, כמו סרגל חישוב, מחשבון, מחשב, וכו'. הבעיה המתמטית מצויה במישור אחד נפרד ו"גבוה", בתוך מציאות פלאטוניסטית, והכלי הפיזיקאלי נמצא במציאות פיזיקאלית, מציאות שהטבע מגדיר. ואכן השימוש בכלי הפיזיקאלי בכדי לפתור בעיות מתמטיות מעלה שאלה פילוסופית כבדת משקל, מהיכן נובע הקשר בין שתי מציאויות כה שונות. המתמטיקה מקורה במחשבה שלנו, היא פרי יצירה רוחנית, אפילו קפריזית, ואילו הפיזיקה היא פרי יצירה של הטבע. העובדה שמצאנו כלי פיזיקאלי שיכול לעזור לנו לפתור בעיה מתמטית או לחילופין העובדה שתופעת טבע מתנהגת על פי כללים מתמטיים היא אם כן פלא, ואין לה שום סיבה ברורה, לכל היותר מקרה.
הרבה פילוסופים התחבטו בבעיה הזאת, והיא קשורה גם לבעיה הידועה כבעית הגוף והנפש. הגישה הדואליסטית לבעיית הגוף והנפש רואה בגוף ובנפש שתי ישויות שונות (לייבוביץ). על פי גישתו של לייבוביץ המחשב או ההתקן הפיזיקאלי הוא הגוף העושה לכל היותר פעולה פיזיקאלית, והאדם נותן לאותה הפעולה את המשמעות המתמטית. מתן המשמעות הוא פעולה שרק הנפש יכולה לעשות.
ההצלחה האדירה והבלתי מוסברת של השימוש במתמטיקה בתוך הפיזיקה הטרידה גם פיזיקאים מן השורה הראשונה (ווינברג), ובנושא זה יש ספרות רחבה. מנגד, מציאת כלים פיזיקאליים לצורך חישוב מתמטי היא בעיה דואלית אשר מטרידה את אנשי מחשבים.
השאלות המתעוררות: האם לכל בעיה מתמטית נוכל למצוא מכשיר פיזיקאלי מתאים ? אם לא, אז אלו בעיות מתמטיות ניתנות לחישוב כך, ואלו לא ? בהנתן כלי פיזיקאלי כלשהו, מהן הבעיות המתמטיות אותן ניתן לפתור באמצעותו ? במקרה וקיימים מספר מכשירים פיזיקאליים כאלו האם הם נבדלים זה מזה ביעילותם, כמו למשל בזמן הדרוש להפעלתם כדי לקבל את התוצאה או בקושי בבניתם, או בנתון אחר כלשהו ?
התבוננות פילוסופית אנאליטית במושג 'מחשב', לאור כל האמור למעלה, מובילה להגדרה הפיזיקאלית הבאה: מחשב, הוא התקן פיזיקאלי המצוי בתנאי התחלה מסויימים (הנקבעים על ידי נתוני הבעיה החישובית), ואשר עובר אבולוציה בזמן המובילה אותו לנקודה (בזמן) ידועה מראש, בה ניתן למדוד את אחד הגדלים על פניו, כאשר תוצאת המדידה היא תוצאת החישוב הרצוי.
לאור כל זאת נוכל אולי לסכם כי:
התקן פיזיקאלי המבצע חישוב מתמטי הוא מודל עליו נעשית סימולציה למציאות אחרת, לעיתים פיזיקאלית, ולעיתים קלושה יותר, מופשטת ומתמטית. שאלת היחס בין המודל הפיזיקאלי ל'מציאות' המתמטית שאותה הוא מנסה לדמות, קשורה לשאלת החישוביות, כלומר לשאלה אילו פונקציות אותו התקן מסוגל לחשב.
בהרצאה הקצרה הזאת ננסה להבהיר מקצת מן השאלות באמצעות הצגת דוגמאות. נזכיר שלושה מודלים שונים של חישוב: חישוב אנאלוגי, חישוב דיגיטאלי, וחישוב קוונטי. שני הראשונים הינם מודלים ידועים של חישוב ואילו השלישי הוא מודל חדש ומשלב תכונות של שניהם. תוך כדי הדיון בחישוב הדיגיטאלי, ננסה לנסח מעט פורמאלית יותר את בעית המודל באמצעות תזה הידועה כתזת טיורינג צ'רצ'.
חישוב אנאלוגי
בחישוב האנאלוגי אנו מנסים לבנות כלי פיזיקאלי המתנהג על פי אותן נוסחאות מתמטיות אותן אנו נדרשים לפתור. ההתקן הפיזיקאלי האנאלוגי לא פותר את הבעיה בצורה אנאליטית, כלומר על ידי פתרון של הנוסחאות באמצעות מניפולציה של סמלים לוגיים, אלא על ידי סימולציה פיזיקאלית המתנהגת על פי אותן נוסחאות. לדוגמא חישוב הפונקציה sin(q) לא יבוצע על ידי טור חזקות של qכפי שעושה מחשב דיגיטאלי אלא על ידי סיבוב דיסק כלשהו בזוית qומדידה של היטל הוקטור על הצירים הראשיים.
המכונה יכולה לעשות סימולציה פזיקאלית מדוייקת וישירה לתופעה. לדוגמא, אם ברצוננו לחשב עילוי על כנף של מטוס, נוכל להשתמש במנהרת רוח כמחשב אנאלוגי. מנהרת רוח עושה סימולציה פיזיקאלית מאוד מדוייקת לתופעה עצמה. אנו פשוט מודדים את כוחות העילוי שנוצרו על גבי כנף המודל הממוזער של המטוס, וכך מחשבים את כוחות העילוי על הכנף האמיתית. לעומת זאת הבעיה המתמטית יכולה להיות מוצגת בצורה מופשטת יותר (לאו דוקא קשורה לבעיה פיזיקאלית ספציפית) כגון חישוב של פונקציה או טור פונקציות (כמו למשל טור פורייה). רכיבי המכונה האנאלוגית צריכים אם כן להתנהג על פי אותה פונקציה או טור פונקציות. לדוגמא נציג מכונה פשוטה מאוד מסוף המאה התשע עשרה לחישוב טור (פורייה) של פונקציות.
המכונה הוצגה על ידי ראסל W.H.L.Russell ב- 1869 והיא מדהימה בפשטותה. הציור המופיע למטה לקוח מן המאמר המקורי. המכונה בנויה ממספר דיסקים המניעים אחד את השני. היחס בין הרדיוסים של הדיסקים יקבע את היחס בין המהירויות שלהם. על גבי כל דיסק ובמרחק כלשהו מן המרכז מוצמד כפתור (פרפר). הדיסקים מסומנים באותיות A B C ואילו הפרפרים מסומנים ב- a b g . הפרפרים מוצבים במרחקים a b c מן המרכז. הדיסקים מכסים זויות של rq nq mq באותו זמן, בשל היחס בין הרדיוסים. המיתרים המאוזנים מונחים חופשית על גבי הכפתורים. כל כפתור נע בתנועה סיבובית ודוחף כלפי מעלה את המיתר המונח עליו. המיתר עולה ויורד ועימו הציר המאונך לו. הצירים המאונכים עולים ויורדים בקצב של , c sin(rq) b sin(nq) ו- a sin(mq) .
הכבל שעובר מנקודה Q ועד לנקודה Q1 מסכם את שלושת הפאזות. תוצאת החישוב היא מיקומו של קצה הכבלQ1.
קלווין השתמש ברעיון הזה מספר שנים מאוחר יותר (1873) לצורך בנייתה של המכונה המפורסמת שלו לאנאליזה של גאות ושפל.
ציור 1: אנליזת פורייה באמצעות מכונה אנאלוגית
במכונה אנאלוגית אם כן, הפתרון לבעיית החישוב נובע מן הסימולציה ולא מהפעלת כלל לוגי כזה או אחר (כפי שנראה במקרה הדיגיטאלי). עוד אפשר לראות כי החישוב האנאלוגי מתבצע באמצעות משתנים רציפים. אנו יכולים להכניס נתונים או לקרוא אותם מתוך רצף של אפשרויות. כאן גם חבוי הקושי העיקרי בהפעלה של מכונות אנאלוגיות. המכונה לא יודעת להבחין בין טעות חישוב (רעש) לבין תוצאה אמיתית עבור תנאי התחלה שונים במעט.
המכונות האנאלוגיות יכולות לחשב פעולות אריתמטיות בסיסיות, הן יכולות לחשב אינטגראלים, לפתור משוואות דיפרנציאליות, לפתור מערכת משוואות ליניאריות, לעשות אנאליזת פוריה, ועוד.
המכונות האנאלוגיות הראשונות מסוף המאה התשע עשרה היו בנויות מגלגלים, קפיצים וכד'. לקראת אמצע המאה העשרים החליפו אותן מכונות אנאלוגיות המבוססות על רכיבים אלקטרומגנטיים כמו קבלים סלילים ונגדים. הורסיה השלישית והחדשה של מכונות אנאלוגיות היתה מבוססת על מגברי שרת (Operational Amplifiers)
חישוב דיגיטאלי
מודל החישוב הנפוץ ביותר כיום הוא מודל החישוב הדיגיטאלי. ראשיתו בשנות השלושים של המאה התשע עשרה (צארלס בבג'). ארכיטקטורת החישוב הנפוצה כיום ראשיתה בשנות הארבעים של המאה העשרים (וון ניומן). את המודל הדיגיטאלי ניתן לתאר בצורה הקומפקטית ביותר על ידי 'מכונת טיורינג'.
מכונת טיורינג היא מכונה וירטואלית פרימיטיבית בעלת סרט נתונים וראש קריאה וכתיבה הנמצא באחד מסדרת מצבים. ראש המכונה רץ על גבי הסרט, קורא וכותב סימנים.
ציור 2: מכונת טיורינג
מצב ראש המכונה וכן הנתון על גבי הסרט יקבעו את כיוון התזוזה של הראש (שלב אחד ימינה או שמאלה, או ללא תזוזה) ואת הנתון החדש אשר יודפס על גבי הסרט. לדוגמא אנו יכולים לבנות מכונה המסוגלת לחבר מספרים. אחת ההוראות המצויות בראש מכונה כזאת תהיה: אם ראש המכונה נמצא במצב 1 וקורא את הספרה 3 על גבי הסרט, על ראש המכונה לזוז ימינה צעד אחד ולהדפיס את הסימן 4 על גבי הסרט במיקום החדש. באופן דומה אפשר יהיה לבנות מכונות לפעולות אחרות במספרים הטבעיים.
השאלה המתבקשת היא אלו פונקציות מתמטיות מסוגלת מכונה כזאת לחשב ואלו לא. לצורך התשובה נגדיר שתי משפחות של פונקציות.
פונקציות ניתנות לחישוב: אלו כל הפונקציות אשר ניתנות לחיושב באמצעות תהליך ברור, מתכון ברור, המופעל צעד אחר צעד, על פי הוראות הניתנות מראש, או באמצעות הפעלת מכונה. המושג 'ניתן לחישוב' הוא אם כן אינטואיטיבי.
פונקציות ניתנות לחישוב באמצעות מכונת טיורינג: אלו כל הפונקציות הניתנות לחישוב באמצעות מכונה מן הסוג המתואר למעלה או נגזרת של מכונה כזאת, כמו למשל מכונה הפועלת על דף נתונים דו מימדי במקום על סרט נתונים.
ברור כי פונקציות ה'ניתנות לחישוב באמצעות מכונת טיורינג' הם 'ניתנות לחישוב'. ואולם לא ברור אם כל הפונקציות ה'ניתנות לחישוב' הינן 'ניתנות לחישוב באמצעות מכונת טיורינג'. פונקציה הניתנת לחישוב יכולה להיות מחושבת באמצעות מכונה אחרת כמו למשל מכונה אנאלוגית. האם יתכן כי קיימת מכונה אנאלוגית המחשבת פונקציה מסויימת אשר אין עבורה מכונת טיורינג ? טיורינג חשב כי לא תתכן אפשרות כזאת כלומר אם הפונקציה לא ניתנת לחישוב באמצעות מכונת טיורינג היא לא תהיה ניתנת לחישוב באמצעות מכונה כלשהי, זהו התוכן של תזת טיורינג צ'רצ.
כיום זו אחת השאלות העקרוניות ביותר בתורת המחשבים. מכונות טיורינג מתארות את המחשב המודרני שלנו, ותזת טיורינג – צ'רצ' אומרת כי המכונות שיש בידנו מסוגלות לחשב כל מה שניתן יהיה אי פעם לחשב באמצעות מכונה כלשהי, לרבות מכונות מודרניות כמו מחשבים קוונטיים או מחשבי ד.נ.א. הטענה של טיורינג וצ'רצ היא בגדר תזה ואין לה הוכחה, ואולם עד היום לא נמצאה פונקציה מתמטית אשר לא ניתן לחשב אותה באמצעות מכונת טיורינג ואשר קיים התקן פיזיקאלי (שונה ממכונת טיורינג) המחשב אותה.
שאלה נוספת עדינה יותר קיימת לגבי יעילות החישוב. את הבעיות הקלאסיות בתורת המחשבים אנו מחלקים למחלקות של סיבוכיות. סיבוכיות החישוב נמדדת על פי המקום (גודל הזכרון) הזמן (זמן הפעולה) האנרגיה, ושאר המשאבים הנדרשים למחשב כדי לפתור את הבעיה. יתכן כמובן כי שימוש במכונה אחת לפתרון בעיה כלשהי יהפוך להיות מסובך הרבה יותר מאשר שימוש במכונה אחרת. יתכן למשל כי לצורך פתרון משוואות ליניאריות יותר כדאי לנו מבחינת זמן הפעולה להשתמש במכונה אנאלוגית מאשר במכונה דיגיטאלית. בדיון בתזת טיורינג צ'רצ' עסקנו בעצם היכולת לפתור את הבעיה, ואולם כאן אנו דנים ביעילות הפתרון. שינוי המכונה יכול להביא לשינוי ביעילות הפתרון. המחשב הקוונטי למשל הופך להיות יעיל יותר בפתרון מספר בעיות קלאסיות בתורת המחשבים כמו למשל בבעית חיפוש איבר ברשימה לא ממויינת, או בבעית פירוק מספר למרכיביו הראשוניים.
לסיכום החישוב הדיגיטאלי הערה הסטורית: בעזרת המכונה שלו התכוון טיורינג להראות כי ניתן לעשות סימולציה פיזיקאלית של תהליך חשיבה אנושי. טיורינג חשב על הדרך בה אנו מחברים או מחסרים מספרים. בעזרת המודל שהציג הוא יצר קשר בין מושגים מתמטיים לבין מושגים פיזיקאליים של חישוב. תזת טיורינג צ'רצ' טוענת כי המודל הזה של טיורינג הוא יוניברסלי.
חישוב קוונטי
חישוב קוונטי אנו עושים שימוש בפיזיקה קוונטית בכדי לחשב. כלומר האלגוריתמים עצמם עושים שימוש בתכונות קוונטיות. גם במחשב הקלאסי המודרני אנו עושים שימוש בפיזיקה קוונטית וזאת בכדי לבנות את התקני החישוב העשויים מוליכים למחצה כמו למשל הטרנזיסטורים. ואולם בחישוב הקוונטי האלגוריתם עצמו הוא קוונטי ולא רק ההתקן. כיצד יתכן איפה שמושגים פיזיקאליים הלקוחים מעולם הפיזיקה הקוונטית, מוצאים דרכם לעולם המחשבים. זו שוב החידה שהזכרנו בתחילת הדיון הקושרת פיזיקה ומתמטיקה.
מהו אם כן מחשב קוונטי ? בתחילה נתאר את היחידה הבסיסית של החישוב הקוונטי, היא הקיו-ביט, אח"כ נביא דוגמא לאלגוריתם קוונטי.
סופרפוזיציה, קיו-ביט, שער קוונטי, ואלגוריתם קוונטי.
סופרפוזיציה
הדיאגרמה הבאה ידועה כדיאגרמת נקר (ע"ש קריסטלוגראף מן המאה ה 19) והיא משמשת כניסוי בפסיכולוגיה של התפיסה.
ציור 3: קוביות נקר
שתי הקוביות נראות לעיתים כאילו הן בולטות מן הדף החוצה, ולעיתים כאילו הן חודרות את מישור הדף פנימה. לעיתים נראה כאילו רק אחת מהן בולטת החוצה ואילו השניה פנימה, נסה. במובן מסויים כל האפשרויות מצויות בדיאגרמה בעת ובעונה אחת. אולם בשעה שמתבוננים בהן מקבלים רק את אחת האפשרויות. במבט מאומץ או לאחר שנסיט את המבט הצידה ונחזור ונתבונן בקוביות נוכל להבחין באפשרות אחרת אשר מתממשת.
בפיזיקה קוונטית קיימים חלקיקים אשר מסוגלים להמצא בבת אחת במספר 'מצבים'. 'מצב' החלקיק יכול לתאר את מיקומו של החלקיק או את המומנט שלו או משתנה מדיד אחר. אנו אומרים אז כי החלקיק נמצא בסופרפוזיציה של כל המצבים. לאחר המדידה או ההתבוננות בחלקיק נוכל למצוא אותו באחד מן המצבים (הענפים) ובאחד בלבד. אנו אומרים כי המדידה הביאה ל 'קריסה' של הסופרפוזיציה לאחד מן הענפים. בדיוק כמו בדוגמה למעלה, שם ההתבוננות בקוביות משמעותה מדידה והיא מביאה ל 'קריסה' של הסופרפוזיציה כלומר להתממשות של אחד מן המצבים בלבד.
נסה לסובב כעת את הדיאגרמה, נניח ב 900 ימינה. כעת אם תתבונן שוב סביר להניח שהסופרפוזיציה תקרוס מהר יותר דוקא לאחת מהאפשרויות האחרות. מה שעשית עכשיו זו פעולה של מחשב קוונטי. הסיבוב פועל על הסופרפוזיציה כולה כלומר על כל המצבים בבת אחת והוא מוביל לסופרפוזיציה אחרת. הסיבוב שינה את ההסתברות לקריסה לתוך כל אחד מן הענפים. ההסתברות היתה רשומה במובן זה או אחר בתוך הסופרפוזיציה.
קיוביט
נתבונן כעת בחלקיק הנמצא בסופרפוזיציה של שני מצבים. נסמן את המצבים ב <1| וב <0|. אנו רושמים את הסופרפוזיציה כ –
a |1> + b |0>
הקבועים a ו – b הם מספרים מרוכבים ונקראים אמפליטודות והם נקבעים על פי ההסתברות למצוא את הסופרפוזיציה במצב <0| או <1| לאחר מדידה ( a|2| זו ההסתברות לכך כי לאחר מדידה נמצא את החלקיק במצב <1| ו - b|2| זו ההסתברות לכך שלאחר המדידה נמצא את החלקיק במצב <0| ). סופרפוזיצה כזאת נקראת קיוביט והיא משמשת כרכיב הבסיסי של המחשב הקוונטי. הסיבה לשם הוא הדמיון לביט הקלאסי. אלא שהביט הקלאסי יכול להמצא או במצב 0 או במצב 1 ואילו הקיוביט נמצא בשני המצבים בבת אחת. לדוגמא החלקיק יכול להיות אלקטרון, והמצבים <0| או <1| הם מצבי הספין שלו, ספין למעלה או ספין למטה. האלקטרון יכול להמצא בסופרפוזיציה של שני מצבי הספין. במובן מסויים הוא גם במצב ספין למעלה וגם במצב ספין למטה. האלקטרון ומצבי הספין שלו מהווים קיוביט אחד.
שער קוונטי
נתבונן כעת במעגל הלוגי (השער) הקלאסי הבא:
ציור 4: שער XOR קלאסי
לשער זה יש שתי כניסות ושתי יציאות. השער נקרא XOR . הוא מחשב את הפונקציה XOR(הפונציה הלוגית "או מוציא") של הכניסות. כאשר אחת הכניסות היא 0 והשניה 1 המוצא התחתון יהיה 1, כאשר שתי הכניסות הן אפס או שתיהן 1 המוצא התחתון יהיה 0.
כעת נתבונן בורסיה הקוונטית של אותו מעגל כלומר נציב את הסופרפוזיציה הבאה בכניסה למעגל :
|0>|0> + |0>|1> + |1>|0> + |1>|1>
במוצא המעגל נקבל את הסופרפוזיציה:
|0>|0> + |0>|1> + |1>|1> + |1>|0>
מעגל כזה ניתן למימוש פיזיקאלי קוונטי. העובדה שהכנסנו סופרפוזיציה בכניסה למעגל וקיבלנו סופרפוזיציה במוצא המעגל פירושה כי יש כאן חישוב מקבילי. השער מבצע ארבעה חישובים במקביל מכיוון שמדובר כאן בשני ביטים. במקרה של שלושה ביטים היינו עושים שמונה חישובים במקביל ובמקרה של n ביטים אנחנו עושים n2 חישובים במקביל.
על פי תאורמה ידועה בתורת המחשבים ניתן לרשום כל אלגוריתם (מחשב) קלאסי באמצעות סדרה של מעגלים מן הסוג האמור למעלה ווריאציות שלהם, ובלשון תורת המחשבים, XOR הוא מעגל יוניברסלי. לכן נוכל לפרק כל מחשב קלאסי לרכיבים הדומים למעגל XOR ולהחליף כל אחד מהם במקבילה הקוונטית שלו, אותה ניתן ניתן לממש פיזית. בדרך זו הפכנו את המחשב הקלאסי למחשב קוונטי.
אלגוריתם קוונטי
נניח לדוגמא כי נתונה לנו בעיה של פירוק מספר לגורמים הראשוניים שלו. נניח כי c הוא מספר בן ספרות רבות (מספר כזה מופיע בקודים צבאיים או בנקאיים). נניח כי אנו רוצים למצוא את כל המחלקים שלו. נניח גם כי נתון לנו מחשב (אלגוריתם) קלאסי אשר בודק אם מספר נתון מחלק את c או לא. למצוא אם מספר נתון הוא מחלק או לא ניתן בקלות ואולם לאתר את כל המחלקים זה קצת קשה יותר. ידוע כי הסיבוכיות של הבעיה הינה גבוהה מאוד. פירוש הדבר כי עבור מספר בן כמה מאות ספרות גם מחשב מודרני יתקשה לפתור את הבעיה בזמן סביר. ואולם נראה להלן כיצד עושה זאת מחשב קוונטי. ננצל את תכונת החישוב המקבילי שלו.
ציור 5: אלגוריתם קוונטי
נהפוך את המחשב הקלאסי לקוונטי על פי האמור למעלה. כעת בכניסה למעגל נציב סופרפוזיציה של כל המספרים בין 1 ל שורש הריבועי של c . המעגל יחשב את כל הנתונים בבת אחת ותתקבל התוצאה:
|2>|0> + |3>|0> + |4>|0> + |5>|1> + . . . . .
כלומר תתקבל סופרפוזיציה של כל התוצאות. בביט העליון של התוצאה יש העתק של ביט הכניסה, ואילו הביט התחתון הוא 'דגל' המורה אם המספר הנבדק מחלק את c או לא. בדוגמא למעלה קיבלנו כי 2 לא מחלק את c, 3 גם הוא לא מחלק את c, 4 לא מחלק את c , 5 מחלק את c וכן הלאה.
כעת כדי לקבל תוצאה נבצע מדידה. תוצאת המדידה תתן לנו מספר כלשהו בין 1 לשורש הריבוע של cוכן ביט המורה אם המספר מחלק את c או לא. אין לנו כל שליטה על המספר אליו תקרוס כל התוצאה כפי שראינו למעלה בדוגמא עם הקוביות. כעת מאחר וההסתברות לקריסה לכל אחד מהמספרים בין 1 לשורש הריבועי של c היא שווה, וכי רוב המספרים האלו אינם מחלקים את c סביר שנקבל איזו אינפורמציה חסרת ערך כגון שמספר מסויים לא מחלק את c.
ראינו אם כן כי אמנם חסכנו זמן רב בכך שהחישוב היה מקביל ואולם קשה לנו לקרוא את התוצאה. בכדי לקרוא את התוצאה נצטרך להשתמש ברכיב קוונטי המשמש כמגבר הסתברות. מגבר כזה ישחק באמפליטודות של הסופרפוזיציה במוצא המחשב ויגביר את האמפליטודות השייכות לענפים בהם הביט השני מורה על <1| על חשבון שאר האמפליטודות. נראה לכאורה כי עלינו לדעת את התשובה לבעית הפירוק בכדי שנוכל לבנות רכיב כזה, ואולם אין הדבר כך. המחשב הקוונטי לא בודק את האפשרויות אחת אחת כפי שעושה מחשב קלאסי, אלא הוא פועל על כולן בבת אחת. פעולה של רכיב כזה ראינו למעלה כאשר סובבנו את קוביות נקר בזוית כלשהי. כל הסופרפוזיציה על כל ענפיה "הסתובבה" באותה זוית. התוצאה היתה כי על ידי הסיבוב הגברנו את ההסתברות לקריסת הסופרפוזיציה לכיוון זה או אחר.
מגבר הסתברות כזה יש להפעיל לפני המדידה. כעת נוכל למדוד. הסיכוי שנקבל תוצאה משמעותית יהיה כעת גבוה יותר. אחרי המדידה יהיה בידנו מספר כלשהו d אשר מחלק את c ונוכל לחזור על כל התהליך עם c/d.
חישוב קוונטי הוא אם כן חישוב מקבילי, ואולם הרבה יותר מחישוב מקבילי, ניתן להשיג באמצעותו תוצאות טובות יותר מאשר ניתן להשיג עם מחשב קלאסי דיגיטאלי. בין השאר ידועים אלגוריתמים קוונטיים לחישוב טרנספורמצית פוריה ולחיפוש ברשימה לא ממויינת טובים יותר ממקביליהם הקלאסיים.
נסיים בתוצאה מעניינת נוספת הקשורה לחישוב הקוונטי. ב 1985 הראה פיזיקאי בשם דויד דויטש
כי ניתן לבנות מכונה קוונטית יוניברסלית כך שכך תהליך פיזיקאלי ניתן יהיה לתאר באמצעותה. עם ה'תוכנה' המתאימה יוכל מחשב קוונטי כזה לשמש כמודל לכל תהליך פיזיקאלי כולל למשל תהליך חשיבה אנושי. המשמעויות של הטענה הזאת של דויטש מרחיקות לכת וחורגות מן הדיון כאן.
סיכום
הופעתו של מודל חישוב חדש כמו המודל הקוונטי מעוררת מחדש שאלות של הגדרת מושג החישוב. מהו היחס בין המודל הפיזיקאלי לבין כל מה שניתן לחישוב מתמטי בעזרתו של אותו מודל. ראינו שלושה מודלים של חישוב, האנאלוגי, הדיגיטאלי, והקוונטי. במחשב האנאלוגי המושגים מודל וסימולציה ברורים ואינטואיטיביים מאוד. המודל הדיגיטאלי שורשיו בנסיון לעשות סימולציה לתהליך חשיבה לוגי.
המודל הקוונטי מפתיע אותנו בכל הנוגע לקשר בין הפיזיקה ליעילות חישוב מתמטית. המכונה היוניברסלית הקוונטית של דויטש מציגה שאלות פילוספיות כבדות הנוגעות לסוגיית הגוף והנפש.
המודל הדיגיטאלי הוא המפותח ביותר כיום בעיקר מסיבות של יעילות. בעזרת מודל כזה נעשתה בעבר הקלאסיפיקציה של רמות סיבוכיות החישוב, והוגדרו פונקציות ניתנות ולא ניתנות לחישוב (תזת טיורינג צ'רצ'). החיפוש אחר מודלים חדשים נובע בין השאר מן הנסיון להבין טוב יותר את גבולות סיבוכיות החישוב, מן הנסיון לחצות אותם בעזרת הצגת מודל חדש, ומן הנסיון לאשש או להעמיד במבחן את תזת טיורינג צ'רצ'.
שאלות רבות הקשורות לחישוביות עדיין לא ברורות כגון: מה מעמדה של תזת טיורינג צ'רצ' ? האם ניתן להציג תזה דומה עבור מכונות אנאלוגיות או קוונטיות או אחרות ?
מענה על השאלות האלו הנראות לכאורה כשאלות טכניות, יגלה כנראה הבנה עמוקה יותר של מושג החישוביות. הבנה כזאת אולי תשפוך אור על השאלה הכבדה יותר והפילוסופית של היעילות הבלתי מוסברת של המתמטיקה בתוך הפיזיקה.
בבליוגרפיה
H.Goldstine, The computer, from Leibniz to Von Neumann, Princeton University Press, 1972
M.Nielsen, I.Chuang, Quantum computation and quantum information, Cambridge 2000
J.Searle, Minds, brains and science, B.B.C.London, 1984
M.Steiner, The applicability of mathematics as a philosophical problem, Harvard Univ. Press, 1998
A.Turing, On computable numbers with an application to the Entscheidungsproblem, Proc.London Math.Soc.42
דוקטור למתימטיקה מטעם מכון ויצמן למדעים. בשנים האחרונות ערך מספר מחקרים בתחום פיסיקת הקוונטים והפילוסופיה של המדע, ופרסם כמה מאמרים בנושא החישוב הקוונטי. מרצה כיום באקדמיה לאמנויות, "בצלאל".
