מה זה אומר ש-MIP*=RE? (חלק ב': מה זה אומר MIP*?)

בפוסט הקודםהתחלתי לדבר על ההוכחה ש-\( \text{MIP}^{*}=\text{RE} \) והסברתי מה זו \( \text{RE} \). הפעם אני ארצה לנסות להבין מה זו \( \text{MIP}^{*} \), ולשם כך נבין קודם כל מה זו \( \text{MIP} \) ולשם כך נבין קודם כל מה זו \( \text{IP} \) ולשם כך קודם כל ניזכר במה שקרה בפוסט הקודם.

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

1. (שלמות) אם \( x\in L \) אז קיים \( \pi \) כך ש-\( V\left(x,\pi\right)=\text{T} \)
2. (נאותות) אם \( x\notin L \) אז לכל \( \pi \) מתקיים ש-\( V\left(x,\pi\right)=\text{F} \)

כאשר \( \pi \) - ה”הוכחה” לשייכות \( x \) ל-\( L \) - פולינומי בגודל של \( x \).

אחרי הגדרת \( \text{NP} \) הגדרתי את \( \text{RE} \) בצורה דומה מאוד, רק בלי דרישות הסיבוכיות - לא הגבלתי את האורך של \( \pi \) ולא דרשתי ש-\( V \) ירוץ בזמן יעיל. בצורה הזו נראה ש-\( \text{RE} \) היא מעין הכללה של \( \text{NP} \) שמתקבלת מהקלה ב”כללי המשחק” של \( \text{NP} \). בפועל קרה ההפך - המחלקה \( \text{RE} \) הייתה מוכרת הרבה לפני שהתחילו לדבר על \( \text{NP} \), מהטעם הפשוט ש-\( \text{RE} \) הייתה גדולה מדי. אבל אחרי ש-\( \text{NP} \) הפכה לבת בית רגילה בתורת הסיבוכיות, אכן התחילו לשאול איך עוד אפשר להקל ב”כללי המשחק” של \( \text{NP} \) ומה מקבלים אז.

דרך אחת שבה אפשר להקל בכללי המשחק של \( \text{NP} \) היא על ידי הוספת אינטראקטיביות לתהליך הוידוא. מה קורה ב-\( \text{NP} \)? אני הוא המוודא \( V \). אני מקבל לידיים “הוכחה” \( \pi \). מה זו ההוכחה הזו? מהיכן היא הגיעה? מהשמיים? ממולטיוואק? מהראש של זאוס? זה לא חלק מהסיפור. יש הוכחה. כל האתגר שלי הוא לבדוק בסיועה האם \( x\in L \) או לא. במילים אחרות, אין מוכיח שהוא חלק מהסיפור. קיבלתי ספר ואני קורא אותו וזהו.

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

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

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

המודל הזה חביב ונחמד ולא תורם לנו שום דבר חדש כי כל מה שאפשר לעשות בו, אפשר לעשות גם ב-\( \text{NP} \). פשוט תחשבו על ההוכחה \( \pi \) כאילו היא כוללת את התשובות של המוכיח לשאלות של המוודא - בשביל מה צריך אינטראקטיביות כאן אם המוודא צפוי ואפשר לדעת מראש מה ישאל? תחשבו על ספר ש”מדבר עם הקורא” כי הוא ניחש מצויין מה הקורא הולך להגיד.

אם כן, כדי שהעניינים יהיו יותר מעניינים, אנחנו הופכים את המוודא להסתברותי - מעכשיו מותר לו להטיל מטבעות ולשאול שאלות בהתאם לתוצאות ההטלה. על פניו לא שיניתי הרבה כי הוכחה \( \pi \) עדיין יכולה לכלול את התשובות לכל השאלות האפשריות של המוודא - אבל אם המוודא הוא הסתברותי יכולות להיות המון שאלות שונות, ולכן ההוכחה \( \pi \) הזו תהיה ארוכה מדי ממה שמותר לה להיות במסגרת \( \text{NP} \). חשבו על זה כך: אם אני מטיל מטבע \( n \) פעמים יש לי \( 2^{n} \) תוצאות אפשריות של ההטלה, ולכן \( 2^{n} \) שאלות אפשריות - זה מספר לא פולינומי ב-\( n \). אם \( \pi \) כוללת תשובה לכל שאלה כזו אז הגודל שלה יהיה מסדר גודל \( 2^{n} \) ואם \( n \) הוא בערך מסדר הגודל של \( x \), אז קיבלנו הוכחה ארוכה מדי.

העניין הוא שאם כל מה ששינינו הוא רק את היכולת של המוודא להטיל מטבעות, זה עדיין לא תרם שום דבר חדש כי כדי לוודא ש-\( x\in L \) לא צריך את כל התשובות לשאלות. בואו נראה במדויק למה. נניח שיש לנו מערכת הוכחה אינטראקטיבית עם מוודא הסתברותי \( V \) ומוכיח כל יודע \( P \). עכשיו אני בונה מוכיח חדש שאקרא לו \( V^{\prime} \), שמקבל ליד הוכחה \( \pi \) לשייכות \( x \) ל-\( L \) ובודק אותה באופן הבא:

ההוכחה \( \pi \) של \( V^{\prime} \) תהיה בעצם תעתיק של שיחה בין \( V \) המקורי ובין \( P \). כלומר - אני אראה את השאלות ש-\( V \) שאל את \( P \) ואת מה ש-\( P \) ענה לו, ובנוסף לכך אראה גם את תוצאות הטלת המטבע של \( V \). עכשיו אני יכול לבדוק שהתעתיק הזה באמת אמין, במובן זה שאני יכול לבצע סימולציה של \( V \) המקורי ולראות אם הוא באמת שואל את אותן שאלות כמו בתעתיק, ובסוף אני אענה כמו שהוא ענה.

עכשיו, אם \( x\in L \) אז קיימת סדרת שאלות ותשובות שבה \( P \) הצליח לשכנע את \( V \) לומר \( \text{T} \) - ולכן גם אני אומר \( \text{T} \) על התעתיק שמתאר את הסדרה הזו. זה מטפל בדרישת ה”שלמות”. כמו כן, אם \( x\notin L \) אז לא משנה מה \( P \) אומר ל-\( V \); אסור ל-\( V \) לטעות, בכלל, אז הוא בודאות יאמר \( \text{F} \) בסוף וכך גם אני אגיד. בקיצור, גם כל הסיפור הזה נופל בתוך המסגרת של \( \text{NP} \). אם רוצים להתרחב מעבר אליה חייבים לוותר על עוד משהו. ומה שמוותרים עליו הוא האמינות של התשובה של \( V \). כלומר, מרשים ל-\( V \) לטעות בהסתברות מסויימת.

באופן כללי, אם אלגוריתם הסתברותי שעונה “כן/לא” טועה בהסתברות שהיא טובה יותר מ-\( \frac{1}{2} \) בפער כלשהו - למשל, \( \frac{1}{3} \) זה המספר שאוהבים לתת בדרך כלל - אז על ידי מספיק חזרות על האלגוריתם ולקיחת התוצאה שהוא החזיר יותר פעמים אפשר לנפח את ההסתברות שנענה תשובה נכונה, ומספיק שנחזור על האלגוריתם מספר פולינומי של פעמים כדי להשיג שיפור אקספוננציאלי בהסתברות להצליח (זה דורש טיעון הסתברותי כלשהו שמערב משהו שנקרא חסם צ'רנוף ולא אכנס אליו כאן). בגלל זה מסתפקים בלדרוש הסתברות טעות של לכל היותר \( \frac{1}{3} \) ולא משהו נמוך יותר (כמו לכל היותר \( 0.000000000001 \)) - כי מבחינה תיאורטית זה כמעט אותו הדבר.

אחרי שהנקודה הזו הובהרה אפשר לעבור להגדרה הפורמלית. אנחנו אומרים שבעיה \( L \) שייכת למחלקה IP (ראשי תיבות של Interactive Proof) אם קיים מוודא הסתברותי יעיל \( V \) כך שלכל \( x \):

1. (שלמות) אם \( x\in L \) אז קיים מוכיח \( P \) כך שההסתברות ש-\( V \) יגיד "כן" על \( x \) בסוף הפרוטוקול עם \( P \) היא לפחות \( \frac{2}{3} \).
2. (נאותות) אם \( x\notin L \) אז לכל מוכיח \( P \) ההסתברות ש-\( V \) יגיד "כן" על \( x \) בסוף הפרוטוקול עם \( P \) היא לכל היותר \( \frac{1}{3} \).

שימו לב להבדל בין שלמות ונאתות - בשלמות, מספיק שיהיה \( P \) מסויים שעבורו האפקט החיובי מושג (כמו שב-\( \text{NP} \) הספיקה הוכחה אחת נכונה) ולעומת זאת בנאותות צריך להבטיח שכל מוכיח כל יודע, לא משנה כמה הוא תחמן ורמאי, לא יצליח לעבוד על \( V \) יותר מדי. זו גם החשיבה שצריך לאמץ על מערכות הוכחה כאלו באופן כללי: \( P \) הוא לא חבר שלנו. הוא האויב. הוא הרוע. הוא מי שמנסה להטעות אותנו בכל צעד ושעל. פרוטוקולי הוכחה אינטראקטיביים בנויים הרבה יותר על להבטיח ש-\( P \) רמאי לא יצליח לרמות אותנו, והרבה פחות על “הו ידידי הטוב בוא תעזור לי להרחיב את הידע שלנו יחד”.

האם כל הזוועה הזו מהווה שיפור ביחס ל-\( \text{NP} \)? ובכן, כנראה שכן. אחת מהתוצאות היפות והמפתיעות בתורת הסיבוכיות (ויש לי עליה פוסט) הייתה ש-\( \text{IP=PSPACE} \). בפשטות, הטענה הזו אומרת ש-\( \text{IP} \) היא הרבה יותר חזקה ממה שחשבו במבט ראשון. כמובן, קודם כל צריך להסביר מה זו בכלל \( \text{PSPACE} \), וזה קל - זו מחלקת כל בעיות הההכרעה שאפשר לפתור עם אלגוריתם שפועל בסיבוכיות זיכרון פולינומית (כלומר, המקום שהוא צריך בשביל לאחסן מידע הוא פולינומי בגודל הקלט). העניין הוא שההגדרה היבשה הזו לא מעבירה טוב עד כמה המחלקה הזו גדולה יחסית - רוב האקשן של תורת הסיבוכיות מתרחש בתוכה. הנה פוסט שלי על המחלקה הזו שאולי יעזור להבהיר את זה יותר.

אם כן, זו \( \text{IP} \), אבל מהי \( \text{MIP} \)? זו הכללה די מתבקשת של \( \text{IP} \) ששואלת את השאלה - מה קורה אם יש לנו שני מוכיחים במקום מוכיח אחד? על פניו, לא אמור לקרות שום דבר חדש. הרי כבר מוכיח אחד הוא כל-יכול מבחינה חישובית, הוא לא צריך שעוד אחד יעזור לו. אבל כזכור, נקודת המבט שלנו על הוכחות אינטראקטיביות היא שהמוכיח הוא האויב ולכן המטרה של שני מוכיחים במקום אחד היא דווקא לעזור לנו להפיל בפח “מוכיחים” רמאים שמנסים לעבוד עלינו.

לרעיון הזה יש אנלוגיה פשוטה מחיי היום יום, שהיא כל כך מתבקשת עד שהופיעה כבר במאמר המקורי שבו \( \text{MIP} \) הוגדרה: פושעים. חשבו על שני פושעים שביצעו ביחד פשע ולאחר מכן תיאמו ביניהם את האליבי. ואז המשטרה תופסת אותם וחוקרת אותם בנפרד. החקירה הזו נותנת יתרון לחוקרי המשטרה על פני חקירה של אחד מהפושעים ותו לא, כי כך ניתן לגלות סתירות בין הגרסאות שלהם, אם תיאום האליבי לא היה טוב מספיק.

את ההגדרה היבשה קל לתת, היא כמעט זהה להגדרה של \( \text{IP} \): אנחנו אומרים שבעיה \( L \) שייכת למחלקה MIP (ראשי תיבות של Multiprover Interactive Proof) אם קיים מוודא הסתברותי יעיל \( V \) כך שלכל \( x \):

1. (שלמות) אם \( x\in L \) אז קיימים זוג מוכיחים \( P_{1},P_{2} \) כך שההסתברות ש-\( V \) יגיד "כן" על \( x \) בסוף הפרוטוקול עם המוכיחים היא לפחות \( \frac{2}{3} \).
2. (נאותות) אם \( x\notin L \) אז לכל זוג מוכיחים \( P_{1},P_{2} \) ההסתברות ש-\( V \) יגיד "כן" על \( x \) בסוף הפרוטוקול עם המוכיחים היא לכל היותר \( \frac{1}{3} \).

אפשר כמובן לשאול למה רק שני מוכיחים ולא יותר מכך - הסיבה היא פשוט שלא צריך יותר מכך; כבר במאמר שהציג את \( \text{MIP} \) ניתנה ההוכחה לכך שהוספת מוכיחים נוספים לא מגדילה את המחלקה \( \text{MIP} \).

כמה שנים אחרי שהוגדרה, התברר שגם \( \text{MIP} \) גדולה בצורה מרשימה: היא שווה למחלקה שנקראת \( \text{NEXP} \), שהיא כמו \( \text{NP} \) רק שהמוודא יכול לרוץ בזמן אקספוננציאלי. כדי להבין עד כמה זה גדול, חשבו על זה כך: נכון שאמרתי ש-\( \text{PSPACE} \) גדולה ועצומה? למרות כל זה, אין לנו שום הוכחה כרגע ש-\( \text{P}\ne\text{PSPACE} \), כלומר ייתכן שכל מה שקורה בתוך \( \text{PSPACE} \) “יקרוס” לכך שהכל פשוט קל לחישוב וזהו (זה מאוד, מאוד לא סביר שזה מה שיקרה; התעלומה היא פחות האם המחלקות באמת שונות ויותר איך לכל הרוחות אפשר להוכיח דבר כזה). לעומת זאת עבור \( \text{NEXP} \) יש הוכחה פשוטה יחסית לכך שהיא שונה מ-\( \text{NP} \), כך ש-\( \text{MIP} \) היא באמת יותר חזקה מ-\( \text{NP} \) (לעומת \( \text{IP} \) שאנחנו פשוט לא יודעים לגביה).

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

\( \text{MIP} \) הופכת ל-\( \text{MIP}^{*} \) כשהמידע שמשותף לפני תחילת הפרוטוקול הוא מצב קוונטי שזור. הופס, ביצענו את החטא הקדמון - הוספנו באזוורדס לעולם היפה והנקי של תורת הסיבוכיות! ואכן, “מצב קוונטי” נראה במבט ראשון כמו איזה מושג זר לכל מה שדיברנו עליו עד כה - קוונטים זה משהו בפיזיקה ומה בכלל הקשר לאבסטרקציות של חישוב.

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

תורת הקוונטים היא נסיון לעשות סדר בבלאגן שהוא האופן המוזר שבו דברים מתנהגים בסקלות גודל נמוכות - נסיון שהצליח בצורה מרשימה ביותר. הכלי המתמטי הבסיסי שבו משתמשים לצורך עשיית הסדר הזה הוא סופרפוזיציה: אם יש לנו מערכת שכשאנחנו מודדים אותה אנחנו מגלים שהיא נמצאת באחד מכמה “מצבי בסיס” אפשריים - למשל \( \left|0\right\rangle \) ו-\( \left|1\right\rangle \) - אז התיאור הכללי של מצב המערכת הוא בתור צירוף לינארי של המצבים הללו, כשהמרחב שלנו חי מעל המספרים המרוכבים \( \mathbb{C} \). כלומר, מצב קוונטי “כללי” עבור שני מצבי הבסיס הללו הוא \( \alpha\left|0\right\rangle +\beta\left|1\right\rangle \) כעוד דרישה היא שהמצב יהיה מנורמה 1, כלומר \( \left|\alpha\right|^{2}+\left|\beta\right|^{2}=1 \).

בסיטואציה כזו אפשר לעשות שני דברים עם המצב: לשנות אותו בצורה שלא “שוברת” את הסופרפוזיציה - זה ניתן לתיאור על ידי הפעלת טרנספורמציה לינארית אוניטרית על המצב - או “למדוד” אותו, מה שמכריח את הסופרפוזיציה “לקרוס”: אחד משני מצבי היסוד נבחר באופן אקראי והמצב משתנה אליו. ה”מידע” על \( \alpha,\beta \) פשוט נמחק. הדרך היחידה שבה הוא מתבטא היא בכך שהמצב \( \left|0\right\rangle \) נבחר לתוצאת המדידה בהסתברות \( \left|\alpha\right|^{2} \) והמצב \( \left|1\right\rangle \) נבחר בהסתברות \( \left|\beta\right|^{2} \).

במבט ראשון לא ברור בשביל מה כל זה טוב, אז הנה סיבוך של הסיפור. מה שתיארתי כרגע נקרא “קיוביט” - מערכת עם שני מצבי בסיס שקצת מזכירה ביט קלאסי שהוא או 0 או 1. אבל אפשר גם לבנות מערכות של שני קיוביטים או יותר, והסיפור בהן מסתבך. ל-3 קיוביטים, למשל, כבר יש שמונה מצבי יסוד אפשריים: \( \left|000\right\rangle ,\left|001\right\rangle ,\ldots,\left|111\right\rangle \) ולכן סופרפוזיציה של שלושה קיוביטים היא כבר משהו שחי במרחב וקטורי ממימד 8, ואם תקחו \( n \) קיוביטים תקבלו מרחב ממימד \( 2^{n} \) - יש כאן גידול אקספוננציאלי של מה שאנחנו יודעים לייצג. זה לא מתורגם בקלות ליתרון חישובי כלשהו כי יש לנו מגבלות גדולות לגבי מה שאפשר לעשות עם המצב הזה - אבל יש דרכים להפיק ממנו תועלת, כשהמפורסמת שבהם היא האלגוריתם של שור לפירוק לגורמים של מספרים בזמן פולינומי. לא נדבר על זה הפעם.

על מה אני כן רוצה לדבר? שזירות. נדבר שניה על מערכת בת שני קיוביטים. נניח שסתם לקחנו שני קיוביטים ושמנו אותם אחד באיזור של השני ואנחנו מנסים לחשוב עליהם בתור מערכת אחת - מה יקרה? אם הראשון הוא \( \alpha_{1}\left|0\right\rangle +\beta_{1}\left|1\right\rangle \) והשני הוא \( \alpha_{2}\left|0\right\rangle +\beta_{2}\left|1\right\rangle \) אז אפשר לחשוב על המערכת המשולבת שלהם בתור מין מכפלה של שני אלו:

\( \left(\alpha_{1}\left|0\right\rangle +\beta_{1}\left|1\right\rangle \right)\left(\alpha_{2}\left|0\right\rangle +\beta_{2}\left|1\right\rangle \right)=\alpha_{1}\alpha_{2}\left|00\right\rangle +\alpha_{1}\beta_{2}\left|01\right\rangle +\beta_{1}\alpha_{2}\left|10\right\rangle +\beta_{1}\beta_{2}\left|11\right\rangle \)

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

\( \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}} \)

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

