חישוב קוונטי - דברי סיום ופרידה

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

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

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

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

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

על אילו דברים עוד לא יצא לי לדבר אבל כל סדרת פוסטים חייבת להזכיר אותם? ראשית, עוד לא סיימנו עם האלגוריתם של שור. הצגתי את האלגוריתם בתור אלגוריתם לפירוק מספרים לגורמים - מה שיחסל, למשל, את מערכת ההצפנה RSA; אבל בפועל האלגוריתם היה שיטה כללית למציאת מחזור של פונקציה, שבו השתמשנו כדי למצא את הסדר של איבר בחבורה \( \mathbb{Z}_{N}^{*} \). זה מביא אותנו קרוב מאוד אל בעיה דומה, שגם לה יש חשיבות גדולה בהצפנה (אולי אף יותר מאשר פירוק לגורמים): לוגריתם דיסקרטי. לוגריתם “רגיל” מוגדר כך: אם \( a^{x}=y \) אז \( \log_{a}y=x \). כלומר, \( \log_{a}y \) הוא הערך שעונה על השאלה “באיזו חזקה צריך להעלות את \( a \) כדי לקבל את \( y \)?” כשהשאלה הזו נשאלת על מספרים ממשיים (שהם עולם “רציף”, במובן שלא אכנס אליו כאן).

לוגריתם דיסקרטי שואל את אותה השאלה, אבל על העולם ה”בדיד” של \( \mathbb{Z}_{N}^{*} \). נניח שנתונים לנו \( a,b\in\mathbb{Z}_{N}^{*} \); אז בעיית הלוגריתם הדיסקרטי היא למצוא \( x \) כך ש-\( a^{x}=b \) בחבורה \( \mathbb{Z}_{N}^{*} \) (אם קיים כזה). לרוב ההסתמכות על קושי הבעיה במערכות הצפנה נובעת מכך ששולחים את המידע הסודי \( x \) בתור \( a^{x} \) (\( a \) ידוע לשני הצדדים), כאשר לצד השני יש מידע נוסף שמאפשר “לחלץ” את \( x \) מתוך החזקה (ולפעמים, כמו במערכת דיפי-הלמן, לא צריך לחלץ כלום). מיותר לציין שפתרון יעיל לבעיית הלוגריתם הדיסקרטי יפיל עוד מערכות הצפנה קיימות. הפאנץ’ הוא שוריאציה על האלגוריתם של שור תפתור גם את בעיית הלוגריתם הדיסקרטי.

אינטואיטיבית, גם לוגריתם דיסקרטי הוא בעיה של מציאת מחזור של פונקציה, רק שהפעם המחזור מחוכם קצת יותר. נניח שנתונים לנו \( a,b \) כך ש-\( a^{t}=b \), אז נגדיר פונקציה בשני משתנים \( f\left(x,y\right)=a^{x}b^{y} \). תוך שימוש בכך שידוע לנו ש-\( b=a^{t} \) אפשר לכתוב את הפונקציה מחדש כך:

\( f\left(x,y\right)=a^{x}a^{ty}=a^{x+ty} \)

עכשיו, קחו מספר שלם כלשהו \( k \), ושימו לב לכך שמתקיים:

\( f\left(x-kt,y+k\right)=a^{\left(x-kt\right)+t\left(y+k\right)}=a^{x+ty}=f\left(x,y\right) \)

כלומר, ל-\( f \) יש “מחזור” בדמות זוג מספרים שמוסיפים לשני הפרמטרים של \( f \) ומקבלים את אותה התוצאה - הזוג \( \left(-kt,k\right) \) (לכל \( k \) שלם). אם נצליח למצוא מחזור כזה, נוכל לחלץ מתוכו את \( t \) (אם ידוע ש-\( \left(\alpha,\beta\right) \) הוא מחזור כזה עם \( \beta\ne0 \) אז \( t=-\frac{\alpha}{\beta} \)). האלגוריתם למציאת מחזור כזה מזכיר את האלגוריתם של שור, עם קצת התחכמויות נוספות, ולא אכנס אליו.

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

הבעיה באופן כללי היא זו: נתונה לנו חבורה \( G \) ותת-חבורה \( H \). אין לנו מושג מהי \( H \), ואנחנו מעוניינים למצוא אותה; הנשק שנתון לנו לשם כך היא פונקציה \( f:G\to X \) כאשר \( X \) היא קבוצה כלשהי, ואנחנו יודעים ש-\( f \) היא קבועה בדיוק על הקוסטים של \( H \). כלומר, \( f\left(x\right)=f\left(y\right) \) אם ורק אם \( xH=yH \) (או במילים אחרות, אם תרצו טרמינולוגיה מיותרת כאן - \( f \) היא הרמה ל-\( G \) של פונקציה חח”ע שמוגדרת על \( G/H \)).

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

