”הוכחה ראשונה לעליונות מחשב קוונטי“ - מה כן (אזהרה - עלול לכלול מתמטיקה)

מבוא

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

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

המודלים החישוביים שאנחנו מדברים עליהם כאן מנסים למדל חישוב מקבילי קצר. המודל ה”קלאסי” שמתאר חישוב מקבילי נקרא מעגלים בוליאניים ומחלקת הסיבוכיות המתאימה לו מסומנת ב-NC (ראשי תיבות של Nick’s Class. כן, ניק זה שם של מישהו. אל תשאלו). תיארתי מעגלים בוליאניים כאן, אבל הנה שוב הרעיון: מעגל בוליאני הוא גרף מכוון חסר מעגלים; כל צומת שלא נכנס אליה כלום היא קלט וכל צומת שלא יוצא ממנה כלום היא פלט וכל צומת פנימי הוא שער לוגי. את הקלטים מסמנים ב-\( x_{1},x_{2},\dots,x_{n} \) ואת הפלטים ב-\( y_{1},y_{2},\dots,y_{m} \) (שימו לב שמספר הקלטים והפלטים יכול להיות שונה). השערים הלוגיים יכולים להיות AND, OR, NOT ואנחנו דורשים שלכל שער כזה ייכנסו שתי קשתות לכל היותר.

חישוב שמבצע המעגל מתבצע בדרך המתבקשת: מציבים ב-\( x \)-ים ערכים כלשהם של 0 ו-1 ו”מפעפעים” את הערכים הללו בגרף: לכל שער לוגי שהכניסות אליו הן מצמתים שהערך שלהם כבר נקבע, מחשבים את הערך של השער הלוגי בהתאם לפונקציה שלו (שער AND שנכנסים אליו 1 ו-0? הערך שלו יהיה 0). בצורה הזו בסופו של דבר נקבעים הערכים של הפלטים, והרי לנו חישוב של פונקציה. שימו לב שזו פונקציה \( f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{m} \), כלומר בפרט מספר הביטים בכניסה הוא קבוע (מכונות טיורינג, להבדיל, יודעות לפעול על קלטים מאורך כלשהו של ביטים). לכן יותר נפוץ לדבר על משפחה של מעגלים - לכל \( n \) יש לנו מעגל שמחשב פונקציה על הקלטים מאורך \( n \); בדרך כלל דורשים שבהינתן \( n \) נדע לבנות את המעגל הזה אלגוריתמית, אחרת משפחה של מעגלים שכזו עלולה לעשות דברים מוזרים כמו לפתור את בעיית העצירה.

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

המחלקה \( \text{NC} \) מחולקת ל”תת-מחלקות”: \( \text{NC}^{k} \) כוללת את משפחות המעגלים שבהן הגודל של מעגל עם \( n \) קלטים הוא פולינומי ב-\( n \), ואילו העומק שלו הוא \( O\left(\log^{k}n\right) \), מה שנקרא “פולי-לוגריתמי”. המחלקה \( \text{NC}^{0} \) כוללת, אם כן, מעגלים שבהם יש לנו חסם עליון על העומק שלא תלוי בגודל הקלט. כלומר, לא משנה אם הקלט הוא מאורך 2 ביטים או 200, עומק המעגל עדיין יהיה חסום על ידי, נאמר, 17. לא קשה לראות שההגבלה הזו יוצרת מגבלה רצינית על הפונקציות שאפשר לחשב במחלקה הזו - כל ביט של פלט יכול להיות תלוי רק במספר סופי של ביטים מהקלט (משהו כמו 2 בחזקת עומק המעגל לכל היותר).

מעגלים ושערים קוונטיים

נעבור למעגלים קוונטיים. גם על זה יש לי פוסט, אבל הנה הסבר שבאמת דורש מינימום היכרות עם קוונטים. אם יש לנו מעגל על \( n \) קיוביטים, אנחנו לא מפרידים אותם, כמו ב-\( \text{NC}^{0} \), לכל מני אותות שרצים להם על גרף. במקום זה, אנחנו חושבים על המצב של המעגל בכל רגע נתון בתור וקטור במרחב וקטורי מעל \( \mathbb{C} \) ממימד \( 2^{n} \). כל אביר בסיס של המרחב הזה הוא מחרוזת ב-\( \left\{ 0,1\right\} ^{n} \). למשל, אם \( n=3 \) אז אברי הבסיס של המרחב הם \( \left|000\right\rangle ,\left|001\right\rangle ,\left|010\right\rangle ,\left|011\right\rangle ,\left|100\right\rangle ,\left|101\right\rangle ,\left|110\right\rangle ,\left|111\right\rangle \).

הפעלה של שער במעגל היא כפל של הוקטור הזה במטריצה אוניטרית מעל \( \mathbb{C}_{2^{n}\times2^{n}} \). זה כל מה שמעגל קוונטי עושה - כופל את הוקטור בעוד ועוד מטריצות. כדי לשמור את העניינים פשוטים יותר וקרובים יותר למציאות, על פי שער קוונטי משפיע רק על קיוביט אחד או שניים בכל פעם. אבל “משפיע על קיוביט אחד” לא אומר שהפעולה שלו על הוקטור שמייצג את המצב הקוונטי תשנה רק כניסה אחת או שתיים בו; זה רק אומר שמה שהשער בעצם עושה לכל קואורדינטה יושפע רק מביט אחד או שניים במחרוזת שמתארת את הקואורדינטה הזו.

בואו נראה דוגמא מרכזית שנשתמש בה כל הזמן - שער הדאמר, \( H \). כשחושבים על השער הזה בתור מטריצה שפועלת על מרחב עם קיוביט בודד, התיאור המפורש הוא \( H=\frac{\sqrt{2}}{2}\left(\begin{array}{cc} 1 & 1\\ 1 & -1 \end{array}\right) \). זו צורת כתיב סבירה, אבל אני אשתמש בצורת כתיב קצת שונה, שבה קצת יותר קל להרגיש מה \( H \) עושה:

• \( H\left|0\right\rangle =\left|0\right\rangle +\left|1\right\rangle \)
• \( H\left|1\right\rangle =\left|0\right\rangle -\left|1\right\rangle \)

הכתיב הזה קצת מרמה - מה שאני באמת צריך לכתוב הוא \( H\left|0\right\rangle =\frac{\sqrt{2}}{2}\left|0\right\rangle +\frac{\sqrt{2}}{2}\left|1\right\rangle \) כי בלי המקדמים הללו המצב הוא לא תקין (הוא חייב להיות וקטור מנורמה 1) אבל אני מחפף בזה כי בלי המקדמים העסק יותר קריא ואין סכנה אמיתית לבלבול.

