חישוב קוונטי - מה זה בדיוק

הפוסט הזה הוא הלב התיאורטי של כל סדרת הפוסטים שלי על חישוב קוונטי. עד עכשיו הצגתי את הרעיונות הפיזיקליים ואת המסגרת המתמטית שבה הם מתוארים, ונתתי דוגמאות לתעלולים שונים ומשונים שמתבצעים בעזרת הרעיונות הפיזיקליים הללו ומפורמלים בעזרת המתמטיקה, אבל לא דיברתי בכלל על מה שמדעני מחשב אוהבים לדבר עליו - מודלים חישוביים. זה בדיוק מה שצריך לדבר עליו אם רוצים לטעון טענות כמו “כנראה שחישוב קוונטי חזק יותר מחישוב רגיל” שאני עומד לטעון בהמשך - צריך להבין מה זה אומר “חישוב קוונטי” ומה זה “חישוב רגיל”; ומה זה אומר “חזק יותר”, ולמה “כנראה”. כל הדברים הללו דורשים פורמליזם, וכזה יגיע בהמשך.

לפני שנגיע לפורמליזם ואולי נבריח קוראים שהגיעו לכאן בטעות, אני רוצה להקדיש כמה דקות להסבר למה חישוב קוונטי הוא יותר מאשר מציגים אותו לרוב, כשהפעם אני גם יכול לגבות את עצמי בהסברים יותר רציניים מאשר בפתיחת סדרת הפוסטים הזו. המיסקונספציה העיקרית שאני רוצה לצאת נגדה בכל סדרת הפוסטים הזו על חישוב קוונטי היא התפיסה של חישוב קוונטי בתור “סופר-דופר-חישוב-מקבילי” ותו לא. זו תפיסה שמוצגת בכל מקום, כולל במאמרים ובספרים של אנשים רציניים מאוד שכנראה מבינים את התחום הרבה יותר טוב ממני, אבל עושים פשרות בשל הנסיון לכתוב לקהל רחב.

בואו נראה כמה דוגמאות לזה. בכתבה הזו אומרים

בניגוד למחשב רגיל, שיכול לבצע רק חישוב אחד בכל פעם - מהיר ככל שיהיה, מחשב קוונטי מסוגל לבצע כמה חישובים במקביל או להימנע במקרים מסוימים מביצוע חישובים שאינם הכרחיים להשלמת משימה. בכך הוא מקצר משמעותית את הזמן הדרוש להשלמתה.

כלומר, חישוב מקבילי ששונה מזה של מחשב “רגיל” (שבו כדי להשיג מקביליות אמיתית צריך כמה מעבדים שרצים במקביל, אבל גם במקרה זה כל מעבד עדיין מבצע פעולה אחת בפעם).

וכאן אומרים

באמצעות קיוביטים הנמצאים במצב הביניים הזה אפשר ליצור מעבדים למחשבים, שיפעלו במקביל: החלקיקים שינועו במעגלים האלקטרוניים יהיו בכמה מצבים בעת ובעונה אחת, תוך כדי שהם מבצעים מספר פעולות חישוביות בעת ובעונה אחת.

שזה שוב אותו דבר.

ואילו כאן אומרים

המערכות השזורות מציעות אפשרות לחישוב במקביל - כלומר, בדיקה של מספר פתרונות בעת ובעונה אחת, באמצעות חישוב המתבצע לפי חוקים מתמטיים חדשים, שאינם מתקיימים מחוץ למערכות שזורות... חישוב קוונטי כזה דומה לבעיה של סריקת מספר גדול של מזוודות בחיפוש אחר פצצה. במצב רגיל יש לסרוק את המזוודות בזו אחר זו, תהליך שעלול להימשך זמן רב מדי. לעומת זאת, התייחסות למזוודות כאל מערכות שזורות מאפשרת לבדוק רק חלק קטן מהן, ובכל זאת לקבל מידע על כולן - ובכך לקבוע במהירות ובוודאות היכן מוטמנת הפצצה. המגבלה העיקרית על השימוש במערכות שזורות לצורך חישובים מהירים היא הכלל הידוע של תורת הקוונטים, שלפיו המדידה - או התצפית - משפיעה על התוצאה. מכיוון שכך, במשך כל תהליך החישוב אסור "להציץ" אל תוך המערכת...

כאן כבר רומזים קצת על המורכבות של הסיפור האמיתי (ה”חוקים מתמטיים חדשים” והעובדה ש”אסור להציץ”) אבל גם כאן מתקבל רושם שגוי.

