CSS-коди

Класичні лінійні коди

Класичні коди виправлення помилок вперше почали вивчатись у 1940-х роках, і відтоді стало відомо багато різних кодів. Найпоширеніші та найуживаніші з них належать до категорії, відомої як лінійні коди. Зовсім скоро ми побачимо, що саме означає слово «лінійний» у цьому контексті, але дуже просто висловити суть лінійних кодів можна так: це стабілізаторні коди, які є класичними. CSS-коди — це, по суті, пари класичних лінійних кодів, об'єднаних для створення квантового коду виправлення помилок. Тож для подальшого обговорення нам потрібно розуміти кілька базових речей про класичні лінійні коди.

Нехай $\Sigma$ — двійковий алфавіт для всього подальшого обговорення. Коли ми кажемо класичний лінійний код, ми маємо на увазі непорожню множину $\mathcal{C}\subseteq\Sigma^n$ двійкових рядків довжини $n$ для деякого натурального числа $n$, яка повинна задовольняти лише одну базову властивість: якщо $u$ і $v$ — двійкові рядки з $\mathcal{C},$ то рядок $u\oplus v$ також належить $\mathcal{C}.$ Тут $u\oplus v$ означає побітовий виключний АБО рядків $u$ і $v,$ з яким ми неодноразово зустрічалися в курсі «Основи квантових алгоритмів».

По суті, коли ми називаємо класичний код виправлення помилок лінійним, ми розглядаємо двійкові рядки довжини $n$ як $n$-вимірні вектори з компонентами $0$ або $1$ і вимагаємо, щоб сам код утворював лінійний підпростір. Проте замість звичайного додавання векторів над дійсними або комплексними числами ми використовуємо додавання за модулем $2,$ яке є просто виключним АБО. Тобто якщо у нас є два кодових слова $u$ і $v,$ тобто $u$ і $v$ — двійкові рядки з $\mathcal{C},$ то $u + v$ за модулем 2, тобто $u\oplus v,$ теж повинно бути кодовим словом у $\mathcal{C}.$ Зверни увагу, що зокрема це твердження має бути справедливим навіть при $u = v.$ Це означає, що $\mathcal{C}$ обов'язково містить нульовий рядок $0^n,$ адже побітовий виключний АБО будь-якого рядка з самим собою дає нульовий рядок.

Приклад: 3-бітний код повторення

3-бітний код повторення — приклад класичного лінійного коду. Зокрема, $\mathcal{C} = \{000,111\},$ тож щодо умови лінійності є лише два можливих вибори для $u$ і два — для $v.$ Перебрати всі чотири пари і переконатися, що при виключному АБО ми завжди отримуємо кодове слово, — елементарно:

$$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]$. Це один із найперших класичних кодів виправлення помилок, що коли-небудь були відкриті; він складається з 16 двійкових рядків довжини 7. (Іноді під кодом Хеммінга $[7,4,3]$ розуміють код, де ці рядки взяті у зворотному порядку, але ми будемо вважати, що це код, що містить саме ті рядки, які показані нижче.)

$$\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$ біти (оскільки є $16 = 2^4$ кодових слів), і це код відстані $3$, тобто будь-які два різних кодових слова відрізняються в не менш ніж $3$ позиціях — щоб перетворити одне кодове слово на інше, потрібно перевернути не менше $3$ бітів. Те, що це код відстані $3$, означає, що він здатний виправляти до однієї помилки перевертання бітів.

Опис класичних лінійних кодів

Щойно наведені приклади — дуже прості приклади класичних лінійних кодів, але навіть код Хеммінга $[7,4,3]$ виглядає дещо загадковим, коли кодові слова просто перераховані. Існують кращі, ефективніші способи описати класичні лінійні коди, зокрема такі два.

