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

קודי CSS

קודים לינאריים קלאסיים​

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

נסמן ב־Σ\Sigma את האלפבית הבינארי לאורך כל הדיון הזה. כשאנו מדברים על קוד לינארי קלאסי, הכוונה לקבוצה לא ריקה C⊆Σn\mathcal{C}\subseteq\Sigma^n של מחרוזות בינאריות באורך n,n, לאיזשהו מספר שלם חיובי n,n, שחייבת לקיים תכונה בסיסית אחת בלבד: אם uu ו־vv הן מחרוזות בינאריות ב־C,\mathcal{C}, אז המחרוזת u⊕vu\oplus v גם היא ב־C.\mathcal{C}. כאן, u⊕vu\oplus v מסמן את ה־XOR הסיביתי של uu ו־v,v, כפי שנתקלנו בו מספר פעמים בקורס "יסודות אלגוריתמים קוונטיים".

במהותו, כשאנו מתארים קוד קלאסי לתיקון שגיאות כלינארי, אנחנו חושבים על מחרוזות בינאריות באורך nn כוקטורים בממד n,n, שהערכים בהם הם 0 או 1, ודורשים שהקוד עצמו ייצור תת-מרחב לינארי. אלא שבמקום חיבור וקטורי רגיל מעל המספרים הממשיים או המרוכבים, אנו משתמשים בחיבור מודולו 2, שהוא פשוט ה־XOR. כלומר, אם יש לנו שתי מילות קוד uu ו־v,v, כלומר uu ו־vv הן מחרוזות בינאריות ב־C,\mathcal{C}, אז u+vu + v מודולו 2, כלומר u⊕v,u\oplus v, חייבת גם היא להיות מילת קוד ב־C.\mathcal{C}. שימו לב, בפרט, שהשלכה זו חייבת להיות נכונה גם אם u=v.u = v. משמע ש־C\mathcal{C} חייבת לכלול את המחרוזת האפסית 0n,0^n, כי ה־XOR הסיביתי של כל מחרוזת עם עצמה הוא המחרוזת האפסית.

דוגמה: קוד החזרה על 3 סיביות​

קוד החזרה על 3 סיביות הוא דוגמה לקוד לינארי קלאסי. בפרט, C={000,111},\mathcal{C} = \{000,111\}, כך שביחס לתנאי הלינאריות, יש רק שתי בחירות אפשריות ל־uu ושתי בחירות אפשריות ל־v.v. בנקל ניתן לבדוק את ארבעת הזוגות האפשריים ולראות שתמיד מקבלים מילת קוד כשלוקחים את ה־XOR הסיביתי:

000⊕000=000,000⊕111=111,111⊕000=111,111⊕111=000.000 \oplus 000 = 000, \quad 000 \oplus 111 = 111, \quad 111 \oplus 000 = 111, \quad 111 \oplus 111 = 000.

דוגמה: קוד המינג [7,4,3][7,4,3]​

הנה עוד דוגמה לקוד לינארי קלאסי הנקרא קוד המינג [7,4,3].[7,4,3]. הוא היה אחד מקודי תיקון השגיאות הקלאסיים הראשונים שהתגלו, והוא מכיל את 16 המחרוזות הבינאריות באורך 7 הבאות. (לפעמים מבינים קוד המינג [7,4,3][7,4,3] כקוד עם המחרוזות הפוכות, אך אנחנו ניקח את הקוד המכיל את המחרוזות המוצגות כאן.)

0000000110000110100100110011011010010101011100110000011111110000011001010101010010111001100010110100111101111111\begin{array}{cccc} 0000000 & 1100001 & 1010010 & 0110011\\[1mm] 0110100 & 1010101 & 1100110 & 0000111\\[1mm] 1111000 & 0011001 & 0101010 & 1001011\\[1mm] 1001100 & 0101101 & 0011110 & 1111111 \end{array}

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

הסימון [7,4,3][7,4,3] (בסוגריים מרובעים בודדים) מציין משהו דומה לסימון הסוגריים המרובעים הכפולים לקודי ייצוב שהוזכר בשיעור הקודם, אלא שכאן הוא מתייחס לקודים לינאריים קלאסיים. בפרט, למילות קוד יש 77 סיביות, ניתן לקודד 44 סיביות באמצעות הקוד (כי יש 16=2416 = 2^4 מילות קוד), וזהו קוד ממרחק 3,3, כלומר כל שתי מילות קוד שונות חייבות להשתנות בלפחות 33 מיקומים — לכן יש להפוך לפחות 33 סיביות כדי להמיר מילת קוד אחת לאחרת. העובדה שזהו קוד ממרחק 33 גוררת שניתן לתקן עד שגיאת היפוך סיביות אחת.

