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

פרולוג, ובו סקירה מהירה של השור הנורא

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

הכוכבת של הפוסט היא בעיית הפירוק לגורמים של מספרים טבעיים: נתון מספר טבעי \( N \), ואנחנו רוצים למצוא מספרים ראשוניים \( p_{1},p_{2},\dots,p_{k} \) כך ש-\( N=p_{1}p_{2}\cdots p_{k} \). הסיבה התיאורטית לכך שאנחנו רוצים למצוא משהו כזה היא שיש כל מני דברים שיותר קל לעשות על מספרים כשאנחנו יודעים את הפירוק לגורמים שלהם; הסיבה הפרקטית היא שיש שיטות הצפנה שמסתמכות על כך שבהינתן \( N \), אנחנו דווקא לא יודעים מה הפירוק לגורמים של \( N \), כי מי שכן יודע יכול לפצח את ההצפנה. במילים אחרות, יש הסתמכות על כך שבעיית הפירוק לגורמים היא בעיה קשה מבחינה חישובית.

פירוק לגורמים היא בעיה עם היסטוריה מפוארת שמתמטיקאים דגולים מכל הדורות התעסקו איתה. היסטוריה כזו היא עניין לפוסט נפרד; אבל אני מקווה שדי ברור שלא מדובר על בעיה זניחה אלא על בעיה מעניינת ומרכזית במתמטיקה. קיימים אלגוריתמים מאוד מאוד מתוחכמים שפותרים אותה בימינו, אבל הם לא יעילים מבחינה חישובית. הם אמנם מצליחים לפרק לגורמים מספרים גדולים מאוד, אבל זה עדיין לא מספיק כדי לרסק שיטת הצפנה כמו RSA. בשל כך, כאשר פיטר שור הציג בשנת 1994 אלגוריתם פירוק לגורמים קוונטי, זו הייתה סנסציה: אחת מהבעיות החישוביות המפורסמות ביותר נפתרת על ידי מודל חישוב לא קלאסי! על פניו, זה מצביע על כך שהמודל הקוונטי חזק בצורה מהותית יותר מהמודל הקלאסי. עם זאת, חשוב לי לציין שפירוק לגורמים אינה מה שנקרא בעיה NP-שלמה (או ליתר דיוק - אם היא כזו, אנחנו לא יודעים איך להוכיח את זה). זה אומר שחישוב קוונטי לאו דווקא פותר כל בעיה ב-NP. זה כן אומר שחישוב קוונטי פותר את מה שהיא כנראה הבעיה החישובית המפורסמת ביותר שאיננו יודעים על שייכות שלה ל-P (או ליתר דיוק, ל-BPP - לחישוב יעיל הסתברותי).

אז איך האלגוריתם של שור עובד?

אם חשבתם (או שמעתם ממישהו) שהוא מקבל קלט \( N \), עובד עובד עובד ואז מבצע מדידה ומוציא את רשימת הגורמים של \( N \) - תשכחו מזה. באופן שאולי קצת מפתיע אנשים שלא בקיאים בפרטים, האלגוריתם של שור בכלל לא מתעסק עם פירוק לגורמים של \( N \). הוא מתעסק עם שאלה אחרת: בהינתן מספר \( a \), מה הסדר של \( a \) מודולו \( N \), כלומר מהו \( 0<r \) המינימלי המקיים \( a^{r}\equiv_{N}1 \) (הסימון \( \equiv_{N} \) הוא הדרך שלי לסמן שקילות מודולו \( N \), מה שלרוב מסומן כ-\( a^{r}\equiv1\left(\mbox{mod }N\right) \); אני מוצא שהסימון שלי חוסך לי כתיבה מיותרת). כבר לפני זמנו של שור ידעו שפתרון לבעיה הזו גורר פתרון לבעיית הפירוק לגורמים - זו תוצאה “קלאסית” בתורת המספרים שהיא הדבר הראשון שאציג (מי שלא מתעניין ברדוקציה הזו יכול לדלג מעליה ולהגיע לחלקים הקוונטיים).

הרעיון הבסיסי של שור הוא זה: בואו נגדיר פונקציה \( f \) באופן הבא: \( f\left(x\right)=a^{x}\left(\mbox{mod }N\right) \). אם מתקיים \( f\left(x\right)=f\left(y\right) \), זה אומר ש-\( a^{x}\equiv_{N}a^{y} \), כלומר \( a^{x-y}\equiv_{N}1 \), ולא קשה לראות שזה אומר ש-\( r \) מחלק את \( x-y \), כלומר \( x=y+ir \) עבור \( i \) שלם כלשהו. גם ההפך כמובן נכון: \( f\left(x+ir\right)=f\left(x\right) \) לכל \( i \) שלם. קיבלנו ש-\( f \) היא פונקציה מחזורית עם מחזור \( r \). המטרה של שור היא לגלות את המחזור הזה.

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

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

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

פרק ראשון, ובו יסופר על מציאת סדרים ופירוק לגורמים

אז יש לנו \( N \) ואנחנו רוצים לפרק אותו לגורמים. האבחנה הראשונה היא שמספיק לנו למצוא מספר כלשהו \( 1<a<N \) שמחלק את \( N \). אם אנחנו יודעים לעשות את זה לכל \( N \) בזמן יעיל, פתרנו את בעיית הפירוק לגורמים. למה? כי עכשיו כל מה שנשאר לעשות הוא לפרק את \( a \) לגורמים ואת \( \frac{N}{a} \) לגורמים (או, במקרה שהם ראשוניים, לזהות את זה; אבל בדיקת ראשוניות היא עניין קל). מכיוון של-\( N \) יש לכל היותר \( \lg N \) גורמים ראשוניים, מספר ההפעלות הכולל של אלגוריתם-מציאת-המחלק שיידרש מאיתנו הוא נמוך.

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

כעת, הימור בטוח על \( a \) כזה שהוא לא זר ל-\( N \) יכול להתקבל אם הצלחנו למצוא שורש לא טריוויאלי של 1 מודולו \( N \). שורש “טריוויאלי” הוא \( 1 \) או \( -1 \), כשחושבים עליהם בתור איברים ב-\( \mathbb{Z}_{N} \) - בבירור כשמעלים אותם בריבוע מקבלים 1, וגם אם \( N \) ראשוני הם עדיין היו שורשים של 1. אבל כש-\( N \) אינו ראשוני יש יותר שורשים של 1 מאשר שני אלו. נניח ש-\( Y \) הוא שורש כזה, כלומר \( Y^{2}\equiv_{N}1 \) אבל \( Y\not\equiv_{N}1,-1 \), כלומר אפשר לבחור \( 1<Y<N-1 \). מה זה אומר? ש-\( N|Y^{2}-1=\left(Y-1\right)\left(Y+1\right) \). עכשיו, קחו גורם ראשוני \( p|N \) כלשהו, אז \( p|\left(Y-1\right)\left(Y+1\right) \). תכונה מהותית של ראשוניים היא שאם הם מחלקים מכפלה, אז הם מחלקים את אחד המוכפלים, כלומר \( p|Y-1 \) או \( p|Y+1 \). אני רוצה לטעון שקיים לפחות ראשוני אחד כך ש-\( p|Y-1 \), אחרת היינו מקבלים ש-\( N|Y+1 \), בסתירה לכך ש-\( 1<Y<N-1 \).

