דלג לתוכן הראשי

האלגוריתם של סיימון

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

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

בעיית סיימון​

פונקציית הקלט לבעיית סיימון היא מהצורה

f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m

עבור מספרים שלמים חיוביים nn ו-m.m. ניתן להגביל את הדיון למקרה m=nm = n לשם פשטות, אך אין הרבה מה להרוויח מהנחה זו — האלגוריתם של סיימון והניתוח שלו בעצם זהים בשני המקרים.

בעיית סיימון

קלט: פונקציה f:Σn→Σmf:\Sigma^n \rightarrow \Sigma^m
הבטחה: קיימת מחרוזת s∈Σns\in\Sigma^n כך ש-[f(x)=f(y)]⇔[(x=y)∨(x⊕s=y)][f(x) = f(y)] \Leftrightarrow [(x = y) \vee (x \oplus s = y)] לכל x,y∈Σnx,y\in\Sigma^n
פלט: המחרוזת ss

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

ישנם שני מקרים עיקריים: המקרה הראשון הוא ש-ss הוא מחרוזת האפסים 0n,0^n, והמקרה השני הוא ש-ss אינו מחרוזת האפסים.

  • מקרה 1: s=0n.s=0^n. אם ss הוא מחרוזת האפסים, אפשר לפשט את משפט "אם ורק אם" בהבטחה כך שיקרא [f(x)=f(y)]⇔[x=y].[f(x) = f(y)] \Leftrightarrow [x = y]. זה שקול לכך ש-ff היא פונקציה חד-חד-ערכית.

  • מקרה 2: s≠0n.s\neq 0^n. אם ss אינו מחרוזת האפסים, אזי קיום ההבטחה עבור מחרוזת זו מחייב ש-ff היא שתיים-לאחת, כלומר עבור כל מחרוזת פלט אפשרית של f,f, קיימות בדיוק שתי מחרוזות קלט שגורמות ל-ff להוציא אותה. יתר על כן, שתי מחרוזות הקלט האלה חייבות להיות מהצורה ww ו-w⊕sw \oplus s עבור מחרוזת ww כלשהי.

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

הנה דוגמה לפונקציה מהצורה f:Σ3→Σ5f:\Sigma^3 \rightarrow \Sigma^5 שמקיימת את ההבטחה עבור המחרוזת s=011.s = 011.

f(000)=10011f(001)=00101f(010)=00101f(011)=10011f(100)=11010f(101)=00001f(110)=00001f(111)=11010\begin{aligned} f(000) & = 10011 \\ f(001) & = 00101 \\ f(010) & = 00101 \\ f(011) & = 10011 \\ f(100) & = 11010 \\ f(101) & = 00001 \\ f(110) & = 00001 \\ f(111) & = 11010 \end{aligned}

יש 88 מחרוזות קלט שונות ו-44 מחרוזות פלט שונות, כל אחת מהן מופיעה פעמיים — כך שזו פונקציה שתיים-לאחת. יתר על כן, עבור כל שתי מחרוזות קלט שונות המייצרות את אותה מחרוזת פלט, ניתן לראות שה-XOR הביטי של שתי מחרוזות הקלט שווה ל-011,011, מה שכשקול לאמירה שאחת מהן שווה לשנייה עם XOR עם s.s.

שימו לב שהדבר היחיד שחשוב לגבי מחרוזות הפלט בפועל הוא האם הן זהות או שונות עבור בחירות שונות של מחרוזות קלט. לדוגמה, בדוגמה לעיל, ישנן ארבע מחרוזות (10011,(10011, 00101,00101, 00001,00001, ו-11010)11010) שמופיעות כפלטים של f.f. ניתן להחליף את ארבע המחרוזות האלה במחרוזות אחרות, כל עוד כולן שונות זו מזו, והפתרון הנכון s=011s = 011 לא ישתנה.

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

הנה דיאגרמת מעגל קוונטי המייצגת את האלגוריתם של סיימון.

Simon's algorithm

להבהרה, יש nn Qubits בחלק העליון שעליהם פועלים שערי הדאמרד ו-mm Qubits בחלק התחתון שנכנסים ישירות לשער השאילתה. זה נראה מאוד דומה לאלגוריתמים שכבר דנו בהם בשיעור, אך הפעם אין בעיטת פאזה; כל mm ה-Qubits התחתונים נכנסים לשער השאילתה במצב ∣0⟩.\vert 0\rangle.

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

ניתוח​

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

12n∑x∈Σn∣0m⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert 0^m \rangle \vert x\rangle.

