CSS-конструкция семикубитного кода Стейна

Некоторые классические линейные коды непосредственно дают квантовые коды. Разберите пример такой конструкции и основные понятия классических линейных кодов.

(a) Линейный код $C$, кодирующий $k$ бит в $n$ бит, задаётся двоичной порождающей матрицей $G$ размера $n\times k$. Его $2^k$ кодовых слов имеют вид $Gx$, где столбец $x$ содержит $k$ бит; все операции выполняются по модулю 2. Для матрицы

$$G=\begin{pmatrix}1&0&0&0\\0&1&0&0\\0&0&1&0\\0&0&0&1\\0&1&1&1\\1&0&1&1\\1&1&0&1\end{pmatrix}$$

выпишите шестнадцать семибитных кодовых слов.

(b) Ошибки обнаруживаются проверками чётности. Для всех кодовых слов $x$ проверочная матрица $H$ размера $(n-k)\times n$ удовлетворяет $Hx=0$. Для данного кода возьмём

$$H=\begin{pmatrix}0&0&0&1&1&1&1\\0&1&1&0&0&1&1\\1&0&1&0&1&0&1\end{pmatrix}.$$

Проверьте $Hx=0$ для всех найденных слов и докажите $HG=0$.

(c) Ошибка моделируется прибавлением по модулю 2 случайной строки $e$ к кодовому слову $x$: $y=x+e$. Если $y$ не принадлежит коду, ошибка обнаруживается ненулевым синдромом $Hy=He$. Покажите, что при одной ошибке в позиции $j$ синдром $Hy$ — двоичная запись числа $j$, которая указывает исправляемый бит.

(d) Минимальное расстояние Хэмминга между кодовыми словами равно

$$d(C)=\min_{x,y\in C,\ x\ne y}d(x,y),$$

где $d(x,y)$ — число различающихся битов. Оно определяет число допускаемых ошибок инверсии битов. Найдите $d(C)$.

(e) Рассмотрим код $C^\perp$ с порождающей матрицей $G'=H^T$ и проверочной $H'=G^T$. Докажите, что он имеет параметры $n=7,k=3$ и что $C^\perp\subseteq C$.

(f) Докажите, что $\sum_{y\in C}(-1)^{x\cdot y}=|C|$ при $x\in C^\perp$, а при $x\notin C^\perp$ сумма равна нулю.

(g) Для $x\in C$ определим квантовое состояние

$$|\psi(x)\rangle=\frac1{\sqrt{|C^\perp|}}\sum_{y\in C^\perp}|x+y\rangle.$$

Явно выпишите $|\psi(0000000)\rangle$ и $|\psi(1111111)\rangle$.

(h) Пусть двоичные векторы $e_1,e_2$ длины $n$ указывают позиции битовых и фазовых ошибок соответственно. Предположим $d(e_1,0)\le1$, $d(e_2,0)\le1$. Покажите, что после ошибок состояние $|\psi(x)\rangle$ переходит в

$$\begin{aligned} |\psi_{b+p\,\mathrm{err}}\rangle={}&\frac1{\sqrt{|C^\perp|}}\sum_{y\in C^\perp}\\ &(-1)^{(x+y)\cdot e_2}|x+y+e_1\rangle. \end{aligned}$$

(i) Объясните, как схемой только из CNOT реализовать $|x\rangle|0\rangle\to|x\rangle|Hx\rangle$. Покажите, как при её применении к состоянию из (h) получить $e_1$. Поскольку $e_1$ содержит не более одной ошибки, после исправления получается

$$\begin{aligned} |\psi_{p\,\mathrm{err}}\rangle={}&\frac1{\sqrt{|C^\perp|}}\sum_{y\in C^\perp}\\ &(-1)^{(x+y)\cdot e_2}|x+y\rangle. \end{aligned}$$

(j) Найдите состояние после применения Адамара к каждому кубиту состояния из (i). С помощью подходящей проверочной матрицы — какой именно? — и результата (f) покажите, как определить $e_2$ и восстановить $|\psi(x)\rangle$.

В этой CSS-конструкции $C^\perp\subseteq C$, а проверка кода $C$ позволяет исправить битовую ошибку до Адамара и фазовую после Адамара. Поскольку битовые и фазовые ошибки порождают произвольную однокубитную ошибку, построенный квантовый код исправляет её.