Стабілізаторні коди

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

Визначення стабілізаторних кодів

$n$-кубітний стабілізаторний код задається списком $n$-кубітних операцій Паулі, $P_1,\ldots,P_r.$ Ці операції в даному контексті називаються генераторами стабілізатора, і вони повинні задовольняти трьом умовам.

1. Генератори стабілізатора попарно комутують.

   $$P_j P_k = P_k P_j \qquad \text{(для всіх $j,k\in\{1,\ldots,r\}$)}$$

2. Генератори стабілізатора утворюють мінімальну породжувальну множину.

   $$P_k \notin \langle P_1,\ldots,P_{k-1},P_{k+1},\ldots,P_r\rangle \qquad \text{(для всіх $k\in\{1,\ldots,r\}$)}$$

3. Існує хоча б один вектор квантового стану, який фіксується всіма генераторами стабілізатора.

   $$-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle$$

   (Не одразу очевидно, що існування вектора квантового стану $\vert\psi\rangle$, який фіксується всіма генераторами, тобто $P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle,$ еквівалентне умові $-\mathbb{I}^{\otimes n} \notin \langle P_1,\ldots, P_r\rangle,$ — але це дійсно так, і ми побачимо чому трохи пізніше в цьому уроці.)

Припускаючи, що такий список $P_1,\ldots,P_r$ задано, кодовий простір, визначений цими генераторами стабілізатора, — це підпростір $\mathcal{C}$, який містить усі $n$-кубітні вектори квантових станів, що фіксуються всіма $r$ генераторами стабілізатора.

$$\mathcal{C} = \bigl\{ \vert\psi\rangle \,:\, P_1 \vert\psi\rangle = \cdots = P_r \vert\psi\rangle = \vert\psi\rangle \bigr\}$$

Саме ці вектори квантових станів у підпросторі є тими, що можна розглядати як допустимі кодування квантових станів. Сам процес кодування ми обговоримо далі.

Нарешті, стабілізатор коду, визначеного генераторами $P_1, \ldots, P_r,$ — це множина, породжена цими операціями:

$$\langle P_1,\ldots,P_r\rangle.$$

Природний спосіб мислити про стабілізаторний код — розглядати генератори стабілізатора як спостережувані величини, а результати вимірювань, пов'язаних з ними, колективно інтерпретувати як синдром помилки. Допустимі кодування — це $n$-кубітні вектори квантових станів, для яких результати вимірювань (як власні значення) гарантовано рівні $+1.$ Будь-який інший синдром, де хоча б один результат дорівнює $-1,$ свідчить про те, що помилку виявлено.

Незабаром ми розглянемо кілька прикладів, але спочатку варто зробити кілька зауважень щодо трьох умов на генератори стабілізатора.

Перша умова є природною з огляду на інтерпретацію генераторів як спостережуваних величин: вона означає, що порядок вимірювань не має значення — спостережувані комутують, а отже, і вимірювання теж. Це накладає певні алгебраїчні обмеження на стабілізаторні коди, які є важливими для їхньої роботи.

Друга умова вимагає, щоб генератори стабілізатора утворювали мінімальну породжувальну множину, тобто видалення будь-якого з них давало б менший стабілізатор. Строго кажучи, ця умова не є суттєвою для роботи стабілізаторних кодів в операційному сенсі — і, як ми побачимо в наступному уроці, іноді має сенс розглядати множини генераторів стабілізатора, які насправді не задовольняють цю умову. Однак для аналізу стабілізаторних кодів і пояснення їхніх властивостей ми будемо вважати цю умову виконаною. Коротко кажучи, ця умова гарантує, що кожна спостережувана, яку ми вимірюємо для отримання синдрому помилки, додає інформацію про можливі помилки, а не є надлишковою і не дає результати, які можна вивести з інших вимірювань генераторів стабілізатора.

Третя умова вимагає, щоб існував хоча б один ненульовий вектор, який фіксується всіма генераторами стабілізатора, — це еквівалентно тому, що $-\mathbb{I}^{\otimes n}$ не міститься в стабілізаторі. Потреба в цій умові пов'язана з тим, що насправді можна вибрати мінімальну породжувальну множину $n$-кубітних операцій Паулі, які попарно комутують, і при цьому жоден ненульовий вектор не буде фіксований всіма цими операціями. Нас не цікавлять «коди», в яких немає допустимих кодувань, тому ми виключаємо цю можливість, включаючи дану умову до визначення.

Приклади

Наведемо кілька прикладів стабілізаторних кодів для малих значень $n.$ Більше прикладів, у тому числі таких, де $n$ може бути значно більшим, ми побачимо в наступному уроці.

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