זה מחזיר אותנו אל \( \text{MIP}^{*} \). אנחנו עדיין לא מבינים את הפורמליזם המתמטי (ולא אכנס אליו בפוסט הזה), אבל תוספת המצב הקוונטי השזור פותחת פתח לתקשורת בין המוכיחים שלא הייתה אפשרית קודם. וכאן מגיע החלק המוזר ביותר בכל הסיפור. על פניו, הוספת היכולת הזו מחזקת את המוכיחים. אבל כזכור, המוכיח הוא האויב. בכך שאנחנו מחזקים אותם ונותנים להם פתח כלשהו לתקשורת, אנחנו עוזרים להם לעבוד עלינו ורק מחלישים את מה שאנחנו יודעים לעשות עם הוכחות אינטראקטיביות. במאמר שבו \( \text{MIP}^{*} \) נולדה, זה מה שעשו - הראו איך פרוטוקולים מסויימים של הוכחות אינטראקטיביות לא יכולות לעבוד יותר. עם זאת, הצביעו גם על כך שזה לא מוכיח ש-\( \text{MIP}^{*} \) חלשה יותר מ-\( \text{MIP} \); זה שנפסלו פרוטוקולים מסויימים לא אומר שלא יכולים להיות אחרים שמשתמשים איכשהו בשזירות לטובת המוודא.