תיאור קודים לינאריים קלאסיים​

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

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

    בפירוט רב יותר, המחרוזות u1,…,um∈Σnu_1,\ldots,u_m\in\Sigma^n מחוללות את הקוד הלינארי הקלאסי C\mathcal{C} אם

    C={α1u1⊕⋯⊕αmum : α1,…,αm∈{0,1}},\mathcal{C} = \bigl\{\alpha_1 u_1 \oplus \cdots \oplus \alpha_m u_m\,:\,\alpha_1,\ldots,\alpha_m\in\{0,1\}\bigr\},

    כאשר αu=u\alpha u = u אם α=1\alpha = 1 ו־αu=0n\alpha u = 0^n אם α=0,\alpha = 0, והרשימה מינימלית אם הסרת אחת המחרוזות מחוללת קוד קטן יותר. דרך טבעית לחשוב על תיאור שכזה היא שהאוסף {u1,…,um}\{u_1,\ldots,u_m\} מהווה בסיס ל־C\mathcal{C} כתת-מרחב, כשאנחנו חושבים על מחרוזות כוקטורים עם ערכים בינאריים, תוך הבנה שאנחנו עובדים במרחב וקטורי שבו חשבון מתבצע מודולו 2.2.

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

    כלומר, המחרוזות v1,…,vr∈Σnv_1,\ldots,v_r\in\Sigma^n הן מחרוזות בדיקת זוגיות לקוד הלינארי הקלאסי C\mathcal{C} אם

    C={u∈Σn : u⋅v1=⋯=u⋅vr=0},\mathcal{C} = \bigl\{ u\in \Sigma^n\,:\, u\cdot v_1 = \cdots = u \cdot v_r = 0 \bigr\},

    וקבוצת המחרוזות מינימלית אם הסרת אחת מהן מביאה לקוד גדול יותר. אלה נקראות מחרוזות בדיקת זוגיות כי למחרוזת uu מכפלה בינארית נקודתית שווה אפס עם vv אם ורק אם הסיביות של uu במיקומים שבהם vv מכיל 1 הן בעלות זוגיות זוגית. כך, כדי לקבוע אם מחרוזת uu נמצאת בקוד C,\mathcal{C}, מספיק לבדוק את הזוגיות של תתי-קבוצות מסוימות של סיביות u.u.

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

קודים לינאריים קלאסיים מעל האלפבית הבינארי תמיד מכילים מספר מחרוזות שהוא חזקה של 22 — ולגבי קוד לינארי קלאסי יחיד המתואר בשתי הדרכים שתוארו, תמיד יתקיים n=m+r.n = m + r. בפרט, אם יש לנו קבוצה מינימלית של mm מחוללים, הקוד מקודד mm סיביות ובהכרח יהיו לנו 2m2^m מילות קוד; ואם יש לנו קבוצה מינימלית של rr מחרוזות בדיקת זוגיות, יהיו 2n−r2^{n-r} מילות קוד. כלומר, כל מחולל מכפיל את גודל מרחב הקוד בשניים, בעוד כל מחרוזת בדיקת זוגיות מחלקת אותו בשניים.

לדוגמה, קוד החזרה על 3 סיביות הוא קוד לינארי, ולכן ניתן לתארו בשתי הדרכים הללו. בפרט, יש בחירה אחת בלבד למחולל שעובדת: 111.111. לחלופין, ניתן לתאר את הקוד עם שתי מחרוזות בדיקת זוגיות, כגון 110110 ו־011011 — שאמורות להיות מוכרות מהדיונים הקודמים על קוד זה — או שנוכל לבחור את 110110 ו־101,101, או 101101 ו־011.011. (מחוללים ומחרוזות בדיקת זוגיות בדרך כלל אינם יחידים לקוד לינארי קלאסי נתון.)

כדוגמה שנייה, שקלו את קוד המינג [7,4,3].[7,4,3]. הנה בחירה אחת לרשימת מחוללים שעובדת.

