קודי חזרה

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

קידוד ופענוח קלאסיים

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

בפרט, נתחיל בקוד החזרה בן 3 הסיביות, רק בהקשר של מידע קלאסי. קוד זה מקודד סיבית אחת לשלוש על ידי חזרה על הסיבית שלוש פעמים, כך ש-$0$ מקודד כ-$000$ ו-$1$ מקודד כ-$111.$

$$\begin{aligned} 0 & \mapsto 000\\ 1 & \mapsto 111 \end{aligned}$$

אם הכל תקין, ניתן כמובן להבחין בין שתי האפשרויות לסיבית המקורית מתוך הקידודים שלהן. הנקודה היא שאם הייתה שגיאה ואחת משלוש הסיביות התהפכה — כלומר שה-0 הפך ל-1 או ה-1 הפך ל-0 — עדיין ניתן לגלות מה הייתה הסיבית המקורית על ידי קביעה איזו משתי הערכים הבינאריים מופיעה פעמיים. באופן שקול, ניתן לפענח על ידי חישוב ערך הרוב (כלומר, הערך הבינארי המופיע הכי הרבה פעמים).

$$a b c \mapsto \operatorname{majority}(a,b,c)$$

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

הפחתת רעש לערוץ הסימטרי הבינארי

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

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

ההסתברות שסיביתיים יתהפכו בזמן ההעברה היא $3p^2(1-p),$ שהיא $p^2(1-p)$ לכל אחת משלוש האפשרויות לסיבית שלא תתהפך, בעוד ההסתברות שכל שלוש הסיביות יתהפכו היא $p^3.$ ההסתברות הכוללת של שניים או שלושה היפוכי סיביות היא לכן

$$3 p^2 (1 - p) + p^3 = 3 p^2 - 2 p^3.$$

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

קידוד Qubit

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

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

$$\alpha \vert 0\rangle + \beta \vert 1\rangle \mapsto \alpha \vert 000\rangle + \beta \vert 111\rangle$$

קידוד זה מיושם בקלות על ידי ה-Circuit הקוונטי הבא, שמשתמש בשני Qubit מאותחלים כמרחב עבודה ובשני שערי NOT מבוקרים.

שים לב, בפרט, שקידוד זה אינו זהה לחזרה על המצב הקוונטי שלוש פעמים, כפי שבמצב Qubit נתון $\vert\psi\rangle$ מקודד כ-$\vert\psi\rangle \mapsto \vert\psi\rangle\vert\psi\rangle\vert\psi\rangle.$ קידוד כזה אינו ניתן ליישום עבור מצב קוונטי לא ידוע $\vert\psi\rangle$ בגלל משפט אי-השכפול.

שגיאות היפוך סיביות

נניח כעת שמתרחשת שגיאה לאחר ביצוע הקידוד. ספציפית, נניח ש-Gate מסוג $X$, כלומר היפוך סיבית, מתרחש על אחד מה-Qubit. לדוגמה, אם ה-Qubit האמצעי חווה היפוך סיבית, מצב שלושת ה-Qubit מומר למצב הבא:

$$\alpha \vert 010\rangle + \beta \vert 101\rangle.$$

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

ניתן לראות בבירור מהביטוי המתמטי של המצב לעיל שהסיבית האמצעית היא זו השונה בתוך כל ket. אך נניח שהיו לנו שלושת ה-Qubit ברשותנו ולא ידענו את מצבם. אם היינו חושדים שהיפוך סיבית אולי התרחש, אפשרות אחת לאימות שסיבית התהפכה הייתה לבצע מדידה בבסיס סטנדרטי, שבמקרה הנדון הייתה גורמת לנו לראות $010$ או $101$ עם הסתברויות $\vert\alpha\vert^2$ ו-$\vert\beta\vert^2$, בהתאמה. בכל מקרה, מסקנתנו הייתה שהסיבית האמצעית התהפכה — אך, לצערנו, היינו מאבדים את המצב הקוונטי המקורי $\alpha\vert 0\rangle + \beta \vert 1\rangle.$ זה המצב שאנחנו מנסים להגן עליו, אז מדידה בבסיס סטנדרטי אינה אפשרות מספקת.

מה שניתן לעשות במקום זאת הוא להשתמש ב-Circuit הקוונטי הבא, תוך הזנת המצב המקודד לשלושת ה-Qubit העליונים. Circuit זה מודד זוגיות (parity) של מצבי הבסיס הסטנדרטי של שני ה-Qubit העליונים וגם שני ה-Qubit התחתונים מתוך הקידוד בן שלושת ה-Qubit, וזאת ללא הרס המצב.

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

הנקודה החשובה היא שמצב שלושת ה-Qubit העליונים אינו קורס באף אחד מהמקרים, מה שמאפשר לנו לתקן שגיאת היפוך סיבית אם אחת התרחשה — פשוט על ידי הפעלת אותו היפוך סיבית שוב עם Gate מסוג $X$. הטבלה הבאה מסכמת את המצבים שנקבל מלכל היותר היפוך סיבית אחד, תוצאות המדידה (הנקראות תסמונת (syndrome) בהקשר של תיקון שגיאות), והתיקון הנדרש לחזרה לקידוד המקורי.

