האלגוריתם של שור

למודול Qiskit in Classrooms הזה, הסטודנטים צריכים סביבת Python פעילה עם החבילות הבאות מותקנות:

• qiskit v2.1.0 או חדש יותר
• qiskit-ibm-runtime v0.40.1 או חדש יותר
• qiskit-aer v0.17.0 או חדש יותר
• qiskit.visualization
• numpy
• pylatexenc

להגדרה והתקנת החבילות שלעיל, ראו את המדריך התקנת Qiskit. כדי להריץ משימות על מחשבי קוונטום אמיתיים, הסטודנטים יצטרכו להגדיר חשבון ב-IBM Quantum® לפי השלבים במדריך הגדרת חשבון IBM Cloud שלך.

מודול זה נבדק והשתמש בשלוש שניות של זמן QPU. זוהי הערכה בלבד. השימוש בפועל שלך עשוי להשתנות.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

מבוא

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

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

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

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

בעיית הפירוק לגורמים

המטרה של בעיית הפירוק לגורמים היא למצוא את הגורמים הראשוניים של מספר $N$. עבור כמה מספרים $N$, זה די קל. לדוגמה, אם $N$ זוגי, אחד מהגורמים הראשוניים שלו יהיה 2. אם $N$ הוא חזקת ראשוני, כלומר $N=p^k$ עבור מספר ראשוני $p$ כלשהו, גם קל יחסית למצוא את $p$: פשוט מקרבים את השורש ה-$k^{\text{th}}$ של $N$ ומחפשים ראשוניים קרובים שיכולים להיות $p$.

אבל היכן מחשבים קלאסיים מתקשים, הוא כאשר $N$ אי-זוגי ואינו חזקת ראשוני. זהו המקרה שאלגוריתם שור מתמודד איתו. האלגוריתם מוצא שני גורמים $p$ ו-$q$ כך ש-$N=pq$. ניתן להפעיל אותו רקורסיבית עד שכל הגורמים ראשוניים. בסעיפים הבאים נראה כיצד מתמודדים עם בעיה זו.

רלוונטיות לאבטחת סייבר

תכניות הצפנה רבות נבנו על בסיס העובדה שפירוק מספרים גדולים לגורמים הוא קשה, כולל אחת הנפוצה כיום, הנקראת RSA. ב-RSA, מפתח ציבורי נוצר על ידי כפל שני מספרים ראשוניים גדולים יחד לקבלת $N = p\cdot q$. לאחר מכן, כל אחד יכול להשתמש במפתח הציבורי הזה להצפנת נתונים. אבל רק מי שיש לו את המפתח הפרטי, $p$ ו-$q$, יכול לפענח את הנתונים.

אם $N$ היה קל לפירוק, אז כל אחד היה מסוגל לקבוע מהם $p$ ו-$q$ ולשבור את ההצפנה. אבל זה לא כך. זוהי בעיה ידועה כקשה במיוחד. למעשה, הגורמים הראשוניים של מספר הנקרא RSA1024, שהוא באורך 1024 ספרות בינאריות ו-309 ספרות עשרוניות, עדיין לא נמצאו, למרות שפרס של $100,000 הוצע לפירוקו עוד ב-1991.

הפתרון של שור

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

חשבון מודולרי

חשבון מודולרי הוא מערכת ספירה שהיא מחזורית, כלומר בעוד שהספירה מתחילה בדרך הרגילה, עם מספרים שלמים 0, 1, 2 וכו', בנקודה מסוימת, לאחר תקופה $N$, הספירה מתחילה מחדש. בואו נראה כיצד זה עובד עם דוגמה. נגיד שהתקופה שלנו היא 5. אז, כשאנחנו סופרים, במקום להגיע ל-5, מתחילים מחדש ב-0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

זה מפני שבעולם "modulo-5", 5 שקול ל-0. אנו אומרים ש-$5\bmod 5 \ = 0$. למעשה, כל כפולות של 5 יהיו שקולות ל-$0\bmod 5$.

בדוק את ההבנה שלך

