אלגוריתם שור

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

אלגוריתם שוֹ‏ר (Shor - על שם פיטר שור, ממציאו), הוא אלגוריתם קוונטי המשמש לפירוק לגורמים של מספר גדול, כלומר מציאת הגורמים הראשוניים של המספר. האלגוריתם פורסם לראשונה על ידי פיטר שור‏[1] בשנת 1994, ויחד עם אלגוריתם גרובר נחשב לאחד משני האלגוריתמים החשובים ביותר בתחום החישוב הקוונטי.‏‏‏[2] פיתוח האלגוריתם זיכה את ממציאו בפרס גדל (1999). אלגוריתם שור מבוסס על הרעיונות הקוונטיים שהודגמו באלגוריתם סימון למציאת מחזור של פונקציה. האלגוריתם עושה שימוש בהתמרת פורייה קוונטית (QFT), על מנת לקבל מחזור שהינו כפולה של אחד מהגורמים הראשוניים של המספר אותו רוצים לפרק.


האלגוריתמים הטובים ביותר הידועים, מפרקים מספר גדול \ n,לגורמיו בסיבוכיות זמן של \ O(e^{(\log(n))^{1/3}(\log\log(n))^{2/3}}), שאינה פולינומית ב-\ O(\log^3(n)). לעומת זאת, אלגוריתם שור פועל בסיבוכיות זמן של \ O(\log^3(n)). אלגוריתם זה מהווה דוגמה ליתרון אקספוננציאלי בסיבוכיות הזמן של אלגוריתמים קוונטיים לעומת אלגוריתם קלאסי.

השלכות ומשמעויות[עריכת קוד מקור | עריכה]

שימוש באלגוריתם זה על מנת לפרק מספרים גדולים מהווה איום על אלגוריתמים מתחום ההצפנה האסימטרית, אשר מושתתים על פעולות מתמטיות עם מספרים גדולים, כגון RSA‏. שיטות אלו מסתמכות על מספר גדול \ N בן 512–8192 סיביות (מספר בעל מאות ספרות), אשר ידוע לכלל. הגורמים הראשוניים של מספר זה מהווים את המפתח הסודי. שימוש באלגוריתם שור מאפשר מציאת המפתח באופן יעיל, כלומר, במספר "קטן" יחסית של פעולות.

עם זאת, היישום הפיזיקלי של האלגוריתם הינו קשה. בשנת 2001 בוצע אלגוריתם שור על מספר בן 5 סיביות במעבדות IBM‏, על ידי בניית מעגל קוונטי המכיל 7 קיוביטים.[3] בנית מחשב קוונטי בעל מספר גדול יותר של קיוביטים, נחשבת אתגר קשה מאד בטכנולוגיה בת ימינו.

תיאור האלגוריתם לפירוק המספר \ N[עריכת קוד מקור | עריכה]

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

השלב הקלאסי[עריכת קוד מקור | עריכה]

  1. בחר מספר כלשהו \ a < N.
  2. בדוק האם ‎gcd(a, N) ≠ 1‏. אם כן - מצאנו גורם, סיים.
  3. אם לא, בצע את השלב הקוונטי על מנת למצוא את המספר \ r, שהינו המחזור של הפונקציה
    f(x)=a^x \mod N
  4. אם המספר r המתקבל הינו אי-זוגי, חזור לסעיף 1.
  5. אחרת, בדוק האם a^{r/2}\equiv -1 \ (mod\ N).
    1. אם כן - חזור ל1.
    2. אחרת, לa^{r/2}\pm 1 גורם ראשוני משותף עם N. חשב \ gcd(a^{r/2}\pm 1,N) וקבל גורם ראשוני של N.
(הסבר: אם \ r מחזור של \ f(x) אזי \ a^r \equiv 1\ (mod\ N), כלומר, \ a^r-1\equiv 0. נפתח את הביטוי:

\ (a^{r/2}-1)(a^{r/2}+1) = kN = kN_pN_q

כאשר \ N=N_pN_q, הגורמים של N).

השלב הקוואנטי[עריכת קוד מקור | עריכה]

בחר מספר Q כך ש N^2 \le Q \le 2N^2 וכן Q הינו חזקה שלמה של 2, כלומר ניתן לכתיבה \ Q=2^q עבור q מספר טבעי.

1. אתחל שני אוגרים קוונטים, בגודל q קיוביטים כל אחד, למצב

Q^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|0\rangle

שהינו סופרפוזיציה של Q מצבים.

2. הפעל את הפונקציה הקוונטית \ f(x) על האוגרים, לקבלת

Q^{-1/2}\sum_{x=0}^{Q-1}|x\rangle|f(x)\rangle

3. בצע התמרת פורייה קוונטית על האוגר הראשון. מהתמרת |x\rangle מקבלים Q^{-1/2} \sum_y \omega^{x y} \left|y\right\rangle, כאשר \ \omega^i=e^{2\pi i/Q}, ועל כן מצב האוגרים לאחר הפעלת השער הינו סופרפוזיציה של הרבה יותר מ \ Q מצבים, אך הרבה פחות מ \ Q^2:

Q^{-1} \sum_x \sum_y \omega^{x y} |y\rangle |f(x)\rangle

4. בצע מדידה. מתקבל ערך \ y_m כלשהו וערך \ f(x_0) כלשהו. ההסתברות למדוד את הזוג \ y_m, f(x_0) נתונה על ידי

\left| Q^{-1} \sum_{x:\, f(x)=f(x_0)} \omega^{x y} \right|^2
= Q^{-2} \left| \sum_{b} \omega^{(x_0 + r b) y} \right|^2

הסתברות זו נובעת מקיומם של ערכים רבים של \ x עבורם \ f(x)=f(x_0), כאשר כל האברים הללו תורמים להסתברות למדוד את אותו המצב |f(x_0)\rangle. החלק הימני של השיווין נובע מהעובדה שהפונקציה \ f(x) הינה מחזורית, בעלת מחזור r (בהנחה שהאבר \ x_0 הינו הקטן ביותר באותו מחזור, וb מקבל ערכים מ-0 עד \ [Q-x_0-1]/r, אז הביטוי \ x_0+r\cdot b הינו כלל ה-\ xים הקטנים מ-\ Q המקיימים \ f(x)=f(x_0)).

5. מצא מספר \ c ומספר \ r', כך ש \ r' < N ו \ c/r' קרוב מאד ל\ y/Q, ובאופן מפורש, \ |y/Q-c/r'|<1/2Q.

6. קיים סיכוי גבוה מאד כי \ r' הינו המחזור המבוקש. בדוק האם \ f(x)=f(x+r'). אם כן, סיים. אם לא - חזור על ביצוע האלגוריתם.

הערות שוליים[עריכת קוד מקור | עריכה]

  1. ^ גרסה מתוקנת ומשופרת של המאמר של פיטר שור ‏פירוק לראשוניים של מספרים בזמן פולינומי על ידי מחשב קוונטי(באנגלית)
  2. ^ מהו מחשב קוונטי, 01/2005‏
  3. ^
    L. M. K. Vandersypen et al. (2001). "Experimental realization of Shor’s quantum factoring algorithm using nuclear magnetic resonance". Nature 414: 883–887. 

קישורים חיצוניים[עריכת קוד מקור | עריכה]