3-бітний код повторення є прикладом стабілізаторного коду, де генераторами стабілізатора є $Z \otimes Z \otimes \mathbb{I}$ та $\mathbb{I} \otimes Z \otimes Z.$

Легко перевірити, що ці два генератори задовольняють необхідні умови. По-перше, генератори $Z \otimes Z \otimes \mathbb{I}$ та $\mathbb{I} \otimes Z \otimes Z$ комутують між собою.

$$(Z \otimes Z \otimes \mathbb{I})(\mathbb{I} \otimes Z \otimes Z) = Z \otimes \mathbb{I} \otimes Z = (\mathbb{I} \otimes Z \otimes Z)(Z \otimes Z \otimes \mathbb{I})$$

По-друге, ми маємо мінімальну породжувальну множину (що в цьому випадку очевидно).

$$\begin{aligned} Z \otimes Z \otimes \mathbb{I} \notin \langle\mathbb{I} \otimes Z \otimes Z\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, \mathbb{I} \otimes Z \otimes Z\}\\[1mm] \mathbb{I} \otimes Z \otimes Z \notin \langle Z \otimes Z \otimes \mathbb{I}\rangle & = \{\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z \otimes Z \otimes \mathbb{I}\} \end{aligned}$$

По-третє, ми вже знаємо, що $\vert 000\rangle$ та $\vert 111\rangle,$ а також будь-яка їхня лінійна комбінація, фіксуються обома операціями $Z \otimes Z \otimes \mathbb{I}$ та $\mathbb{I} \otimes Z \otimes Z.$ Як альтернативу, можна скористатися еквівалентною умовою з визначення.

$$-\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\notin \langle Z \otimes Z \otimes \mathbb{I}, \mathbb{I} \otimes Z \otimes Z\rangle = \{ \mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}, Z\otimes Z\otimes\mathbb{I}, Z\otimes\mathbb{I}\otimes Z, \mathbb{I}\otimes Z\otimes Z \}$$

Перевірити ці умови для більш складних стабілізаторних кодів може бути значно важче.

Модифікований 3-бітний код повторення

У попередньому уроці ми бачили, що 3-бітний код повторення можна модифікувати так, щоб він захищав від помилок фазового перекидання, а не бітового. Як стабілізаторний код, цей новий код легко описати: його генераторами стабілізатора є $X \otimes X \otimes \mathbb{I}$ та $\mathbb{I} \otimes X \otimes X.$

Цього разу генератори стабілізатора відповідають спостережуваним $X\otimes X$, а не $Z\otimes Z,$ тобто вони фактично є перевірками парності в базисі плюс/мінус, а не в стандартному базисі. Три необхідні умови на генератори стабілізатора легко перевіряються — аналогічно до звичайного 3-бітного коду повторення.

9-кубітний код Шора

Ось 9-кубітний код Шора, який також є стабілізаторним кодом, виражений через генератори стабілізатора.

$$\begin{gathered} Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes Z \otimes Z\\[1mm] X \otimes X \otimes X \otimes X \otimes X \otimes X \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\\[1mm] \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}\otimes X \otimes X \otimes X \otimes X \otimes X \otimes X \end{gathered}$$

У цьому випадку ми фактично маємо три копії 3-бітного коду повторення — по одній для кожного з трьох блоків по три кубіти, — а також два останніх генератори стабілізатора, які нагадують за формою схему для виявлення фазових перекидань у цьому коді.

Інший спосіб осмислити два останніх генератори стабілізатора: вони мають таку ж форму, як і для 3-бітного коду повторення для фазових перекидань, але замість $X$ підставлено $X\otimes X\otimes X,$ — що узгоджується з тим, що $X\otimes X\otimes X$ відповідає операції $X$ на логічних кубітах, закодованих за допомогою 3-бітного коду повторення.

Перш ніж перейти до інших прикладів, варто зазначити, що символи тензорного добутку часто опускають при описі стабілізаторних кодів через списки генераторів, оскільки це зазвичай полегшує читання і дозволяє краще побачити їхні закономірності. Наприклад, ті самі генератори стабілізатора для 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}$$

7-кубітний код Стіна

Ось ще один приклад стабілізаторного коду, відомий як 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}$$

Поки що просто зазначимо, що це є допустимим стабілізаторним кодом. Перші три генератори стабілізатора явно комутують між собою, оскільки $Z$ комутує з собою, а одинична матриця комутує з усім — аналогічна ситуація і для трьох останніх генераторів. Залишається перевірити, що якщо взяти один із $Z$-генераторів стабілізатора (тобто один із перших трьох) та один із $X$-генераторів (тобто один із останніх трьох), то ці два генератори комутують; для цього можна перебрати всі 9 можливих пар. В усіх цих випадках матриці $X$ та $Z$ Паулі завжди збігаються на одній позиції парну кількість разів, тому два генератори комутуватимуть — так само, як $X\otimes X$ та $Z\otimes Z$ комутують. Це також мінімальна породжувальна множина, і вона визначає нетривіальний кодовий простір — ці факти пропонуємо тобі осмислити самостійно.