1111000011010010100101100001\begin{array}{c} 1111000\\[1mm] 0110100\\[1mm] 1010010\\[1mm] 1100001 \end{array}

והנה בחירה לרשימת בדיקות הזוגיות לקוד זה.

111100011001101010101\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}

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

הערה אחרונה על קודים לינאריים קלאסיים, המחברת אותם לפורמליזם של ייצוב, היא שמחרוזות בדיקת זוגיות שקולות למחוללי ייצוב המורכבים רק ממטריצות Pauli ZZ וזהות. לדוגמה, מחרוזות בדיקת הזוגיות 110110 ו־011011 לקוד החזרה על 3 סיביות מתאימות בדיוק למחוללי הייצוב Z⊗Z⊗IZ\otimes Z\otimes \mathbb{I} ו־I⊗Z⊗Z,\mathbb{I}\otimes Z\otimes Z, וזה עקבי עם הדיונים על אופרטורי Pauli מהשיעור הקודם.

הגדרת קודי CSS​

קודי CSS הם קודי ייצוב המתקבלים משילוב של זוגות מסוימים של קודים לינאריים קלאסיים. זה לא עובד עבור שני קודים לינאריים קלאסיים שרירותיים — שני הקודים חייבים לקיים קשר מסוים ביניהם. עם זאת, בניה זו פותחת אפשרויות רבות לקודי תיקון שגיאות קוונטיים, המבוססים בחלקם על למעלה מ־75 שנות תורת קידוד קלאסית.

בפורמליזם של ייצוב, מחוללי ייצוב המכילים רק מטריצות Pauli ZZ וזהות שקולים לבדיקות זוגיות, כפי שראינו לגבי קוד החזרה על 3 סיביות. לדוגמה נוספת, שקלו את מחרוזות בדיקת הזוגיות הבאות לקוד המינג [7,4,3].[7,4,3].

111100011001101010101\begin{array}{c} 1111000\\[1mm] 1100110\\[1mm] 1010101 \end{array}

מחרוזות בדיקת הזוגיות הללו מתאימות למחוללי הייצוב הבאים (כתובים ללא סמלי מכפלה טנסורית), שמתקבלים על ידי החלפת כל 11 ב־ZZ וכל 00 ב־I.\mathbb{I}. אלה שלושה ממחוללי הייצוב השישה של קוד Steane בן 7 Qubit-ים.

ZZZZIIIZZIIZZIZIZIZIZ\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \end{array}

נקרא למחוללי ייצוב כאלה בשם מחוללי ייצוב ZZ, כלומר מחוללים שיש בהם רק Pauli ZZ ואיברי זהות כגורמים טנסוריים — כך ש־XX ו־YY לא מופיעים במחוללי ייצוב ZZ.

אפשר גם לשקול מחוללי ייצוב שבהם מופיעים רק XX ואיברי זהות כגורמים טנסוריים. מחוללי ייצוב כאלה יכולים להיחשב דומים למחוללי ייצוב ZZ, אלא שהם מתארים בדיקות זוגיות בבסיס {∣+⟩,∣−⟩}\{\vert+\rangle,\vert-\rangle\} ולא בבסיס הסטנדרטי. מחוללי ייצוב מסוג זה נקראים מחוללי ייצוב XX — הפעם לא מורשים YY ו־ZZ.

לדוגמה, שקלו את שלושת מחוללי הייצוב הנותרים מקוד Steane בן 7 Qubit-ים.

XXXXIIIXXIIXXIXIXIXIX\begin{array}{ccccccc} X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}

הם עוקבים בדיוק אחרי אותו תבנית מקוד המינג [7,4,3][7,4,3] כמו מחוללי ייצוב ה־ZZ, אלא שהפעם מחליפים XX ב־11 במקום Z.Z. מה שמתקבל משלושת מחוללי הייצוב הללו בלבד הוא קוד הכולל את 16 המצבים המוצגים כאן, שמתקבלים על ידי הפעלת פעולות Hadamard על מצבי הבסיס הסטנדרטי המתאימים למחרוזות בקוד המינג [7,4,3].[7,4,3]. (כמובן, מרחב הקוד של קוד זה כולל גם קומבינציות לינאריות של מצבים אלה.)