עכשיו, איך \( H \) פועל על מצב קוונטי שמורכב משני קיוביטים? כאן צריך להיזהר - אין משמעות לומר ש-\( H \) פועל על המצב בלי לומר על איזה מהקיוביטים הוא פועל. אז אני אכתוב \( H^{1} \) כדי להגיד \textquotedblright\( H \) שמופעל על הקיוביט הראשון” ו-\( H^{2} \) כדי לומר \textquotedblright\( H \) שמופעל על הקיוביט השני”. תחת הסימן הזה:

• \( H^{1}\left|00\right\rangle =\left|00\right\rangle +\left|10\right\rangle \)
• \( H^{1}\left|10\right\rangle =\left|00\right\rangle -\left|10\right\rangle \)
• \( H^{1}\left|01\right\rangle =\left|01\right\rangle +\left|11\right\rangle \)
• \( H^{1}\left|11\right\rangle =\left|01\right\rangle -\left|11\right\rangle \)

ואתם כבר יכולים להשלים את מה ש-\( H^{2} \) עושה בעצמכם. עכשיו, הנה השאלה המעניינת באמת - מה מקבלים אם מפעילים את \( H^{1} \) ואחריו את \( H^{2} \)? אפשר גם בסדר ההפעלה ההפוך, מקבלים את אותו הדבר. בואו נכתוב רגע מקרה אחד במפורש:

\( H^{2}\left(H^{1}\left|00\right\rangle \right)=H^{2}\left|00\right\rangle +H^{2}\left|10\right\rangle =\left|00\right\rangle +\left|01\right\rangle +\left|10\right\rangle +\left|11\right\rangle \)

כלומר, קיבלנו מצב של “פיזור אחיד” בין כל וקטורי הבסיס הקיימים במרחב. כדי לפשט את הסימנים, במקום לכתוב \( H^{2}H^{1} \) אפשר לכתוב \( H^{\otimes2} \), וגם אפשר “לקודד” את הפעולה הזו בתור אופרטור יחיד, כלומר מטריצה בודדת במקום מכפלה של שתי מטריצות בזו אחר זו (פשוט כפלו את האחת בשניה וקיבלתם את האופרטור). כל הסיפור הזה עובד גם ל-\( n \) ביטים; אנחנו תמיד נקבל

\( H^{\otimes n}\left|0^{n}\right\rangle =\sum_{x}\left|x\right\rangle \)

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

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

חוץ מ-\( H \) יש עוד כמה וכמה שערים נפוצים מאוד. ראשית, ישנם שערי פאולי שמסומנים ב-\( X,Y,Z \) ומתוארים על ידי המטריצות

\( X=\left(\begin{array}{cc} 0 & 1\\ 1 & 0 \end{array}\right),Y=\left(\begin{array}{cc} 0 & -i\\ i & 0 \end{array}\right),Z=\left(\begin{array}{cc} 1 & 0\\ 0 & -1 \end{array}\right) \)

מה ש-\( X \) עושה הוא בעצם פעולת NOT:

• \( X\left|0\right\rangle =\left|1\right\rangle \)
• \( X\left|1\right\rangle =\left|0\right\rangle \)

מה ש-\( Z \) עושה מזכיר קצת את \( H \), רק ש-\( Z \) לא מפצל לשניים, רק מכפיל במינוס 1 באחד מהמקרים:

• \( Z\left|0\right\rangle =\left|0\right\rangle \)
• \( Z\left|1\right\rangle =-\left|1\right\rangle \)

ואילו מה ש-\( Y \) עושה נראה כמו שילוב של \( X \) ו-\( Z \) כשגם מכניסים פנימה את המספר המרוכב \( i \):

• \( Y\left|0\right\rangle =-i\left|1\right\rangle \)
• \( Y\left|1\right\rangle =i\left|0\right\rangle \)

הדמיון הזה לא מקרי - קל לראות ש-\( Y=iXZ \), ובאופן דומה גם \( Z=iXY \) וכדומה, כל מטריצת פאולי מתקבלת מכפל של שתי האחרות וסקלר הפיך. תחת ההגדרה המתאימה (שתזהה את כל הכפולות בסקלר הפיך של המטריצות בתור אותו איבר) ותוספת מטריצת היחידה מקבלים פה חבורה - חבורת פאולי.

אל האוסף הזה מצטרפת מטריצה נוספת שנקראת לפעמים פאזה ומזכירה את \( Z \):

\( S=\left(\begin{array}{cc} 1 & 0\\ 0 & -i \end{array}\right) \)

קל לבדוק ש-\( S^{2}=Z \), כך שאפשר לחשוב על \( S \) בתור “שורש” של \( Z \) (למעשה, כמעט תמיד בוחרים בתור \( S \) את המטריצה שבה הכניסה השניה היא \( i \) ולא \( -i \), אבל המאמר הנוכחי לקח את זו אז אני דבק בסימון הזה). עוד דבר שקל לבדוק הוא ש-\( X=HZH \) (תנסו!) ולכן בעצם אפשר לקבל את כל מטריצות פאולי מתוך \( H,S \) לבד. החבורה שנוצרת על ידי \( H,S \) באופן הזה (כזכור, כשמזהים שתי מטריצות שנבדלות זו מזו על ידי כפל בקבוע) נקראת חבורת קליפורד (עבור קיוביט בודד) והיא עומדת במרכז אחד מהמשפטים היפים שאני מכיר בתחום - משפט Gottesman–Knill שמראה כיצד ניתן לבצע סימולציה של מעגל קוונטי שנבנה מתוך שערים מחבורת קליפורד בלבד בזמן ומקום פולינומיים. אני מקווה להקדיש לזה פוסט מתישהו, אבל כרגע השורה התחתונה היא שהשערים שראינו עד כה הם לא בדיוק מה שנותן לחישוב קוונטי את הכוח שלו - צריך “עוד משהו”. ה”עוד משהו” הזה נקרא שער-\( T \) והוא מוגדר כך: \( T=\left(\begin{array}{cc} 1 & 0\\ 0 & e^{\frac{i\pi}{4}} \end{array}\right) \).