קרא את השאלה/ות למטה, חשוב על התשובה שלך, ואז לחץ על המשולש לגלות את הפתרון.

השתמש בחשבון מודולרי לפתרון הבעיה הבאה:

אתה יוצא לנסיעת רכבת ארוכה, בין-יבשתית בשעה 8 בבוקר. הנסיעה ברכבת ארוכה 60 שעות. מה השעה כשאתה מגיע?

תשובה:

התקופה היא 24, מכיוון שיש 24 שעות ביום. לכן, ניתן לכתוב בעיה זו בחשבון מודולרי כ:

$(8+60)\text{mod}(24) = 20$

אז, תגיע ליעדך ב-20:00, כלומר בשעה 8 בערב.

$\mathbb{Z}_N$ ו-$\mathbb{Z}_N^*$

לעיתים קרובות שימושי להציג שתי קבוצות, $\mathbb{Z}_N$ ו-$\mathbb{Z}_N^*$. $\mathbb{Z}_N$ היא פשוט קבוצת המספרים שקיימים בעולם "modulo-$N$". לדוגמה, כאשר ספרנו modulo-5, הקבוצה תהיה $\mathbb{Z}_5=\{0,1,2,3,4\}$. דוגמה נוספת: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. ניתן לבצע חיבור וכפל (modulo $N$) על האיברים ב-$\mathbb{Z}_N$, והתוצאה של כל אחת מהפעולות הללו היא גם איבר ב-$\mathbb{Z}_N$, מה שהופך את $\mathbb{Z}_N$ לאובייקט מתמטי הנקרא חוג.

יש תת-קבוצה מיוחדת של $\mathbb{Z}_N$ שמעניינת אותנו במיוחד לאלגוריתם שור. זוהי תת-קבוצת המספרים ב-$\mathbb{Z}_N$ כך שהמחלק המשותף הגדול ביותר בין כל איבר ל-$N$ הוא 1, כלומר כל איבר "קו-ראשוני" ל-$N$. אם ניקח את קבוצת המספרים הללו יחד עם פעולת הכפל המודולרי, אז זה יוצר אובייקט מתמטי אחר, הנקרא חבורה. אנו קוראים לחבורה זו $\mathbb{Z}_N^*$. מתברר שעם $\mathbb{Z}_N^*$ (וחבורות סופיות בכלל), אם ניקח כל איבר $a \in \mathbb{Z}_N^*$, ונכפול את $a$ בעצמו שוב ושוב, תמיד בסופו של דבר נקבל את המספר $1$. המספר המינימלי של פעמים שצריך לכפול את $a$ בעצמו כדי לקבל $1$ נקרא הסדר של $a$. עובדה זו תהיה חשובה מאוד לדיון שלנו על כיצד לפרק מספרים למטה.

בדוק את ההבנה שלך

קרא את השאלה/ות למטה, חשוב על התשובה שלך, ואז לחץ על המשולש לגלות את הפתרון.

מהו $\mathbb{Z}_{15}^*$?

תשובה:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

אנו השמטנו את המספרים הבאים:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

מהו הסדר של כל אחד מהאיברים ב-$\mathbb{Z}_{15}^*$?

תשובה:

הסדר $r$ הוא המספר הנמוך ביותר כך ש-$a^r\text{mod}(15)=1$ עבור כל איבר $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

שים לב שאמנם הצלחנו למצוא את הסדר של המספרים ב-$\mathbb{Z}_{15}^*$, אבל זו אינה משימה קלה בכלל, עבור $N$ גדול יותר. זהו לב ליבה של בעיית הפירוק לגורמים ולכן אנחנו צריכים מחשב קוונטי. נראה למה ככל שנתקדם בשאר המחברת.

יישום חשבון מודולרי על בעיית הפירוק לגורמים

המפתח למציאת גורמים $p$ ו-$q$ כך ש-$N=pq$ נובע ממציאת מספר שלם אחר $x$ כך ש

$x^2 \equiv 1 \bmod N$ וגם $x \not\equiv \pm 1 \bmod N.$

