חישוב קוונטי - האלגוריתם של סימון

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

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

הבעיה של סימון היא זו: נתונה פונקציה \( f:\left\{ 0,1\right\} ^{n}\to\left\{ 0,1\right\} ^{n} \) שמקבלת \( n \) ביטים (קלאסיים) ומחזירה \( n \) ביטים. הפונקציה הזו היא מאוד מיוחדת, במובן זה שכל ערך שהיא מחזירה, היא מחזירה בדוק פעמיים, ובאופן שהוא מעין מחזורי. פורמלית, קיים \( a\in\left\{ 0,1\right\} ^{n} \) כך ש-\( f\left(x\right)=f\left(y\right) \) עבור \( x\ne y \) אם ורק אם \(  x\oplus y=a \) (או בסימון אחר, \( x=y\oplus a \)). זה מזכיר פונקציות מחזוריות “קלאסיות”: \( g:\mathbb{R}\to\mathbb{R} \) היא מחזורית אם \( g\left(x+a\right)=g\left(x\right) \) עבור \( a\in\mathbb{R} \) כלשהו, שהוא ה”מחזור” של \( g \); עבור \( f \) אנחנו משתמשים בפעולת ה-XOR שאני מסמן \( \oplus \) מכיוון שאנחנו מתעסקים לא עם מספרים ממשיים אלא עם מחרוזות בינאריות.

אם כן, הקלט לבעיה היא \( f \) שמובטח שהיא מחזורית במובן שהוצג לעיל. המטרה? למצוא את המחזור שלה, דהיינו את \( a \).

איך יעבוד אלגוריתם קלאסי שמנסה לפתור את הבעיה? הפתרון הנאיבי ביותר הוא פשוט להזין ל-\( f \) ערכים ולקוות שנקבל את אותו פלט פעמיים; אם זה קורה, מן הסתם מצאנו את \( a \) (אם מצאנו \( x\ne y \) כך ש-\( f\left(x\right)=f\left(y\right) \) אז \( a=x\oplus y \)). הבעיה היא שאלגוריתם כזה קל להכשיל, במובן זה שיידרש ממנו המון זמן לפתור את הבעיה. חשבו על כך שאליס בוחרת אילו ערכים להזין ל-\( f \), ואילו בוב בוחר מראש את \( f \) כדי להקשות עליה. אם דרך הפעולה של אליס היא דטרמיניסטית, אז לבוב ממש קל להכשיל אותה - הוא יבחר \( f \) שנותנת תשובות שונות לכמה שיותר שאילתות של אליס שרק אפשר (ואפשר בערך \( 2^{\frac{n}{2}} \) שאילתות להפיל ככה). אם אליס נוקטת בגישה הסתברותית ומגרילה את הערכים שהיא שואלת עליהם אז לבוב יהיה קצת יותר קשה לבחור את \( f \) מראש, אבל הוא עדיין יכול לעשות את זה בצורה שתדרוש מאליס מספר אקספוננציאלי של שאלות במקרים מסויימים. אז הפתרון הנאיבי הזה הוא בעייתי.

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

אז מה סימון עושה?

מה שכל כך נחמד באלגוריתם הזה הוא הגישה השונה מהותית שלו לענייני החישוב הקוונטי ביחס לאלגוריתם של גרובר. מה שגרובר עשה היה לחזור שוב ושוב על פעולת הגברה שקירבה את המצב הקוונטי של החישוב שלו אל הפתרון הנכון, כך שכאשר מדדנו לבסוף את מצב הרגיסטר הקוונטי, בהסתברות גבוהה הוא החזיר לנו את הפתרון הנכון. סימון עושה משהו שונה לגמרי: הוא משתמש בכך שהמידע על \( a \) במובן מסויים “מפוזר בכל המרחב” (כי לכל \( x\in\left\{ 0,1\right\} ^{n} \) שרק ניקח, קיים \( y\in\left\{ 0,1\right\} ^{n} \) כך ש-\( f\left(x\right)=f\left(y\right) \) ועל כן \( a=x\oplus y \)) והוא משתמש בחישוב הקוונטי כדי לשלוף מידע לא טריוויאלי כלשהו על \( a \) מתוך מקום אקראי במרחב הזה. הוא חוזר על השיטה הזו מספר פעמים עד שהוא שולף די והותר מידע על \( a \) שמאפשר את השחזור המדויק שלו.

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