עד עכשיו דיברתי רק על שערים על קיוביט בודד, אבל זו בעצם קצת רמאות. כל עוד כל מה שמבצעים במעגל קוונטי הוא פעולות על קיוביט בודד, אין שום דבר מעניין במעגל הזה ואפשר לסמלץ אותו קלאסית בלי בעיה - בודקים מה קורה לכל קיוביט בנפרד, וזהו. הכוח של מעגלים קוונטיים מגיע כשגורמים לקיוביטים להיות תלויים זה בזה. למשל, אם אני יוצר את המצב הקוונטי \( \left|00\right\rangle +\left|11\right\rangle \) אז קיבלתי מצב שאי אפשר להבין אותו על ידי חשיבה על כל קיוביט בנפרד (להבדיל מ-\( \left|00\right\rangle +\left|01\right\rangle +\left|10\right\rangle \left|11\right\rangle \) שעליו אפשר לחשוב בתור \( \left(\left|0\right\rangle +\left|1\right\rangle \right)\left(\left|0\right\rangle +\left|1\right\rangle \right) \) שכזה). אז מה עושים? שערים “נשלטים”. אלו שערים של שני קיוביטים, ולכן כאלו שמיוצגים על ידי מטריצה מסדר \( 4\times4 \). אני אציג שלושה כאלו - בשניהם הרעיון הוא “אם הקיוביט הראשון הוא 0 לא לעשות כלום, ואם הוא 1 אז להפעיל שער פאולי מסויים על הקיוביט השני”. כשמפעילים \( X \) השער נקרא CNOT וכשמפעילים \( Z \) או \( S \) השער נקרא, ובכן, Controlled-Z ו-Controlled-S, או בקיצור \( CZ \) ו-\( CS \). דווקא \( CZ \) ו-\( CS \) יהיו השערים שבהם נשתמש עבור התוצאה הנוכחית למרות ש-CNOT הוא יותר פופולרי באופן כללי.

המטריצות של השערים הרלוונטיים הן \( CNOT=\left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 \end{array}\right),CZ=\left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -1 \end{array}\right),CS=\left(\begin{array}{cccc} 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0\\ 0 & 0 & 0 & -i \end{array}\right) \) והן פשוטות למדי - הן פשוט מטריצות בלוקים אלכסוניות שבהן הבלוק הראשון הוא מטריצת היחידה והשני הוא \( X \) או \( Z \) או \( S \), בהתאמה. הפעולה שלהן מתוארת כך:

• \( CNOT\left|00\right\rangle =\left|00\right\rangle \)
• \( CNOT\left|01\right\rangle =\left|01\right\rangle \)
• \( CNOT\left|10\right\rangle =\left|11\right\rangle \)
• \( CNOT\left|11\right\rangle =\left|10\right\rangle \)

ו-

• \( CZ\left|00\right\rangle =\left|00\right\rangle \)
• \( CZ\left|01\right\rangle =\left|01\right\rangle \)
• \( CZ\left|10\right\rangle =\left|10\right\rangle \)
• \( CZ\left|11\right\rangle =-\left|11\right\rangle \)

ו-

• \( CS\left|00\right\rangle =\left|00\right\rangle \)
• \( CS\left|01\right\rangle =\left|01\right\rangle \)
• \( CS\left|10\right\rangle =\left|10\right\rangle \)
• \( CS\left|11\right\rangle =-i\left|11\right\rangle \)

שערי \( CZ \) ו-\( CS \) הם מאוד סימטריים, להבדיל מ-\( CNOT \) - אפשר לחשוב עליהם בתור מעין שערי AND שכאלו, שמכפילים בקבוע ספציפי רק אם ה-AND של שני הקלטים הוא 1. במובן מסויים הסימטריה לא מפתיעה כי גם \( CNOT \) הוא שער סימטרי, אם מסתכלים על הקלטים כשהם מיוצגים בבסיס קצת שונה, אבל לא ניכנס לזה כרגע.

וזהו, סיימנו להציג את כל השערים הקוונטיים שיהיו רלוונטיים לנו. עכשיו אפשר לחזור למה שקראתי לו “חבורת קליפורד” קודם; ההגדרה המלאה של החבורה היא בתור החבורה שנוצרת על ידי \( H,S \) ו-\( \text{CNOT} \), ומשפט Gottesman–Knill תקף עבורה - כלומר, הוספת \( \text{CNOT} \)-ים לא מקלקלת את היכולת שלנו לסמלץ מעגלים כאלו באופן קלאסי.

מעגל קוונטי הוא בסך הכל סדרה של השערים הללו. את הסדרה אפשר לחלק ל”שכבות” - בכל שכבה אנחנו דורשים שכל השערים יפעלו על קיוביטים שונים (כלומר, אין שני שערים באותה שכבה שפועלים על אותו קיוביט). למשל, ביצוע פעולת \( H^{\otimes n} \) דורש \( n \) שערי \( H \), אבל כולם יכולים להתבצע “בבת אחת”, באותה שכבה. המחלקה SQC כוללת את כל המשפחות של מעגלים קוונטיים עם מספר שערים פולינומי שמספר השכבות שלהם הוא חסום על ידי קבוע שלא תלוי ב-\( n \).

עכשיו אנחנו מבינים את התוצאה: הוכחה ש-\( \text{SQC}\ne\text{NC}^{0} \). אבל עדיין צריך להבין את הבעיה שתהיה שייכת למחלקה אחת ולא לשניה.

בעיית ברנשטיין-וזירני

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

באופן כללי אם \( F^{n} \) הוא מרחב וקטורי ממימד \( n \) מעל שדה \( F \) ו-\( f:F^{n}\to F \) היא פונקציונל לינארי (\( f\left(\lambda x+y\right)=\lambda f\left(x\right)+f\left(y\right) \)) אז קל לראות שקיים \( z\in F^{n} \) כך ש-\( f\left(x\right)=z\cdot x=\sum_{i=1}^{n}z_{i}x_{i} \) ; פשוט מגדירים \( z_{i}=f\left(e_{i}\right) \) כאשר \( e_{i} \) הוקטור ב-\( F^{n} \) שכולו 0 למעט 1 במקום \( i \). כעת,

\( f\left(x\right)=f\left(\sum_{i=1}^{n}x_{i}e_{i}\right)=\sum_{i=1}^{n}x_{i}f\left(e_{i}\right)=\sum_{i=1}^{n}z_{i}x_{i} \)