1. Генератори. Один зі способів описати класичний лінійний код — навести мінімальний список кодових слів, що породжують код, тобто з яких, беручи всі можливі підмножини та застосовуючи XOR, можна отримати весь код.

   Детальніше: рядки $u_1,\ldots,u_m\in\Sigma^n$ породжують класичний лінійний код $\mathcal{C},$ якщо

   $$\mathcal{C} = \bigl\{\alpha_1 u_1 \oplus \cdots \oplus \alpha_m u_m\,:\,\alpha_1,\ldots,\alpha_m\in\{0,1\}\bigr\},$$

   де $\alpha u = u$ при $\alpha = 1$ і $\alpha u = 0^n$ при $\alpha = 0,$ а список називається мінімальним, якщо видалення будь-якого з рядків породжує менший код. Природний спосіб сприймати такий опис: множина $\{u_1,\ldots,u_m\}$ утворює базис для $\mathcal{C}$ як підпростору, де ми розглядаємо рядки як вектори з двійковими компонентами, маючи на увазі, що ми працюємо у векторному просторі з арифметикою за модулем $2.$

2. Перевірки парності. Інший природний спосіб описати класичний лінійний код — через перевірки парності, тобто мінімальний список двійкових рядків, за яким рядки коду — це рівно ті рядки, чий двійковий скалярний добуток з кожним із рядків перевірки парності дорівнює нулю. (Подібно до побітового виключного АБО, двійковий скалярний добуток зустрічався кілька разів у курсі «Основи квантових алгоритмів».)

   Тобто рядки $v_1,\ldots,v_r\in\Sigma^n$ є рядками перевірки парності для класичного лінійного коду $\mathcal{C},$ якщо

   $$\mathcal{C} = \bigl\{ u\in \Sigma^n\,:\, u\cdot v_1 = \cdots = u \cdot v_r = 0 \bigr\},$$

   а ця множина рядків є мінімальною, якщо видалення одного з них дає більший код. Ці рядки називають рядками перевірки парності, бо двійковий скалярний добуток $u$ і $v$ дорівнює нулю тоді й тільки тоді, коли біти $u$ на позиціях, де $v$ має одиниці, мають парний паритет. Тож щоб визначити, чи належить рядок $u$ коду $\mathcal{C},$ достатньо перевірити паритет певних підмножин бітів $u.$

   Важлива деталь: двійковий скалярний добуток — це не внутрішній добуток у формальному сенсі. Зокрема, якщо двійковий скалярний добуток двох рядків дорівнює нулю, це не означає, що вони ортогональні у звичному розумінні. Наприклад, двійковий скалярний добуток рядка $11$ з самим собою дорівнює нулю — тобто рядок перевірки парності класичного лінійного коду може сам бути кодовим словом.

Класичні лінійні коди над двійковим алфавітом завжди містять кількість рядків, що є степенем $2,$ — і для одного класичного лінійного коду, описаного двома зазначеними способами, завжди виконується $n = m + r.$ Зокрема, якщо є мінімальний набір із $m$ генераторів, то код кодує $m$ бітів і обов'язково матиме $2^m$ кодових слів; якщо є мінімальний набір із $r$ рядків перевірки парності, то кодових слів буде $2^{n-r}.$ Тобто кожен генератор подвоює розмір кодового простору, а кожен рядок перевірки парності зменшує його вдвічі.

Наприклад, 3-бітний код повторення є лінійним кодом, тому його можна описати обома способами. Зокрема, є лише один вибір генератора, що підходить: $111.$ Альтернативно, код можна описати двома рядками перевірки парності, наприклад $110$ і $011$ — що мають виглядати знайомо з попередніх обговорень цього коду — або взяти $110$ і $101,$ чи $101$ і $011.$ (Генератори і рядки перевірки парності зазвичай не є унікальними для даного класичного лінійного коду.)

Як другий приклад розглянемо код Хеммінга $[7,4,3].$ Ось один варіант списку генераторів, що підходить.

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

А ось один варіант списку перевірок парності для цього коду.

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

Тут, до речі, бачимо, що всі наші рядки перевірки парності самі є кодовими словами.

Остання зауважена щодо класичних лінійних кодів, що пов'язує їх із стабілізаторним формалізмом: рядки перевірки парності еквівалентні генераторам стабілізатора, що складаються лише з матриць Паулі $Z$ та одиничних. Наприклад, рядки перевірки парності $110$ і $011$ для 3-бітного коду повторення відповідають рівно генераторам стабілізатора $Z\otimes Z\otimes \mathbb{I}$ і $\mathbb{I}\otimes Z\otimes Z,$ що узгоджується з обговоренням операторів Паулі в попередньому уроці.