∣+++++++⟩∣−−++++−⟩∣−+−++−+⟩∣+−−++−−⟩∣+−−+−++⟩∣−+−+−+−⟩∣−−++−−+⟩∣++++−−−⟩∣−−−−+++⟩∣++−−++−⟩∣+−+−+−+⟩∣−++−+−−⟩∣−++−−++⟩∣+−+−−+−⟩∣++−−−−+⟩∣−−−−−−−⟩\begin{array}{cccc} \vert {+++++++} \rangle \quad & \vert {--++++-} \rangle \quad & \vert {-+-++-+} \rangle \quad & \vert {+--++--} \rangle \\ \vert {+--+-++} \rangle \quad & \vert {-+-+-+-} \rangle \quad & \vert {--++--+} \rangle \quad & \vert {++++---} \rangle \\ \vert {----+++} \rangle \quad & \vert {++--++-} \rangle \quad & \vert {+-+-+-+} \rangle \quad & \vert {-++-+--} \rangle \\ \vert {-++--++} \rangle \quad & \vert {+-+--+-} \rangle \quad & \vert {++----+} \rangle \quad & \vert {-------} \rangle \end{array}

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

הגדרה

קוד CSS הוא קוד ייצוב שניתן לבטא באמצעות מחוללי ייצוב XX ו־ZZ בלבד.

כלומר, קודי CSS הם קודי ייצוב שבהם אין מטריצות Pauli YY במחוללי הייצוב, ו־XX ו־ZZ לא מופיעים באותו מחולל ייצוב.

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

הנה דוגמה פשוטה מאד לקוד CSS הכולל גם מחולל ייצוב ZZ וגם מחולל ייצוב XX:

ZZXX\begin{array}{cc} Z & Z \\[1mm] X & X \end{array}

ברור שזהו קוד CSS, כי המחולל הראשון הוא מחולל ייצוב ZZ והשני הוא מחולל ייצוב X.X. כמובן, קוד CSS חייב להיות גם קוד ייצוב חוקי — כלומר מחוללי הייצוב חייבים להתחלף, ליצור קבוצה מחוללת מינימלית, ולקבע לפחות וקטור מצב קוונטי אחד. דרישות אלה פשוטות לבדיקה עבור קוד זה. כפי שציינו בשיעור הקודם, מרחב הקוד של קוד זה הוא המרחב החד-ממדי הפרוש על ידי מצב Bell ∣ϕ+⟩.\vert\phi^+\rangle. העובדה ששני מחוללי הייצוב מקבעים מצב זה ברורה כשבוחנים את שני הביטויים הבאים של e-bit, יחד עם פרשנות מחוללי הייצוב הללו כבדיקות זוגיות בבסיסים {∣0⟩,∣1⟩}\{\vert 0\rangle, \vert 1\rangle\} ו־ {∣+⟩,∣−⟩}.\{\vert +\rangle, \vert -\rangle\}.

∣ϕ+⟩=∣0⟩∣0⟩+∣1⟩∣1⟩2=∣+⟩∣+⟩+∣−⟩∣−⟩2\vert\phi^+\rangle = \frac{\vert 0\rangle\vert 0\rangle + \vert 1\rangle\vert 1\rangle}{\sqrt{2}} = \frac{\vert +\rangle\vert +\rangle + \vert -\rangle\vert -\rangle}{\sqrt{2}}

קוד Steane בן 7 Qubit-ים הוא דוגמה נוספת לקוד CSS.

ZZZZIIIZZIIZZIZIZIZIZXXXXIIIXXIIXXIXIXIXIX\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}

כאן יש שלושה מחוללי ייצוב ZZ ושלושה מחוללי ייצוב XX, וכבר אימתנו שזהו קוד ייצוב חוקי.

וקוד Shor בן 9 Qubit-ים הוא דוגמה נוספת.

ZZIIIIIIIIZZIIIIIIIIIZZIIIIIIIIZZIIIIIIIIIZZIIIIIIIIZZXXXXXXIIIIIIXXXXXX\begin{array}{ccccccccc} Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & \mathbb{I} & Z & Z\\[1mm] X & X & X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I}\\[1mm] \mathbb{I} & \mathbb{I} & \mathbb{I}& X & X & X & X & X & X \end{array}

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