כלומר, כל פונקציונל לינארי הוא בעצם “מכפלה סקלרית”, ואם יש לנו דרך לחשב את \( f \) על הערכים \( e_{1},\dots,e_{n} \) נוכל תוך \( n \) הפעלות של \( f \) “ללמוד” מהו ה-\( z \) שמגדיר את הפונקציונל הזה, ולא משנה באיזו דרך הפונקציונל נתון לנו. גם אם הוא נתון בתור “קופסה שחורה” שכל מה שאנחנו יכולים לעשות איתה הוא להכניס קלט ולקבל פלט, תוך \( n \) שאילתות נלמד את \( f \).

בהקשר הקונקרטי שלנו, \( F=\mathbb{Z}_{2} \) ו-\( f \) נתונה באמצעות אורקל, שהוא הפורמליזם המתמטי של “קופסה שחורה” שכזו. לא קשה להוכיח, אחרי פירמול מתאים, שחייבים \( n \) שאילתות כדי ללמוד את \( z \) - אחרי \( n-1 \) שאילתות, האינפורמציה שהתקבלה עדיין מתאימה לשני ערכים שונים של \( z \). מצד שני, אם האורקל שלנו הוא קוונטי, אפשר בקריאות - באופן דרסטי! מספיקה קריאה אחת בלבד לאורקל.

אבל מה זה “אורקל קוונטי”? אורקל רגיל הוא משהו שמקבל \( x \) ומחזיר \( f\left(x\right) \). האורקל הקוונטי שבו נשתמש כאן עושה משהו מוזר יותר: הוא מקבל סופרפוזיציה \( \sum_{x\in\mathbb{Z}_{2}^{n}}a_{x}\left|x\right\rangle \) ומחזיר סופרפוזיציה \( \sum_{x\in\mathbb{Z}_{2}^{n}}a_{x}\left(-1\right)^{f\left(x\right)}\left|x\right\rangle \). באופן קומפקטי, אם אסמן אותו \( U_{f} \), הוא אופרטור אוניטרי שמבצע את הפעולה הבאה: \( U_{f}\left|x\right\rangle =\left(-1\right)^{f\left(x\right)}\left|x\right\rangle \).

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

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

\( \left|z\right\rangle =H^{\otimes n}U_{f}H^{\otimes n}\left|0\right\rangle \)

המעגל הזה עושה שלושה דברים: מתחילים מהמצב \( \left|0\right\rangle \) ומפעילים עליו \( H^{\otimes n} \), מה שכפי שכבר ראינו מייצר את הסופרפוזיציה האחידה של כל המצבים הקוונטיים האפשריים על \( n \) קיוביטים. אחר כך מפעילים את \( U_{f} \) על המצב הזה - מחשבים “במקביל” את \( f \) על כל הקלטים האפשריים. לבסוף, “מקפלים חזרה” את הסופרפוזיציה באמצעות עוד הפעלה של \( H^{\otimes n} \) ובאופן פלאי היא תתקפל למצב קוונטי אחד ויחיד - \( \left|z\right\rangle \) - שמקודד בדיוק את הוקטור שחיפשנו. כל מה שנשאר בסיום הוא לבצע מדידה, ומכיוון שאנחנו במצב בסיס אחד ויחיד, המדידה תחזיר את התשובה הנכונה בהסתברות 1: האלגוריתם הוא אפילו לא הסתברותי באופיו, הצלחה תמיד מובטחת. זה יפהפה.

למה זה עובד? בשביל להבין את זה צריך לחזור לשאלה ששאלתי קודם - מהו באופן כללי \( H^{\otimes n}\left|y\right\rangle \), עבור \( \left|y\right\rangle \) שהוא לא בהכרח \( \left|0\right\rangle \)? לשם כך בואו נזכיר לעצמנו את ההגדרה של \( H \):

• \( H\left|0\right\rangle =\left|0\right\rangle +\left|1\right\rangle \)
• \( H\left|1\right\rangle =\left|0\right\rangle -\left|1\right\rangle \)

אפשר לחשוב על \( H \) שפועל על וקטור של \( n \) קיוביטים באופן הבא: הוא פועל על קיוביט ספציפי (סימנתי ב-\( H^{i} \) את שער \( H \) שפועל על הקיוביט ה-\( i \)) והוא מייצר שני וקטורים מוקטור הקלט - אחד שבו הקיוביט נותר כמות שהוא, ואחד שבו הקיוביט התהפך. בשלושה מבין ארבעת המקרים הללו הוא לא משנה את הסימן של הוקטור, אבל במקרה אחד הוא מכפיל את הסימן של הוקטור במינוס 1 - במקרה שבו הקיוביט שעליו הוא פועל הוא 1, והוא הותיר אותו כמות שהוא.

כעת, נניח ש-\( \left|y\right\rangle =\left|0110\right\rangle \). כשאנחנו מפעילים את \( H^{\otimes4} \) על \( \left|y\right\rangle \) נקבל סופרפוזיציה של מצבים. מה יהיה הסימן של המצב \( \left|1100\right\rangle \)? לשם כך, בואו נבין מה ה”מסלול” שבו נוצר המצב הזה. הפעלנו \( H^{1} \) על \( \left|y\right\rangle \) והחלטנו להפוך את הקיוביט הראשון ל-\( 1 \) - זה לא כופל במינוס 1 כי הקיוביט לא היה 1 קודם. אחר כך הפעלנו את \( H^{2} \) על התוצאה, \( \left|1110\right\rangle \) והחלטנו לא להפוך את הקיוביט השני, מה שמשאיר אותנו ב-\( \left|1110\right\rangle \) ומכפיל את המקדם שלנו ב-\( -1 \). את הקיוביט השלישי בחרנו להפוך (לא מכפיל במינוס 1) ואת הרביעי בחרנו להותיר כמות שהוא, כך שבסופו של דבר קיבלנו \( -\left|1100\right\rangle \).

אם כן, כדי לדעת מה יהיה הסימן של \( \left|x\right\rangle \) שהתקבל מ-\( \left|y\right\rangle \) צריך לעשות שני דברים:

• לבדוק אילו קיוביטים הם 1 ב-\( \left|y\right\rangle \) ונשארו כאלו גם ב-\( \left|x\right\rangle \).
• לספור האם המספר שלהם הוא זוגי (ואז ביצענו מספר זוגי של מכפלות במינוס 1 וכלום לא השתנה) או אי-זוגי.

לשני אלו יחד יש תיאור פשוט במיוחד: אנחנו מתעניינים ב-\( x\cdot y \) מודולו 2 - וזה, במקרה, בדיוק גם מה שברנשטיין וזירני מתעסק בו. פורמלית:

\( H^{\otimes n}\left|y\right\rangle =\sum_{x\in\mathbb{Z}_{2}^{n}}\left(-1\right)^{x\cdot y}\left|x\right\rangle \)

ועכשיו קל לראות למה המעגל הקוונטי עובד:

\( H^{\otimes n}U_{f}H^{\otimes n}\left|0\right\rangle =H^{\otimes n}U_{f}\sum_{y}\left|y\right\rangle = \)

\( =H^{\otimes n}\sum_{y}\left(-1\right)^{z\cdot y}\left|y\right\rangle =\sum_{y}\sum_{x}\left(-1\right)^{z\cdot y}\left(-1\right)^{x\cdot y}\left|x\right\rangle =\sum_{x}\left(\sum_{y}\left(-1\right)^{\left(x+z\right)\cdot y}\right)\left|x\right\rangle \)

כדי להבין מה קורה עכשיו, בואו נקבע את \( x \) להיות משהו, ונבדוק את הערך של המחובר הפנימי, \( \sum_{y}\left(-1\right)^{\left(x+z\right)\cdot y} \). אולי יהיה יותר קל אם במקום \( x+z \) יופיע שם \( x-z \), מה ששקול לחלוטין כי אנחנו מעל \( \mathbb{Z}_{2} \) ולכן \( 1=-1 \). אז מהו \( \sum_{y}\left(-1\right)^{\left(x-z\right)\cdot y} \)? יש פה שתי אפשרויות. ראשית, אם \( x=z \) אז נקבל את הסכום \( \sum_{y}1=2^{n} \) כי \( y \) רץ על כל \( \left\{ 0,1\right\} ^{n} \). כעת, אם \( x\ne z \) ולו בקואורדינטה בודדת אז נקבל 0. למה? בואו נניח שההבדל הוא בקואורדינטה הראשונה, כלומר \( x-z=1w^{\prime} \) כך ש-\( w^{\prime} \) היא מחרוזת של \( n-1 \) ביטים. עכשיו אפשר לחלק את כל ה-\( y \)-ים לזוגות זוגות של איברים מהצורה \( 0y^{\prime} \) ו-\( 1y^{\prime} \) כך ש-\( y^{\prime} \) היא מחרוזת של \( n-1 \) ביטים; בבירור \( \left(0y^{\prime}\right)\cdot\left(1w^{\prime}\right)\ne\left(1y^{\prime}\right)\cdot\left(1w^{\prime}\right) \) כי באגף שמאל הקואורדינטה הראשונה לא תורמת כלום למכפלה הסקלרית, ובאגף ימין הוא תורמת 1. לכן \( \left(-1\right)^{\left(0y^{\prime}\right)\cdot\left(1w^{\prime}\right)}+\left(-1\right)^{\left(1y^{\prime}\right)\cdot\left(1w^{\prime}\right)}=0 \) ולכן כל הסכום \( \sum_{y}\left(-1\right)^{\left(x-z\right)\cdot y} \) יהיה שווה אפס כי הוא סכום של זוגות של איברים שסכומם הוא אפס.

המסקנה? \( \sum_{x}\left(\sum_{y}\left(-1\right)^{\left(x-z\right)\cdot y}\right)\left|x\right\rangle =2^{n}\left|z\right\rangle \), אבל הקבוע לא באמת צריך להיות שם. זוכרים שאני מחפף בכתיבת הקבועים? כשאני כותב \( H^{\otimes n}\left|0\right\rangle =\sum_{x}\left|x\right\rangle \) זה שקר; אני באמת צריך לכתוב \( \left(\frac{1}{\sqrt{2}}\right)^{n}\sum_{x}\left|x\right\rangle \); וגם ההפעלה השניה של \( H^{\otimes n} \) מכפילה בקבוע הזה, כך שבסך הכל הכפלנו בקבוע \( \frac{1}{2^{n}} \) שמתקזז בדיוק עם ה-\( 2^{n} \) שהתווסף לנו. המסקנה הסופית היא ש-\( H^{\otimes n}U_{f}H^{\otimes n}\left|0\right\rangle =\left|z\right\rangle \), כפי שהבטחתי.

בעיית הפונקציה הלינארית החבויה

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

הפונקציה המורכבת יותר תהיה סוג של תבנית ריבועית עם הזזה אפינית. לא אומר לכם כלום? זו פשוט פונקציה \( q\left(x\right):\mathbb{Z}_{2}^{n}\to\mathbb{Z}_{4} \) (שימו לב: הטווח הוא \( \mathbb{Z}_{4} \) ולא \( \mathbb{Z}_{2} \)) שמוגדרת בעזרת מטריצה \( A\in\mathbb{Z}_{2}^{n\times n} \) ווקטור \( b\in\mathbb{Z}_{2}^{n} \) כך ש-

\( q\left(x\right)=2x^{t}Ax+bx=2\sum_{1\le i<j\le n}A_{i,j}x_{i}x_{j}+\sum_{i=1}^{n}b_{i}x_{i} \)

הפונקציה \( q \) נתונה במפורש; אנחנו לא מתעניינים בדיוק בה, אלא בפונקציה לינארית \( f \) שהיא הצמצום של \( q \) לתת-מרחב מסויים של \( \mathbb{Z}_{2}^{n} \). תת-המרחב מוגדר כך:

\( \mathcal{L}_{q}=\left\{ x\in\mathbb{Z}_{2}^{n}\ |\ \forall y\in\mathbb{Z}_{2}^{n}:q\left(x+y\right)=q\left(x\right)+q\left(y\right)\right\} \)

כלומר, \( \mathcal{L}_{q} \) כולל את כל הוקטורים ב-\( \mathbb{Z}_{2}^{n} \) שעבורם \( q \) “נראית לינארית” ביחס לכל הוקטורים ב-\( \mathbb{Z}_{2}^{n} \). אנחנו רוצים להשתכנע ש-\( \mathcal{L}_{q} \) הוא באמת תת-מרחב לינארי וש-\( q \) מצומצמת אליו היא פונקציה לינארית. מכיוון שאנחנו מעל \( \mathbb{Z}_{2} \), כלומר הסקלרים היחידים הם 0 ו-1, העבודה שלנו קלה יחסית: כדי להוכיח שקבוצה היא תת-מרחב מספיק להראות שהיא סגורה לחיבור, וכדי להראות שפונקציה היא לינארית מספיק להראות שהיא מקיימת \( q\left(x+y\right)=q\left(x\right)+q\left(y\right) \), מה שאוטומטית הולך להתקיים עבור אברי \( \mathcal{L}_{q} \) כי כך המרחב הזה מוגדר.