בשנים מאז הגדרת \( \text{MIP}^{*} \) הגיעו שלל תוצאות מרהיבות שהראו שזה בדיוק המצב. ראשית, הוכחה ש-\( \text{NEXP}\subseteq\text{MIP}^{*} \), כלומר שמערכות הוכחה קוונטיות שכאלו חזקות לפחות כמו מערכות הוכחה קלאסיות. אחר כך, הוכחה ש-\( \text{NEEXP}\subseteq\text{MIP}^{*} \) כאשר NEEXP (שימו לב ל-E הנוסף!) היא ההכללה של \( \text{NP} \) למוודא עם זמן ריצה אקספוננציאלי-כפול (אקספוננציאלי זה סדר גודל של \( 2^{n} \); אקספוננציאלי כפול זה סדר גודל של \( 2^{2^{n}} \)). כאן כבר היה שמשהו מאוד מוזר קורה פה וש-\( \text{MIP}^{*} \) היא מחלקה חזקה עד להפתיע - אבל עד כמה? מה הגבול העליון? גבול עליון “טריוויאלי” היה \( \text{RE} \), כי עם הכוח החישובי הבלתי מוגבל של מוודא \( \text{RE} \) אפשר לקבל מה שנראה כמו תעתיק של פרוטוקול \( \text{MIP}^{*} \) ולבדוק שהכל עובד בו כמו שצריך - אבל \( \text{RE} \) הוא חסם עליון מפחיד בגובהו. ואז \( \text{MIP}^{*} \) הגיעה בבום אל החסם העליון הזה. זו התוצאה \( \text{MIP}^{*}=\text{RE} \). הרעיון, כפי שרמזתי בפוסט הקודם, היה להציג פרוטוקול \( \text{MIP}^{*} \) עבור בעיית העצירה.

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