Означення CSS-кодів

CSS-коди — це стабілізаторні коди, отримані поєднанням певних пар класичних лінійних кодів. Для двох довільних класичних лінійних кодів це не завжди спрацює — між двома кодами має виконуватися певне співвідношення. Тим не менше ця конструкція відкриває безліч можливостей для квантових кодів виправлення помилок, частково спираючись на понад 75 років класичної теорії кодування.

У стабілізаторному формалізмі генератори стабілізатора, що містять лише матриці Паулі $Z$ та одиничні, еквівалентні перевіркам парності, як ми щойно спостерігали для 3-бітного коду повторення. Як ще один приклад розглянемо такі рядки перевірки парності для коду Хеммінга $[7,4,3].$

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

Ці рядки перевірки парності відповідають наступним генераторам стабілізатора (записаним без символів тензорного добутку), які ми отримуємо, замінюючи кожну $1$ на $Z$, а кожен $0$ — на $\mathbb{I}.$ Це три з шести генераторів стабілізатора 7-кубітного коду Стіна.

$$\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}$$

Назвемо $Z$-генераторами стабілізатора такі генератори стабілізатора, тобто ті, що містять лише тензорні множники Паулі $Z$ та одиничні — матриці Паулі $X$ і $Y$ у $Z$-генераторах стабілізатора ніколи не зустрічаються.

Можна також розглядати генератори стабілізатора, у яких як тензорні множники з'являються лише матриці Паулі $X$ та одиничні. Такі генератори стабілізатора можна розглядати як аналог $Z$-генераторів стабілізатора, з тією різницею, що вони описують перевірки парності в базисі $\{\vert+\rangle,\vert-\rangle\}$ замість стандартного базису. Генератори стабілізатора такого виду називаються $X$-генераторами стабілізатора — цього разу матриці Паулі $Y$ і $Z$ не допускаються.

Наприклад, розглянемо три генератори стабілізатора 7-кубітного коду Стіна, що залишились.

$$\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],$ що й $Z$-генератори стабілізатора, але тепер ми замінюємо $1$ на $X$ замість $Z.$ Код, що отримується лише з цих трьох генераторів стабілізатора, включає 16 станів, показаних нижче; їх отримуємо, застосовуючи операції Адамара до станів стандартного базису, що відповідають рядкам коду Хеммінга $[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-код — це стабілізаторний код, який можна виразити лише за допомогою $X$- і $Z$-генераторів стабілізатора.

Тобто CSS-коди — це стабілізаторні коди, для яких існують генератори стабілізатора, в яких матриці Паулі $Y$ не з'являються, а $X$ і $Z$ ніколи не зустрічаються в одному генераторі стабілізатора.

Щоб бути точним: за цим означенням CSS-кодом є такий код, для якого можна вибрати лише $X$- і $Z$-генератори стабілізатора, — але треба пам'ятати, що у виборі генераторів стабілізатора є свобода. Тому зазвичай для CSS-коду існуватимуть різні варіанти генераторів стабілізатора, що не є $X$- чи $Z$-генераторами стабілізатора (на додаток до хоча б одного варіанту, де вони є).

Ось дуже простий приклад CSS-коду, що містить і $Z$-генератор стабілізатора, і $X$-генератор стабілізатора:

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

Очевидно, що це CSS-код, адже перший генератор стабілізатора є $Z$-генератором, а другий — $X$-генератором. Звичайно, CSS-код повинен також бути дійсним стабілізаторним кодом — тобто генератори стабілізатора мають комутувати, утворювати мінімальний порожній набір і фіксувати принаймні один квантовий вектор стану. Для цього коду ці вимоги легко перевіряються. Як ми зазначили в попередньому уроці, кодовий простір цього коду — одновимірний простір, натягнутий на стан Белла $\vert\phi^+\rangle.$ Те, що обидва генератори стабілізатора фіксують цей стан, випливає з двох таких виразів для е-біта разом із інтерпретацією цих генераторів стабілізатора як перевірок парності в базисах $\{\vert 0\rangle, \vert 1\rangle\}$ і $\{\vert +\rangle, \vert -\rangle\}.$

$$\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}}$$