מצב	תסמונת	תיקון
$\alpha\vert 000\rangle + \beta \vert 111\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert 001\rangle + \beta \vert 110\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes X$
$\alpha\vert 010\rangle + \beta \vert 101\rangle$	$11$	$\mathbb{I}\otimes X\otimes\mathbb{I}$
$\alpha\vert 100\rangle + \beta \vert 011\rangle$	$10$	$X\otimes\mathbb{I}\otimes\mathbb{I}$

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

שגיאות היפוך פאזה

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

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

למרבה הצער, קוד החזרה בן 3 הסיביות אינו מגן בכלל מפני היפוכי פאזה. לדוגמה, נניח שמצב Qubit $\alpha\vert 0\rangle + \beta\vert 1\rangle$ קודד בקוד החזרה בן 3 הסיביות, ושגיאת היפוך פאזה מתרחשת על ה-Qubit האמצעי. התוצאה היא המצב

$$(\mathbb{I} \otimes Z \otimes \mathbb{I}) ( \alpha \vert 000\rangle + \beta \vert 111\rangle) = \alpha \vert 000\rangle - \beta \vert 111\rangle,$$

שהוא בדיוק המצב שהיינו מקבלים מקידוד מצב ה-Qubit $\alpha\vert 0\rangle - \beta\vert 1\rangle.$ אכן, לשגיאת היפוך פאזה על כל אחד משלושת ה-Qubit של הקידוד יש אותה השפעה, שהיא שקולה לשגיאת היפוך פאזה על ה-Qubit המקורי לפני הקידוד. בהנחה שהמצב הקוונטי המקורי הוא מצב לא ידוע, לכן אין דרך לזהות שהתרחשה שגיאה, כי המצב המתקבל הוא קידוד תקף לחלוטין של מצב Qubit שונה. בפרט, הפעלת Circuit זיהוי השגיאות מקודם על המצב $\alpha \vert 000\rangle - \beta \vert 111\rangle$ בהכרח תניב תסמונת $00$, שמציעה בטעות שלא התרחשו שגיאות.

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

$$3 p (1 - p)^2 + p^3.$$

ערך זה גדול מ-$p$ כאשר $0<p<1/2$, כך שהקוד מגביר את ההסתברות לשגיאת היפוך פאזה עבור ערכים של $p$ בטווח זה.

גרסה מותאמת של קוד החזרה לשגיאות היפוך פאזה

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

הנה הגרסה המותאמת של Circuit הקידוד מלעיל, שתוכל כעת לזהות שגיאות היפוך פאזה. השינוי פשוט מאוד: אנחנו פשוט מפעילים Gate של Hadamard על כל Qubit לאחר ביצוע שני ה-NOT Gate המבוקרים.

Gate של Hadamard ממיר מצב $\vert 0\rangle$ למצב $\vert + \rangle$, ומצב $\vert 1\rangle$ למצב $\vert - \rangle$, כך שהאפקט הכולל הוא שמצב ה-Qubit הבודד $\alpha\vert 0\rangle + \beta \vert 1\rangle$ מקודד כ-

$$\alpha \vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-} \rangle$$

כאשר $\vert {+}\,{+}\,{+} \rangle = \vert + \rangle \otimes \vert + \rangle \otimes\vert + \rangle$ ו- $\vert {-}\,{-}\,{-} \rangle = \vert - \rangle \otimes \vert - \rangle \otimes\vert - \rangle.$

שגיאת היפוך פאזה, או בשקולים Gate מסוג $Z$, מחליפה בין המצבים $\vert + \rangle$ ו-$\vert - \rangle$, כך שקידוד זה יהיה שימושי לזיהוי (ותיקון) שגיאות היפוך פאזה. ספציפית, ניתן לשנות את Circuit זיהוי השגיאות מקודם כך:

במילים, לוקחים את ה-Circuit מקודם ופשוט שמים Gate של Hadamard על שלושת ה-Qubit העליונים גם בתחילה וגם בסוף. הרעיון הוא ששלושת Gate של Hadamard הראשונים ממירים מצבי $\vert + \rangle$ ו-$\vert - \rangle$ בחזרה למצבי $\vert 0\rangle$ ו-$\vert 1\rangle$, בדיקות הזוגיות הרגילות מתבצעות, ואז שכבת Gate של Hadamard השנייה ממירה את המצב בחזרה למצבי $\vert + \rangle$ ו-$\vert - \rangle$ כך שאנחנו מקבלים בחזרה את הקידוד שלנו. לעיון עתידי, נשים לב ש-Circuit זיהוי היפוך הפאזה זה ניתן לפישוט כך:

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

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

מצב	תסמונת	תיקון
$\alpha\vert {+}\,{+}\,{+} \rangle + \beta \vert {-}\,{-}\,{-}\rangle$	$00$	$\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}$
$\alpha\vert {+}\,{+}\,{-}\rangle + \beta \vert {-}\,{-}\,{+}\rangle$	$01$	$\mathbb{I}\otimes\mathbb{I}\otimes Z$
$\alpha\vert {+}\,{-}\,{+}\rangle + \beta \vert {-}\,{+}\,{-}\rangle$	$11$	$\mathbb{I}\otimes Z\otimes\mathbb{I}$
$\alpha\vert {-}\,{+}\,{+} \rangle + \beta \vert {+}\,{-}\,{-}\rangle$	$10$	$Z\otimes\mathbb{I}\otimes\mathbb{I}$

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