האלגוריתם, כאמור, מורכב חזרה שוב ושוב על אותו חישוב, כאשר הפלט הסופי של החישוב בכל איטרציה הוא וקטור \( b\in\left\{ 0,1\right\} ^{n} \) המקיים \( a\cdot b=0 \) ונבחר באקראי מבין כל הוקטורים שמקיימים את התכונה הזו. כלומר, אנחנו מקבלים סדרה \( b_{1},b_{2},\dots,b_{k} \) של וקטורים כאלו, ואחרי שאנחנו מוצאים מספיק מהם נוכל לשחזר את \( a \) על ידי פתרון של מערכת המשוואות הלינאריות שמוגדרת על ידי ה-\( b \)-ים הללו (נצטרך \( n-1 \) וקטורים בלתי תלויים לינארית כדי להבטיח קיום פתרון לא טריוויאלי יחיד למערכת - אפשר להוכיח שעבור \( k\ge2n \) ההסתברות שיהיו לנו כאלו היא גבוהה). מכירים את הציטוט הידוע שמיוחס לאיינשטיין על כך ש”טירוף הוא לחזור שוב ושוב על אותה פעולה ולצפות לתוצאות אחרות”? זה בדיוק מה שנעשה (ומיותר לציין שאיינשטיין מעולם לא אמר משהו טיפשי שכזה, אפילו לא בתור בדיחה).

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

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

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

\( \sum_{x\in\left\{ 0,1\right\} ^{n}}\left|x\right\rangle \left|f\left(x\right)\right\rangle =\sum\left(\left|x\right\rangle +\left|x\oplus a\right\rangle \right)\left|f\left(x\right)\right\rangle \)

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

עכשיו מה עושים? מודדים את \( n \) הביטים האחרונים. כתוצאה מכך אנחנו מקבלים באופן אקראי (בהתפלגות אחידה) ערך כלשהו של \( f \) (משהו שהוא כמובן חסר ערך עבורנו) והמערכת הקוונטית שלנו קורסת למצב הקוונטי \( \left|x\right\rangle +\left|x\oplus a\right\rangle \). כלומר, מה שעשינו עד כה הניב לנו סופרפוזיציה מהצורה \( \left|x\right\rangle +\left|y\right\rangle \) בין שני איברים קונקרטיים של המרחב שנותנים לנו אותו ערך של \( f \).

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

מצד שני, וגם את זה כבר אמרתי, חישוב קוונטי הוא גם חזק יותר מחישוב הסתברותי רגיל בכך שיש לנו סט אופרטורים מתוחכם יותר שבו אפשר להשתמש. מן הסתם נצטרך לשלוף אחד כזה מהשרוול עכשיו, ומה שנשלוף מהשרוול יהיה שוב את ידידינו הותיק \( H \). כל שנעשה הוא להפעיל את \( H \) על \( n \) הקיוביטים של \( \left|x\right\rangle +\left|x\oplus a\right\rangle \) ונבצע מדידה. ה-\( b \) שהמדידה תחזיר יקיים \( a\cdot b=0 \) וייבחר באקראי מבין מרחב ה-\( b \)-ים שמקיימים את זה.

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

\( H\left(\left|x\right\rangle \right)=H\left(\left|x_{1}x_{2}\dots x_{n}\right\rangle \right)=\prod_{i=1}^{n}\left(\left|0\right\rangle +\left(-1\right)^{x_{i}}\left|1\right\rangle \right)= \)

\( \sum_{y\in\left\{ 0,1\right\} ^{n}}\left(\prod_{i:y_{i}=1}\left(-1\right)^{x_{i}}\right)\left|y\right\rangle =\sum_{y\in\left\{ 0,1\right\} ^{n}}\left(-1\right)^{x\cdot y}\left|y\right\rangle \)

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

חזרה לענייננו. אנחנו במצב הקוונטי \( \left|x\right\rangle +\left|x\oplus a\right\rangle \). מה נקבל אחרי הפעלה של \( H \)? ובכן, זכרו ש-\( H \) הוא אופרטור לינארי, כלומר \( H\left(\left|x\right\rangle +\left|x\oplus a\right\rangle \right)=H\left(\left|x\right\rangle \right)+H\left(\left|x\oplus a\right\rangle \right) \). מכאן זה רק חישוב קטן, ומקבלים שנגיע אל המצב:

\( \sum_{y\in\left\{ 0,1\right\} ^{n}}\left(\left(-1\right)^{x\cdot y}+\left(-1\right)^{x\cdot y+a\cdot y}\right)\left|y\right\rangle \)