מסקנה מכל זה: אם \( Y \) הוא שורש לא טריוויאלי של 1, אז \( Y-1 \) לא זר ל-\( N \). לכן כדי לפרק את \( N \) לגורמים, מספיק לנו לדעת למצוא שורש לא טריוויאלי של 1 מודולו \( N \).

איך מציאת סדר קשורה לכל זה?

ובכן, קחו \( 1<A<N-1 \) אקראי כלשהו. אם נמצא \( r \) כלשהו כך ש-\( A^{r}\equiv_{N}1 \), וגם \( r \) זוגי, וגם \( A^{\frac{r}{2}}\not\equiv_{N}1,-1 \) אז שיחקנו אותה: \( Y=A^{\frac{r}{2}} \) הוא השורש הלא טריוויאלי שאנחנו מחפשים. תכף אני הולך לשכנע אתכם שיש הרבה \( A \)-ים שמקיימים את התכונה הזו, אז מספיק לנו לבחור \( A \) אקראי ואז למצוא \( r \) כך ש-\( A^{r}\equiv_{N}1 \). אין הכרח ש-\( r \) יהיה הסדר של \( A \), אבל מה שקל לנו למצוא עם השיטה של שור הוא את הסדר, כי הפונקציה \( f \) שהגדרנו קודם תהיה בעלת מחזור שהוא בדיוק הסדר.

אז רק נשאר לנו להשתכנע שיש הרבה \( A \)-ים מתאימים ונוכל לסיים את החלק הקלאסי של הפוסט ולעבור לקוונטים. בשביל מה שיקרה בהמשך אני אניח שאתם מכירים קצת תורת מספרים בסיסית בפרט, אתם מכירים את משפט השאריות הסיני. כדי להבין את העיקרון, בואו נתחיל מהמקרה שבו \( N=pq \) עם \( p,q \) ראשוניים אי זוגיים. אנחנו מגרילים \( A\in\mathbb{Z}_{N}^{*} \) ורוצים להבין אותו (למה אני יכול להניח שהוא ב-\( \mathbb{Z}_{N}^{*} \), כלומר זר ל-\( N \)? כי אפשר לבדוק את זה בקלות, ואם זה לא קורה - ניצחנו ומצאנו גורם של \( N \)). עכשיו, ממשפט השאריות הסיני אנחנו יודעים ש- \( \mathbb{Z}_{N}^{*}\cong\mathbb{Z}_{p}^{*}\times\mathbb{Z}_{q}^{*} \) ולכן מספיק לדבר על זוגות \( \left(Y,Z\right)\in\mathbb{Z}_{p}^{*}\times\mathbb{Z}_{q}^{*} \). הניתוח עבורם יהיה קל יותר מכיוון ש-\( \mathbb{Z}_{p},\mathbb{Z}_{q} \) הם שדות. להגריל \( A\in\mathbb{Z}_{N}^{*} \) באקראי זה אותו הדבר כמו להגריל את הזוג \( \left(Y,Z\right) \) שמותאם לו על ידי האיזומורפיזם.

אם \( r_{Y},r_{Z} \) הם הסדרים של \( Y,Z \) מה יהיה \( r \), הסדר של ה-\( A \) שמתאים להם? מכיוון שאם \( A^{s}=1 \) עבור \( s>0 \) כלשהו אז \( r \) מחלק את \( s \), ומכיוון שכל כפולה משותפת של \( r_{Y},r_{Z} \) היא \( s \) שכזה, אז ברור ש-\( r \) מחלק את כל הכפולות המשותפות של \( r_{Y},r_{Z} \). מצד שני, גם ברור ש-\( r_{Y}|r \) ו-\( r_{Z}|r \) ולכן הכפולה המשותפת המינימלית שלהם מחלק את \( r \). המסקנה היא ש-\( r=\mbox{lcm}\left(r_{Y},r_{Z}\right) \).

עכשיו הטענה המרכזית שלי: כדי שיתקיימו שני הדברים שאני רוצה - ש-\( r \) יהיה זוגי וש-\( A^{\frac{r}{2}} \) יהיה שורש לא טריוויאלי של 1 - מספיק שיתקיים הדבר הבא: שהחזקה הגבוהה ביותר של 2 שמחלקת את \( r_{Y} \) תהיה שונה מזו שמחלקת את \( r_{Z} \). פורמלית, אפשר לכתוב \( r_{Y}=2^{k}c \) ו-\( r_{Z}=2^{t}d \) כאשר \( c,d \) הם אי זוגיים; אני טוען שמספיק לדרוש \( k\ne t \) כדי שמה שאני רוצה שיקרה, אכן יקרה. ואני גם טוען שזה יקרה בהסתברות \( \frac{3}{4} \) לפחות, אבל את זה נראה עוד מעט.

כדי להבין למה זה קורה, קודם כל שימו לב לכך ש-\( r=2^{\max\left\{ k,t\right\} }\mbox{lcm}\left(c,d\right) \) - זה נובע מהגדרת ה-lcm. כמובן שאם \( k\ne t \) אז \( \max\left\{ k,t\right\} \ge1 \) ולכן \( r \) יהיה זוגי. כמו כן, בואו נניח ש-\( k<t \); זה אומר ש-\( r=2^{t}\mbox{lcm}\left(c,d\right) \) ולכן \( r_{Y}=2^{k}c|2^{t-1}\mbox{lcm}\left(c,d\right)=\frac{r}{2} \). מכאן אנו מקבלים ש-\( A^{\frac{r}{2}}\mapsto\left(Y^{\frac{r}{2}},Z^{\frac{r}{2}}\right)=\left(1,Z^{\frac{r}{2}}\right) \) וזה מספיק כדי להוכיח לנו ש-\( A^{\frac{r}{2}}\ne-1 \), שכן \( -1\mapsto\left(-1,-1\right) \) (וכמובן ש-\( A^{\frac{r}{2}}\ne1 \) כי זה עומד בסתירה לכך ש-\( r \) הוא הסדר של \( A \)).