איך מציאת $x$ עוזרת לנו למצוא את הגורמים $p$ ו-$q$? בואו נעבור על ההנמקה עכשיו. מכיוון ש-$x^2 \equiv 1 \bmod N$, זה אומר ש-$x^2 - 1 \equiv 0 \bmod N$. במילים אחרות, $x^2 - 1$ הוא כפולה של $N$. אז, עבור מספר שלם $l$ כלשהו,

$x^2 - 1 = l N$

ניתן לפרק את $x^2 - 1$ לקבל:

$(x+1)(x-1) = l N$

מהנחות הפתיחה שלנו אנחנו יודעים ש-$x \not\equiv \pm 1 \bmod N$, לכן $N$ אינו מחלק באופן שווה לא את $x+1$ ולא את $x-1$. אז, שני הגורמים של $N$, $p$ ו-$q$ חייבים להתחלק כל אחד ב-$x-1$ וב-$x+1$. או שe $p$ הוא גורם של $x-1$ ו-$q$ הוא גורם של $x+1$, או להפך. לכן, אם נחשב את המחלקים המשותפים הגדולים ביותר (GCDs) בין $N$ לבין $x-1$ וגם $x+1$, זה ייתן לנו את הגורמים $p$ ו-$q$. חישוב ה-GCD בין שני מספרים הוא משימה קלה קלאסית שניתן לבצע, לדוגמה, באמצעות אלגוריתם אוקלידס.

בדוק את ההבנה שלך

קרא את השאלה/ות למטה, חשוב על התשובה שלך, ואז לחץ על המשולש לגלות את הפתרון.

אולי יהיה קשה להבין כל שלב בהיגיון לעיל, אז נסה לעבור על דוגמה. השתמש ב-$N=15$ ו-$x=11$. ראשית, אמת ש-$x^2 \equiv 1 \text{mod}(N)$ ו-$x \not\equiv \pm 1 \bmod N$. לאחר מכן המשך לאמת כל שלב. לבסוף, חשב $\text{GCD}(11\pm1,15)$ ואמת שהם הגורמים של $15$.

תשובה:

$11^2 = 121$, שהוא $15*8 + 1$, לכן $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, שאינו שקול ל-$0\bmod 15$. $\checkmark$

$11 + 1 = 12$, שאינו שקול ל-$0\bmod 15$. $\checkmark$

כעת, אנחנו יודעים ש-$(x+1)(x-1) = l N$ עבור מספר שלם $l$ כלשהו. זה מאומת כשמציבים $x$ ו-$N$: $(12)(10) = l 15$ כאשר $l = 8$. $\checkmark$

כעת, עלינו לחשב $\text{GCD}(12,15)$ ו-$\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

אז, מצאנו את הגורמים של $15$!

האלגוריתם

כעת לאחר שראינו כיצד מציאת מספר שלם $x$ כך ש-$x^2 \equiv 1\bmod N$ עוזרת לנו לפרק את $N$ לגורמים, נוכל לעבור על אלגוריתם שור. הוא בעצם מסתכם במציאת $x$:

1. בחר מספר שלם אקראי בחר מספר שלם אקראי $a$ כך ש-$1 < a < N$.

• חשב $\text{GCD}(a, N)$ קלאסית.
  • אם $\text{GCD}(a, N) > 1$, כבר מצאת גורם. עצור.
  • אחרת, המשך.

2. מצא סדר $r$ של $a$ modulo $N$ מצא את המספר השלם החיובי הקטן ביותר $r$ המקיים $a^r \equiv 1 \pmod N$.

3. בדוק אם הסדר זוגי

• אם $r$ אי-זוגי, חזור לשלב 1 ובחר $a$ חדש.
• אם $r$ זוגי, המשך לשלב 4.

4. חשב $x = a^{r/2} \bmod N$

• בדוק ש-$x \not\equiv 1 \pmod N$ וגם $x \not\equiv -1 \pmod N$.
  • אם $x \equiv \pm 1 \pmod N$, חזור לשלב 1 ובחר $a$ חדש.
• אחרת, חשב את ה-GCDs כדי לחלץ את הגורמים:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