הדוגמה המצערת ביותר מבחינתי היא בספר Anathem של ניל סטיבנסון. סטיבנסון הוא סופר מדע בדיוני מוכשר ביותר, שלא מהסס להיכנס לפרטים טכניים ולהציג רעיונות מתמטיים לא טריוויאליים. לא אגלה כלום על עלילת Anathem או הרקע שלו כדי לא לקלקל לקוראים הפוטנציאליים, אבל אציין שסטיבנסון בהחלט לוקח את הזמן בספר הזה כדי להסביר רעיונות לא טריוויאליים לעומק, ויש לו זמן, ויש לו הצדקה עלילתית לזה, והוא עושה את זה מצוין והספר באופן כללי נפלא. מתישהו בספר הוא עושה את זה גם עבור מחשב קוונטי. והתיאור שלו הוא בדיוק התיאור ה”מקבילי” הרגיל - לא אצטט כאן, אבל הרעיון הוא שהמחשב נמצא בסופרפוזיציה של כל האפשרויות שהוא רוצה לבדוק, מבצע את החישוב בכולן, ואז מודדים אותו והוא קורס אל התוצאה ה”נכונה”.

התיאורים הללו הם כולם נכונים. אני לא בא לומר שמישהו טועה כאן במשהו. חישוב קוונטי הוא אכן, בבסיסו, חישוב מקבילי מחוכם. אבל אני חושב שהתיאורים הללו מפספסים את הפואנטה ולא באמת מעבירים לקורא ההדיוט את הסיבה שבגללה חישוב קוונטי הוא משהו חדש לגמרי ושונה באופיו מחישובים רגילים. אני גם חושב שהתיאורים הללו גורמים לחישוב קוונטי להיראות חזק יותר מכפי שהוא באמת.

אז הנה שתי הנקודות שאני חושב שכל מי שרוצה להכיר חישוב קוונטי צריך להיות מודע להן, גם אם הוא רוצה להסתפק בידע ברמת המדע הפופולרי. גם הן, כמובן, לא כל הסיפור, אבל לדעתי ברמת המדע הפופולרי הן מה שחסר כדי שהסיפור יהיה פחות או יותר שלם. הראשונה מראה למה חישוב קוונטי הוא במובן מסויים מוגבל, והשניה מראה למה חישוב קוונטי הוא במובן מסויים חזק.

הנקודה הראשונה היא שחישוב קוונטי שמתנהל כך: מתחילים עם סופרפוזיציה של כל הקלטים האפשריים לפונקציה כלשהי, מחשבים את הפונקציה על כולם “בבת אחת” ולבסוף מבצעים מדידה - חישוב כזה הוא חסר ערך. מה שנקבל בו בסופו של דבר הוא את הערך של הפונקציה על אחד מהקלטים, ואת הערך הזה נקבל באקראי. באותה המידה כבר יכלנו לבחור קלט באקראי ואז לבצע את החישוב עליו בעצמנו. לב לבו של העניין - האתגר המרכזי של כל אלגוריתם קוונטי שהתחיל עם גישת הסופרפוזיציה של הכל - הוא בביצוע מניפולציה כלשהי של הסופרפוזיציה-של-כל-ערכי-הפונקציה בצורה כזו שמבטיחה שהפלט שנקבל יכיל אינפורמציה מועילה עבורנו. אנחנו נראה בהמשך דוגמאות לשתי דרכים שונות לעשות את זה - דרך אחת היא לתת איכשהו משקל הסתברותי גבוה יותר לתוצאות “רצויות” של הפונקציה, שיבטיחו הסתברות יותר גבוהה למדוד אותה; ודרך אחרת היא לשלוף מידע מועיל שנמצא בצורה כלשהי בכל ערכי הפונקציה. אלו לא רעיונות שקל להסביר על רגל אחת ולכן יוקדשו להם פוסטים; מה שחשוב לי להסביר ברמת המדע הפופולרי הוא עד כמה השלב הזה קריטי. אחרי שביצענו חישוב קוונטי וקיבלנו סופרפוזיציה של כל ערכי הפונקציה האפשריים, אין לנו דרך לגשת אל המידע הזה בצורה ישירה - אנחנו חייבים להשתמש בתכסיסים שיאפשרו לנו לשלוף איכשהו פיסת מידע מתוך הסופרפוזיציה הנפלאה הזו. הברכה של הסופרפוזיציה שהיא בלב החישוב הקוונטי היא גם הקללה שלו. לטעמי זה מרתק, מרתק לחלוטין; הרבה יותר מרתק מסתם “חישוב קוונטי מבצע המון פעולות במקביל”.