מה שנשאר לנו הוא לנסות ולהבין מה ההסתברות לכך שעבור איברים שנבחר באקראי מ-\( \mathbb{Z}_{p}^{*} \) ו-\( \mathbb{Z}_{q}^{*} \) נקבל \( k=t \). לצורך כך די אם נוכיח שקיים איזה שהוא \( k_{0} \) כך שההסתברות שנקבל עבור \( r_{Y}=2^{k}c \) ש-\( k\ge k_{0} \) היא בדיוק \( \frac{1}{2} \). זה אומר שלא משנה מהו \( t \): אם \( t<k_{0} \) אז ההסתברות שנקבל \( k<k_{0} \) היא \( \frac{1}{2} \) ולכן ההסתברות שנקבל \( k=t \) חסומה על ידי \( \frac{1}{2} \); ובדומה גם אם \( t\ge k_{0} \).

כדי להוכיח את הטענה הזו, צריך להבין קצת יותר את המבנה של \( \mathbb{Z}_{p}^{*} \). לא אוכיח זאת כרגע (זה משפט מעניין ולא טריוויאלי), אבל זו חבורה ציקלית. נסמן את היוצר שלה ב-\( g \), אז \( g \) הוא איבר מסדר \( p-1 \), ולהגריל איבר ב-\( \mathbb{Z}_{p}^{*} \) זה בעצם להגריל \( 1<d<p-1 \) ולקבל את האיבר \( g^{d} \).

כעת, בואו נבחר את \( k_{0} \) להיות המעריך של החזקה הגדולה ביותר של 2 שמחלקת את סדר החבורה, כלומר את \( p-1 \) (כלומר \( p-1 \) היא \( 2^{k_{0}} \) כפול משהו אי זוגי). נתבונן באיבר \( g^{d} \). אני טוען שאם \( d \) אי זוגי, אז הסדר של \( g^{d} \) מתחלק על ידי \( 2^{k_{0}} \), ואם \( d \) זוגי אז הסדר של \( g^{d} \) אינו מתחלק על ידי \( 2^{k_{0}} \), מה שמוכיח את הטענה שלנו (כי בין 1 ל-\( p-1 \) יש אותו מספר של זוגיים ואי-זוגיים).

בכל אחד מהמקרים, נסמן ב-\( e \) את הסדר של \( g^{d} \), כלומר \( \left(g^{d}\right)^{e}=1 \), או \( g^{de}=1 \). מכיוון שהסדר של \( g \) הוא \( p-1 \), נובע מכך ש-\( p-1|de \), ולכן \( 2^{k_{0}}|de \). אם \( d \) אי זוגי, אז כל ה-\( 2 \)-ים בביטוי \( de \) מגיעים מ-\( e \) ולכן \( 2^{k_{0}}|e \) - זה היה קל. לטפל במקרה שבו \( d \) זוגי יהיה טיפה יותר קשה.

אם \( d \) זוגי, ננצל את זה שאפשר לחלק אותו ב-2 ונכתוב: \( \left(g^{d}\right)^{\frac{p-1}{2}}=\left(g^{p-1}\right)^{\frac{d}{2}}=1^{\frac{d}{2}}=1 \). על כן, הסדר של \( g^{d} \) מחלק את \( \frac{p-1}{2} \), כלומר החזקה הגבוהה ביותר של 2 ב-\( e \) היא לכל היותר \( 2^{k_{0}-1} \), ומכאן ש-\( e \) לא מתחלק על ידי \( 2^{k_{0}} \). זה מסיים את ההוכחה.

טיפלנו במקרה של \( N=pq \), אבל המקרה הכללי לא קשה בהרבה. במקרה הכללי, \( N=\prod_{i=1}^{m}p_{i}^{k_{i}} \) ולכן נקבל ממשפט השאריות הסיני ש-\( \mathbb{Z}_{N}^{*}\cong\prod\mathbb{Z}_{p_{i}^{k_{i}}}^{*} \). כמקודם, אנחנו מסתכלים על הסדרים של הרכיבים ב-\( \prod\mathbb{Z}_{p_{i}^{k_{i}}}^{*} \) ומספיק לנו שבפירוק של הסדרים הללו לחזקה של 2 ומספר אי זוגי, יהיו שני מספרים עם חזקות שונות של 2. כעת, עבור \( p^{k} \) כלשהו, אנחנו שוב מקבלים ש-\( \mathbb{Z}_{p^{k}}^{*} \) היא ציקלית ולכן הניתוח ההסתברותי הקודם עובד באותה מידה - רק תכתבו \( \varphi\left(p^{k}\right) \) במקום \( p-1 \). נקבל שהאיברים האקראיים ב-\( \mathbb{Z}_{p^{k}}^{*} \) מתחלקים חצי-חצי מבחינת ההתחלקות של הסדר שלהם בחזקה מסויימת של 2, ומכך נובע שההסתברות שב-\( \prod_{i=1}^{m}\mathbb{Z}_{p_{i}^{k_{i}}}^{*} \) כל הרכיבים שנבחר באקראי יהיו בעלי אותה חזקה של 2 בסדר שלהם היא \( \frac{1}{2^{m}} \), ולכן ההסתברות שלנו לבחור איבר “מוצלח” היא \( 1-\frac{1}{2^{m}} \).

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

פרק שני, ובו הקוונטים מתמירים את התמרת פורייה המהירה אפילו עוד יותר מהר

בואו נסכם ונפרמל את מה שעשינו עד כה. נתון לנו מספר טבעי \( N \). אנחנו מסתכלים על החוג \( \mathbb{Z}_{N} \) ומגרילים בו איבר \( A \). אם \( A \) לא זר ל-\( N \), ניצחנו; אלגוריתם אוקלידס יניב לנו גורם משותף של \( N \) ו-\( A \) וסיימנו. אחרת, \( A \) שייך לחבורה הכפלית מודולו \( N \), \( \mathbb{Z}_{N}^{*} \). ככזה, יש לו סדר, כלומר \( r \) חיובי מינימלי כך ש-\( A^{r}=1 \) (החשבון מתבצע ב-\( \mathbb{Z}_{N} \) ואני כבר לא טורח לכתוב \( \equiv \) וכאלה). מה שראינו עד כה היה שאם אני מגריל \( A \), אז בהסתברות טובה \( r \) יהיה זוגי ויתקיים ש-\( A^{\frac{r}{2}}\ne1,-1 \). במקרה הזה, \( A^{\frac{r}{2}}-1 \) יהיה גורם של \( N \). לדוגמה, אם \( N=15 \) ואני מגריל \( A=7 \), אז \( r=4 \), כי החזקות של 7 מודולו 15 הן \( 7,4,13,1 \). כעת, \( 7^{\frac{4}{2}}=7^{2}=4 \) וזה אכן לא שורש טריוויאלי כי \( 4\ne1,-1 \); ואכן, \( 4-1 \) הוא גורם של \( N \). יפה! זה עובד!