איך זה נראה עבור הבעיות שכבר הכרנו? נתחיל מהבעיה של מציאת סדר. נתון \( N \) ואיבר \( g \), ואנו מחפשים את \( r \) עבורו \( g^{r}=1 \) מודולו \( N \). אנחנו יודעים שמתקיים \( g^{x}=g^{y} \) אם ורק אם \( x-y \) מתחלק ב-\( r \), כלומר אם ורק אם \( x,y \) שקולים מודולו \( r \). כעת, אנחנו יודעים שמתקיים \( a^{\varphi\left(N\right)}=1 \) לכל \( a\in\mathbb{Z}_{N}^{*} \) (זה מה שנקרא משפט אוילר) ולכן מספיק להסתכל על החזקות רק עד ל-\( \varphi\left(N\right) \). זה אומר שיש לנו מקרה של בעיית תת-החבורה החבוייה עבור החבורה \( G=\mathbb{Z}_{\varphi\left(N\right)} \) עם תת-החבורה \( H=r\mathbb{Z}_{\varphi\left(N\right)} \), הקבוצה \( X=\mathbb{Z}_{N}^{*} \) והפונקציה \( f:G\to X \) המוגדרת על ידי \( f\left(x\right)=g^{x}\mbox{ mod }N \).

נעבור לבעיית הלוגריתם הדיסקרטי. כאן \( G=\mathbb{Z}_{\varphi\left(N\right)}\times\mathbb{Z}_{\varphi\left(N\right)} \) והפונקציה היא \( f:G\to\mathbb{Z}_{N}^{*} \) ומוגדרת על ידי \( f\left(x,y\right)=a^{x}b^{y}\mbox{ mod }N \). בואו נראה שבמקרה הזה, \( H=\left\{ \left(-t\alpha,\alpha\right)\ |\ \alpha\in\mathbb{Z}_{\varphi\left(N\right)}\right\} \): אם \( f\left(x_{1},y_{1}\right)=f\left(x_{2},y_{2}\right) \) אז \( a^{x_{1}+ty_{1}}=a^{x_{2}+ty_{2}} \), כלומר \( x_{1}+ty_{1}=x_{2}+ty_{2} \) מודולו \( \varphi\left(N\right) \), ולכן \( x_{1}-x_{2}=-t\left(y_{1}-y_{2}\right) \) מודולו \( \varphi\left(N\right) \). אם נסמן \( \alpha=y_{1}-y_{2} \) נקבל ש-\( \left(x_{1},y_{1}\right)-\left(x_{2},y_{2}\right)=\left(x_{1}-x_{2},y_{1}-y_{2}\right)=\left(-t\alpha,\alpha\right)\in H \), כלומר \( \left(x_{1},y_{1}\right) \) ו-\( \left(x_{2},y_{2}\right) \) אכן שייכים לאותו קוסט (להוכחה הזו יש גם כיוון שני, קל יותר, שאתם יכולים להוכיח לעצמכם).

בשני המקרים החבורה \( G \) שלנו הייתה אבלית, כלומר התקיים בה ש-\( ab=ba \). זה חשוב, מכיוון שאת השיטות שראינו באלגוריתם של שור אפשר להכליל כדי לפתור את בעיית תת-החבורה החבויה לכל חבורה אבלית סופית. ומה על חבורות סופיות לא אבליות? או, שאלה מצויינת - כרגע לא ידוע על אלגוריתם קוונטי יעיל עבורן באופן כללי, וגם לא עבור המקרים הפרטיים המעניינים.

ואילו מקרים פרטיים מעניינים יש? הנה דוגמה אחת. בעיה מפורסמת מאוד במדעי המחשב היא בעיית איזומורפיזם הגרפים. נתונים שני גרפים, \( G_{1}=\left(V_{1},E_{1}\right),G_{2}=\left(V_{2},E_{2}\right) \). הם איזומורפיים אם הם בעצם אותו גרף, רק בסימונים שונים - אם אפשר לצייר את \( G_{1} \) כך שייראה כמו \( G_{2} \). פורמלית, אם קיימת פונקציה חח”ע ועל \( f:V_{1}\to V_{2} \) המקיימת \( \left(u,v\right)\in E_{1}\iff\left(f\left(u\right),f\left(v\right)\right)\in E_{2} \).

בעיית איזומורפיזם הגרפים היא הבעיה הפשוטה הבאה: נתון זוג גרפים סופיים \( \left(G_{1},G_{2}\right) \) - האם הם איזומורפיים? מן הסתם, אם הם איזומורפיים ומישהו נותן לנו את האיזומורפיזם אז קל לבדוק שהוא מקיים את הקריטריון שלעיל; זה מראה שהבעיה היא ב-NP. אבל יותר מזה - לא ידוע. לא ידוע אם הבעיה ב-P (לפני כמה שנים הייתה מהומה סביב פתרון שנראה מאוד מבטיח, אבל בסופו של דבר כשל), ולא ידוע אם הבעיה NP-שלמה. היא נראית כמו עוד מועמד מעניין להיות בעיית “ביניים” שכזו, כמו פירוק לגורמים - אבל להבדיל מפירוק לגורמים, ולמרות שעל פניו יותר סביר שיתגלה שהיא ב-P מאשר שזה יתגלה עבור פירוק לגורמים, לא ידוע אלגוריתם קוונטי עבור הבעיה הזו.

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

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

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