כדי להראות ש-\( \mathcal{L}_{q} \) הוא מרחב וקטורי צריך להראות שאם \( x,z\in\mathcal{L}_{q} \) אז גם \( x+z\in\mathcal{L}_{q} \), כלומר שלכל \( y \) מתקיים \( q\left(\left(x+z\right)+y\right)=q\left(x+z\right)+q\left(y\right) \). כדי לראות את זה, נשים לב לכך ש-\( q\left(\left(x+z\right)+y\right)=q\left(x+\left(z+y\right)\right) \) ומכיוון ש-\( x\in\mathcal{L}_{q} \) נסיק ש

\( q\left(x+\left(z+y\right)\right)=q\left(x\right)+q\left(z+y\right) \)

ומכיוון ש-\( z\in\mathcal{L}_{q} \) אפשר לפתוח גם את המחובר השמאלי ולקבל

\( q\left(x\right)+q\left(z+y\right)=q\left(x\right)+q\left(z\right)+q\left(y\right) \)

ולסיום, \( q\left(x\right)+q\left(z\right)=q\left(x+z\right) \) כמובן שמתקיים בגלל ש-\( x\in\mathcal{L}_{q} \). זה מסיים את ההוכחה הזו.

אם נצמצם את \( q \) אל \( \mathcal{L}_{q} \) עדיין קשה יהיה לקרוא למה שנקבל “פונקציה לינארית” כי הטווח של פונקציה לינארית צריך להיות מרחב וקטורי בעצמו מעל השדה שלנו, במקרה הזה \( \mathbb{Z}_{2} \), אבל \( \mathbb{Z}_{4} \) אינו כזה (כי אם \( V \) מרחב וקטורי מעל \( \mathbb{Z}_{2} \) אז \( v+v=\left(1+1\right)v=0\cdot v=0 \), אבל ב-\( \mathbb{Z}_{4} \) קיים איבר מסדר 4). מה שכן קל לראות הוא שדה-פקטו, \( q \) מחזירה רק 0 או 2 על אברי \( \mathcal{L}_{q} \), כי \( q\left(x\right)+q\left(x\right)=q\left(x+x\right)=q\left(0\right)=0 \), כלומר \( 2q\left(x\right)=0 \) מה שקורה רק אם \( q\left(x\right)\in\left\{ 0,2\right\} \). לכן אפשר להגדיר פונקציה \( f:\mathcal{L}_{q}\to\mathbb{Z}_{2} \) על ידי \( f\left(x\right)=\frac{q\left(x\right)}{2} \) וזו תהיה הפונקציה הלינארית שלנו, כלומר קיים \( z\in\mathbb{Z}_{2}^{n} \) כך ש-\( f\left(x\right)=z\cdot x \), מה שאומר ש-\( q\left(x\right)=2z\cdot x \) לכל \( x\in\mathcal{L}_{q} \). הנה האתגר שלנו במפורש - למצוא את ה-\( z \) הזה. לבעיה הזו המאמר קורא Hidden Linear Function Problem, והיא כמעט הבעיה ששייכת ל-SQC אבל לא ל-\( \text{NC}^{0} \); הבעיה פה תהיה שהבעיה לא שייכת ל-SQC ויהיה צורך בהגבלה נוספת עליה כדי להכניס אותה ל-SQC למרות שזה לא יהיה מספיק כדי להכניס אותה ל-\( \text{NC}^{0} \).

המעגל הקוונטי שפותר את הבעיה הזו יהיה שוב פשוט עד להפתיע, ובערך מהצורה \( H^{\otimes n}U_{q}H^{\otimes n}\left|0\right\rangle \). אני אומר “בערך” כי החלק של ה-\( U_{q} \) הוא עכשיו לא אורקל אלא מעגל קונקרטי שמקבל כקלט, בנוסף ל-\( H^{\otimes n}\left|0\right\rangle \), גם את \( A \) ו-\( b \). האפקט של \( U_{q} \) על \( \left|x\right\rangle \) מאוד דומה לזה של ברנשטיין וזירני אבל מביא בחשבון את זה שהפעם יש ארבעה פלטים אפשריים שונים של \( q \) על קלט כללי, ולכן המקדם שהוא מצמיד ל-\( \left|x\right\rangle \) יהיה בעל אחד מבין ארבעה ערכים מובחנים:

\( U_{q}\left|x\right\rangle =i^{q\left(x\right)}\left|x\right\rangle \)

כאשר \( i \) הוא מספר מדומה שמקיים \( i^{2}=-1 \).

עוד דבר שהוא קצת שונה הוא שהפעם לא יתקיים \( H^{\otimes n}U_{q}H^{\otimes n}\left|0\right\rangle =\left|z\right\rangle \); הפלט יהיה סופרפוזיציה של מצבים. רק שכל המצבים הללו יתאימו לערכים אפשריים של \( z \) שפותר את הבעיה; הפעם פשוט יש יותר מערך אחד כזה.

אז יש לנו שתי שאלות:

1. איך אנחנו מממשים את \( U_{q} \) עם שערים קוונטיים?
2. למה בדיוק כל איבר שכלול ב-\( H^{\otimes n}U_{q}H^{\otimes n}\left|0\right\rangle \) הוא פתרון?

התשובה ל-1 פשוטה ויפה: \( U_{q}=\bigotimes_{j}S_{j}^{b_{j}}\cdot\prod_{1\le i\le j\le n}CZ_{i,j}^{A_{i,j}} \), אבל בואו נסביר מה זה אומר.

שער \( CZ_{i,j} \) מפעיל Controlled-Z על \( i,j \) כש-\( i \) הוא קיוביט ה”בקרה”. כשאני מסמן \( CZ_{i,j}^{A_{i,j}} \) פירוש הדבר הוא שאני מוסיף עוד התניה על השער הזה - אם \( A_{i,j}=1 \) אז הוא יופעל, ואם \( A_{i,j}=0 \) הוא לא יופעל; דה פקטו אפשר לקרוא לזה שער \( CCZ \). הסימון \( \prod \) בא לומר שאני מפעיל את השערים הללו סדרתית ולא “בבת אחת”, למרות שאם אפשר למקבל חלק מההפעלות מן הסתם נעשה את זה.