האתגר שלנו הפך להיות מציאת הסדר של \( A \), אבל גם זה לא הדבר האמיתי שאנחנו פותרים: מה שהאלגוריתם של שור פותר הוא מציאת מחזור של פונקציה. במקרה שלנו, הפונקציה \( f:\mathbb{Z}_{N}\to\mathbb{Z}_{N} \) מוגדרת על ידי \( f\left(x\right)=A^{x} \). בשל התכונות של הסדר של \( A \), אנחנו מקבלים שלכל \( x\in\mathbb{Z}_{N} \) מתקיים \( f\left(x+r\right)=f\left(x\right) \).

אז המטרה החדשה שלנו היא זו: בהינתן \( f:\mathbb{Z}_{N}\to\mathbb{Z}_{N} \) שקיים עבורה \( r \) מינימלי כך ש-\( f\left(x+r\right)=f\left(x\right) \) לכל \( x\in\mathbb{Z}_{N} \), יש למצוא את \( r \). הרעיון המרכזי כאן הוא שהניתוח של \( f \) יהיה קל משמעותית יותר אם נעבוד לא על \( f \) עצמה אלא על התמרת פורייה הבדידה שלה, שאסמן \( \hat{f} \). את התמרת פורייה הבדידה הצגתי כאן, ומייד אחר כך הראיתי אלגוריתם להתמרת פורייה מהירה. ההגדרה שאני הולך לתת כאן תהיה טיפה שונה מזו שנתתי בפוסטים הללו (וגם בהם השתמשתי בעצם בשתי הגדרות טיפה שונות) כי אני בוחר את ההגדרה שיהיה הכי נוח לעבוד איתה; כל ההגדרות הן פחות או יותר אותו הדבר כך שזה לא משנה.

התמרת פורייה הבדידה של פונקציה \(  f:\mathbb{Z}_{N}\to\mathbb{Z}_{N} \), שאסמן \( \hat{f} \) מתוארת על ידי זוג משוואות: משוואת אנליזה ומשוואת סינתזה. משוואת האנליזה אומרת לנו איך מוצאים את \( \hat{f} \) מתוך \( f \); משוואת הסינתזה אומרת לנו איך לשחזר את \( f \) מתוך \( \hat{f} \). האינטואיציה היא ש-\( \hat{f} \) מתארת הצגה של \( f \) בתור צירוף לינארי של שורשי יחידה. אני משתמש בסימון \( \omega_{N}=e^{\frac{2\pi i}{N}} \) כדי לתאר שורש יחידה פרימיטיבי מסדר \( N \). הפעם נצטרך רק את משוואת האנליזה:

משוואת האנליזה: \( \hat{f}\left(k\right)=\sum_{t=0}^{N-1}f\left(t\right)\omega_{N}^{kt} \)

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

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

\( \sum_{x\in\mathbb{Z}_{N}}f\left(x\right)\left|x\right\rangle \)

לבצע חישוב קוונטי, ולהגיע אל המצב הקוונטי

\( \sum_{x\in\mathbb{Z}_{N}}\hat{f}\left(x\right)\left|x\right\rangle \)

הדרך שבה אפשר לבצע את החישוב הזה ביעילות משתמשת באותו רעיון שבו מחשבים התמרת פורייה בדידה קלאסית ביעילות - גישת ההפרד-ומשול של התמרת פורייה המהירה. בהתמרת פורייה מהירה אנחנו ראשית מניחים ש-\( N \) הוא חזקה של 2, כלומר ניתן לחלק אותו שוב ושוב ב-2 עד שגודלו יהיה 1 (זה לא המצב אצלנו אבל עוד מעט אסביר למה זו לא בעיה). אנחנו מנצלים את התכונה הבאה של שורשי היחידה: \( \left(\omega_{N}^{k}\right)^{2}=\omega_{N/2}^{k} \) על מנת להפוך את החישוב של מקדם פורייה \( \hat{f}\left(k\right) \) לחישוב של שתי התמרות על מרחב מגודל \( \frac{N}{2} \). אחרי כן מאחדים את המידע משתי ההתמרות הללו חזרה לקבלת ההתמרה המקורית; החסכון המרכזי נובע מכך שכל מקדם שמופיע בתת-התמרות משמש אותנו פעמיים.

לא אחזור על הפרטים של הפוסט שהיה לי על התמרת פורייה המהירה אלא אציג את השורה התחתונה. אנחנו חושבים על \( f \) בתור וקטור מגודל \( N \) של מספרים מרוכבים; נסמן ב-\( \mbox{FT}_{N}\left(f\right) \) את הוקטור של \( \hat{f} \). אם \( v \) הוא וקטור מאורך זוגי, נסמן ב-\( v_{low} \) את החצי הראשון שלו וב-\( v_{high} \) את החצי השני, ה-\( v_{even} \) את הוקטור שמתקבל מלקיחת הכניסות במקומות הזוגיים (המקום הראשון הוא 0 ולכן נחשב זוגי) וב-\( v_{odd} \) את הוקטור שמתקבל מלקיחת הכניסות במקומות האי-זוגיים. לסיום, נסמן ב-\( W \) את האופרטור שמתואר על ידי מטריצה אלכסונית שהאלכסון שלה כולל את הכניסות \( \omega^{0},\omega^{1},\dots\omega^{\frac{N}{2}-1} \) (כלומר, האופרטור כופל את הכניסה הראשונה בוקטור ב-\( \omega^{0} \), את השניה ב-\( \omega^{1} \) וכן הלאה). כעת קיבלנו את המשוואות הבאות:

\( \mbox{FT}_{N}\left(f\right)_{low}=\mbox{FT}_{N/2}\left(f_{even}\right)+W\cdot\mbox{FT}_{N/2}\left(f_{odd}\right) \)

\( \mbox{FT}_{N}\left(f\right)_{high}=\mbox{FT}_{N/2}\left(f_{even}\right)-W\cdot\mbox{FT}_{N/2}\left(f_{odd}\right) \)

שתי המשוואות הללו מלמדות על האלגוריתם שלנו: מחשבים את \( \mbox{FT}_{N/2}\left(f_{even}\right) \) ואת \( \mbox{FT}_{N/2}\left(f_{odd}\right) \) ואז משתמשים בהם פעמיים כדי לחשב את \( \mbox{FT}_{N}\left(f\right) \). זו לא בדיוק הצורה שבה הצגתי את ההתמרה המהירה בפוסט הרלוונטי; מן הסתם אני בוחר בדרך ההצגה הזו כי היא תהיה יותר קלה עבורנו בחישוב הקוונטי. מה שמוביל אותנו לשאלה: איך עושים את זה במסגרת חישוב קוונטי?