אלה יהיו גורמים לא-טריוויאליים של $N$.

5. פרק לגורמים רקורסיבית אם נדרש

• אם $p$ ו/או $q$ אינם ראשוניים, החל את האלגוריתם רקורסיבית לפירוקם לחלוטין.
• ברגע שכל הגורמים ראשוניים, הפירוק הושלם.

בהתבסס על הליך זה, אולי לא ברור למה נדרש מחשב קוונטי להשלמת המשימה. הוא הכרחי מפני שהשלב 2, מציאת הסדר של $a$ modulo $N$, הוא קלאסית בעיה קשה מאוד. המורכבות גדלה אקספוננציאלית במספר $N$. אבל עם מחשב קוונטי, אנחנו רק צריכים להשתמש באמידת פאזה קוונטית (Quantum Phase Estimation) כדי לפתור אותו. השלב 4, מציאת ה-GCD של שני מספרים שלמים, הוא למעשה דבר קל למדי לביצוע קלאסי. לכן, השלב היחיד שבאמת צריך את כוחו של מחשב קוונטי הוא שלב מציאת הסדר. אנחנו אומרים שבעיית הפירוק "מצטמצמת" לבעיית מציאת הסדר.

החלק הקשה: מציאת הסדר

כעת, נעבור על כיצד נוכל להשתמש במחשב קוונטי למציאת הסדר. ראשית, בואו נבהיר מה אנחנו מתכוונים ב"סדר". כמובן, כבר אמרתי לכם מה משמעות הסדר מתמטית: זהו המספר השלם הראשון השונה מאפס $r$ כך ש-$a^r = 1 \pmod N.$ אבל בואו נראה אם נוכל לקבל קצת יותר אינטואיציה למושג זה.

עבור $N$ קטן מספיק, אנחנו יכולים פשוט לקבוע את הסדר על ידי חישוב כל חזקה של $a$, לקיחת modulus $N$ של אותו מספר, ואז עצירה כשנמצא את החזקה $r$ שמקיימת $a^r = 1 \text{mod}(N)$. זה מה שעשינו עם הדוגמה שלנו, $N=15$, לעיל. בואו נסתכל על כמה גרפים של החזקות המודולריות הללו עבור ערכי דגימה של $a$ ו-$N$:

שמים לב למשהו? אלה פונקציות מחזוריות! והסדר $r$ זהה לתקופה! לכן, מציאת הסדר שקולה למציאת התקופה.

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

באמידת פאזה קוונטית (QPE), אנחנו מתחילים עם אוניטרי $U$ ומצב עצמי של אותו אוניטרי $|\psi\rangle$. לאחר מכן, אנחנו משתמשים ב-QPE לקירוב הערך העצמי המתאים, שמאחר שהאופרטור הוא אוניטרי, יהיה בצורה $e^{2\pi i \theta}$. לכן, מציאת הערך העצמי שקולה למציאת הערך של $\theta$ בפונקציה המחזורית. ה-Circuit נראה כך:

כאשר מספר ה-Qubit הבקרה (ה-$m$ Qubit העליונים באיור לעיל) קובע את דיוק הקירוב.

באלגוריתם שור, אנחנו משתמשים ב-QPE על אופרטור האוניטרי $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

כאן, $|y\rangle$ מציין מצב בסיס חישובי של הרגיסטר הרב-Qubit, כאשר הערך הבינארי של ה-Qubit תואם למספר השלם $y$. לדוגמה, אם $N=15$ ו-$y = 2$, אז $|y\rangle$ מיוצג על ידי מצב הבסיס הארבעה-Qubit $|0010\rangle$, מכיוון שנדרשים ארבעה Qubit לקידוד מספרים עד 15. (אם מושג זה אינו מוכר, ראה את מודול Qiskit in classrooms המבואי לסקירה על קידוד בינארי של מצבים קוונטיים.)

כעת, עלינו לברר מצב עצמי של אוניטרי זה. אם נתחיל במצב $|1\rangle$, נוכל לראות שכל הפעלה עוקבת של $U$ תכפיל את מצב הרגיסטר שלנו ב-$a \pmod N$, ואחרי $r$ הפעלות נגיע חזרה למצב $|1\rangle$. לדוגמה עם $a = 3$ ו-$N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