7-кубітний код Стіна — ще один приклад CSS-коду.

$$\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}$$

Тут маємо три $Z$-генератори стабілізатора і три $X$-генератори стабілізатора, і ми вже переконались, що це дійсний стабілізаторний код.

Ще один приклад — 9-кубітний код Шора.

$$\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}$$

Тут маємо шість $Z$-генераторів стабілізатора і лише два $X$-генератори стабілізатора. Це цілком допустимо — між двома типами генераторів не потрібні баланс або симетрія (хоча вони часто є).

Знову наголосимо: CSS-коди обов'язково мають бути дійсними стабілізаторними кодами, і зокрема кожен $Z$-генератор стабілізатора повинен комутувати з кожним $X$-генератором стабілізатора. Тому не кожна сукупність $X$- і $Z$-генераторів стабілізатора визначає дійсний CSS-код.

Виявлення та виправлення помилок

Щодо виявлення та виправлення помилок, CSS-коди загалом мають схожу характеристику з 9-кубітним кодом Шора: помилки $X$ і $Z$ можна виявляти та виправляти повністю незалежно; $Z$-генератори стабілізатора описують код, що захищає від перевертань бітів, а $X$-генератори стабілізатора описують код, що незалежно захищає від перевертань фази. Це працює, тому що $Z$-генератори стабілізатора обов'язково комутують із $Z$-помилками, а також із $Z$-операціями, що застосовуються як корекції, — тобто вони абсолютно нечутливі до тих і інших; аналогічно для $X$-генераторів стабілізатора, помилок і корекцій.

Як приклад розглянемо 7-кубітний код Стіна.

$$\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]$ для помилок перевертання фази. Те, що $X$- і $Z$-генератори стабілізатора комутують, — мабуть, щаслива обставина, адже без цього це не був би дійсний стабілізаторний код. Але насправді відомо багато прикладів класичних лінійних кодів, що дають дійсний стабілізаторний код при аналогічному використанні.

Загалом, припустимо, що маємо CSS-код, для якого $Z$-генератори стабілізатора дозволяють виправляти до $j$ помилок перевертання бітів, а $X$-генератори стабілізатора — до $k$ помилок перевертання фази. Наприклад, $j = 1$ і $k = 1$ для коду Стіна, оскільки код Хеммінга $[7,4,3]$ може виправити одне перевертання біта. Тоді, завдяки дискретизації помилок, цей CSS-код може виправляти будь-яку помилку на числі кубітів до мінімуму з $j$ і $k.$ Це пояснюється тим, що при вимірюванні синдрому довільна помилка на цій кількості кубітів ефективно колапсує імовірнісно до деякої комбінації $X$-помилок, $Z$-помилок або обох — а потім $X$-помилки та $Z$-помилки виявляються й виправляються незалежно.

Підсумовуючи: якщо є два класичних лінійних коди (або два примірники одного класичного лінійного коду), що сумісні — тобто визначають $X$- і $Z$-генератори стабілізатора, що комутують, — то CSS-код, який ми отримуємо їх поєднанням, успадковує властивості виправлення помилок цих двох кодів у щойно описаному сенсі.

Зверни увагу, що є й ціна: ми не можемо кодувати стільки кубітів, скільки бітів закодовано двома класичними кодами. Це пояснюється тим, що загальна кількість генераторів стабілізатора для CSS-коду є сумою кількостей перевірок парності двох класичних лінійних кодів, а кожен генератор стабілізатора зменшує розмірність кодового простору вдвічі. Наприклад, код Хеммінга $[7,4,3]$ дозволяє кодувати чотири класичних біти, адже для нього є лише три рядки перевірки парності, тоді як 7-кубітний код Стіна кодує лише один кубіт, оскільки має шість генераторів стабілізатора.

Кодові простори CSS-кодів

Останнє, що ми розглянемо в обговоренні CSS-кодів, — це кодові простори цих кодів. Це дасть нам можливість детальніше дослідити співвідношення, яке повинно виконуватися між двома класичними лінійними кодами, щоб вони були сумісними — тобто могли бути об'єднані для утворення CSS-коду.