7-кубітний код Стіна схожий на 9-кубітний код Шора тим, що кодує один кубіт і дозволяє виправляти довільну помилку на одному кубіті, але вимагає лише 7 кубітів, а не 9.

5-кубітний код

Сім — це не найменша кількість кубітів, необхідна для кодування одного кубіта з захистом від довільної помилки на одному кубіті — ось стабілізаторний код, який робить це лише за допомогою 5 кубітів.

$$\begin{array}{ccccc} X & Z & Z & X & \mathbb{I} \\[1mm] \mathbb{I} & X & Z & Z & X \\[1mm] X & \mathbb{I} & X & Z & Z \\[1mm] Z & X & \mathbb{I} & X & Z \\[1mm] \end{array}$$

Цей код зазвичай називають 5-кубітним кодом. Це найменша кількість кубітів у квантовому коді виправлення помилок, яка дозволяє виправляти довільну помилку на одному кубіті.

Одновимірні стабілізаторні коди

Ось ще один приклад стабілізаторного коду, хоча він фактично не кодує жодного кубіта: кодовий простір є одновимірним. Проте за визначенням це все одно є допустимим стабілізаторним кодом.

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

Зокрема, кодовий простір — це одновимірний простір, натягнутий на e-біт $\vert\phi^+\rangle.$

Ось пов'язаний приклад стабілізаторного коду, кодовий простір якого — одновимірний простір, натягнутий на GHZ-стан $(\vert 000\rangle + \vert 111\rangle)/\sqrt{2}.$

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

Розмірність кодового простору

Припустимо, що у нас є стабілізаторний код, описаний $n$-кубітними генераторами стабілізатора $P_1,\ldots,P_r.$ Мабуть, перше питання, що виникає про цей код: «Скільки кубітів він кодує?»

Відповідь проста. Якщо $n$-кубітні генератори стабілізатора $P_1, \ldots, P_r$ задовольняють три вимоги визначення (а саме: генератори попарно комутують, утворюють мінімальну породжувальну множину, і кодовий простір непорожній), то кодовий простір цього стабілізаторного коду має розмірність $2^{n-r},$ тобто за допомогою цього коду можна закодувати $n-r$ кубітів.

Інтуїтивно кажучи, у нас є $n$ кубітів для кодування, і кожен генератор стабілізатора фактично «забирає один кубіт» з погляду кількості кубітів, які ми можемо закодувати. Зауважимо, що це не стосується того, які помилки і скільки їх можна виявити або виправити — це лише твердження про розмірність кодового простору.

Наприклад, для 3-бітного коду повторення та його модифікованої версії для помилок фазового перекидання маємо $n=3$ кубіти та $r=2$ генератори стабілізатора, тому кожен із цих кодів кодує 1 кубіт. Для іншого прикладу розглянемо 5-кубітний код: маємо 5 кубітів і 4 генератори стабілізатора, тому кодовий простір знову має розмірність 2, тобто один кубіт можна закодувати за допомогою цього коду. Нарешті, код із генераторами стабілізатора $X\otimes X$ та $Z\otimes Z$ має одновимірний кодовий простір, натягнутий на стан $\vert\phi^+\rangle,$ — що узгоджується з $n=2$ кубітами та $r=2$ генераторами стабілізатора.

Тепер подивимося, як можна довести цей факт. Перший крок — зауважити, що оскільки генератори стабілізатора комутують і кожна операція Паулі є своїм власним оберненим, кожен елемент стабілізатора можна подати у вигляді добутку

$$P_1^{a_1} \cdots P_r^{a_r},$$

де $a_1,\ldots,a_r\in\{0,1\}.$ Еквівалентно, кожен елемент стабілізатора отримується множенням деякої підмножини генераторів стабілізатора. Насправді кожен елемент стабілізатора подається в такому вигляді єдиним чином завдяки умові про те, що $\{P_1,\ldots,P_r\}$ є мінімальною породжувальною множиною.

Далі визначимо $\Pi_k$ як проєктор на простір власних векторів $+1$ оператора $P_k$ для кожного $k\in\{1,\ldots,r\}.$ Ці проєктори можна отримати усередненням відповідних операцій Паулі з одиничною операцією таким чином:

$$\Pi_k = \frac{\mathbb{I}^{\otimes n} + P_k}{2}$$