הנקודה השניה שחשוב לי להתייחס אליה - והיא לטעמי אפילו יותר Mind blowing מהראשונה, אם כי ייתכן שרק עבור קוראים עם יותר ידע מתמטי - היא מה ההבדל המהותי בין חישוב קוונטי ובין חישוב הסתברותי. חישוב הסתברותי הוא משהו שקיים במחשבים כבר כיום ומוכיח את עצמו בצורה נפלאה בפועל (למשל, אלגוריתם מילר-רבין למציאת ראשוניים). אפשר לתאר חישובים הסתברותיים בצורה דומה מאוד לזו שבה אתאר חישוב קוונטי בפוסט הזה; במובן מסויים גם חישוב הסתברותי הוא סוג של מקביליות (החישוב לא נמצא בו זמנית בכמה מצבים, אבל הוא יכול להיות בכמה מצבים שונים על אותו קלט ולכל מצב יש את “ההסתברות שאני נמצא במצב הזה כרגע”). גם חישוב קוונטי נגמר על ידי מדידה, שמחזירה תוצאה באופן הסתברותי. אז מה כל כך שונה, תגידו? למה יש אלגוריתם קוונטי יעיל שיודע לפרק מספר לגורמים אבל אין אלגוריתם הסתברותי יעיל שעושה את זה? אני אסביר את מלוא ההבדל הטכני לקראת סוף הפוסט, אבל הנה שורת מחץ (שהיא כמובן לא מדויקת ונועדה לתת אפקט Wham) בשבילכם - כי בחישוב קוונטי, להבדיל מחישוב הסתברותי רגיל, ההסתברויות יכולות להיות מספר שלילי.

עבורי, הרגע שבו “נפל לי האסימון” והתחלתי להבין מה זה חישוב קוונטי ולמה הוא כל כך נפלא היה בדיוק כשהבנתי את הנקודה הזו. אני מקווה שאלו מכם שישרדו איתי עד סוף הפוסט, כשאציג את הפורמליזם המלא, יחושו כמוני.

עכשיו בואו נעבור לדבר על הגדרות פורמליות. ראשית כל אני רוצה להזכיר בקצרה איך מפרמלים חישובים רגילים. המודל הסטנדרטי הוא מכונת טיורינג. המודל הזה הוא המצאה גאונית, לא פחות; בזמנו של טיורינג לא היו מחשבים, וכל הפורמליזמים המתמטיים שתיארו את מה שהיום אנחנו קוראים לו פונקציות ניתנות לחישוב היו מאוד מתמטיים באופיים. בא טיורינג והמציא משהו שנראה כמו מכונה, שאפשר לממש פיזיקלית, ואפשר “להרגיש בידיים” מה היא עושה. הרעיון הוא כזה: יש לנו סרט שמחולק לתאים כאשר בכל תא יכול להיות כתוב 0 או 1 (לרוב מרשים גם תאים ריקים, או ערכים נוספים פרט ל-0 או 1, אבל הפעם זה לא יסייע לנו). על גבי הסרט הזה מתרוצצת לה מכונה קטנה שכוללת ראש קורא וכותב, ומחוברת ליחידה לוגית שמכילה סט סופי של הוראות. ההוראות הן תמיד מהצורה “אם עכשיו אתה רואה 0 ואתה נמצא במצב בקרה 7, אז כתוב 1 ולך צעד אחד ימינה” וכדומה. זה הכל. היצור הקטן והעלוב הזה, שאפשר לבנות אותו בלגו אם רוצים, יכול לממש כל תוכנית מחשב שאתם יכולים לכתוב כיום.

עכשיו, מה שאנחנו נרצה לדבר עליו כל הזמן הוא מכונות טיורינג יעילות. המושג של “יעילות” הוא לא טריוויאלי, והקונצנזוס שהגיעו אליו יכול להיראות מוזר לחלקכם. הרעיון הוא שמכונה היא יעילה אם זמן הריצה שלה על כל קלט הוא פולינומי בגודל הקלט. כלומר, קיים פולינום \( p \) כך שלכל קלט \( x \), זמן הריצה של המכונה על \( x \) הוא לכל היותר \( p\left(\left|x\right|\right) \), כאשר \( \left|x\right| \) הוא מספר הביטים שמרכיבים את \( x \). המגבלה הזו על זמן הריצה של המכונה גם משרה מגבלה על גודל הסרט שהיא עשויה “לנצל” - אפשר להניח שגודל הסרט הוא לא יותר מ-\( p\left(\left|x\right|\right) \). ליודעי דבר אעיר שאני מנסה להתחמק כאן מכך שבהגדרה הכללית שלה, הסרט של מכונת טיורינג הוא לא חסום, ואז לכו תתווכחו עם אנשים שטוענים שזה לא מודל ריאליסטי כי אין בעולם האמיתי סרטים לא חסומים (כמובן, גם עכשיו יבוא חכמולוג ויטען שעבור \( x \) מספיק גדול, \( p\left(\left|x\right|\right) \) יכול להיות גדול יותר ממספר האטומים ביקום ולכן אין מימוש פיזיקלי למכונת הטיורינג שמטפלת ב-\( x \) הזה; אבל זו תמיד עם העובדה שאנחנו מרשים ל-\( x \) להיות גדול באופן בלתי חסום).