כשמבצעים את UfU_f, פלט הפונקציה ff מבוצע XOR על המצב האפסי של mm ה-Qubits התחתונים, כך שהמצב הופך ל:

12n∑x∈Σn∣f(x)⟩∣x⟩.\frac{1}{\sqrt{2^n}} \sum_{x\in\Sigma^n} \vert f(x) \rangle \vert x\rangle.

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

12n∑x∈Σn∑y∈Σn(−1)x⋅y∣f(x)⟩∣y⟩\frac{1}{2^n} \sum_{x\in\Sigma^n} \sum_{y\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \vert y\rangle

בשלב זה הניתוח מסתעף מהניתוחים של האלגוריתמים הקודמים בשיעור זה.

אנחנו מתעניינים בהסתברות שהמדידות יניבו כל מחרוזת אפשרית y∈Σn.y\in\Sigma^n. מתוך הכללים לניתוח מדידות המתוארים בשיעור מערכות מרובות של קורס יסודות המידע הקוונטי, אנו מוצאים שההסתברות p(y)p(y) לקבל את המחרוזת yy שווה ל:

p(y)=∥12n∑x∈Σn(−1)x⋅y∣f(x)⟩∥2.p(y) = \left\|\frac{1}{2^n} \sum_{x\in\Sigma^n} (-1)^{x\cdot y} \vert f(x) \rangle \right\|^2.

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

range⁡(f)={f(x):x∈Σn}\operatorname{range}(f) = \{ f(x) : x\in \Sigma^n \}

שנית, עבור כל מחרוזת z∈range⁡(f),z\in\operatorname{range}(f), ניתן לבטא את הקבוצה של כל מחרוזות הקלט שגורמות לפונקציה להעריך למחרוזת הפלט zz כ-f−1({z}).f^{-1}(\{z\}).

f−1({z})={x∈Σn:f(x)=z}f^{-1}(\{z\}) = \{ x\in\Sigma^n : f(x) = z \}

הקבוצה f−1({z})f^{-1}(\{z\}) מכונה תמונה הקדומה של {z}\{z\} תחת f.f. ניתן להגדיר את התמונה הקדומה תחת ff של כל קבוצה במקום {z}\{z\} באופן אנלוגי — זו קבוצת כל האיברים ש-ff ממפה לאותה קבוצה. (אין לבלבל בין סימון זה להפוך של הפונקציה f,f, שאולי אינו קיים. העובדה שהארגומנט בצד שמאל הוא הקבוצה {z}\{z\} ולא האיבר zz היא הרמז שמאפשר לנו להימנע מבלבול זה.)

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

p(y)=∥12n∑z∈range⁡(f)(∑x∈f−1({z})(−1)x⋅y)∣z⟩∥2.p(y) = \left\| \frac{1}{2^n} \sum_{z\in\operatorname{range}(f)} \Biggl(\sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y}\Biggr) \vert z \rangle \right\|^2.

כל מחרוזת x∈Σnx\in\Sigma^n מיוצגת בדיוק פעם אחת על ידי שני הסכומים — בעצם אנחנו פשוט מכניסים את המחרוזות האלה לדליים נפרדים בהתאם למחרוזת הפלט z=f(x)z = f(x) שהן מייצרות כשמחשבים את הפונקציה ff, ואז סוכמים בנפרד על כל הדליים.

כעת נוכל לחשב את הנורמה האוקלידית בריבוע ולקבל:

p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2.p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2.

כדי לפשט עוד יותר את ההסתברויות האלה, נסתכל על הערך

∣∑x∈f−1({z})(−1)x⋅y∣2(1)\left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 \tag{1}

עבור בחירה שרירותית של z∈range⁡(f).z\in\operatorname{range}(f).

אם במקרה s=0n,s = 0^n, אז ff היא פונקציה חד-חד-ערכית ותמיד יש רק איבר x∈f−1({z})x\in f^{-1}(\{z\}) יחיד, עבור כל z∈range⁡(f).z\in\operatorname{range}(f). ערך הביטוי (1)(1) הוא 11 במקרה זה.

אם, לעומת זאת, s≠0n,s\neq 0^n, אז יש בדיוק שתי מחרוזות בקבוצה f−1({z}).f^{-1}(\{z\}). לדיוק, אם נבחר w∈f−1({z})w\in f^{-1}(\{z\}) כאחת משתי המחרוזות האלה, אז המחרוזת האחרת חייבת להיות w⊕sw \oplus s לפי ההבטחה בבעיית סיימון. בעזרת תצפית זו ניתן לפשט את (1)(1) כך:

∣∑x∈f−1({z})(−1)x⋅y∣2=∣(−1)w⋅y+(−1)(w⊕s)⋅y∣2=∣(−1)w⋅y(1+(−1)s⋅y)∣2=∣1+(−1)y⋅s∣2={4y⋅s=00y⋅s=1\begin{aligned} \left\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \right\vert^2 & = \Bigl\vert (-1)^{w\cdot y} + (-1)^{(w\oplus s)\cdot y} \Bigr\vert^2 \\ & = \Bigl\vert (-1)^{w\cdot y} \Bigl(1 + (-1)^{s\cdot y}\Bigr) \Bigr\vert^2 \\ & = \Bigl\vert 1 + (-1)^{y\cdot s} \Bigr\vert^2 \\ & = \begin{cases} 4 & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases} \end{aligned}

כך מתברר שהערך (1)(1) אינו תלוי בבחירה הספציפית של z∈range⁡(f)z\in\operatorname{range}(f) בשני המקרים.

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

  • מקרה 1: s=0n.s = 0^n. במקרה זה הפונקציה ff היא חד-חד-ערכית, כך שיש 2n2^n מחרוזות z∈range⁡(f),z\in\operatorname{range}(f), ואנו מקבלים:

    p(y)=122n⋅2n=12n.p(y) = \frac{1}{2^{2n}} \cdot 2^n = \frac{1}{2^n}.

    במילים, המדידות מניבות מחרוזת y∈Σny\in\Sigma^n שנבחרת אחידה באקראי.

  • מקרה 2: s≠0n.s \neq 0^n. במקרה זה ff היא שתיים-לאחת, כך שיש 2n−12^{n-1} איברים ב-range⁡(f).\operatorname{range}(f). בעזרת הנוסחה מלעיל נסיק שההסתברות למדוד כל y∈Σny\in\Sigma^n היא:

    p(y)=122n∑z∈range⁡(f)∣∑x∈f−1({z})(−1)x⋅y∣2={12n−1y⋅s=00y⋅s=1p(y) = \frac{1}{2^{2n}} \sum_{z\in\operatorname{range}(f)} \Biggl\vert \sum_{x\in f^{-1}(\{z\})} (-1)^{x\cdot y} \Biggr\vert^2 = \begin{cases} \frac{1}{2^{n-1}} & y \cdot s = 0\\[1mm] 0 & y \cdot s = 1 \end{cases}

    במילים, אנו מקבלים מחרוזת שנבחרת אחידה באקראי מהקבוצה {y∈Σn:y⋅s=0},\{y\in\Sigma^n : y \cdot s = 0\}, שמכילה 2n−12^{n-1} מחרוזות. (מאחר ש-s≠0n,s\neq 0^n, בדיוק חצי ממחרוזות הבינארי באורך nn בעלות מכפלה נקודתית בינארית 11 עם ss והאחרות בעלות מכפלה נקודתית בינארית 00 עם s,s, כפי שכבר ראינו בניתוח אלגוריתם דויטש-ג'וזה לבעיית ברנשטיין-ווזיראני.)

עיבוד קלאסי לאחר המדידה​

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

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

נניח שאנחנו מריצים את המעגל kk פעמים באופן עצמאי, עבור k=n+10.k = n + 10. אין שום דבר מיוחד במספר האיטרציות הספציפי הזה — ניתן לקחת את kk גדול יותר (או קטן יותר) בהתאם להסתברות הכישלון שאנחנו מוכנים לסבול, כפי שנראה. בחירת k=n+10k = n + 10 תבטיח שיש לנו סיכוי גדול מ-99.999.9% לשחזר את s.s.

על ידי הרצת המעגל kk פעמים, אנו מקבלים מחרוזות y1,...,yk∈Σn.y^1,...,y^{k} \in \Sigma^n. להבהרה, האינדקסים העליונים כאן הם חלק משמות המחרוזות האלה, לא חזקות או אינדקסים לביטים שלהן, אז יש לנו:

y1=yn−11⋯y01y2=yn−12⋯y02    ⋮yk=yn−1k⋯y0k\begin{aligned} y^1 & = y^1_{n-1} \cdots y^1_{0}\\[1mm] y^2 & = y^2_{n-1} \cdots y^2_{0}\\[1mm] & \;\; \vdots\\[1mm] y^{k} & = y^{k}_{n-1} \cdots y^{k}_{0} \end{aligned}

כעת אנחנו בונים מטריצה MM עם kk שורות ו-nn עמודות על ידי לקיחת הביטים של המחרוזות האלה כערכים בינאריים.

M=(yn−11⋯y01yn−12⋯y02⋮⋱⋮yn−1k⋯y0k)M = \begin{pmatrix} y^1_{n-1} & \cdots & y^1_{0}\\[1mm] y^2_{n-1} & \cdots & y^2_{0}\\[1mm] \vdots & \ddots & \vdots \\[1mm] y^{k}_{n-1} & \cdots & y^{k}_{0} \end{pmatrix}

כעת, אנחנו לא יודעים מהו ss בשלב זה — המטרה שלנו היא למצוא את המחרוזת הזו. אך נדמיין לרגע שאנחנו כן יודעים את המחרוזת s,s, ונבנה וקטור עמודה vv מהביטים של המחרוזת s=sn−1⋯s0s = s_{n-1} \cdots s_0 כך:

v=(sn−1⋮s0)v = \begin{pmatrix} s_{n-1}\\ \vdots\\ s_0 \end{pmatrix}

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

Mv=(y1⋅sy2⋅s⋮yk⋅s)=(00⋮0)M v = \begin{pmatrix} y^1 \cdot s\\ y^2 \cdot s\\ \vdots\\[1mm] y^{k} \cdot s \end{pmatrix} = \begin{pmatrix} 0\\ 0\\ \vdots\\[1mm] 0 \end{pmatrix}

כלומר, כשמתייחסים אל המחרוזת ss כוקטור עמודה vv כפי שתואר כרגע, ss תמיד יהיה איבר במרחב האפסי של המטריצה M,M, בתנאי שנבצע את החשבון מודולו 2.2. זה נכון גם במקרה ש-s=0ns = 0^n וגם כאשר s≠0n.s\neq 0^n. ליתר דיוק, וקטור האפסים תמיד נמצא במרחב האפסי של M,M, ומצטרף אליו הוקטור שערכיו הם ביטי ss במקרה ש-s≠0n.s\neq 0^n.

השאלה שנותרת היא האם יהיו וקטורים נוספים במרחב האפסי של MM מלבד אלה המתאימים ל-0n0^n ול-s.s. התשובה היא שהדבר הופך לפחות סביר ככל ש-kk גדל — ואם נבחר k=n+10k = n + 10, מרחב האפסי של MM לא יכיל וקטורים נוספים בנוסף לאלה המתאימים ל-0n0^n ול-ss בסיכוי גדול מ-99.999.9%. באופן כללי יותר, אם נחליף k=n+10k = n + 10 ב-k=n+rk = n + r עבור בחירה שרירותית של מספר שלם חיובי r,r, ההסתברות שהוקטורים המתאימים ל-0n0^n ול-ss נמצאים לבדם במרחב האפסי של MM היא לפחות 1−2−r.1 - 2^{-r}.

בעזרת אלגברה לינארית, ניתן לחשב ביעילות תיאור של מרחב האפסי של MM מודולו 2.2. ספציפית, ניתן לעשות זאת באמצעות אלימינציית גאוס, שעובדת באותה דרך כשהחשבון מבוצע מודולו 22 כמו עם מספרים ממשיים או מרוכבים. כל עוד הוקטורים המתאימים ל-0n0^n ול-ss נמצאים לבדם במרחב האפסי של M,M, מה שקורה בהסתברות גבוהה, ניתן להסיק את ss מתוצאות חישוב זה.

הקושי הקלאסי​

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

ישנן הצהרות מדויקות שונות שניתן לנסח לגבי הקושי הקלאסי של בעיה זו, והנה אחת מהן. אם יש לנו אלגוריתם שאילתות הסתברותי כלשהו, ואותו אלגוריתם מבצע פחות מ-2n/2−1−12^{n/2 - 1} - 1 שאילתות, שהוא מספר שאילתות אקספוננציאלי ב-n,n, אז האלגוריתם הזה ייכשל בפתרון בעיית סיימון בהסתברות לפחות 1/2.1/2.

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

אנחנו מנסים למצוא את המחרוזת הנסתרת s,s, אך כל עוד לא שואלים את הפונקציה על שתי מחרוזות בעלות אותו ערך פלט, נקבל מידע מוגבל מאוד על s.s. באופן אינטואיטיבי, כל מה שנלמד הוא שהמחרוזת הנסתרת ss אינה ה-XOR בלעדי של שתי מחרוזות שונות ששאלנו. ואם שאלנו על פחות מ-2n/2−1−12^{n/2 - 1} - 1 מחרוזות, עדיין יישארו הרבה בחירות ל-ss שלא שללנו מכיוון שאין מספיק זוגות מחרוזות לכך. זו אינה הוכחה פורמלית, זו רק הרעיון הבסיסי.

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