Кодовий простір $\mathcal{C}$ — це підпростір усіх векторів, що фіксуються всіма $r$ генераторами стабілізатора $P_1,\ldots,P_r,$ або еквівалентно — всіма $r$ проєкторами $\Pi_1,\ldots,\Pi_r.$

Оскільки генератори стабілізатора попарно комутують, проєктори $\Pi_1,\ldots,\Pi_r$ теж комутують. Це дозволяє скористатися фактом з лінійної алгебри: добуток цих проєкторів є проєктором на перетин підпросторів, що відповідають окремим проєкторам. Іншими словами, добуток $\Pi_1\cdots\Pi_r$ є проєктором на кодовий простір $\mathcal{C}.$

Тепер розкриємо добуток $\Pi_1\cdots\Pi_r$ за формулами для цих проєкторів і отримаємо такий вираз:

$$\Pi_1\cdots\Pi_r = \biggl(\frac{\mathbb{I}^{\otimes n} + P_1}{2}\biggr)\cdots\biggl(\frac{\mathbb{I}^{\otimes n} + P_r}{2}\biggr) = \frac{1}{2^r}\sum_{a_1,\ldots,a_r \in \{0,1\}} P_1^{a_1}\cdots P_r^{a_r}$$

Словами: проєктор на кодовий простір стабілізаторного коду як матриця дорівнює середньому по всіх елементах стабілізатора цього коду.

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

$$\operatorname{dim}(\mathcal{C}) = \operatorname{Tr}(\Pi_1\cdots\Pi_r) = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r})$$

Обчислимо цей вираз, скориставшись кількома базовими фактами.

• Маємо $P_1^0 \cdots P_r^0 = \mathbb{I}^{\otimes n},$ тому

  $$\operatorname{Tr}(P_1^{0}\cdots P_r^{0}) = 2^n.$$

• При $(a_1,\ldots,a_r) \neq (0,\ldots,0)$ добуток $P_1^{a_1}\cdots P_r^{a_r}$ повинен бути рівним $\pm 1$ разів деякій операції Паулі — але ми не можемо отримати $\mathbb{I}^{\otimes n},$ оскільки це суперечило б мінімальності множини $\{P_1,\ldots,P_r\},$ і не можемо отримати $-\mathbb{I}^{\otimes n},$ оскільки це забороняє третя умова на генератори стабілізатора. Тому, оскільки слід кожної не-одиничної операції Паулі дорівнює нулю, маємо

  $$\operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) = 0.$$

Таким чином, розмірність кодового простору дорівнює $2^{n-r},$ як і стверджувалося:

$$\begin{aligned} \operatorname{dim}(\mathcal{C}) & = \frac{1}{2^r} \sum_{a_1,\ldots,a_r \in \{0,1\}} \operatorname{Tr}(P_1^{a_1}\cdots P_r^{a_r}) \\ & = \frac{1}{2^r} \operatorname{Tr}(P_1^{0}\cdots P_r^{0}) \\ & = 2^{n-r}. \end{aligned}$$

Зауважимо, що тепер ми бачимо: припущення про те, що $-\mathbb{I}^{\otimes n}$ не міститься в стабілізаторі, означає, що кодовий простір обов'язково містить хоча б один вектор квантового стану. Це пояснюється тим, що, як ми щойно перевірили, це припущення означає, що розмірність кодового простору дорівнює $2^{n-r},$ а вона не може бути нулем. Обернена імплікація є тривіальною: якщо $-\mathbb{I}^{\otimes n}$ міститься в стабілізаторі, то кодовий простір не може містити жодного вектора квантового стану, оскільки жоден ненульовий вектор не фіксується цією операцією.

Операції Кліффорда та кодування

Далі ми коротко обговоримо, як кодуються кубіти за допомогою стабілізаторних кодів, але спершу потрібно ввести операції Кліффорда.

Операції Кліффорда

Операції Кліффорда — це унітарні операції над будь-якою кількістю кубітів, які можна реалізувати квантовими схемами з обмеженим набором вентилів:

• вентилі Адамара
• вентилі $S$
• вентилі CNOT

Зверни увагу, що вентилі $T$ не включені, а також вентилі Тоффолі та Фредкіна. Мало того, що ці вентилі відсутні в списку — їх насправді неможливо реалізувати через перелічені вентилі; вони не є операціями Кліффорда. Операції Паулі, однак, є операціями Кліффорда, оскільки їх можна реалізувати за допомогою послідовностей вентилів Адамара та $S$.