כזכור, אנחנו מניחים ש-\( N=2^{n} \). אז הרגיסטר הקוונטי שלנו יהיה בעל \( n \) קיוביטים. את \( f_{low} \) ניתן לתאר בתור החלק של ההתמרה עבור הקיוביטים מהצורה \( \left|0\right\rangle \left|x\right\rangle \) (כלומר, כאלו שמתחילים ב-0) ואת \( f_{low} \) באמצעות \( \left|1\right\rangle \left|x^{\prime}\right\rangle \). בדומה, \( f_{even} \) הוא החלק של \( f \) עם הקיוביטים מהצורה \( \left|x\right\rangle \left|0\right\rangle \) ו-\( f_{odd} \) החלק עם הקיוביטים מהצורה \( \left|x\right\rangle \left|1\right\rangle \). הקלט שלנו הוא \( \sum_{x\in\mathbb{Z}_{N}}f\left(x\right)\left|x\right\rangle \). הדבר הראשון שנעשה יהיה להפעיל רקורסיבית את ההתמרה עבור \( \frac{N}{2} \). זה יניב לנו את המצב הקוונטי הבא:

\( \mbox{FT}_{N/2}\left(f_{even}\right)\left|0\right\rangle +\mbox{FT}_{N/2}\left(f_{odd}\right)\left|1\right\rangle \)

השלב הבא הוא כפל של \( \mbox{FT}_{N/2}\left(f_{odd}\right)\left|1\right\rangle \) ב-\( W \). המשמעות של זה היא הפעולה הקוונטית הבאה: \( \left|x\right\rangle \left|1\right\rangle \mapsto\omega^{x} \). איך מבצעים את זה? עוברים ביט-ביט ברגיסטר עד ולא כולל הביט האחרון (ה-\( n \)-י). על הביט ה-\( i \) מפעילים את הפעולה \( \left|0\right\rangle \mapsto\left|0\right\rangle \) ו-\( \left|1\right\rangle \mapsto\omega^{2^{i}}\left|1\right\rangle \), כשהפעולה מותנה בכך שהביט האחרון ברגיסטר יהיה \( \left|1\right\rangle \). קצת מחשבה ותראו שזה פועל, בהנחה שאתם לא רואים את זה כרגע.

אם כן, אנחנו מגיעים אל המצב הקוונטי הבא:

\( \mbox{FT}_{N/2}\left(f_{even}\right)\left|0\right\rangle +W\cdot\mbox{FT}_{N/2}\left(f_{odd}\right)\left|1\right\rangle \)

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

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

\( \mbox{FT}_{N/2}\left(f_{even}\right)\left|0\right\rangle +W\cdot\mbox{FT}_{N/2}\left(f_{odd}\right)\left|0\right\rangle + \)

\( \mbox{FT}_{N/2}\left(f_{even}\right)\left|1\right\rangle -W\cdot\mbox{FT}_{N/2}\left(f_{odd}\right)\left|1\right\rangle \)

וזה שווה ל-

\( \mbox{FT}_{N}\left(f\right)_{low}\left|0\right\rangle +\mbox{FT}_{N}\left(f\right)\left|1\right\rangle \)

זה עדיין לא בדיוק מה שאנחנו רוצים. הרי \( \mbox{FT}_{N}\left(f\right)_{low} \) היא ההתמרה על כל הקיוביטים שהקיוביט הראשון, המשמעותי ביותר שלהם, הוא \( \left|0\right\rangle \). כלומר, מה שקיבלנו הוא את \( \sum\hat{f}\left(0x\right)\left|x\right\rangle \left|0\right\rangle \) במקום את \( \sum\hat{f}\left(0x\right)\left|0x\right\rangle \). אבל למרבה המזל, אין לנו בעיה להחליף קיוביטים, ולכן מעבירים את הקיוביט האחרון להיות הראשון ומזיזים את היתר בהתאם. התוצאה היא בדיוק \( \sum_{x\in\mathbb{Z}_{N}}\hat{f}\left(x\right)\left|x\right\rangle \) המבוקש. מסקנה: אפשר ואפילו לא יותר מדי מסובך לחשב את התמרת פורייה הקוונטית. למעשה, זמן הריצה שלנו הוא מרשים למדי - לוגריתמי ב-\( N \). זה משהו שבלתי אפשרי לבצע בחישוב קלאסי.

אבל איך זה עוזר לנו?

פרק שלישי, ובו מציאת המחזור לפתרון תעזור

נתחיל מלדבר על הפיל באמצע החדר: כל ענייני התמרת הפורייה שלנו היו עבור \( N \) שהוא חזקה של 2, כלומר \( N=2^{n} \) עבור \( n \) כלשהו. זה לא עניין זניח. בלי זה אין אלגוריתם. אבל הרי אנחנו רוצים לפרק לגורמים את \( N \); מן הסתם הוא לא מהצורה \( 2^{n} \)! (באופן כללי קל לבדוק אם מספר הוא מהצורה \( p^{n} \) עבור \( p \) ראשוני ועושים את זה לפני שמנסים לפרק לגורמים).

לכן מה שנעשה הוא התמרת פורייה לא מעל \( \mathbb{Z}_{N} \) אלא מעל \( \mathbb{Z}_{M} \), כאשר \( M \) הוא חזקה של 2 שגדולה מספיק כדי לכסות את \( \mathbb{Z}_{N} \) בצורה שנוחה לנו. פורמלית, נחשב את \( m=\left\lceil 2\lg N\right\rceil \) (כאשר \( \lg \) הוא לוגריתם על בסיס 2) ונגדיר \( M=2^{m} \). שימו לב שכך מתקיים \( N^{2}<M \); נזדקק לזה בהמשך. הרגיסטר הקוונטי שלנו יכלול \( m \) קיוביטים עיקריים, ועוד שלל קיוביטי “זבל” לצורך החישוב. האלגוריתם יפעל כך:

ראשית, נשתמש ב-\( H \) כדי לקבל סופרפוזיציה של כל \( \mathbb{Z}_{M} \), כרגיל. נגיע למצב הקוונטי

\( \sum_{x\in\mathbb{Z}_{M}}\left|x\right\rangle \left|0^{t}\right\rangle \)

כאשר ה-\( 0 \)-ים הם יתר הקיוביטים ה”זבליים” שלנו. עכשיו נחשב את הטרנספורמציה \( \left|x\right\rangle \left|y\right\rangle \mapsto\left|x\right\rangle \left|y\oplus A^{x}\right\rangle \) (כש-\( A^{x} \) הוא מודולו \( N \), כרגיל). נגיע למצב

\( \sum_{x\in\mathbb{Z}_{M}}\left|x\right\rangle \left|y\right\rangle \)