הדבר החשוב ביותר במודל הזה הוא הלוקליות שלו (“אה-הא!” אתם אומרים, “זה מה שהולך להישבר במכונה קוונטית!” - ובכן, לא). הראש הקורא וכותב הוא קטן ומסכן ובכל רגע נתון הוא נמצא רק על תא מסויים בסרט. זה אומר שהשינוי שהוא יכול לעשות הוא תמיד במקום אחד; הוא לא יכול לשנות את כל הסרט בו זמנית, והוא לא יכול לראות את כל הסרט בבת אחת ולהגיב על פי זה. זה לא כל כך חשוב שהוא יכול לראות רק תא אחד בו זמנית - אפשר היה גם לדבר על סיטואציה שבה הוא רואה את מאה התאים שמסביבו ויכול לשנות את כולם בבת אחת - מה שקריטי הוא רק שמספר התאים שהוא יכול לראות בו זמנית הוא חסום, כלומר לא תלוי ב-\( \left|x\right| \). מודל שבו המגבלה הזו תוסר יהיה כבר חזק מדי ואני לא הולך לדבר עליו (לב הבעיה במודל כזה הוא שאחד משניים - או שהתיאור הפורמלי של מכונה במודל הזה יהיה אינסופי, וזה לא ריאליסטי; או שהתיאור שלה יהיה סופי, אבל אז אפשר יהיה לסמלץ אותה עם מכונת טיורינג מוגבלת ולא הרווחנו כלום).

עכשיו, אפשר קצת להגמיש את ההגדרה ולקבל מודל שקול למכונת טיורינג אבל שמרחם עלינו קצת ברמת הפרטים. במודל הזה, שדומה יותר לאופן שבו מחשב פועל, החישוב שלנו על קלט \( x \) מתחיל עם רגיסטר שגודלו \( p\left(\left|x\right|\right) \), כאשר “רגיסטר” הוא שם מפוצץ לתא זכרון שכולל כמה ביטים. בואו נסמן \( \left|x\right|=m \) ו-\( p\left(\left|x\right|\right)=n \), אז הרגיסטר ניתן לתיאור על ידי סדרה \( a_{1},\dots,a_{n} \) של ביטים. אבל מכיוון שאנחנו בסדרת פוסטים על קוונטים, בואו נשתמש בסימון \( \left|a_{1}\dots a_{n}\right\rangle \) כדי לתאר את התוכן של הרגיסטר בזמן נתון כלשהו.

בתחילת החישוב, הרגיסטר כולל את הקלט ואפסים בכל מקום אחר, כלומר המצב ההתחלתי של החישוב ניתן לתיאור בתור \( \left|x0^{n-m}\right\rangle \). וכעת, מהו החישוב? סדרה של ערכים שונים שהרגיסטר מקבל, כך שכל שני ערכים סמוכים בסדרה מתקבלים האחד מהשני על ידי ביצוע של צעד חישוב אחד.

כעת, מהו צעד חישוב? במכונת טיורינג, כפי שאמרנו, מה שחשוב בצעד חישוב הוא הלוקליות שלו. כל צעד מתבסס על כמות חסומה של מידע, ומשפיע רק על כמות חסומה של ביטים בסרט. עם זאת, צריך להיזהר לא לחסום את המידע הזה יותר מדי - אחרת אנחנו עלולים לקבל מודל מוגבל וחלש יותר ממכונת טיורינג. הנה פשרה מתקבלת על הדעת: כל צעד חישוב מסתכל על שלושה ביטים מתוך הרגיסטר, ומשנה רק אותם, כשהערך החדש שהוא נותן להם מחושב איכשהו מתוך הביטים הללו.

פורמלית, כל פעולה אטומית כזו ניתנת לתיאור באמצעות מעגל לוגי קטן \( F \) שמקבל שלושה קלטים ומוציא שלושה פלטים, כלומר \( F\left(x,y,z\right)=\left(a,b,c\right) \). עכשיו אני אשתמש בסימון קצת עקום כדי לתאר את פעולת \( F \) על רגיסטר שלם, אבל תבינו את הכוונה שלי:

\( F^{ijk}\left|x_{1}\dots x_{n}\right\rangle =\left|x_{1}\dots x_{i-1}ax_{i+1}\dots x_{j-1}bx_{j+1}\dots x_{k-1}cx_{k+1}\dots x_{n}\right\rangle \)

כאשר \( \left(a,b,c\right)=F\left(x_{i},x_{j},x_{k}\right) \).

זה סימון מתוסבך, אבל המשמעות ברורה: \( F^{ijk} \) הוא האופרטור שפועל על הרגיסטר על ידי הפעלת \( F \) על הביטים \( x_{i},x_{j},x_{k} \) והחלפתם בתוצאה של \( F \). למה, הו למה אני משתמש בכזה סימון מתוסבך כשיש לי מכונת טיורינג? מן הסתם, כי חישובים קוונטיים יתוארו (בצורה נוחה) בעזרת הסימון המתוסבך הזה ואני רוצה שתראו שגם חישוב רגיל אפשר לתאר באותו האופן (כלומר, ההבדל בין שתי שיטות החישוב הוא לא כזה גדול).