לכן, סופרפוזיציות של המצבים במחזור הזה ($|\psi_j\rangle$) בצורה:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

הן כולן מצבים עצמיים של $M_a$. (יש מצבים עצמיים נוספים מעבר לאלה. אבל אנחנו מתעניינים רק באלה שבצורה לעיל.)

בדוק את ההבנה שלך

קרא את השאלה/ות למטה, חשוב על התשובה שלך, ואז לחץ על המשולש לגלות את הפתרון.

מצא מצב עצמי של האוניטרי המתאים ל-$a=2$ ו-$N = 15$.

תשובה:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

אז, הסדר $r=4$. המצבים העצמיים שאנחנו מתעניינים בהם יהיו סופרפוזיציה שווה של כל המצבים שעברו עליהם לעיל, עם פאזות שונות:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

נניח שהיינו מסוגלים לאתחל את מצב ה-Qubit שלנו לאחד מהמצבים העצמיים האלה (ספוילר — אנחנו לא. או לפחות לא בקלות. נסביר למה ומה ניתן לעשות במקום זאת בקרוב). אז יכולנו להשתמש ב-QPE לאמידת הערך העצמי המתאים, $\omega_j = e^{2 \pi i \theta_j}$ כאשר $\theta_j = \frac{j}{r}$. לאחר מכן, נוכל לקבוע את הסדר $r$ מהמשוואה הפשוטה:

$r = \frac{j}{\theta_j}.$

אבל זכרו, אמרתי ש-QPE מעריך את $\theta_j$ — הוא לא נותן לנו ערך מדויק. אנחנו צריכים שהאומדן יהיה טוב מספיק כדי להבחין בין $r$ ל-$r+1$. ככל שיש יותר Qubit בקרה $m$, כך האומדן יהיה טוב יותר. בתרגילים שבסוף השיעור, תתבקשו לקבוע את ה-$m$ המינימלי הנדרש לפירוק מספר $N$.

כעת, עלינו ליישב בעיה. כל ההסבר לעיל על כיצד למצוא $r$ מתחיל בהכנת המצב העצמי $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. אבל אנחנו לא יודעים כיצד לעשות זאת מבלי לדעת כבר מהו $r$. ההיגיון מעגלי. אנחנו צריכים דרך לאמוד את הערך העצמי מבלי לאתחל את המצב העצמי.

במקום להתחיל עם מצב עצמי של $M_a$, אנחנו יכולים להכין את המצב הראשוני למצב ה-$n$-Qubit המתאים ל-$|1\rangle$ בבינארי (כלומר, $|000...01\rangle$). אמנם מצב זה עצמו ברור שאינו מצב עצמי של $M_a$, אבל הוא סופרפוזיציה על כל המצבים העצמיים $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

בדוק את ההבנה שלך

קרא את השאלה/ות למטה, חשוב על התשובה שלך, ואז לחץ על המשולש לגלות את הפתרון.

אמת ש-$|1\rangle$ שקול לסופרפוזיציה על המצבים העצמיים שמצאת עבור $N=15$ ו-$a=2$ בשאלת הבדיקה הקודמת.

תשובה:

ארבעת המצבים העצמיים היו:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

אז,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

כיצד זה מאפשר לנו למצוא את הסדר $r$? מאחר שמצב ההתחלה הוא סופרפוזיציה על כל המצבים העצמיים בצורה המפורטת לעיל, אלגוריתם ה-QPE מעריך בו-זמנית כל אחד מ-$\theta_k$ המתאים למצבים העצמיים הללו. לכן, המדידה של ה-$m$ Qubit הבקרה בסוף תניב קירוב לערך $k/r$ כאשר $k \in \{0,1,2,...,r-1\}$ הוא אחד מהערכים העצמיים שנבחר אקראית. אם נחזור על ה-Circuit הזה כמה פעמים ונקבל כמה דגימות עם ערכי $k$ שונים, נוכל במהרה להסיק את $r$.