כאשר \( \left|y\right\rangle \) הוא ערך פלט אפשרי ב-\( \mathbb{Z}_{N} \) (אני משמיט את שאר הקיוביטים ה”זבליים”). נמדוד את החלק השני של הרגיסטר ונקרוס לאיזה ערך קונקרטי \( y_{0}\in\mathbb{Z}_{N} \). ה-\( \left|x\right\rangle \)-ים שנישאר איתם הם בדיוק אלו שמקיימים \( A^{x}=y_{0} \). מי אלו? ובכן, אפשר לכתוב \( x=x_{0}+lr \) כאשר \( x_{0} \) הוא החיובי המינימלי מביניהם, ו-\( r \) הוא הסדר של \( A \) - מה שאנחנו מחפשים. \( l \) הוא מספר טבעי כך שעדיין מתקיים \( x<M \), כלומר \( x\le M-1 \), כלומר \( lr\le M-1-x_{0} \), כלומר \( l\le\left\lfloor \frac{M-1-x_{0}}{r}\right\rfloor \). כדי לא להסתרבל, נסמן \( K=\left\lfloor \frac{M-1-x_{0}}{r}\right\rfloor \). כעת, אחרי המדידה אנחנו נמצאים במצב הקוונטי

\( \sum_{l=0}^{K}\left|x_{0}+lr\right\rangle \left|y_{0}\right\rangle \)

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

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

\( \sum_{x\in\mathbb{Z}_{M}}\left(\sum_{l=0}^{K}\omega^{\left(x_{0}+lr\right)x}\right)\left|x\right\rangle \)

ועכשיו מודדים ומקבלים \( x\in\mathbb{Z}_{M} \). נשארנו עם השאלה הגדולה - מה זה ה-\( x \) הזה? מה הוא בעצם אומר? מה אנחנו צריכים לעשות עכשיו? \( x \) איננו \( r \). אם נחשב את \( A^{x} \) לא נקבל שום דבר מועיל. מה הולך פה?

כדי לקבל אינטואיציה על המשמעות של \( x \) הזה ומה עושים איתו בכלל, בואו נתחיל מתיאור של מקרה מנוון ופשוט יחסית. נניח ש-\( r|M \), כלומר שאיכשהו במקרה ממוזל יצא שהסדר של \( A \) שאנו מחפשים מחלק את \( M \), שהוא חזקה של 2 שבחרנו כדי שתהיה מספיק גדולה מ-\( N \). אין ממש סיכוי שזה יקרה (ואפשר תמיד לבדוק אם חזקות של 2 הן סדר של \( A \) גם בלי מחשב קוונטי), אבל כאמור - במקרה הזה דברים מסתדרים נחמד ואז קל להבין את הרעיון.

במקרה הזה, ל-\( x \) שאנחנו מודדים תהיה משמעות מאוד פשוטה. מכיוון ש-\( M \) מתחלק על ידי \( r \), זה אומר שקיים \( c \) כך ש-\( M=rc \). הטענה היא ש-\( x \) הוא פשוט \( ac \) עבור ערך אקראי של \( 0\le a<r \). אם נוכיח שהטענה הזו נכונה, סיימנו: זה אומר ש-\( \frac{x}{M}=\frac{ac}{rc}=\frac{a}{r} \). כלומר, \( \frac{x}{M} \) הוא מספר רציונלי מהצורה \( \frac{a}{r} \). זה אומר שאם ההצגה \( \frac{a}{r} \) היא ההצגה של השבר בתור שבר מצומצם, כלומר ש-\( a \) זר ל-\( r \), אז על ידי חישוב ההצגה המצומצת של \( \frac{x}{M} \) ולקיחת המכנה, מצאנו את \( r \)! כמובן, לא עבור כל ערך של \( a \) זה עובד, אבל לא קשה להוכיח שעבור רובם זה עובד - אפשר להראות שלפחות (אסימפטוטית) \( \frac{r}{\ln r} \) מה-\( a \)-ים האפשריים יהיו זרים ל-\( r \).

אם כן, למה ש-\( x \) יצא \( ac \) אקראי שכזה? ובכן, בואו וניקח \( x\in\mathbb{Z}_{M} \) כלשהו, ונראה מה ההסתברות למדוד אותו - כלומר, מה הערך המוחלט בריבוע של המקדם שלו, או במילים אחרות - מהו \( \left|\sum_{l=0}^{K}\omega^{\left(x_{0}+lr\right)x}\right| \). קודם כל, בואו נפשט קצת את הביטוי הזה:

\( \left|\sum_{l=0}^{K}\omega^{\left(x_{0}+lr\right)x}\right|=\left|\sum_{l=0}^{K}\omega^{x_{0}x}\omega^{lrx}\right|=\left|\omega^{x_{0}x}\right|\cdot\left|\sum_{l=0}^{K}\omega^{lrx}\right|=\left|\sum_{l=0}^{K}\omega^{lrx}\right| \)

כי \( \left|\omega^{x_{0}x}\right|=1 \).

עכשיו בואו ניפטר מה-\( K \). ראשית, \( 0\le x_{0}<r \) (כי אם \( x_{0}\ge r \) גם \( x_{0}-r \) היה מקיים \( A^{x_{0}-r}=y_{0} \), בסתירה למינימליות \( x_{0} \)), ולכן \( \frac{x_{0}+1}{r}\le1 \). מכיוון ש-\( \frac{M}{r}=c \) נקבל ש-\( \left\lfloor \frac{M-\left(x_{0}+1\right)}{r}\right\rfloor =c-1 \). לכן הסכום שאנו מנסים להעריך הוא \( \left|\sum_{l=0}^{c-1}\left(\omega^{rx}\right)^{l}\right| \).

עכשיו, בואו ניזכר קצת במה שקורה עם שורשי יחידה. \( \omega \) הוא שורש יחידה מסדר \( M \), כלומר \( \omega^{M}=1 \). זה אומר ש-\( \sum_{k=0}^{M-1}\omega^{k}=\frac{\omega^{M}-1}{\omega-1}=0 \), על פי נוסחת הסכום של סדרה הנדסית. בדומה, \( \omega^{r} \) הוא שורש יחידה מסדר \( c \) (כי \( \left(\omega^{r}\right)^{c}=\omega^{M}=1 \)) ולכן \( \sum_{k=0}^{c-1}\left(\omega^{r}\right)^{k}=0 \). אבל מה עם \( \omega^{rx} \)?