Розглянемо довільний CSS-код на $n$ кубітах і нехай $z_1, \ldots, z_s \in \Sigma^n$ — $n$-бітні рядки перевірки парності, що відповідають $Z$-генераторам стабілізатора цього коду. Це означає, що класичний лінійний код, описаний лише $Z$-генераторами стабілізатора і названий нами $\mathcal{C}_Z,$ має такий вигляд.

$$\mathcal{C}_Z = \bigl\{ u \in \Sigma^n \,:\, u \cdot z_1 = \cdots = u \cdot z_s = 0 \bigr\}$$

Іншими словами, класичний лінійний код $\mathcal{C}_Z$ містить усі рядки, двійковий скалярний добуток яких з кожним із рядків перевірки парності $z_1, \ldots, z_s$ дорівнює нулю.

Аналогічно, нехай $x_1,\ldots,x_t\in\Sigma^n$ — $n$-бітні рядки перевірки парності, що відповідають $X$-генераторам стабілізатора нашого коду. Тоді класичний лінійний код, що відповідає $X$-генераторам стабілізатора, має такий вигляд.

$$\mathcal{C}_X = \bigl\{ u \in \Sigma^n \,:\, u \cdot x_1 = \cdots = u \cdot x_t = 0 \bigr\}$$

Тому самі лише $X$-генератори стабілізатора описують код, схожий на цей, але в базисі $\{\vert {+}\rangle,\vert {-}\rangle\}$ замість стандартного базису.

Тепер введемо два нових класичних лінійних коди, похідних від тих самих рядків $z_1,\ldots,z_s$ і $x_1,\ldots,x_t,$ але де ці рядки беруться як генератори, а не рядки перевірки парності. Зокрема, отримуємо два такі коди.

$$\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}$$

Вони відомі як дуальні коди раніше визначених кодів: $\mathcal{D}_Z$ — дуальний код до $\mathcal{C}_Z,$ а $\mathcal{D}_X$ — дуальний код до $\mathcal{C}_X.$ Чому ці дуальні коди є важливими, наразі може бути не очевидним, але вони виявляються досить важливими з кількох причин, включно з двома, що пояснюються в наступних абзацах.

По-перше, умови, які мають виконуватися для двох класичних лінійних кодів $\mathcal{C}_Z$ і $\mathcal{C}_X,$ щоб вони були сумісними — тобто могли бути об'єднані для утворення CSS-коду, — можна описати просто через дуальні коди. А саме: має виконуватися $\mathcal{D}_Z\subseteq\mathcal{C}_X,$ або еквівалентно — $\mathcal{D}_X\subseteq\mathcal{C}_Z.$ Іншими словами, дуальний код $\mathcal{D}_Z$ містить рядки, що відповідають $Z$-генераторам стабілізатора, і їхнє входження до $\mathcal{C}_X$ еквівалентне тому, що двійковий скалярний добуток кожного з цих рядків із рядками, що відповідають $X$-генераторам стабілізатора, дорівнює нулю. А це, у свою чергу, еквівалентне тому, що кожен $Z$-генератор стабілізатора комутує з кожним $X$-генератором стабілізатора. Аналогічно, змінивши ролі $X$- і $Z$-генераторів стабілізатора і почавши від вкладення $\mathcal{D}_X\subseteq\mathcal{C}_Z,$ можна дійти того самого висновку.

По-друге, звертаючись до дуальних кодів, можна легко описати кодові простори заданого CSS-коду. Зокрема, кодовий простір натягнутий на вектори такого вигляду.

$$\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{(для всіх $u\in\mathcal{C}_Z$)}$$

Іншими словами, ці вектори — рівномірні суперпозиції над рядками дуального коду $\mathcal{D}_X$ коду, що відповідає $X$-генераторам стабілізатора, зсунутими на (тобто побітово XOR-нутими з) рядки коду $\mathcal{C}_Z,$ що відповідає $Z$-генераторам стабілізатора. Для ясності: різні вибори зсуву — рядка $u$ у цьому виразі — можуть давати той самий вектор. Тобто ці стани не обов'язково всі різні, але в сукупності вони натягують увесь кодовий простір.