Це простий спосіб визначити операції Кліффорда, але він не пояснює, чому вони так визначені і що особливого в цьому конкретному наборі вентилів. Справжня причина такого визначення полягає в тому, що з точністю до глобальних фазових множників операції Кліффорда — це саме ті унітарні операції, які завжди перетворюють операції Паулі на операції Паулі за допомогою кон'югування. Точніше, $n$-кубітна унітарна операція $U$ еквівалентна операції Кліффорда з точністю до фазового множника тоді і тільки тоді, коли для кожної $n$-кубітної операції Паулі $P$ маємо

$$U P U^{\dagger} = \pm Q$$

для деякої $n$-кубітної операції Паулі $Q.$

(Зауважимо, що неможливо мати $U P U^{\dagger} = \alpha Q$ при $\alpha\notin\{+1,-1\}$, якщо $U$ є унітарним, а $P$ і $Q$ — операціями Паулі. Це випливає з того, що матриця в лівій частині рівняння є одночасно унітарною та ермітовою, і лише $\alpha\in\{+1,-1\}$ дозволяє правій частині теж бути унітарною та ермітовою.)

Перевірити описану вище властивість кон'югування нескладно, коли $U$ є вентилем Адамара, $S$ або CNOT. Зокрема, для вентилів Адамара це робиться легко:

$$H X H^{\dagger} = Z, \qquad H Y H^{\dagger} = -Y, \qquad H Z H^{\dagger} = X,$$

і для вентилів $S$:

$$S X S^{\dagger} = Y, \qquad S Y S^{\dagger} = -X, \qquad S Z S^{\dagger} = Z.$$

Для вентилів CNOT потрібно перевірити 15 не-одиничних операцій Паулі на двох кубітах. Звичайно, їх можна перевіряти по одній — але зв'язки між вентилями CNOT і вентилями $X$ та $Z$ (у вигляді схем), наведені в попередньому уроці, разом із правилами множення матриць Паулі дають зручний обхідний шлях до того ж висновку.

Як тільки ми знаємо, що властивість кон'югування виконується для вентилів Адамара, $S$ і CNOT, можна одразу зробити висновок, що вона виконується і для схем, складених із цих вентилів, — тобто для всіх операцій Кліффорда.

Довести, що зв'язок працює в зворотньому напрямку — тобто що якщо задана унітарна операція $U$ задовольняє властивість кон'югування для операцій Паулі, то її можна реалізувати (з точністю до глобальної фази) лише за допомогою вентилів Адамара, $S$ і CNOT — складніше. У цьому уроці цього пояснювати не будемо, але це справді так.

Операції Кліффорда не є універсальними для квантових обчислень; на відміну від універсальних наборів квантових вентилів, за допомогою операцій Кліффорда неможливо апроксимувати довільні унітарні операції з будь-якою заданою точністю. Більше того, для фіксованого $n$ існує лише скінченна кількість $n$-кубітних операцій Кліффорда (з точністю до фазових множників). Виконання операцій Кліффорда над станами стандартного базису з наступними вимірюваннями у стандартному базисі також не дозволяє виконувати обчислення, недоступні класичним алгоритмам, — оскільки такі обчислення можна ефективно моделювати класично. Цей факт відомий як теорема Готтесмана–Кніла.

Кодувальники для стабілізаторних кодів

Стабілізаторний код визначає кодовий простір певної розмірності, і ми вільні використовувати цей кодовий простір як завгодно — ніщо не змушує нас кодувати кубіти в цей кодовий простір якимось конкретним чином. Проте завжди можна використати операцію Кліффорда як кодувальник, якщо ми так вирішимо. Якщо говорити точніше: для будь-якого стабілізаторного коду, що дозволяє кодувати $m$ кубітів у $n$ кубітів, існує $n$-кубітна операція Кліффорда $U$ така, що для будь-якого $m$-кубітного вектора квантового стану $\vert\phi\rangle$ виконується

$$\vert\psi\rangle = U \bigl(\vert 0^{n-m} \rangle \otimes \vert \phi\rangle\bigr)$$

— вектор квантового стану в кодовому просторі нашого коду, який можна інтерпретувати як кодування $\vert\phi\rangle.$

Це зручно, тому що операції Кліффорда відносно прості порівняно з довільними унітарними операціями, і існують способи оптимізувати їхню реалізацію за допомогою технік, схожих на ті, що застосовуються в доведенні теореми Готтесмана–Кніла. Завдяки цьому схеми для кодування станів з використанням стабілізаторних кодів ніколи не потребують надто великого розміру. Зокрема, завжди можна виконати кодування для $n$-кубітного стабілізаторного коду за допомогою операції Кліффорда, що потребує $O(n^2/\log(n))$ вентилів. Це тому, що кожну операцію Кліффорда на $n$ кубітах можна реалізувати схемою такого розміру.