ובכן, נבדיל בין שני מקרים. במקרה הראשון, \( x \) הוא כפולה של \( c \). על כן, \( rx \) הוא כפולה של \( M \) (כי \( M=rc \)) ולכן \( \omega^{rx}=1 \), ומכאן נקבל \( \left|\sum_{l=0}^{c-1}\left(\omega^{rx}\right)^{l}\right|=c \). המקרה השני הוא זה שבו \( x \) אינו כפולה של \( c \). במקרה זה, לא ייתכן ש-\( rx \) יהיה כפולה של \( M \) (כי אם \( rx=Mt \) אז \( x=\frac{M}{r}t=ct \)) ולכן \( \omega^{rx}\ne1 \) והוא בבירור שורש יחידה מסדר \( c \) ולכן \( \left|\sum_{l=0}^{c-1}\left(\omega^{rx}\right)^{l}\right|=0 \). קיבלנו, אם כן, תוצאה מקסימה ואלגנטית: כל המקדמים של \( x \)-ים שהם כפולות של \( c \) מקבלים אותו ערך, ואילו כל שאר המקדמים נעלמים. עוד פעם יש לנו סוג של התאבכות בונה והורסת!

לרוע המזל, הסיטואציה הוא היא סיטואציה אידאלית, והמציאות מלוכלכת יותר. בואו נעבור, אם כן, לניתוח של המקרה הכללי, בלי שנוכל להניח ש-\( r \) מחלק את \( M \).

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

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

פרק רביעי, ובו בשילוב השברים המשולבים אנחנו מסיימים את ההוכחה

הצגתי בעבר שברים משולבים בבלוג ולכן אני לא הולך להציג את הנושא מחדש בכלל, מה גם שהוא אינו קשור לקוונטים. למי שלא רוצה להתעמק בהם כרגע או לא זוכר מה בדיוק הם עושים, די לדעת ששברים משולבים נותנים לנו סדרה הולכת ומשתפרת של קירובים עבור מספרים (רציונליים ואי רציונליים כאחד). ספציפית, אם \( \alpha \) הוא המספר שאנחנו מנסים לקרב, אנחנו מקבלים סדרה \( \frac{A_{1}}{B_{1}},\frac{A_{2}}{B_{2}},\dots \) של קירובים בעלי התכונה ש-\( \left|\alpha-\frac{A_{n}}{B_{n}}\right|<\frac{1}{B_{n}B_{n+1}} \). הקירובים האלו הם אופטימליים במובן הבא: אם \( \frac{a}{b} \) הוא מספר רציונלי כלשהו כך ש-\( 1\le b\le B_{n} \), אז \( \left|\alpha-\frac{A_{n}}{B_{n}}\right|\le\left|\alpha-\frac{a}{b}\right| \). דהיינו \( \frac{A_{n}}{B_{n}} \) הוא הקירוב הרציונלי הטוב ביותר של \( \alpha \) מבין כל המספרים הרציונליים שהמכנה שלהם הוא לכל היותר \( B_{n} \).

למשפט הזה יש סוג של הופכי נפלא, שאומר שאם מספר רציונלי הוא קירוב ממש טוב של \( \alpha \), אז הוא חייב להתקבל מתוך סדרת הקירובים שהשבר המשולב נותן. פורמלית, אם \( T \) הוא מספר טבעי כלשהו ומתקיים \( \left|\alpha-\frac{a}{b}\right|<\frac{1}{2T^{2}} \) כאשר \( b\le T \), אז נובע ש-\( \frac{a}{b} \) נמצא בסדרת השברים המשולבים של \( \alpha \), ויותר מכך: \( \frac{a}{b} \) הוא המספר הרציונלי היחיד עם \( b\le T \) המקיים \( \left|\alpha-\frac{a}{b}\right|<\frac{1}{2T^{2}} \).

את היחידות הזו אפשר לראות עם טיעון די פשוט: נניח ש-\( \frac{a^{\prime}}{b^{\prime}} \) הוא עוד מספר רציונלי שונה מ-\( \frac{a}{b} \) עם \( b^{\prime}\le T \) המקיים \( \left|\alpha-\frac{a^{\prime}}{b^{\prime}}\right|<\frac{1}{2T^{2}} \), אז נוכל להעריך את ההפרש בין שני הרציונליים הללו ולהגיע לכך שהוא בו זמנית קטן וגדול מדי:

\( \left|\frac{a}{b}-\frac{a^{\prime}}{b^{\prime}}\right|=\left|\left(\frac{a}{b}-\alpha\right)+\left(\alpha-\frac{a^{\prime}}{b^{\prime}}\right)\right|\le\left|\left(\frac{a}{b}-\alpha\right)\right|+\left|\left(\alpha-\frac{a^{\prime}}{b^{\prime}}\right)\right|<\frac{1}{2T^{2}}+\frac{1}{2T^{2}}=\frac{1}{T^{2}} \)

אבל מצד שני

\( \left|\frac{a}{b}-\frac{a^{\prime}}{b^{\prime}}\right|=\left|\frac{ab^{\prime}-a^{\prime}b}{bb^{\prime}}\right|=\frac{\left|ab^{\prime}-a^{\prime}b\right|}{\left|bb^{\prime}\right|}\ge\frac{\left|ab^{\prime}-a^{\prime}b\right|}{T^{2}}\ge\frac{1}{T^{2}} \)

והגענו לסתירה, כך שלא ייתכן ש-\( \frac{a^{\prime}}{b^{\prime}} \) שונה מ-\( \frac{a}{b} \).

כעת, נניח שאכן קיים \( \frac{a}{b} \) עם \( b\le T \) כך ש-\( \left|\alpha-\frac{a}{b}\right|<\frac{1}{2T^{2}} \). אז מובטח לנו שהאלגוריתם ימצא אותו בשלב כלשהו, אבל כמה מהר? בניסוח אחר: נתון ש-\( \left|\alpha-\frac{A_{n}}{B_{n}}\right|<\frac{1}{2T^{2}} \) כך ש-\( B_{n}\le T \) - מהו \( n \) כפונקציה של \( T \)? בשביל זה אני צריך לשלוף לרגע את הנוסחה שבה נעזרים כדי לחשב את \( B_{n} \) מתוך הפיתוח של \( \alpha \) כשבר משולב: \( B_{n}=a_{n}B_{n-1}+B_{n-2} \). זה לא חשוב איך מגיעים אל \( a_{n} \) כרגע, אלא רק שהוא תמיד שלם חיובי. לכן \( B_{n}\ge B_{n-1}+B_{n-2}\ge2B_{n-2} \), וקיבלנו שהערך של \( B_{n} \) קופץ פי 2 אחרי כל זוג איברים, כלומר \( B_{n}\ge2^{\frac{n}{2}} \) (הדבר די דומה לניתוח של קצב הגידול של מספרי פיבונאצ’י שתיארתי פעם בבלוג). מכיוון ש-\( B_{n}\le T \) קיבלנו ש-\( 2^{\frac{n}{2}}\le T \), כלומר \( n\le2\lg T \) - מספר קטן של צעדים, כך שסיבוכיות היא לא הבעיה כאן.