אחרי שערי ה-\( CZ \) מגיעה הפעלה “בבת אחת” של שערי פאזה: \( S_{j} \) מסמן הפעלה של שער פאזה, כלומר \( \left(\begin{array}{cc} 1 & 0\\ 0 & -i \end{array}\right) \), על קיוביט מספר \( j \). רק שכאן גם שערי הפאזה מותנים בכך ש-\( b_{j}=1 \) ואחרת הם לא מופעלים; קראתי לשער כזה \( CS \) בהתחלה.

עכשיו, למה שיתקיים \( U_{q}\left|x\right\rangle =i^{q\left(x\right)}\left|x\right\rangle \)?

ראשית, \( CZ_{i,j}\left|x\right\rangle =\left(-1\right)^{x_{i}\cdot x_{j}}\left|x\right\rangle \) - זוכרים שאמרתי ש-\( CZ \) הוא סוג של AND? כאן רואים את זה. על כן, \( CZ_{i,j}^{A_{i,j}}\left|x\right\rangle =\left(-1\right)^{A_{i,j}x_{i}\cdot x_{j}}\left|x\right\rangle \). מכיוון ש-\( i^{2}=-1 \) אפשר גם לכתוב \( CZ_{i,j}^{A_{i,j}}\left|x\right\rangle =i^{2A_{i,j}x_{i}\cdot x_{j}}\left|x\right\rangle \)

שנית, \( S_{j}^{b_{j}}\left|x\right\rangle =i^{b_{j}\cdot x_{j}}\left|x\right\rangle \); גם שער \( CS \) הוא מעין AND, הפעם בין \( b_{i} \) ו-\( x_{i} \).

משני אלו נקבל:

\( U_{q}\left|x\right\rangle =i^{q\left(x\right)}\left|x\right\rangle =\prod_{i,j}i^{\left(2A_{i,j}x_{i}\cdot x_{j}\right)}\prod_{j}i^{b_{j}\cdot x_{j}}\left|x\right\rangle \)

\( =i^{\left(2\sum_{i,j}A_{i,j}x_{i}x_{j}+\sum_{j}b_{j}x_{j}\right)}\left|x\right\rangle =i^{q\left(x\right)}\left|x\right\rangle \)

שזה בדיוק מה שרצינו. האורקל נעלם; אנחנו רואים איך אפשר לממש את האפקט \( U_{q}\left|x\right\rangle =i^{q\left(x\right)}\left|x\right\rangle \) עם שערים קונקרטיים לחלוטין. הבעיה היחידה היא עומק המעגל שמבצע את החישוב, ונדבר על זה עוד מעט.

עכשיו ננסה להבין איך נראה המצב הקוונטי \( H^{\otimes n}U_{q}H^{\otimes n}\left|0\right\rangle \). ה-\( H^{\otimes n}\left|0\right\rangle \) שבהתחלה מייצר את הסופרפוזיציה האחידה, \( \sum_{x\in\mathbb{Z}_{2}^{n}}\left|x\right\rangle \), וה-\( U_{q} \) שאחר כך מייצר לנו את הסופרפוזיציה \( \sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left|y\right\rangle \). מה עכשיו?

יותר מוקדם בפוסט ראינו ש-\( H^{\otimes n}\left|y\right\rangle =\sum_{z\in\mathbb{Z}_{2}^{n}}\left(-1\right)^{z\cdot y}\left|z\right\rangle \). אם נשתמש בזה כאן, נקבל שהסופרפוזיציה שמגיעים אליה בסיום היא

\( \sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left(\sum_{z\in\mathbb{Z}_{2}^{n}}\left(-1\right)^{z\cdot y}\left|z\right\rangle \right) \)

או, אם נחליף את סדר הסכימה:

\( \sum_{z\in\mathbb{Z}_{2}^{n}}\left(\sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left(-1\right)^{z\cdot y}\right)\left|z\right\rangle \)

כלומר, המקדם של \( \left|z\right\rangle \) בסופרפוזיציה שבסיום הוא הביטוי \( \sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left(-1\right)^{z\cdot y} \). כדי להקל על חישוב הביטוי הזה, המאמר מאמץ את הסימון הבא, עבור כל תת-מרחב לינארי \( \mathcal{L} \) של \( \mathbb{Z}_{2}^{n} \):

\( \Gamma\left(\mathcal{L},z\right)=\sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left(-1\right)^{z\cdot y} \)

אז המטרה שלנו היא להבין מהו \( \Gamma\left(\mathbb{Z}_{2}^{n},z\right) \). המאמר נכנס לחישוב בפירוט, אבל לנו מספיק להבין כרגע למה זה אפס אם \( z \) הוא לא פתרון לבעיית הפונקציה הלינארית החבויה ומשהו שונה מאפס אם הוא כן. לשם כך, המאמר נוקט בגישה הבאה: ניקח משלים ישר \( \mathcal{K} \) כלשהו של \( \mathcal{L}_{q} \), כלומר תת-מרחב וקטורי של \( \mathbb{Z}_{2}^{n} \) כך שמתקיים \( \mathbb{Z}_{2}^{n}=\mathcal{L}_{q}\oplus\mathcal{K} \). כעת ניתן להוכיח שמתקיים

\( \Gamma\left(\mathbb{Z}_{2}^{n},z\right)=\Gamma\left(\mathcal{L}_{q},z\right)\cdot\Gamma\left(\mathcal{K},z\right) \)

האינטואיציה לכך פשוטה: כל \( y\in\mathbb{Z}_{2}^{n} \) אפשר להציג באופן יחיד בתור \( y=y_{1}+y_{2} \) כך ש-\( y_{1}\in\mathcal{L}_{q} \) ו-\( y_{2}\in\mathcal{K} \). כעת קחו את הביטוי \( \Gamma\left(\mathcal{L},z\right)=\sum_{y\in\mathbb{Z}_{2}^{n}}i^{q\left(y\right)}\left(-1\right)^{z\cdot y} \) והציבו \( y_{1}+y_{2} \) במקום \( y \): שימו לב ש-\( q\left(y_{1}+y_{2}\right)=q\left(y_{1}\right)+q\left(y_{2}\right) \) כי \( y_{1}\in\mathcal{L}_{q} \) וזו בדיוק התכונה המייחדת של \( \mathcal{L}_{q} \), שהקסם הזה מתקיים בה.