Наприклад, ось кодувальник для 7-кубітного коду Стіна. Це справді операція Кліффорда, і, як виявляється, цей кодувальник навіть не потребує вентилів $S$.

Виявлення помилок

Для $n$-кубітного стабілізаторного коду, заданого генераторами стабілізатора $P_1,\ldots, P_r,$ виявлення помилок відбувається таким чином.

Для виявлення помилок всі генератори стабілізатора вимірюються як спостережувані величини. Є $r$ генераторів стабілізатора, а отже — $r$ результатів вимірювання, кожен з яких дорівнює $+1$ або $-1$ (або бінарному значенню, якщо ми вирішимо асоціювати $0$ з $+1$, а $1$ з $-1$, відповідно). Сукупність $r$ результатів ми інтерпретуємо як вектор чи рядок — синдром. Синдром $(+1,\ldots,+1)$ означає, що помилок не виявлено, тоді як хоча б одне значення $-1$ десь у синдромі вказує на виявлену помилку.

Припустимо зокрема, що $E$ — це $n$-кубітна операція Паулі, що представляє гіпотетичну помилку. (До речі, ми розглядаємо лише операції Паулі як помилки, тому що дискретизація помилок працює однаково для довільних стабілізаторних кодів, як і для 9-кубітного коду Шора.) Існують три випадки, що визначають, чи виявляється $E$ як помилка.

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

1. Операція $E$ пропорційна елементу стабілізатора.

   $$E = \pm Q \; \text{for some}\; Q \in \langle P_1,\ldots,P_r\rangle$$

   У цьому разі $E$ має комутувати з кожним генератором стабілізатора, тому ми отримуємо синдром $(+1,\ldots,+1).$ Це означає, що $E$ не виявляється як помилка.

2. Операція $E$ не пропорційна жодному елементу стабілізатора, але попри це комутує з кожним генератором стабілізатора.

   $$E\neq \pm Q\; \text{for} \; Q \in \langle P_1,\ldots,P_r\rangle, \;\text{but}\; E P_k = P_k E \;\text{for every}\; k\in\{1,\ldots,r\}$$

   Це помилка, яка нетривіально змінює вектори в кодовому просторі. Але оскільки $E$ комутує з кожним генератором стабілізатора, синдром залишається $(+1,\ldots,+1),$ тож $E$ не виявляється кодом.

3. Операція $E$ антикомутує хоча б з одним генератором стабілізатора.

   $$P_k E = -E P_k \; \text{for at least one} \; k\in\{1,\ldots,r\}$$

   Синдром відрізняється від $(+1,\ldots,+1),$ тому помилка $E$ виявляється кодом.

У першому випадку помилка $E$ не є проблемою, бо ця операція нічого не робить з векторами в кодовому просторі, хіба що може додати незначну глобальну фазу: $E \ket{\psi} = \pm\ket{\psi}$ для кожного закодованого стану $\ket{\psi}.$ По суті, це насправді не помилка — будь-яка нетривіальна дія $E$ відбувається поза кодовим простором — тому добре, що $E$ не виявляється як помилка: робити нічого не потрібно.

Другий випадок інтуїтивно є поганим. Саме антикомутація помилки з генератором стабілізатора спричиняє появу $-1$ десь у синдромі, сигналізуючи про помилку, — але в цьому випадку цього не відбувається. Тож маємо помилку $E$, яка дійсно нетривіально змінює вектори в кодовому просторі, але код її не виявляє. Наприклад, для 3-бітного коду повторення операція $E = X\otimes X\otimes X$ потрапляє саме в цю категорію.

Те, що така помилка $E$ неодмінно змінює деякі вектори кодового простору нетривіально, можна обґрунтувати так. З припущення, що $E$ комутує з $P_1,\ldots,P_r$, але не пропорційна жодному елементу стабілізатора, можна зробити висновок: якби ми додали $E$ як генератор стабілізатора разом із $P_1,\ldots,P_r$, то отримали б новий, коректний стабілізаторний код. Проте кодовий простір цього нового коду має лише половину розмірності початкового кодового простору, з чого випливає, що дія $E$ на початковий кодовий простір не може бути пропорційною тотожній операції.

У третьому з трьох випадків — коли помилка $E$ антикомутує хоча б з одним генератором стабілізатора — синдром містить хоча б одне значення $-1$, що вказує на щось неправильне. Як вже зазначалося, синдром загалом не ідентифікує $E$ однозначно, тому все ще необхідно обирати корекційну операцію для кожного синдрому — і вона може або виправити помилку $E$, або ні. Ми обговоримо цей крок незабаром, в останній частині уроку.

Відстань стабілізаторного коду