שוב, חיוני שקודי CSS יהיו קודי ייצוב חוקיים, ובפרט כל מחולל ייצוב ZZ חייב להתחלף עם כל מחולל ייצוב X.X. לכן, לא כל אוסף של מחוללי ייצוב XX ו־ZZ מגדיר קוד CSS חוקי.

זיהוי ותיקון שגיאות​

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

כדוגמה, נשקול את קוד Steane בן 7 Qubit-ים.

ZZZZIIIZZIIZZIZIZIZIZXXXXIIIXXIIXXIXIXIXIX\begin{array}{ccccccc} Z & Z & Z & Z & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] Z & Z & \mathbb{I} & \mathbb{I} & Z & Z & \mathbb{I} \\[1mm] Z & \mathbb{I} & Z & \mathbb{I} & Z & \mathbb{I} & Z \\[1mm] X & X & X & X & \mathbb{I} & \mathbb{I} & \mathbb{I} \\[1mm] X & X & \mathbb{I} & \mathbb{I} & X & X & \mathbb{I} \\[1mm] X & \mathbb{I} & X & \mathbb{I} & X & \mathbb{I} & X \end{array}

הרעיון הבסיסי של קוד זה ברור כעת: זהו קוד המינג [7,4,3][7,4,3] לשגיאות היפוך סיביות וקוד המינג [7,4,3][7,4,3] לשגיאות היפוך פאזה. העובדה שמחוללי ייצוב ה־XX וה־ZZ מתחלפים היא אולי מזל טוב, כי אחרת זה לא יהיה קוד ייצוב חוקי. אך למעשה, ידועות דוגמאות רבות של קודים לינאריים קלאסיים שמניבים קוד ייצוב חוקי כשמשתמשים בהם בדרך דומה.

באופן כללי, נניח שיש לנו קוד CSS שבו מחוללי ייצוב ה־ZZ מאפשרים תיקון של עד jj שגיאות היפוך סיביות, ומחוללי ייצוב ה־XX מאפשרים תיקון של עד kk שגיאות היפוך פאזה. לדוגמה, j=1j = 1 ו־k=1k = 1 לקוד Steane, שכן קוד המינג [7,4,3][7,4,3] יכול לתקן היפוך סיביות אחד. מכאן נובע, על ידי דיסקרטיזציה של שגיאות, שקוד CSS זה יכול לתקן כל שגיאה על מספר Qubit-ים עד המינימום של jj ו־k.k. הסיבה לכך היא שכשמודדים את הסינדרום, שגיאה שרירותית על מספר זה של Qubit-ים מתמוטטת הסתברותית לאיזשהי קומבינציה של שגיאות XX, שגיאות ZZ, או שניהם — ואז שגיאות ה־XX ושגיאות ה־ZZ מזוהות ומתוקנות באופן עצמאי.

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

שימו לב שיש כאן מחיר לשלם, שהוא שלא ניתן לקודד כמות Qubit-ים כגדולה כמות הסיביות שהיינו יכולים עם שני הקודים הקלאסיים. הסיבה היא שמספר מחוללי הייצוב הכולל לקוד ה־CSS הוא סכום מספרי בדיקות הזוגיות של שני הקודים הלינאריים הקלאסיים, וכל מחולל ייצוב מחלק את הממד של מרחב הקוד בשניים. לדוגמה, קוד המינג [7,4,3][7,4,3] מאפשר קידוד של ארבע סיביות קלאסיות, כי יש רק שלוש מחרוזות בדיקת זוגיות לקוד זה, בעוד קוד Steane בן 7 Qubit-ים מקודד Qubit אחד בלבד, כי יש לו שישה מחוללי ייצוב.

מרחבי קוד של קודי CSS​

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

שקלו קוד CSS כלשהו על nn Qubit-ים, ויהיו z1,…,zs∈Σnz_1, \ldots, z_s \in \Sigma^n מחרוזות בדיקת הזוגיות בנות nn סיביות המתאימות למחוללי ייצוב ה־ZZ של הקוד. כלומר, הקוד הלינארי הקלאסי המוגדר על ידי מחוללי ייצוב ה־ZZ בלבד, שנקרא לו CZ,\mathcal{C}_Z, הוא:

CZ={u∈Σn : u⋅z1=⋯=u⋅zs=0}\mathcal{C}_Z = \bigl\{ u \in \Sigma^n \,:\, u \cdot z_1 = \cdots = u \cdot z_s = 0 \bigr\}