בואו נשתכנע עכשיו ש-\( \Gamma\left(\mathcal{L}_{q},z\right) \) מתאפס אם ורק אם \( z \) הוא לא פתרון של בעיית הפונקציה הלינארית החבויה. הרעיון הוא כזה: אנחנו רוצים לחשב את \( \sum_{y\in\mathcal{L}_{q}}i^{q\left(y\right)}\left(-1\right)^{z\cdot y} \) ויכולים להיעזר בכך שאנחנו יודעים שמעל \( \mathcal{L}_{q} \), הפונקציה \( q\left(y\right) \) מתנהגת כמו מכפלה באיבר ספציפי שנקרא לו \( z^{\prime} \). פורמלית: \( q\left(y\right)=2z^{\prime}\cdot y \). לכן נקבל:

\( \Gamma\left(\mathcal{L}_{q},z\right)=\sum_{y\in\mathcal{L}_{q}}i^{2z^{\prime}\cdot y}\left(-1\right)^{z\cdot y}=\sum_{y\in\mathcal{L}_{q}}\left(-1\right)^{z^{\prime}\cdot y}\left(-1\right)^{z\cdot y}=\sum_{y\in\mathcal{L}_{q}}\left(-1\right)^{\left(z-z^{\prime}\right)\cdot y} \)

קיבלנו כמעט את אותו הדבר עם ברנשטיין-וזירני, רק ששם הסכום רץ על כל \( \mathbb{Z}_{2}^{n} \) וכאן הוא רץ רק על \( \mathcal{L}_{q} \). בברנשטיין-וזירני הסכום לא התאפס רק אם המכפלה הפנימית כן התאפסה לכל \( y \); מכיוון ששם \( y \) רץ על כל \( \mathbb{Z}_{2}^{n} \) זה קרה רק אם \( z-z^{\prime} \) היה וקטור האפס, אבל עכשיו \( y \) רץ רק על \( \mathcal{L}_{q} \) ולכן המכפלה הפנימית יכולה להתאפס לעוד איברים; כזכור, משתמשים בסימון \( \mathcal{L}_{q}^{\perp} \) כדי לתאר את קבוצת האיברים הזו - המרחב האורתוגונלי של \( \mathcal{L}_{q} \). אז אם \( z-z^{\prime}\in\mathcal{L}_{q}^{\perp} \), הסכום לא מתאפס. במקרה שבו \( z-z^{\prime}\in\mathcal{L}_{q}^{\perp} \), לכל \( y\in\mathcal{L}_{q} \) מתקיים \( \left(z-z^{\prime}\right)y=0 \), כלומר \( zy=z^{\prime}y \), כלומר \( q\left(y\right)=2z\cdot y \) וקיבלנו שגם \( z \) הוא פתרון לבעיית הפונקציה הלינארית החבויה - כפי שרצינו.

מה קורה אם \( z-z^{\prime}\notin\mathcal{L}_{q}^{\perp} \)? במקרה הזה, קיים \( a\in\mathcal{L}_{q} \) כך ש-\( \left(z-z^{\prime}\right)a=1 \), ועכשיו אפשר לחלק את אברי \( \mathcal{L}_{q} \) לזוגות-זוגות: לכל \( y\in\mathcal{L}_{q} \), בן הזוג שלו יהיה \( y+a \) (ובן הזוג של \( y+a \) יהיה, ובכן, \( \left(y+a\right)+a=y+2a=y \) כי אנחנו מעל \( \mathbb{Z}_{2} \)). בבירור \( \left(z-z^{\prime}\right)\left(y+a\right)=\left(z-z^{\prime}\right)y+1 \) כך ששני האיברים הללו מחזירים ערך שונה בכפל סקלרי ב-\( z-z^{\prime} \) ולכן \( \left(-1\right)^{\left(z-z^{\prime}\right)y}+\left(-1\right)^{\left(z-z^{\prime}\right)\left(y+a\right)}=0 \) וקיבלנו ש-\( \Gamma\left(\mathcal{L}_{q},z\right)=0 \) אם \( z-z^{\prime}\notin\mathcal{L}_{q}^{\perp} \), כלומר במקרה שבו \( z \) אינו פתרון של בעיית הפונקציה הלינארית החבויה.

סיכום ביניים זריז ופרידה שהיא בריחה מהירה

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

ראשית, הבעיה עצמה: מה שקראתי לו “בעיית הפונקציה הלינארית החבויה” היא אמנם בעיה שלא שייכת ל-\( \text{NC}^{0} \) אבל גם ל-\( \text{SQC} \) היא כנראה לא שייכת. כדי לקבל בעיה ששייכת ל-\( \text{SQL} \) צריך להגביל את הסיטואציה קצת יותר. בבעיית הפונקציה הלינארית החבויה יש לנו תבנית ריבועית שנתונה על ידי מטריצה \( A\in\mathbb{Z}_{2}^{n\times n} \) ווקטור \( b\in\mathbb{Z}_{2}^{n} \). ההגבלה הנוספת היא הדרישה שיתקיים \( A_{i,j}=0 \) עבור רוב הכניסות של \( A \). הנה הפורמליזם: בואו נסתכל על השריג \( \mathbb{Z}_{N}\times\mathbb{Z}_{N} \) עבור \( N \) כלשהו; כל נקודה בשריג היא מהצורה \( \left(i,j\right) \) כך ש-\( 0\le i,j\le N-1 \) - יש בסך הכל \( N^{2} \) נקודות כאלו. נבחר \( n=N^{2} \) (זה מספר השורות והעמודות של \( A \)) וכעת כל כניסה של \( A \) ניתנת לייצוג בתור נקודה בשריג. כעת, \( A \) מכילה 0 בכל כניסה שמתאימה לזוג נקודות שאינן שכנות בשריג - כלומר, המרחק ביניהן על פי המטריקה \( d\left(\left(i,j\right),\left(x,y\right)\right)=\left|i-x\right|+\left|j-y\right| \) שונה מ-1. עבור כניסות במטריצה שמייצגות נקודות שכנות, הערך יכול להיות 0 או 1. לבעיה הזו קורא המאמר “בעיית הפונקציה הלינארית החבויה הדו-ממדית” והיא הבעיה שהיא קלה מספיק כדי להיות ב-\( \text{SQC} \) אבל לא ב-\( \text{NC}^{0} \).

נותרו שני דברים לעשות, שהם ה”בשר” האמיתי של המאמר - להראות איך לבנות מעגל קוונטי מעומק קבוע עבור הבעיה (בדיוק בעזרת מימוש ה-\( U_{q} \) שראינו למעלה, רק צריך לראות שזה ניתן למימוש), ולהראות שהבעיה לא ב-\( \text{NC}^{0} \). לעת עתה אני אמלט באלגנטיות מלהציג את הדברים הללו כאן.