כעת, \( \left(-1\right)^{x\cdot y+a\cdot y} \) יהיה אחד משניים: אם \( a\cdot y=1 \) אז נקבל \( \left(-1\right)^{x\cdot y+a\cdot y}=-\left(-1\right)^{x\cdot y} \), וכתוצאה מכך אחרי חיבור עם \( \left(-1\right)^{x\cdot y} \) נתאפס; ואם \( a\cdot y=0 \) אז נקבל \( \left(-1\right)^{x\cdot y+a\cdot y}=\left(-1\right)^{x\cdot y} \) ולכן אחרי חיבור עם \( \left(-1\right)^{x\cdot y} \) נקבל \( 2\left(-1\right)^{x\cdot y} \). דהיינו, הסכום שלעיל שווה ל:

\( \sum_{y:a\cdot y=0}2\left(-1\right)^{x\cdot y}\left|y\right\rangle \)

המקדם לא חשוב; מה שחשוב הוא שנפטרנו מכל ה-\( y \)-ים במרחב שעבורם \( a\cdot y=1 \) וקיבלנו פיזור אחיד על כל ה-\( y \)-ים במרחב שעבורם \( a\cdot y=0 \). לכן מדידה תניב אחד כזה באקראי (מה שקראתי לו קודם \( b \)), ומספיק מדידות יניבו לנו את \( a \). זה מסיים את הצגת האלגוריתם. עכשיו, תגידו לי שהצעד האחרון, שבו הפעלת \( H \) פתאום הניבה לנו פיזור אחיד על כל ה-\( y \)-ים שאורתוגונליים ל-\( a \), לא נראה לכם כמו קסם!

למי שזה עדיין לא נראה לו כמו קסם, אני רוצה שתשימו לב לעובדה הבאה: מה שסימון עושה מזכיר בצורה משונה את ניסוי שני הסדקים שהראיתי בתחילת סדרת הפוסטים הזו. רגע, מה? איך זה קשור בכלל? ובכן, הנה האינטואיציה. הפיזור האחיד שממנו התחלנו את האלגוריתם, \( \sum_{x\in\left\{ 0,1\right\} ^{n}}\left|x\right\rangle \left|f\left(x\right)\right\rangle \), הוא מעין מקור אור שיורה לכל הכיוונים. מה שאנחנו עושים במדידה הראשונה שלנו הוא לבחור באקראי את אחד מהכיוונים ולשים מחיצה עם שני סדקים שמאפשרת רק לקרניים ב”כיוון” \( f\left(x\right) \) לעבור - אנחנו נשארים עם שתי קרניים, מה שמתואר על ידי המצב \( \left|x\right\rangle +\left|x\oplus a\right\rangle \) (האור בסופרפוזיציה בין שני הסדקים שהוא יכל לעבור דרכם). כעת, גם בניסוי שני הסדקים אור שעבר דרך סדק לא עבר רק בכיוון אחד ספציפי - היה פיזור כלשהו של האור שעובר דרך סדק מסויים ופוגע בקיר. אצלנו \( H \) מקבלת את התפקיד של תיאור ה”פיזור” הזה. לכל נקודה \( \left|y\right\rangle \) על ה”קיר”, \( H \) נותנת שמפזרת את האור שעובר דרך \( \left|x\right\rangle \) נותנת ערך \( x\cdot y \). מה שמעניין הוא שהערך הזה הוא או 1 או \( -1 \), כלומר הוא מתאר בדיוק את אותה “עוצמה”, רק בפאזה שונה (או קיטוב שונה או איך שלא תרצו לקרוא לזה כדי להבין). אם לא היה לנו את הסדק \( x\oplus a \) והיינו מודדים איפה האור שלנו פגע בקיר, היינו רואים שכל נקודה מתקבלת באותה הסתברות. אבל מכיוון שיש לנו את הסדק \( x\oplus a \) והסדק הזה גורם לפיזור אור עם פאזה \( x\cdot y+a\cdot y \) בנקודה \( \left|y\right\rangle \), אנחנו מקבלים על הקיר תבנית התאבכות: כאשר \( a\cdot y=1 \) ההתאבכות הזו היא הורסת ואנחנו מקבלים הסתברות 0 שהנקודה הזו בקיר תיפגע; וכאשר \( a\cdot y=0 \) זו התאבכות בונה ואנחנו מקבלים בדיוק שאלו הנקודות על הקיר שיהיו “מוארות”.

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