אם כן, אפשר לתאר חישוב רגיל בתור הפעלה סדרתית של אופרטורים שפועלים על שלושה ביטים כל אחד בתורו, אבל הנה לכם שאלה - אילו אופרטורים מפעילים? יש הרבה אופרטורים אפשריים, איך מחליטים מה להפעיל בכל שלב? ובכן, התחושה הטבעית שלנו היא שהמכונה עצמה צריכה להחליט על המקום מה להפעיל, בהתבסס על מצבים פנימיים שלה או משהו דומה. אבל מסתבר שאפשר גם בלי זה - אפשר יהיה להתחייב מראש על סדרת האופרטורים שמפעילים על הרגיסטר, וזאת מבלי לדעת בכלל מה הקלט שהולכים לקבל אלא רק מה אורכו.

במילים אחרות - לכל מספר טבעי \( n \), המודל החישובי שלנו כולל סדרת שערים \( F_{1},F_{2},\dots,F_{n} \), והחישוב הוא הפעלה סדרתית של ה-\( F_{i} \)-ים הללו על הרגיסטר, החל מהרגיסטר ההתחלתי. יש רק בעיה אחת עם ההגדרה זו - היא אומרת שנדרש אינסוף מידע כדי לתאר את המודל החישובי שלנו (וזה אומר, אינטואיטיבית, שהוא לא משהו שאפשר לממש בפועל - “תוכנית מחשב אינסופית”). למה אינסוף מידע? הרי \( F_{1},\dots,F_{n} \) היא סדרה סופית בהחלט! ובכן, כי אנחנו צריכים סדרה כזו לכל \( n \) (ליתר דיוק, לכל \( n \) שמתקבל בתור \( p\left(\left|x\right|\right) \) עבור \( x \) כלשהו, אבל לרוב יהיו אינסוף כאלו). לכן מה שמקובל לדרוש הוא שלכל אינסוף סדרות השערים הללו יהיה איזה שהוא תיאור קומפטי, סופי, מין “נוסחה” שנותנת אותם. איך אני יכול לפרמל את ה”נוסחה” הזו מבלי להגביל את עצמנו יותר מדי? ובכן, זה יצחיק אתכם בוודאי, אבל בעזרת מכונת טיורינג.

זה נראה מגוחך, כי באתי להגדיר מודל חישוב שקול למכונת טיורינג, ובסוף אני אשתמש במכונת טיורינג כדי לתאר חלק ממנו. אבל שימו לב שאני עדיין מקבל מודל שקול, והמכונה הנוספת שבה אני אשתמש תפעל בצורה מוגבלת למדי (היא לא תדע מה הקלט אלא רק מה אורכו) ושהיעד האמיתי שלי הוא הגדרה של חישוב קוונטי.

עכשיו, הנה הגדרה פורמלית לגמרי. קודם אתן אותה ואז אסביר את מה שעדיין אולי לא ברור: פונקציה \( f:\left\{ 0,1\right\} ^{*}\to\left\{ 0,1\right\} \) ניתנת לחישוב (רגיל) בזמן פולינומי אם קיים פולינום \( T:\mathbb{N}\to\mathbb{N} \) כלשהו וקיימת מכונת טיורינג דטרמיניסטית \( M \) פולינומית שעל כל קלט מהצורה \( \left(1^{m},1^{T\left(m\right)}\right) \) עבור \( m\in\mathbb{N} \) פולטת סדרה \( F_{1},\dots,F_{T\left(n\right)} \) של שערים, כך שלכל \( x\in\left\{ 0,1\right\} ^{*} \) מקבלים את \( f\left(x\right) \) באופן הבא (נסמן \( m=\left|x\right| \) ו-\( n=T\left(m\right) \)):

1. מריצים את \( M \) על \( \left(1^{m},1^{n}\right) \) ומקבלים סדרה \( F_{1},\dots,F_{n} \) של שערים.
2. מאתחלים את הרגיסטר למצב \( R_{0}=\left|x0^{n-m}\right\rangle \).
3. מחשבים את הסדרה \( R_{1},R_{2},\dots,R_{n} \) על ידי הנוסחה \( R_{i}=F_{i}\left(R_{i-1}\right) \).
4. נסמן \( R_{n}=\left|r_{1}r_{2}\dots r_{n}\right\rangle \), אז הפלט של התהליך כולו הוא \( r_{1} \).

רוב מה שהולך כאן כבר ברור, אני מקווה. ייתכן שלא ברור מה זו הפונקציה \( f:\left\{ 0,1\right\} ^{*}\to\left\{ 0,1\right\} \) שצצה פתאום. הסימון \( \left\{ 0,1\right\} ^{*} \) מתאר את “כל המחרוזות הבינאריות מאורך סופי”, והפונקציה מוציאה פלט שהוא ביט בודד; לא אכנס עכשיו לפירוט, אבל בפועל זה כל מה שצריך (פלט של כמה ביטים יכול להיות מתואר על ידי כמה חישובים שונים שכל אחד מהם מוציא ביט אחר).