במילים, הקוד הלינארי הקלאסי CZ\mathcal{C}_Z מכיל כל מחרוזת שהמכפלה הבינארית הנקודתית שלה עם כל אחת ממחרוזות בדיקת הזוגיות z1,…,zsz_1, \ldots, z_s שווה אפס.

באופן דומה, ניקח x1,…,xt∈Σnx_1,\ldots,x_t\in\Sigma^n כמחרוזות בדיקת הזוגיות בנות nn סיביות המתאימות למחוללי ייצוב ה־XX של הקוד שלנו. כך, הקוד הלינארי הקלאסי המתאים למחוללי ייצוב ה־XX הוא:

CX={u∈Σn : u⋅x1=⋯=u⋅xt=0}\mathcal{C}_X = \bigl\{ u \in \Sigma^n \,:\, u \cdot x_1 = \cdots = u \cdot x_t = 0 \bigr\}

מחוללי ייצוב ה־XX לבדם מתארים אם כן קוד הדומה לקוד זה, אך בבסיס {∣+⟩,∣−⟩}\{\vert {+}\rangle,\vert {-}\rangle\} במקום הבסיס הסטנדרטי.

כעת נציג שני קודים לינאריים קלאסיים חדשים הנגזרים מאותן בחירות של מחרוזות, z1,…,zsz_1,\ldots,z_s ו־x1,…,xt,x_1,\ldots,x_t, אך הפעם נתייחס למחרוזות אלה כמחוללים ולא כמחרוזות בדיקת זוגיות. בפרט, מתקבלים שני הקודים הבאים.

DZ={α1z1⊕⋯⊕αszs : α1,…,αs∈{0,1}}DX={α1x1⊕⋯⊕αtxt : α1,…,αt∈{0,1}}\begin{aligned} \mathcal{D}_Z & = \bigl\{ \alpha_1 z_1 \oplus \cdots \oplus \alpha_s z_s \,:\, \alpha_1,\ldots,\alpha_s \in \{0,1\} \bigr\}\\[1mm] \mathcal{D}_X & = \bigl\{ \alpha_1 x_1 \oplus \cdots \oplus \alpha_t x_t \,:\, \alpha_1,\ldots,\alpha_t \in \{0,1\} \bigr\} \end{aligned}

אלה ידועים בשם קודים דואליים של הקודים שהוגדרו קודם: DZ\mathcal{D}_Z הוא הקוד הדואלי של CZ\mathcal{C}_Z ו־DX\mathcal{D}_X הוא הקוד הדואלי של CX.\mathcal{C}_X. ייתכן שלא ברור בשלב זה מדוע קודים דואליים אלה רלוונטיים, אך הם מתבררים כרלוונטיים מאוד מכמה סיבות, ובהן שתי הסיבות המוסברות בפסקאות הבאות.

ראשית, התנאים שחייבים להתקיים כדי ששני קודים לינאריים קלאסיים CZ\mathcal{C}_Z ו־CX\mathcal{C}_X יהיו תואמים, במובן שניתן להזווגם יחד ליצירת קוד CSS, ניתנים לתיאור פשוט על ידי הפניה לקודים הדואליים. באופן ספציפי, חייב להתקיים DZ⊆CX,\mathcal{D}_Z\subseteq\mathcal{C}_X, או שקול לכך, DX⊆CZ.\mathcal{D}_X\subseteq\mathcal{C}_Z. במילים, הקוד הדואלי DZ\mathcal{D}_Z מכיל את המחרוזות המתאימות למחוללי ייצוב ה־ZZ, והכלתן ב־CX\mathcal{C}_X שקולה לכך שהמכפלה הבינארית הנקודתית של כל אחת מהמחרוזות הללו עם המחרוזות המתאימות למחוללי ייצוב ה־XX שווה אפס. זה, בתורו, שקול לכך שכל מחולל ייצוב ZZ מתחלף עם כל מחולל ייצוב X.X. לחלופין, על ידי היפוך תפקידי מחוללי ייצוב ה־XX וה־ZZ ותחילת הדיון מהכלה DX⊆CZ,\mathcal{D}_X\subseteq\mathcal{C}_Z, ניתן להגיע לאותה מסקנה.

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