Говорячи про відстань стабілізаторного коду, ми маємо на увазі мінімальну вагу операції Паулі $E$, що потрапляє до другої вищезазначеної категорії — тобто нетривіально змінює кодовий простір, але код цього не виявляє. Коли стабілізаторний код називають $[[n,m,d]]$-кодом (з подвійними квадратними дужками), це означає таке:

1. Кодові слова мають довжину $n$ кубітів,
2. код дозволяє кодувати $m$ кубітів, і
3. відстань коду дорівнює $d.$

Як приклад розглянемо 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}$$

Цей код має відстань 3, і ось як це можна обґрунтувати.

Спочатку розглянемо будь-яку операцію Паулі $E$ з вагою не більше 2 і припустимо, що вона комутує з усіма шістьма генераторами стабілізатора. Ми дійдемо висновку, що $E$ має бути тотожною операцією, яка (як завжди) є елементом стабілізатора. Це покаже, що відстань коду строго більша за 2. Припустимо зокрема, що $E$ має вигляд

$$E = P \otimes Q \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I} \otimes \mathbb{I}$$

де $P$ і $Q$ — можливо нетотожні матриці Паулі. Це лише один випадок, і аналогічний аргумент необхідно повторити для всіх інших можливих розташувань нетотожних матриць Паулі серед тензорних множників $E$, але суть аргументу однакова для всіх можливих розташувань.

Операція $E$ комутує з усіма шістьма генераторами стабілізатора, тому вона комутує й з цими двома зокрема:

$$\begin{gathered} Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z \otimes \mathbb{I} \otimes Z\\[1mm] X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \otimes \mathbb{I} \otimes X \end{gathered}$$

Тензорний множник $Q$ у нашій помилці $E$ збігається з тотожною матрицею в обох цих генераторах стабілізатора (саме тому їх і було обрано). Оскільки в крайніх правих 5 позиціях $E$ стоять тотожні матриці, робимо висновок: $P$ має комутувати з $X$ і $Z$, бо інакше $E$ антикомутувала б з одним із двох генераторів. Проте єдина матриця Паулі, що комутує одночасно з $X$ і $Z$, — це тотожна матриця, тому $P = \mathbb{I}.$

Знаючи це, можна обрати ще два генератори стабілізатора, що мають $X$ і $Z$ на другій позиції зліва, і дійти аналогічного висновку: $Q = \mathbb{I}.$ Отже, $E$ є тотожною операцією.

Таким чином, жодна помилка з вагою не більше 2 не може лишитися непоміченою цим кодом, якщо тільки вона не є тотожною операцією (яка входить до стабілізатора і тому насправді не є помилкою). З іншого боку, існують операції Паулі ваги 3, що комутують з усіма шістьма генераторами стабілізатора, але не пропорційні жодному елементу стабілізатора — наприклад, $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes X\otimes X\otimes X$ та $\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes\mathbb{I}\otimes Z\otimes Z\otimes Z.$ Це підтверджує, що відстань коду дорівнює 3, як і стверджувалося.

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

Остання тема цього уроку — виправлення помилок для стабілізаторних кодів. Як і раніше, припустимо, що маємо стабілізаторний код, заданий $n$-кубітними генераторами стабілізатора $P_1, \ldots, P_r.$

Усі $n$-кубітні операції Паулі, що є можливими помилками для станів, закодованих цим кодом, розбиваються на рівні групи відповідно до синдрому, який вони спричиняють. Є $2^r$ різних синдромів і $4^n$ операцій Паулі, тобто кожному синдрому відповідає $4^n/2^r$ операцій Паулі. Будь-яка з цих помилок може бути відповідальна за відповідний синдром.

Проте серед $4^n/2^r$ операцій Паулі, що спричиняють кожний синдром, деякі слід вважати еквівалентними. Зокрема, якщо добуток двох операцій Паулі пропорційний елементу стабілізатора, то ці дві операції фактично еквівалентні як помилки.

Інакше кажучи: якщо ми застосовуємо корекційну операцію $C$, щоб виправити помилку $E$, то така корекція успішна тоді й тільки тоді, коли композиція $CE$ пропорційна елементу стабілізатора. Оскільки стабілізатор містить $2^r$ елементів, кожна корекційна операція $C$ виправляє $2^r$ різних помилок Паулі. Таким чином, залишається $4^{n-r}$ нееквівалентних класів операцій Паулі як помилок, що відповідають кожному можливому синдрому.

Це означає, що якщо $n\neq r$ (тобто якщо кодовий простір нетривіальний, одновимірний), то виправити кожну помилку, виявлену стабілізаторним кодом, принципово неможливо. Натомість потрібно обрати лише одну корекційну операцію для кожного синдрому, сподіваючись виправити лише один клас еквівалентних помилок, що спричиняють цей синдром.