Ось інтуїтивне пояснення того, чому такі вектори і належать кодовому простору, і натягують його. Розглянемо стандартний базисний стан $\vert u\rangle$ на $n$ кубітах для деякого довільного $n$-бітного рядка $u$ і припустимо, що ми проєктуємо цей стан на кодовий простір. Тобто нехай $\Pi$ — проєктор на кодовий простір нашого CSS-коду; розглянемо вектор $\Pi\vert u\rangle.$ Є два випадки:

• Випадок 1: $u\in\mathcal{C}_Z.$ Це означає, що кожен $Z$-генератор стабілізатора нашого CSS-коду діє тривіально на $\vert u\rangle.$ $X$-генератори стабілізатора, з іншого боку, кожен просто перевертають деякі біти $\vert u\rangle.$ Зокрема, для кожного генератора $v$ із $\mathcal{D}_X$ $X$-генератор стабілізатора, що відповідає $v,$ перетворює $\vert u\rangle$ на $\vert u\oplus v\rangle.$ Характеризуючи проєктор $\Pi$ як середнє по елементах стабілізатора (як ми бачили в попередньому уроці), отримуємо таку формулу:

  $$\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\notin\mathcal{C}_Z.$ Це означає, що хоча б одна з перевірок парності, що відповідають $Z$-генераторам стабілізатора, не виконується, тобто $\vert u\rangle$ є $-1$ власним вектором принаймні одного з $Z$-генераторів стабілізатора. Кодовий простір CSS-коду є перетином $+1$ власних просторів генераторів стабілізатора. Отже, будучи $-1$ власним вектором принаймні одного з $Z$-генераторів стабілізатора, $\vert u\rangle$ ортогональний до кодового простору:

  $$\Pi\vert u\rangle = 0.$$

І тепер, перебираючи всі $n$-бітні рядки $u,$ відкидаючи ті, для яких $\Pi\vert u\rangle = 0,$ і нормуючи решту, ми отримуємо вектори, описані вище, що демонструє: вони натягують кодовий простір.

Можна також скористатися симетрією між $X$- і $Z$-генераторами стабілізатора, щоб описати кодовий простір аналогічним, але дещо іншим способом. Зокрема, це простір, натягнутий на вектори такого вигляду.

$$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{(для $u\in\mathcal{C}_X$)}$$

По суті, $X$ і $Z$ замінені місцями скрізь, де вони з'являються, — але потрібно також замінити стандартний базис на базис $\{\vert+\rangle,\vert-\rangle\},$ саме тому і включені операції Адамара.

Як приклад розглянемо 7-кубітний код Стіна. Рядки перевірки парності для $X$- і $Z$-генераторів стабілізатора однакові: $1111000,$ $1100110$ і $1010101.$ Тому коди $\mathcal{C}_X$ і $\mathcal{C}_Z$ збігаються; обидва рівні коду Хеммінга $[7,4,3].$

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

Дуальні коди $\mathcal{D}_X$ і $\mathcal{D}_Z$ тому також збігаються. Маємо три генератори, тому отримуємо вісім рядків.

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

Всі ці рядки містяться в коді Хеммінга $[7,4,3],$ тому умова CSS виконується: $\mathcal{D}_Z \subseteq \mathcal{C}_X,$ або еквівалентно $\mathcal{D}_X \subseteq \mathcal{C}_Z.$

Оскільки $\mathcal{D}_X$ містить рівно половину всіх рядків $\mathcal{C}_Z,$ при виборі $u\in\mathcal{C}_Z$ можна отримати лише два різних вектори $\vert u\oplus \mathcal{D}_X\rangle.$ Це очікувано, адже 7-кубітний код Стіна має двовимірний кодовий простір. Два отримані таким чином стани можна використати для кодування логічних станів $\vert 0\rangle$ і $\vert 1\rangle$ так.

$$\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}$$

Як завжди, цей вибір не є обов'язковим — ми вільні використовувати кодовий простір для кодування кубітів як завгодно. Втім, це кодування узгоджується з прикладом кола кодування для 7-кубітного коду Стіна з попереднього уроку.