מימוש ב-Qiskit

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

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

1. מיפוי הבעיה ל-Circuit קוונטי
2. אופטימיזציה של ה-Circuit להרצה על חומרה קוונטית
3. הרצת ה-Circuit על המחשב הקוונטי
4. עיבוד לאחר המדידה

1. מיפוי

בואו נפרק את $N=15$, ונבחר ב-$a=2$ כמספר השלם ה-co-prime שלנו.

ראשית, צריך לבנות את ה-Circuit שיממש את האוניטרי של הכפל המודולרי, $M_a$. זה בעצם החלק הכי מסובך בכל המימוש, ויכול להיות יקר מחשובית מאוד, תלוי באיך עושים את זה. בשביל זה, נרמה קצת: אנחנו יודעים שמתחילים במצב $|1\rangle$, ומשאלת הביניים הקודמת,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

אז נבנה אוניטרי שעושה את הפעולות הנכונות על ארבעת המצבים האלה, אבל משאיר את כל שאר המצבים ללא שינוי. זו הרמאות מפני שאנחנו משתמשים בידע שלנו על הסדר של $2\bmod 15$ כדי לפשט את האוניטרי. אם היינו ממש מנסים לפרק מספר שהגורמים שלו לא ידועים לנו, לא היינו יכולים לעשות את זה.

בדוק את ההבנה שלך

קרא את השאלות למטה, חשוב על התשובה, ואז לחץ על המשולש לגילוי הפתרון.

עם הידע שלך על האופן שבו האופרטור $M_2$ ממיר את המצבים לעיל, בנה את האופרטור מסדרת שערי SWAP, שמחליפים את המצבים של שני Qubits. (רמז: כתיבת כל מצב $|i\rangle$ בבינארי תעזור.)

תשובה:

בואו נכתוב מחדש את פעולת $M_2$ על המצבים בבינארי:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

כל אחת מהפעולות האלה ניתנת לביצוע עם SWAP פשוט. $M_2|0001\rangle$ מתקבל על ידי החלפת המצבים של Qubit $0$ ו-$1$. $M_2|0010\rangle$ מתקבל על ידי החלפת המצבים של Qubit $1$ ו-$2$. וכן הלאה. אז אפשר לפרק את המטריצה $M_2$ לסדרת שערי SWAP הבאה:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

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

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

עכשיו אפשר לקודד את ה-Circuit שמקביל לאופרטור הזה ב-Qiskit.

ראשית, מייבאים את החבילות הנחוצות:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

לאחר מכן, בונים את האופרטור $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

אלגוריתם QPE משתמש ב-Gate מסוג controlled-$U$. אז עכשיו שיש לנו Circuit של $M_2$, צריך להפוך אותו ל-Circuit של controlled-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

עכשיו יש לנו את ה-Gate controlled-$U$. אבל כדי להריץ את אלגוריתם אמידת הפאזה הקוונטית, נצטרך controlled-$U^2$, controlled-$U^4$, עד controlled-$U^{2^{m-1}}$, כש-$m$ הוא מספר ה-Qubits המשמשים לאמידת הפאזה. ככל שיש יותר Qubits, כך אמידת הפאזה תהיה מדויקת יותר. נשתמש ב-$m=8$ Qubits בקרה לשגרת אמידת הפאזה שלנו. כלומר, נצטרך:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

כש-האינדקס $k$, עם $0 \le k \le m-1 = 7$, מתאים ל-Qubit הבקרה. עכשיו בואו נחשב את $a^{2^k}\bmod N$ לכל ערך של $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

מכיוון ש-$a^{2^k} \bmod N = 1$ עבור $k \ge 2$, כל האופרטורים המתאימים ($M_8$ ומעלה) שקולים לזהות. אז צריך לבנות עוד מטריצה אחת בלבד, $M_4.$