Одна природна стратегія вибору корекційної операції для кожного синдрому — обирати операцію Паулі найменшої ваги, яка як помилка спричиняє цей синдром. Може існувати кілька операцій, що одночасно є найлегшими для даного синдрому, — тоді можна обрати будь-яку з них. Ідея в тому, що операції Паулі меншої ваги є більш вірогідними поясненнями виміряного синдрому. Проте для деяких моделей шуму це може бути не так, і альтернативною стратегією є обчислення найбільш імовірної помилки для даного синдрому на основі обраної моделі шуму. У цьому уроці ми спростимо підхід і розглядатимемо лише корекції найменшої ваги.

Для стабілізаторного коду з відстанню $d$ стратегія вибору корекційної операції як операції Паулі найменшої ваги, сумісної з виміряним синдромом, завжди дозволяє виправляти помилки з вагою строго менше половини $d$, тобто з вагою не більше $(d-1)/2.$ Це показує, зокрема, що 7-кубітний код Стіна може виправити будь-яку помилку Паулі ваги 1, а завдяки дискретизації помилок це означає, що код Стіна може виправляти довільну помилку на одному кубіті.

Щоб зрозуміти, як це працює, розглянемо діаграму нижче. Коло зліва представляє всі операції Паулі, що дають синдром $(+1,\ldots,+1)$, — тобто синдром, що свідчить про відсутність помилок. Серед цих операцій є елементи стабілізатора (або, точніше, операції пропорційні елементам стабілізатора), а також нетривіальні помилки, що якось змінюють кодовий простір, але не виявляються кодом. За визначенням відстані, кожна операція Паулі в цій категорії має вагу не менше $d$, оскільки $d$ визначається як мінімальна вага таких операцій.

Коло справа представляє операції Паулі, що дають інший синдром $s\neq(+1,\ldots,+1)$, включно з помилкою $E$ з вагою строго менше $d/2$, яку ми розглянемо.

Корекційна операція $C$, обрана для синдрому $s$, — це операція Паулі найменшої ваги з множини, представленої колом справа на діаграмі (або будь-яка з них у разі рівності). Отже, може бути $C = E$, але не обов'язково. Що можна стверджувати напевно — це те, що вага $C$ не може перевищувати вагу $E$, оскільки $C$ має мінімальну вагу серед операцій у цій множині, а отже, вага $C$ строго менша за $d/2.$

Тепер розглянемо, що відбувається, коли корекційну операцію $C$ застосовують до стану, отриманого після дії помилки $E$. Якщо початкове кодування було $\vert\psi\rangle$, то отримуємо $CE\vert\psi\rangle.$ Наша мета — показати, що $CE$ пропорційне елементу стабілізатора, що означатиме успішну корекцію і (з точністю до глобальної фази) повернення початкового закодованого стану $\vert\psi\rangle.$

По-перше, оскільки $E$ і $C$ спричиняють однаковий синдром, композиція $CE$ має комутувати з кожним генератором стабілізатора. Зокрема, якщо $P_k$ — будь-який генератор стабілізатора, то маємо

$$P_k E = \alpha E P_k \quad\text{and}\quad P_k C = \alpha C P_k$$

для одного й того самого значення $\alpha\in\{+1,-1\},$ оскільки це $k$-й елемент синдрому $s$, що генерується як $C$, так і $E$. Отже,

$$P_k (CE) = \alpha C P_k E = \alpha^2 (CE) P_k = (CE) P_k,$$

тобто $P_k$ комутує з $CE$. Ми показали, що $CE$ потрапляє до кола зліва на діаграмі, оскільки породжує синдром $(+1,\ldots,+1).$

По-друге, вага композиції $CE$ не перевищує суму ваг $C$ і $E$ — що випливає з розгляду добутків операцій Паулі — а отже, вага $CE$ строго менша за $d.$ Це означає, що $CE$ пропорційне елементу стабілізатора нашого коду, що й треба було показати. Обираючи корекційні операції як представників найменшої ваги з множин помилок, що породжують кожен синдром, ми гарантовано виправляємо будь-які помилки Паулі з вагою менше половини відстані коду.

Є, однак, одна проблема. Для стабілізаторних кодів загалом обчислення операції Паулі найменшої ваги для даного синдрому є обчислювально складним завданням. (До речі, це справедливо навіть для класичних кодів, які в цьому контексті можна розглядати як стабілізаторні коди, де в генераторах стабілізатора зустрічаються лише матриці $\mathbb{I}$ і $Z$.) Тому, на відміну від кроку кодування, операції Кліффорда цього разу нам не допоможуть.

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