דבר אחר שלא ברור הוא מה הקלט המוזר הזה ש-\( M \) מקבלת. האם לא היה מספיק להעביר ל-\( M \) את המספר \( n \) וזהו? זו נקודה טכנית שאין צורך להתעמק בה יותר מדי - המטרה שלנו היא לדרוש מ-\( M \) לא לרוץ יותר מדי זמן מעבר לכמות השערים שהיא צריכה לכתוב ולמספר הביטים של הקלט, ולכן אנחנו מעבירים לה “קלט מדומה” שהאורך שלו הוא סכום האורכים של שני הנתונים הללו. זאת מכיוון שזמן ריצה של מכונה נמדד ביחס לאורך הקלט. אני לא יודע אם אזדקק לנקודה הזו בהמשך באופן מפורש; אני מעדיף להכניס אותה פנימה כי היא חלק מההגדרה הפורמלית.

זה אתגר נחמד לקוראים שבקיאים קצת בחישוביות להוכיח שהמודל החדש שקול למודל הרגיל. החלק המעניין הוא סימולציה של מכונת טיורינג “רגילה” במודל החדש. הנה התעלול שיאפשר לכם לעשות את זה: מפתה לחשוב על הרגיסטר רק בתור תוכן הסרט של המכונה, אבל בפועל כדי להשתמש בו כך: לכל תא בסרט של המכונה יהיה איבר מתאים ברגיסטר, אבל לידו יהיו איברים שמתאימים למצבי הבקרה הפנימיים של המכונה. ערך של 1 עבור משתנה של מצב בקרה פנימי \( q \) שנמצא ליד משתנה של התא ה-\( i \) במכונה אומר “המכונה כרגע נמצאת בתא \( i \) ובמצב הבקרה \( q \)”. עכשיו, מספיק שנקרא את שני הביטים של תא הבקרה ותא הסרט כדי שנדע מה המכונה רוצה לעשות; הביט השלישי שלנו יתאים לתא הבקרה שאליו המכונה עוברת. מה ש-\( M \) תפלוט היא סדרה של \( F \)-ים שמתארים שוב ושוב את כל המעברים האפשריים של המכונה בהתאם לטבלת המעברים שלה. מסובך? מבולבלים? בסדר גמור, אפשר לשאול אותי בתגובות.

בואו נעבור סוף סוף לסיבה שלשמה התכנסנו פה - הגדרה פורמלית של חישוב קוונטי. בעצם כבר יש לנו את כל הרכיבים, כמעט. ראינו כבר שערים קוונטיים בפוסט הקודם - אלו פשוט טרנספורמציות אוניטריות. אני מרשה שערים שפועלים על שלושה קיוביטים לכל היותר (ולכן מתוארים על ידי מטריצה \( 8\times8 \) - למה?). כרגיל, אפשר לטעון שזו הגדרה מגבילה מדי, אבל גם אם הייתי מחליף את “שלושה קיוביטים” ב”ארבעה קיוביטים” או מספר קבוע דומה לא הייתי מקבל מחלקה חזקה יותר, ואילו שער קוונטי שפועל על רגיסטר מאורך שרירותי - זה משהו שלא סביר בכלל שנוכל לממש, פיזיקלית.

המשמעות של פעולה של שער קוונטי שמטפל בשלושה קיוביטים כשמפעילים אותו על רגיסטר של יותר משלושה קיוביטים אמורה להיות ברורה: על שאר הקיוביטים השער פועל כמו הזהות, ולכן הטרנספורמציה הכוללת שהוא מייצג היא מכפלה טנזורית של השער עם הרבה “זהויות” עבור כל קיוביט שלא נוגעים בו. כבר ראינו את זה בפוסטים הקודמים.

משהסכמנו על שערים קוונטיים שמקבלים לכל היותר שלושה קיוביטים, הנה ההגדרה הפורמלית:

אנחנו אומרים שפונקציה \( f:\left\{ 0,1\right\} ^{*}\to\left\{ 0,1\right\} \) שייכת למחלקה \( \mbox{BQP} \) אם קיים פולינום \( T:\mathbb{N}\to\mathbb{N} \) כלשהו וקיימת מכונת טיורינג דטרמיניסטית \( M \) פולינומית שעל כל קלט מהצורה \( \left(1^{m},1^{T\left(m\right)}\right) \) עבור \( m\in\mathbb{N} \) פולטת סדרה \( F_{1},\dots,F_{T\left(n\right)} \) של שערים קוונטיים, כך שלכל \( x\in\left\{ 0,1\right\} ^{*} \) מקבלים את \( f\left(x\right) \) באופן הבא בהסתברות של לפחות \( \frac{2}{3} \) (נסמן \( m=\left|x\right| \) ו-\( n=T\left(m\right) \)):