∣u⊕DX⟩=12t∑v∈DX∣u⊕v⟩(for all u∈CZ)\vert u \oplus \mathcal{D}_X\rangle = \frac{1}{\sqrt{2^t}} \sum_{v\in\mathcal{D}_X} \vert u \oplus v\rangle \qquad \text{(for all $u\in\mathcal{C}_Z$)}

במילים, וקטורים אלה הם סופרפוזיציות אחידות על המחרוזות בקוד הדואלי DX\mathcal{D}_X של הקוד המתאים למחוללי ייצוב ה־XX, עם הזזה (כלומר XOR סיביתי) של מחרוזות מהקוד CZ\mathcal{C}_Z המתאים למחוללי ייצוב ה־Z.Z. ליתר בהירות, בחירות שונות עבור ההזזה — המיוצגת על ידי המחרוזת uu בביטוי זה — יכולות להניב את אותו וקטור. כלומר, מצבים אלה אינם כולם שונים, אך ביחד הם פורשים את מרחב הקוד כולו.

הנה הסבר אינטואיטיבי מדוע וקטורים כאלה נמצאים במרחב הקוד וגם פורשים אותו. שקלו את מצב הבסיס הסטנדרטי בן nn Qubit-ים ∣u⟩,\vert u\rangle, עבור מחרוזת nn-סיביות שרירותית u,u, ונניח שאנו מקרינים מצב זה על מרחב הקוד. כלומר, נסמן ב־Π\Pi את ההיטל על מרחב הקוד של קוד ה־CSS שלנו, ונשקול את הוקטור Π∣u⟩.\Pi\vert u\rangle. ישנם שני מקרים:

  • מקרה 1: u∈CZ.u\in\mathcal{C}_Z. מכאן נובע שכל מחולל ייצוב ZZ של קוד ה־CSS שלנו פועל טריוויאלית על ∣u⟩.\vert u\rangle. מחוללי ייצוב ה־XX, לעומת זאת, פשוט הופכים חלק מסיביות ∣u⟩.\vert u\rangle. בפרט, עבור כל מחולל vv של DX,\mathcal{D}_X, מחולל ייצוב ה־XX המתאים ל־vv ממיר ∣u⟩\vert u\rangle ל־∣u⊕v⟩.\vert u\oplus v\rangle. על ידי אפיון ההיטל Π\Pi כממוצע על איברי מייצב (כפי שראינו בשיעור הקודם), מתקבל הנוסחה הבאה:

    Π∣u⟩=12t∑v∈DX∣u⊕v⟩=12t∣u⊕DX⟩.\Pi \vert u \rangle = \frac{1}{2^t} \sum_{v\in\mathcal{D}_{X}} \vert u \oplus v\rangle = \frac{1}{\sqrt{2^t}} \vert u \oplus \mathcal{D}_X\rangle.

  • מקרה 2: u∉CZ.u\notin\mathcal{C}_Z. מכאן נובע שלפחות אחת מבדיקות הזוגיות המתאימות למחוללי ייצוב ה־ZZ נכשלת, כלומר ∣u⟩\vert u\rangle הוא ווקטור עצמי עם ערך עצמי −1-1 של לפחות אחד ממחוללי ייצוב ה־ZZ. מרחב הקוד של קוד ה־CSS הוא חיתוך המרחבים העצמיים ב־+1+1 של מחוללי הייצוב. לכן, כוקטור עצמי עם ערך עצמי −1-1 של לפחות אחד ממחוללי ייצוב ה־ZZ, ∣u⟩\vert u\rangle אורתוגונלי למרחב הקוד:

    Π∣u⟩=0.\Pi\vert u\rangle = 0.

וכעת, כשאנחנו עוברים על כל המחרוזות ה־nn-סיביות uu, מסלקים את אלה שעבורן Π∣u⟩=0\Pi\vert u\rangle = 0, ומנרמלים את הנותרים, מתקבלים הוקטורים שתוארו קודם, מה שמוכיח שהם פורשים את מרחב הקוד.

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

H⊗n∣u⊕DZ⟩=12s∑v∈DZH⊗n∣u⊕v⟩(for u∈CX)H^{\otimes n} \vert u \oplus \mathcal{D}_Z\rangle = \frac{1}{\sqrt{2^s}} \sum_{v\in\mathcal{D}_Z} H^{\otimes n}\vert u \oplus v\rangle \qquad \text{(for $u\in\mathcal{C}_X$)}