הערה: פישוט זה עובד כאן רק מכיוון שהסדר של $2 \bmod 15$ הוא $4$. ברגע ש-$k=2$ (כך ש-$2^k = 4$), כל חזקה עוקבת של האופרטור היא הזהות. באופן כללי, עבור מספרים גדולים יותר $N$ או בחירות שונות של $a$, לא ניתן לדלג על בניית החזקות הגבוהות. זו אחת הסיבות לכך שזה נחשב דוגמה צעצוע: המספרים הקטנים מאפשרים קיצורי דרך שלא יעבדו במקרים גדולים יותר.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

וכמו קודם, הופכים אותו לאופרטור controlled-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

עכשיו אפשר לשלב הכל יחד כדי למצוא את הסדר של $2\bmod 15$ עם Circuit קוונטי, תוך שימוש באמידת פאזה:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. אופטימיזציה

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

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

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

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. הרצה

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

אנחנו רואים ארבעה שיאים ברורים ב-00000000, 01000000, 10000000, ו-11000000, עם כמה ספירות במחרוזות סיביות אחרות בגלל רעש במחשב הקוונטי. נתעלם מאלה ונשמור רק את ארבעת הדומיננטיים על ידי הטלת סף: רק ספירות מעל הסף הזה נחשבות לאות אמיתי מעל הרעש.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. עיבוד לאחר המדידה

באלגוריתם שור, חלק גדול מהאלגוריתם מתבצע קלאסית. לכן נשים את שאר הדברים בשלב "עיבוד לאחר המדידה", אחרי שקיבלנו את המדידות שלנו מהמחשב הקוונטי. כל אחת מהמדידות למעלה ניתן להמיר למספרים שלמים, שאחרי שנחלק ב-$2^m$, הם הקירובים שלנו ל-$\frac{k}{r}$, כש-$k$ הוא אקראי בכל פעם.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

סיכום

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

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

בעיות

מושגים מרכזיים:

• מערכות קריפטוגרפיות מודרניות מסתמכות על הקושי הקלאסי בפירוק מספרים שלמים גדולים.
• חשבון מודולרי — כולל המבנים $\mathbb{Z}_N$ ו-$\mathbb{Z}_N^*$ — מספק את הבסיס המתמטי לאלגוריתם שור.
• ניתן לצמצם את בעיית פירוק מספר שלם $N$ לבעיית מציאת הסדר של מספר מודולו $N$.
• מציאת הסדר הקוונטית משתמשת בטכניקות אמידת פאזה קוונטית כדי לקבוע את התקופה של הפונקציה $a^x \mod N$.
• אלגוריתם שור מורכב מתהליך עבודה היברידי קלאסי-קוונטי שבוחר בסיס, מבצע מציאת סדר קוונטית, ואז מחשב קלאסית את הגורמים מהתוצאה.

נכון/לא נכון:

1. נ/ל היעילות של אלגוריתם שור מאיימת על אבטחת הצפנת RSA.
2. נ/ל אפשר להריץ את אלגוריתם שור ביעילות על כל מחשב קוונטי מודרני.
3. נ/ל אלגוריתם שור משתמש באמידת פאזה קוונטית (QPE) כתת-שגרה מרכזית.
4. נ/ל החלק הקלאסי של אלגוריתם שור כולל חישוב המחלק המשותף הגדול ביותר (GCD).
5. נ/ל אלגוריתם שור עובד רק לפירוק מספרים זוגיים.
6. נ/ל הרצה מוצלחת של אלגוריתם שור תמיד מבטיחה את הגורמים הנכונים.

תשובה קצרה:

1. מדוע אלגוריתם שור נחשב לאיום עתידי פוטנציאלי על הצפנת RSA?
2. מדוע מציאת התקופה, או הסדר, של פונקציה אקספוננציאלית מודולרית מועילה לפירוק מספר באלגוריתם שור?

בעיות אתגר:

1. כמה Qubits בקרה $m$ אנחנו צריכים עבור מספר נתון $N$ שאנחנו מנסים לפרק כדי לקבל את הדיוק ב-QPE הדרוש למציאת הערך הנכון של הסדר $r$?

2. בעקבות ההליך שתיארנו כאן לפירוק 15, נסה עכשיו לפרק את 21.