1. מריצים את \( F_{1},\dots,F_{n} \) של שערים קוונטיים.
2. מאתחלים את הרגיסטר למצב הקוונטי \( R_{0}=\left|x0^{n-m}\right\rangle \).
3. מחשבים את הסדרה \( R_{1},R_{2},\dots,R_{n} \) על ידי הנוסחה \( R_{i}=F_{i}\left(R_{i-1}\right) \).
4. מודדים את \( R_{n} \) ביחס לבסיס הסטנדרטי ומקבלים את התוצאה \( Y=\left|y_{1}y_{2}\dots y_{n}\right\rangle \).
5. הפלט של התהליך הוא \( y_{1} \).

שימו לב שההגדרה הזו היא במהותה הסתברותית - אנחנו לא דורשים שתמיד נקבל ש-\( y_{1}=f\left(x\right) \), רק שזה יקרה ברוב הפעמים (ספציפית, ב-\( \frac{2}{3} \) מהפעמים, כי זה מאפשר לנו לחזור שוב ושוב על החישוב ו”לנפח” את ההסתברות שנקבל את התוצאה הנכונה). זה עלול להיראות לכם מגביל, אבל צריך לזכור שבעניינים כמו פירוק לגורמים, האקראיות הזו לא קריטית - אם מצאנו פירוק לגורמים, אנחנו נדע בודאות שהוא “עובד”; החסרון היחיד של אקראיות כאן הוא שלא מובטח לנו שהפירוק לגורמים יתבצע מהר; אבל בהסתברות מאוד, מאוד, מאוד גבוהה זה אכן מה שיקרה. כמו שמילר-רבין ההסתברותי עובד טוב בעולם האמיתי.

מה פשר BQP? פשוט: P מדבר על זמן חישוב פולינומי; Q מדבר על חישוב קוונטי; ו-B מדבר על חישוב הסתברותי עם שגיאה חסומה (שגיאה חסומה היא שגיאה שלא יכולה להיות קרובה כרצוננו לחצי - כי חצי, מבחינה הסתברותית, פירושו “לא יודעים כלום”). השם דומה מאוד, ולא במקרה, ל-BPP, שהיא המחלקה הסטנדרטית של חישוב הסתברותי רגיל - ה-P באמצע הוא מלשון “הסתברותי” במקום “קוונטי”.

כדי להשלים את התמונה, אני רוצה לתת את ההגדרה הפורמלית של BPP כדי שנוכל להשוות אותה ל-BQP ולהבין למה המחלקה השניה חזקה לפחות כמו הראשונה (ועל פי האמונה שלנו, חזקה יתר). בדרך כלל מגדירים את BPP באמצעות מכונת טיורינג הסתברותית: מכונה כזו זהה למכונת טיורינג רגילה, רק שבכל שלב של החישוב, במקום צעד אפשרי אחד יש לה שני צעדים אפשריים שהיא בוחרת ביניהם באקראי, בהסתברות אחידה. זה אומר שאין למכונה פלט בודד, אלא ישנה התפלגות על הפלטים האפשריים - הפלט של המכונה הוא משתנה מקרי. בדרך כלל מגבילים את עצמנו לפלט שהוא ביט בודד, ואז נדרשת הדרישה שכבר ראינו, להסתברות \( \frac{2}{3} \) לפחות לתת את הפלט ה”נכון” על כל קלט \( x \).

הנה הגדרה חלופית, דומה באופיה להגדרה שנתתי של BQP. הדבר הראשון שאני צריך לעשות הוא להגדיר איך מתנהג “שער הסתברותי” \( F \). כרגיל, שער כזה מתייחס לשלושה ביטים ובהתאם לקלט הזה, מוציא פלט של שלושה ביטים, רק שעכשיו יכולה להיות לו התפלגות על כל הפלטים האפשריים. פורמלית:

\(  F\left(x,y,z\right)=\sum_{\left(a,b,c\right)\in\left\{ 0,1\right\} ^{3}}p_{\left(a,b,c\right)}^{\left(x,y,z\right)}\left(a,b,c\right) \)

כאשר \( 0\le p_{\left(a,b,c\right)}^{\left(x,y,z\right)}\le1 \) היא ההסתברות שעל קלט \( \left(x,y,z\right) \) ה”שער” יחזיר פלט \( \left(a,b,c\right) \) ו-\( \sum_{\left(a,b,c\right)\in\left\{ 0,1\right\} ^{3}}p_{\left(a,b,c\right)}^{\left(x,y,z\right)}=1 \), כרגיל עם הסתברות.

את ההגדרה הזו אפשר להרחיב על רגיסטר. במקרה של מכונה הסתברותית, רגיסטר יהיה תמיד סכום מהצורה \( \sum a_{v}v \) כאשר \( v=\left|v_{1}v_{2}\cdots v_{n}\right\rangle \) ו-\( 0\le a_{v}\le1 \) כך ש-\( \sum_{v}a_{v}=1 \). אז \( F \) ראשית כל יתייחס לשלושה ביטים ספציפיים, כמו קודם:

\( F^{ijk}\left(\left|v_{1}v_{2}\cdots v_{n}\right\rangle \right)=\sum_{\left(a,b,c\right)\in\left\{ 0,1\right\} ^{3}}p_{\left(a,b,c\right)}^{\left(v_{i},v_{j},v_{k}\right)}\left|v_{1}\cdots v_{i-1}av_{i+1}\cdots b\cdots c\cdots v_{n}\right\rangle \)

ולבסוף מרחיבים לינארית:

\(  F^{ijk}\left(\sum a_{v}v\right)=\sum a_{v}F^{ijk}\left(v\right) \).

ועכשיו הנה הגדרה פורמלית:

אנחנו אומרים שפונקציה \( f:\left\{ 0,1\right\} ^{*}\to\left\{ 0,1\right\} \) שייכת למחלקה \( \mbox{BPP} \) אם קיים פולינום \( T:\mathbb{N}\to\mathbb{N} \) כלשהו וקיימת מכונת טיורינג דטרמיניסטית \( M \) פולינומית שעל כל קלט מהצורה \( \left(1^{m},1^{T\left(m\right)}\right) \) עבור \( m\in\mathbb{N} \) פולטת סדרה \( F_{1},\dots,F_{T\left(n\right)} \) של שערים הסתברותיים, כך שלכל \( x\in\left\{ 0,1\right\} ^{*} \) מקבלים את \( f\left(x\right) \) באופן הבא בהסתברות של לפחות \( \frac{2}{3} \) (נסמן \( m=\left|x\right| \) ו-\( n=T\left(m\right) \)):

1. מריצים את \(  M \) על \( \left(1^{m},1^{n}\right) \) ומקבלים סדרה \( F_{1},\dots,F_{n} \) של שערים הסתברותיים.
2. מאתחלים את הרגיסטר למצב \( R_{0}=\left|x0^{n-m}\right\rangle \).
3. מחשבים את הסדרה \( R_{1},R_{2},\dots,R_{n} \) על ידי הנוסחה \( R_{i}=F_{i}\left(R_{i-1}\right) \).
4. "מודדים" את \( R_{n} \) ומקבלים את התוצאה \( Y=\left|y_{1}y_{2}\dots y_{n}\right\rangle \).
5. הפלט של התהליך הוא \( y_{1} \).

ה”מדידה” בשלב 4 היא פשוטה: אם אנחנו נמצאים במצב \( \sum a_{v}v \), אז ההסתברות שנקבל \( v \) היא \( a_{v} \).

זה מאוד דומה למכונה קוונטית. מאוד מאוד דומה! אז מה ההבדל הגדול?

ההבדל הוא בדיוק בפרטים הטכניים, אלו שעליהם אף פעם לא מדברים במדע פופולרי (אני משקר, לפעמים כן מדברים וכל הכבוד למי שכן). חישוב קוונטי פשוט מאפשר לנו להשתמש ביותר אופרטורים שפועלים על ה”רגיסטר”, מה שמאפשר לבנות אלגוריתמים מתוחכמים יותר.

מצב כללי של רגיסטר של מכונה הסתברותית הוא צירוף לינארי \( \sum a_{v}v \) כאשר המקדמים \( a_{v} \) מתאימים לכללי תורת ההסתברות: כולם מספרים ממשיים בין 0 ו-1, והסכום של כולם הוא 1, כלומר \( \sum a_{v}=1 \). האופרטורים שאנחנו יכולים להשתמש בהם בחישוב הסתברותי חייבים לשמר את הסיטואציה הזו (כמובן, בהגדרות “טבעיות” כמו של מכונת טיורינג הסתברותית אף אחד לא מכריח אותנו לעשות את זה; זה פשוט מה שנובע מההגדרה).

לעומת זאת, מצב כללי של רגיסטר של מכונה קוונטית הוא צירוף לינארי \( \sum a_{v}v \) כאשר המקדמים יכולים להיות מספרים מרוכבים כלשהם, ואנחנו דורשים רק שהסכום של ריבועי הערכים המוחלטים שלהם יהיה 1, כלומר \( \sum\left|a_{v}\right|^{2}=1 \). זה מאפשר לנו יותר חופש פעולה; יותר אופרטורים; וכפי שאמרתי בהתחלה, מקדמים שליליים של ה”הסתברות”. אם תרצו, לב העניין הוא בכך שהמקדמים של מצב קוונטי הם בעלי יותר משמעות מאשר הסתברות גרידא; כבר ראינו בפוסט של הצפנה קוונטית למה זה יכול להיות קריטי לחלוטין לפעמים.

זהו, סיימנו עם הפורמליזם המדויק. בפוסט הבא נתחיל להראות את הלחם והחמאה של האלגוריתמים הקוונטיים המפורסמים.