בכל זאת, לסיום, אני רוצה להבהיר כמה נקודות מבלבלות שכבר ראיתי שצצו בהקשר הזה.

ראשית, מה שקוונטי בסיפור הזה הוא המוכיחים, לא המוודא. המוודא ממשיך להיות אלגוריתם הסתברותי רגיל. זה שונה מדברים כמו האלגוריתם של שור, שבהם האלגוריתם שפותר את הבעיה הוא בעצמו קוונטי. אם ניקח מערכת הוכחה אינטראקטיבית ונוסיף יכולת קוונטית למוודא אבל לא למוכיחים, זה לא יוסיף כוח למערכת. כלומר, המחלקה \( \text{QIP} \) שהוגדרה בתור ההכללה של \( \text{IP} \) למוודא קוונטי מקיימת \( \text{QIP}=\text{IP}=\text{PSPACE} \). בדומה, \( \text{QMIP}_{\text{NE}}=\text{NEXP} \) כאשר \( \text{QMIP}_{\text{NE}} \) היא המחלקה של חישוב מרובה מוכיחים שבו המוודא קוונטי אבל למוכיחים אין מצב שזור קוונטית (זה ה-\( \text{NE} \) שלמטה).

שנית, אני לא רוצה שיהיה בלבול כלשהו בנקודה הזו - התוצאה הזו לא מראה שאפשר להשתמש איכשהו בתורת הקוונטים בשביל לפתור את בעיית העצירה! לא, לא, לא! בעיית העצירה הייתה ונותרה בלתי פתירה. כל ההקשר של הדיון הוא מערכת הוכחה עבור בעיית העצירה, וכבר ראינו שמערכת הוכחה “קלאסית”, שבה המוודא מקבל ליד הוכחה כתובה ותו לא - היא עצמה מספיקה בשביל לוודא את בעיית העצירה (לא לפתור - לוודא). מה שקורה ב-\( \text{MIP}^{*}=\text{RE} \) הוא שאנחנו רואים שאפשר להחליש מאוד את המוודא ועדיין להצליח לוודא את בעיית העצירה, אם המוכיחים הם חזקים מספיק. אז בבקשה, אני לא רוצה לראות עוד כותרות כמו “‘Remarkable’ Mathematical Proof Describes How to Solve Seemingly Impossible Computing Problem”. המציאות מספיק יפה, לא צריך לגלוש לפנטזיות.