בעיקרון, XX ו־ZZ הוחלפו בכל מקום שהופיעו — אך גם צריך להחליף את הבסיס הסטנדרטי בבסיס {∣+⟩,∣−⟩}\{\vert+\rangle,\vert-\rangle\}, ולכן פעולות Hadamard נכללות.

כדוגמה, נשקול את קוד Steane בן 7 Qubit-ים. מחרוזות בדיקת הזוגיות עבור מחוללי ייצוב ה־XX וה־ZZ זהות: 1111000,1111000, 1100110,1100110, ו־1010101.1010101. הקודים CX\mathcal{C}_X ו־CZ\mathcal{C}_Z זהים אם כן; שניהם שווים לקוד המינג [7,4,3].[7,4,3].

CX=CZ={0000000,0000111,0011001,0011110,0101010,0101101,0110011,0110100,1001011,1001100,1010010,1010101,1100001,1100110,1111000,1111111}\mathcal{C}_X = \mathcal{C}_Z = \{0000000, 0000111, 0011001, 0011110, 0101010, 0101101, 0110011, 0110100, 1001011, 1001100, 1010010, 1010101, 1100001, 1100110, 1111000, 1111111\}

הקודים הדואליים DX\mathcal{D}_X ו־DZ\mathcal{D}_Z זהים אם כן גם הם. יש לנו שלושה מחוללים, ולכן מתקבלות שמונה מחרוזות.

DX=DZ={0000000,0011110,0101101,0110011,1001011,1010101,1100110,1111000}\mathcal{D}_X = \mathcal{D}_Z = \{0000000, 0011110, 0101101, 0110011, 1001011, 1010101, 1100110, 1111000\}

מחרוזות אלה כולן נמצאות בקוד המינג [7,4,3][7,4,3], כך שתנאי ה־CSS מתקיים: DZ⊆CX,\mathcal{D}_Z \subseteq \mathcal{C}_X, או שקול לכך, DX⊆CZ.\mathcal{D}_X \subseteq \mathcal{C}_Z.

מכיוון ש־DX\mathcal{D}_X מכיל מחצית מכל המחרוזות ב־CZ,\mathcal{C}_Z, יש רק שני וקטורים שונים ∣u⊕DX⟩\vert u\oplus \mathcal{D}_X\rangle שניתן לקבל על ידי בחירת u∈CZ.u\in\mathcal{C}_Z. זה צפוי, כי לקוד Steane בן 7 Qubit-ים יש מרחב קוד דו-ממדי. ניתן להשתמש בשני המצבים שמתקבלים בדרך זו לקידוד המצב הלוגי ∣0⟩\vert 0\rangle ו־∣1⟩\vert 1\rangle כדלקמן.

∣0⟩↦∣0000000⟩+∣0011110⟩+∣0101101⟩+∣0110011⟩+∣1001011⟩+∣1010101⟩+∣1100110⟩+∣1111000⟩8∣1⟩↦∣0000111⟩+∣0011001⟩+∣0101010⟩+∣0110100⟩+∣1001100⟩+∣1010010⟩+∣1100001⟩+∣1111111⟩8\begin{aligned} \vert 0\rangle & \mapsto \frac{ \vert 0000000\rangle + \vert 0011110\rangle + \vert 0101101\rangle + \vert 0110011\rangle + \vert 1001011\rangle + \vert 1010101\rangle + \vert 1100110\rangle + \vert 1111000\rangle }{\sqrt{8}}\\[4mm] \vert 1\rangle & \mapsto \frac{ \vert 0000111\rangle + \vert 0011001\rangle + \vert 0101010\rangle + \vert 0110100\rangle + \vert 1001100\rangle + \vert 1010010\rangle + \vert 1100001\rangle + \vert 1111111\rangle }{\sqrt{8}} \end{aligned}

כרגיל, בחירה זו אינה מוכתבת עלינו — אנחנו חופשיים להשתמש במרחב הקוד לקידוד Qubit-ים בכל דרך שנרצה. קידוד זה עקבי, עם זאת, עם הדוגמה של Circuit קידוד לקוד Steane בן 7 Qubit-ים מהשיעור הקודם.