סיימנו עם ההצגה של שברים משולבים ועכשיו אפשר להסביר מה אנחנו עושים באלגוריתם הקוונטי שלנו ולמה. האלגוריתם הוא אותו אלגוריתם שכבר תיארתי. בסופו של דבר אנחנו מקבלים \( x \) כלשהו. אנחנו מחשבים את \( \frac{x}{M} \), ואז מפתחים את \( \frac{x}{M} \) לשבר משולב ומסתכלים על הקירובים שקיבלנו בדרך. התקווה שלנו היא ש-\( \frac{x}{M} \) יהיה ניתן לקירוב מצויין בעזרת שבר ש-\( r \) מופיע במכנה שלו, מה שיבטיח שה-\( r \) הזה יצוץ בתוך הפיתוח של \( \frac{x}{M} \) לשבר משולב ונמצא אותו. כמה מצויין? ובכן, היינו רוצים \( T \) כך ש-\( r\le T \) ומתקיים \( \left|\frac{x}{M}-\frac{a}{r}\right|<\frac{1}{2T^{2}} \) עבור \( a \) כלשהו - כבר ראינו שזה מבטיח ש-\( \frac{a}{r} \) יתקבל די מהר על ידי הפיתוח של \( \frac{x}{M} \) לשבר משולב.

כעת, בואו ניזכר שאנחנו מנסים לפרק לגורמים מספר \( N \), וש-\( r \), הסדר שאנחנו מחפשים, מקיים בהכרח \( r<N \), כך ש-\( N \) הוא מועמד טבעי להיות ה-\( T \) שלנו. אנחנו רוצים, אם כן, שיתקיים \( \left|\frac{x}{M}-\frac{a}{r}\right|<\frac{1}{2N^{2}} \). כעת, מכיוון שבחרנו את \( M \) בצורה כזו שיתקיים \( N^{2}<M \), קיבלנו שכל מה שצריך להוכיח הוא שבהסתברות טובה יתקיים \( \left|\frac{x}{M}-\frac{a}{r}\right|<\frac{1}{2M} \) עם \( a \) זר ל-\( r \) (כי אם \( a \) לא זר ל-\( r \) אז אמנם נגיע אל \( \frac{a}{r} \) אבל המכנה יהיה מחלק כלשהו של \( r \) וזה לא יעזור לנו).

אם כן, אנחנו נכנסים אל הישורת האחרונה של ההוכחה. בואו ננסה להנדס לאחור את הדרישות שלנו ואז נראה מה ההסתברות שהן יתקיימו. ראשית, \( \left|\frac{x}{M}-\frac{a}{r}\right|<\frac{1}{2M} \). אם נכפול את הביטוי הזה ב-\( Mr \) נקבל \( \left|xr-Ma\right|<\frac{r}{2} \). בניסוח אחר, זה אומר שאנחנו רוצים שיתקיים \( xr\mbox{ mod M}<\frac{r}{2} \). זה דומה למה שקרה במקרה ה”מנוון” שבו \( r|M \) וזה גרר ש-\( xr\equiv_{M}0 \); מה שאני אומר הוא שאנחנו לא חייבים לקבל 0 אלא מספיק שנקבל ערך “קטן דיו” (קטן מ-\( \frac{r}{2} \)). הדרישה השניה שלנו מ-\( x \) היא שנקבל ש-\( a \) זר ל-\( r \) בקירוב \( \frac{a}{r} \) של \( \frac{x}{M} \). ההוכחה של הפרטים הללו היא טכנית למדי - הלב של הסיבוך הטכני של ההוכחה - ואני לא הולך להציג אותה כאן. השורה התחתונה היא זו: אפשר להוכיח שיש די הרבה \( x \)-ים שמקיימים בו זמנית את שתי הדרישות - ליתר דיוק, לפחות (אסימפטוטית) \( \frac{r}{\log r} \) מהם. כל מה שנשאר להראות הוא של-\( x \) כזה יש סיכוי סביר להיות מוגרל כשמודדים את הרגיסטר הקוונטי. אפשר להראות שהאמפליטודה (אחרי נרמול) של כל \( x \) כזה היא לפחות \( \frac{1}{\sqrt{r}} \), ולכן ההסתברות שלו לעלות בגורל היא לפחות \( \frac{1}{r} \), ומכאן שבהסתברות \( \frac{1}{\log r} \) האלגוריתם מצליח. זה נראה כמו הסתברות נמוכה, אבל אפשר “לנפח” אותה על ידי מספר חזרות על האלגוריתם, כך שזו לא הבעיה.

אפילוג, ובו דברי סיכום ופרידה

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

התחלנו עם מה שהוא בעצם הסוף - אם אנחנו יודעים למצוא את הסדר של איבר אקראי \( A \) מודולו \( N \), יש לנו סיכוי טוב להצליח לפרק את \( N \) לגורמים. האתגר היה למצוא את הסדר הזה, ולשם כך ביצענו חישוב מקבילי של \( f\left(x\right)=A^{x}\mbox{ mod }N \), שאחריו “קיבצנו” את כל ה-\( x \)-ים שנותנים תוצאה אקראית כלשהי \( y_{0} \) של \( f \). על הוקטור שמתאר את ה-\( x \)-ים הללו (נותן להם 1 וליתר 0) הפעלנו התמרת פורייה קוונטית. שני השלבים הללו - החישוב המקבילי של \( f \) וההתמרה הקוונטית - הם המקום שבו הכוח של תורת הקוונטים עוזר לנו. מה שקורה כאן הוא בהחלט מה שאני קורא לו בלעג “סופר-דופר חישוב מקבילי”, אבל כזה שאת התוצאות שלו אנחנו לא מסוגלים לדעת באופן מפורש, רק לבצע מדידה - ולכן החישוב המקבילי מלכתחילה מיועד להטות את המדידה הזו כדי שתספק לנו מידע על \( r \), גם אם בצורה עקיפה. הצורה העקיפה הזו נראית מוזרה למדי באלגוריתם של שור - בהסתברות טובה, אנחנו מקבלים \( x \) כך ש-\( xr \) “יחסית קרוב” להתחלק ב-\( M \) (שהוא חזקה גדולה של 2 שמהווה חסם מלעיל של \( N \)). מכך נובע ש-\( \left|\frac{x}{M}-\frac{a}{r}\right| \) הוא הפרש קטן מאוד - מה שמבטיח שכאשר אנו מפתחים את \( \frac{x}{M} \) לשבר משולב, אז \( \frac{a}{r} \) יצוץ בדרך. עם קצת מזל, \( a \) יהיה זר ל-\( r \) ואז אפשר יהיה לקרוא את \( r \) מתוך המכנה של השבר שקיבלנו.

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