Классические и квантовые коды

Примеры классических кодов.

$$M_n$$ типа $$(n,1)$$ ; для него $$d(M_n)=n$$.$$M_n=\{(\underbrace{0,\dots,0}_{n}), \(\underbrace{1,\dots,1}_{n})\}.$$

Это самая простая схема кодирования. Повторяем каждый бит много раз, а после каждой операции восстанавливаем кодовое слово, заменяя значения битов на то, которое встречается чаще.

Эта серия кодов, как будет показано ниже, не обобщается на квантовый случай.

Проверка на четность. Код $$M_n^{(2)}$$ типа $$(n,\,n-1)$$, для него $$d(M^{(2)}_n)\double=2$$. Состоит из всех четных слов, т.е. слов, содержащих четное число единиц.

Код Хэмминга $$H_r$$. Это код типа $$(n,\, n-r)$$, где число $$n=2^r-1$$.

Слова из $$\cb^n$$ — это последовательности битов $$x=(x_\alpha:\alpha=1,\dots,n)$$. Номер каждого бита можно записать в двоичной системе как $$\alpha\double=(\alpha_1,\dots,\alpha_n)$$. Введем множество контрольных сумм$$\hskip2cm \mu_j(x)=\sum_{\alpha:\alpha_j=1}^{}x_\alpha$$ (суммирование здесь понимается по модулю 2). На рисунке выделены множества битов, входящих в контрольные суммы при $$r=3$$ (полезно видеть в этой картинке трехмерный куб).

Множество слов кода Хэмминга задается условием равенства всех контрольных сумм 0 (т.е. оно является подпространством по модулю 2). Можно показать, что для кода Хэмминга $$d=3$$.

Линейные коды.

Пусть есть множество $$N=\cb^n=\FF_2^n$$. Линейный код $$M\subseteq N$$ — это линейное подпространство. Линейные коды удобно задавать двойственным базисом (как множество решений системы линейных уравнений).

Пример 14.2. Код Хэмминга, рассмотренный выше, задается как множество решений системы уравнений$$\left\{\begin{aligned} x_{100}+x_{101}+x_{110}+x_{111}=\mu_1(x)=0,\\ x_{010}+x_{011}+x_{110}+x_{111}=\mu_2(x)=0,\\ x_{001}+x_{011}+x_{101}+x_{111}=\mu_3(x)=0. \end{aligned} \right.$$ Поэтому код Хэмминга образует подпространство коразмерности 3.

Квантовые коды.

Будем давать определения аналогично классическому случаю. Набору условных вероятностей $$\bigl(p(y|x): x\in N,\,y\double\in N'\bigr)$$ соответствует физически реализуемое преобразование матриц плотности $$T\colon\LL(\calN)\to\LL(\calN')$$. Имеет смысл и упрощенная модель: по аналогии с множеством переходов $$E\subseteq N\times N'$$ определим пространство ошибок — произвольное линейное пространство $$\calE\subseteq\LL(\calN,\calN')$$. (Таким образом, квантовая ошибка — это любой линейный оператор $$\calN\to\calN'$$ ). Есть и прямой аналог множества $$E(n,k)$$. Рассмотрим $$\calN\double=\calN'=\BB^{\otimes n}$$. Через $$\calE[A]$$ обозначим те ошибки, которые действуют на q-битах из множества $$A$$ и не действуют на остальных q-битах, т.е. $$\calE[A]=\LL(\BB^{\otimes A})\otimes I_{\BB^{\otimes[n]\setminus A}}$$ (здесь и далее $$[n]$$ обозначает множество всех q-битов $$\{1,\dots, n\}$$ ). Тогда полагаем$$\calE(n,k)=\sum_{|A|\le k}^{} \calE[A].$$ (Здесь стоит просто сумма подпространств, не прямая.) В дальнейшем нас будет интересовать именно устойчивость к ошибкам из $$\calE(n,k)$$.

Но перед тем, как заняться изучением кодов, устойчивых к ошибкам из $$\calE(n,k)$$, рассмотрим аналог модели независимо распределенных ошибок в квантовом случае и его связь с ошибками из $$\calE(n,k)$$.

Модель независимых ошибок в квантовом случае.

Предположим, что на каждый q-бит действует одно и то же малое возмущение. Это означает, что на матрицу плотности рассматриваемой системы из $$n$$ q-битов действует преобразование $$T=(I+R)^{\otimes n}$$, где $$R$$ — "мало". В классическом случае малое возмущение означает малую вероятность ошибки. В квантовом случае малое возмущение меняет матрицы плотности "не слишком сильно". Чтобы придать этому выражению точный смысл, нужно ввести норму на матрицах плотности, характеризующую их близость, а затем — такую норму на преобразованиях матриц плотности, чтобы выполнялось условие: малое по норме преобразование переводит матрицу плотности в близкую к ней.

Начнем с того, что выясним, какие нормы пригодны для характеризации близости матриц плотности. Матрица плотности, как мы помним из лекции 9, задает вероятностное распределение на чистых состояниях. Вероятностные распределения естественно сравнивать в $$\ell^1$$ -норме: если $$\boldsymbol p=(p_1,\dots,p_n)$$, $$\boldsymbol q=(q_1,\dots,q_n)$$ — два распределения, то мерой их различия считаем $$\sum_{j=1}^{n}|p_j-q_j|=\|\boldsymbol p-\boldsymbol q\|_1$$. Дадим определение аналогичной нормы для матриц плотности.

Определение 14.4. Следовая норма оператора $$A\in\LL(\calN)$$ равна$$\begin{equation}\label{след} \|A\|_\trr=Tr\left(\sqrt{A^\dagger A}\right). \end{equation}$$

Для эрмитова оператора следовая норма — это сумма модулей собственных чисел.

Задача 14.1. Проверьте, что (14.3) действительно определяет норму. Докажите, что$$\begin{equation}\label{trace-norm-sup-def} \|A\|_\trr=\sup\limits_{X\ne0}\frac{|Tr AX|}{\|X\|} \end{equation}$$ ( $$\|X\|$$ — операторная норма, см. опр. 7.2).

Задача 14.2. Проверьте выполнение следующих свойств следовой нормы:

Следующая лемма показывает, почему можно рассматривать следовую норму для матриц плотности как аналог $$\ell^1$$ -нормы для вероятностных распределений.

Лемма 14.2. Пусть $$\calN=\bigoplus_{j}\calN_j$$ — разложение пространства $$\calN$$ в прямую сумму взаимно ортогональных подпространств. Тогда для любой пары матриц плотности $$\rho$$, $$\gamma$$$$\sum_{j} |\PP(\rho,\calN_j)-\PP(\gamma,\calN_j)|\ \le\ \|\rho-\gamma\|_\trr\hskip2pt.$$

Доказательство. Левую часть этого неравенства можно представить в виде $$Tr((\rho-\gamma)B)$$, где $$B=\sum_{j}(\pm\Pi_{\calN_j})$$. Ясно, что $$\|B\|\le 1$$. Теперь применим представление следовой нормы в виде (14.4).

Теперь кажется естественным определить норму преобразования матриц плотности аналогично операторной норме$$\begin{equation}\label{Tsup1} \|T\|_1=\sup_{X\ne0}\frac{\|TX\|_\trr}{\|X\|_\trr} \end{equation}$$ и мерить этой нормой малость возмущения. Однако использование нормы (14.5) оказывается неудобным, так как она не согласована с тензорным произведением. Поясним это подробнее. Чтобы иметь оценку, аналогичную оценке (14.2) в классическом случае, мы должны написать разложение$$\begin{equation}\label{разложение-тензорной-степени} T=\left(I+R\right)^{\otimes n}=I+\sum_{|A|\le k}^{} R^{\otimes A}\otimes I_{[n]\setminus A}+ \underbrace{\sum\limits_{|A|>k}^{} R^{\otimes A}\otimes I_{[n]\setminus A}}_{P} \end{equation}$$ и оценить норму $$P$$ при условии $$\|P\|_1<\delta$$. Если бы выполнялось неравенство $$\|T\otimes R\|_1\leq \|T\|_1\|R\|_1$$, можно было бы буквально повторить оценку (14.2). Однако это неравенство не всегда выполняется.

Пример 14.3. Рассмотрим преобразование$$T\colon |j\rangle\langle k|\mapsto|k\rangle\langle j|\quad (j,k=0,1).$$ Очевидно, что $$\|T\|_1=1$$, однако $$\|T\otimes I_{\LL(\BB)}\|_1=2$$. (Подействуйте преобразованием $$T\otimes I_{\LL(\BB)}$$ на оператор $$X=\sum_{j,k}|j,j\rangle\langle k,k|$$.)

Оказывается (ниже это будет доказано), что патология примера 14.3 имеет ограничение по размерности. А именно, если $$\dim\calG\geq\dim\calN$$, то $$\|T\otimes I_{\LL(\calG)}\|_1=\|T\|_\trn$$, где величина $$\|T\|_\trn$$ от $$\calG$$ не зависит. Прежде чем доказывать это утверждение, посмотрим на его следствия.

Во-первых, ясно, что определенная таким образом величина $$\|T\|_\trn$$ является нормой.

Во-вторых, поскольку следовая норма мультипликативна относительно тензорного умножения, то $$\|T\otimes R\|_1\geq\|T\|_1\|R\|_1$$. Поэтому $$\|T\|_\trn\geq\|T\|_1$$.

В-третьих, из определения следует, что $$\|TR\|_1\leq\|T\|_1\|R\|_1$$, поэтому имеем такие неравенства$$\begin{equation}\label{tensor-inequalities} \|T\|_1\|R\|_1\leq\|T\otimes R\|_1=\|(T\otimes I)(I\otimes R)\|_1\leq \|T\otimes I\|_1\|I\otimes R\|_1. \end{equation}$$ Из этих неравенств следует мультипликативность нормы $$\|\cdot\|_\trn$$ относительно тензорного умножения.

Чтобы доказать приведенное выше свойство норм $$\|T\otimes I\|_1$$, дадим другое определение величины $$\|T\|_\trn$$.

Определение 14.5. Рассмотрим представления $$T\colon \LL(\calN)\to\LL(\calN')$$ в виде $$T=Tr_\calF A\cdot B^\dagger$$. Здесь $$A\cdot B^\dagger$$ обозначает преобразование $$X\mapsto AXB^\dagger$$, а $$A,B\in\LL(\calN,\calN'\otimes\calF)$$, где $$\calF$$ — произвольное унитарное пространство размерности не меньшей, чем $$(\dim\calN)(\dim\calN')$$. Тогда $$\|T\|_\trn$$ — точная нижняя грань чисел вида $$\|A\|\:\|B\|$$ (это операторные нормы) по всем представлениям указанного вида.

Замечание. Условие $$\dim\calF\ge(\dim\calN)(\dim\calN')$$ гарантирует, что существует хотя бы одно представление $$T=Tr_\calF A_0\cdot B_0^\dagger$$. Для минимизации произведения $$\|A\|\:\|B\|$$ достаточно рассматривать операторы с нормами $$\|A\|\le\|A_0\|$$ и $$\|B\|\le\|B_0\|$$, поэтому инфимум достигается в силу компактности. То, что он не зависит от размерности $$\calF$$, вытекает из следующей теоремы.

Теорема 14.1. Если $$\dim\calG\geq\dim\calN$$, то $$\|T\|_\trn=\|T\otimes I_{\LL(\calG)}\|_1 $$.

Доказательство. Пусть $$TX=Tr_\calF AXB^\dagger$$. Тогда, используя свойства следовой нормы из задачи 14.2, получаем$$\begin{equation*} \|(T\otimes I_{\LL(\calG)})X\|_\trr= \|Tr_\calF(A\otimes I_{\calG})X(B^\dagger\otimes I_{\calG})\|_\trr\leq\\ \leq \|(A\otimes I_{\calG})X(B^\dagger\otimes I_{\calG})\|_\trr\leq \|A\|\:\|B\|\:\|X\|_\trr. \end{equation*}$$

Поэтому $$\|T\|_\trn\geq\|T\otimes I_{\LL(\calG)}\|_1$$.

Доказать неравенство в обратную сторону несколько сложнее. Без уменьшения общности, $$\|T\|_\trn=1$$. Инфимум в определении 14.5 достигается при $$\|A\|=\|B\|=1$$.

Покажем сначала, что существуют три матрицы плотности $$\rho,\gamma\double\in\LL(\calN)$$ и $$\tau\in\LL(\calF)$$, такие что $$Tr_{\calN'}(A\rho A^\dagger)=Tr_{\calN'}(B\gamma B^\dagger)=\tau$$. Пусть$$\begin{align*} \calK=\Ker(A^\dagger A-I_\calN), \calL=\Ker(B^\dagger B-I_\calN),\\ E=\Bigl\{ Tr_{\calN'}(A\rho A^\dagger):\rho\in\DD(\calK) \Bigr\}, F=\Bigl\{ Tr_{\calN'}(B\gamma B^\dagger):\gamma\in\DD(\calL) \Bigr\}, \end{align*}$$ где $$\DD(\calL)$$ обозначает множество матриц плотности на пространстве $$\calL$$. Тогда $$E,F\subseteq\DD(\calF)$$, поэтому в качестве $$\tau$$ годится любой элемент из $$E\cap F$$.

Докажем, что $$E\cap F\not=\emptyset$$. Так как $$E$$ и $$F$$ — компактные выпуклые множества, достаточно доказать, что не существует разделяющей их гиперплоскости. Другими словами, нет такого эрмитова оператора $$Z\in\LL(\calF)$$, что $$Tr XZ>Tr YZ$$ для любых $$X\in E$$, $$Y\in F$$. А это, в свою очередь, следует из минимальности величины $$\|A\|\,\|B\|$$ по отношению к преобразованию$$A\mapsto(I_{\calN'}\otimes e^{-tZ})\,A,\quad\ B\mapsto(I_{\calN'}\otimes e^{tZ})\,B,$$ где $$t$$ положительно, но мало.

Итак, пусть $$Tr_{\calN'}(A\rho A^\dagger)=Tr_{\calN'}(B\gamma B^\dagger)=\tau \in\DD(\calF)$$, где $$\rho,\gamma\double\in\DD(\calN)$$. Представим $$\rho$$ и $$\gamma$$ в виде $$\rho=Tr_\calG\Bigl(|\xi\rangle\langle\xi|\Bigr)$$, $$\gamma=Tr_\calG\Bigl(|\eta\rangle\langle\eta|\Bigr)$$, где $$|\xi\rangle,|\eta\rangle\in\calN\otimes\calG$$ — единичные векторы. Здесь мы используем условие $$\dim\calG\geq\dim\calN$$ и утверждение 9.1. Положим $$X=|\xi\rangle\langle\eta|$$. Очевидно, что $$\|X\|_\trr=1$$.

Докажем, что $$\|(T\otimes I_{\LL(\calG)})X\|_\trr\geq 1$$. Обозначим$$X'=(T\otimes I_{\LL(\calG)})X, \qquad \ket{\xi'}=(A\otimes I_\calG)\ket\xi, \quad\ \ket{\eta'}=(B\otimes I_\calG)\ket\eta,$$ тогда$$X'=Tr_\calF(\ket{\xi'}\bra{\eta'}),\qquad Tr_{\calN'\otimes\calG}(\ket{\xi'}\bra{\xi'})= Tr_{\calN'\otimes\calG}(\ket{\eta'}\bra{\eta'})=\tau.$$ Отсюда, во-первых, следует, что векторы $$\ket{\xi'}$$ и $$\ket{\eta'}$$ имеют единичную длину. Во-вторых, найдется унитарный оператор $$U$$ на пространстве $$\calN'\otimes\calG$$, такой что $$(U\otimes I_\calF)\ket{\xi'}=\ket{\eta'}$$ (это утверждение из задачи 9.3). Следовательно,$$\|X'\|_\trr\ge \frac{|Tr UX'|}{\|U\|} = \left| Tr\big((U\otimes I_\calF)\ket{\xi'}\bra{\eta'}\big) \right| = \left| Tr(\ket{\eta'}\bra{\eta'}) \right|=1.$$

Теперь можно оценить остаточный член $$P$$ в формуле (14.6), почти дословно повторяя рассуждения в классическом случае. Если $$\|R\|_1<\delta$$, то $$\|R\|_\trn<C\delta$$, где $$C$$ — константа (все нормы эквивалентны, причем множитель ограничен размерностью пространства; $$R$$ действует на пространстве матриц плотности одного q-бита). Используя мультипликативность нормы $$\|\cdot\|_\trn$$, заключаем, что$$\|P\|_1\leq\|P\|_\trn=o(\delta^k).$$ Поэтому будем пренебрегать всеми слагаемыми из $$P$$, а действие всех остальных слагаемых будем учитывать. Преобразования $$R^{\otimes A}$$ имеют вид $$R^{\otimes A}\rho=\sum\limits_{i}^{} X_i\rho Y_i^\dagger$$, где $$X_i,\, Y_i\in \calE(A)$$ ; символически это можно записать так: $$R^{\otimes A}\in \calE(A)\cdot\calE^\dagger(A)$$. Сумма преобразований $$\sum_{|A|\le k}^{} R_1^{\otimes A}\otimes I_{[n]\setminus A}$$ лежит в $$\calE(n,k)\cdot\calE^\dagger(n,k)$$. Таким образом, мы приходим к выводу, что нужно рассматривать ошибки из $$\calE(n,k)$$.

Основные определения и простейшие следствия.

Следующее определение дает в квантовом случае формальное выражение требования "различные состояния переходят в различные состояния" (это необходимое условие возможности восстановления исходных состояний физически реализуемым преобразованием).

Определение 14.6. Квантовый код (подпространство $$\calM\subseteq\calN$$ ) исправляет ошибки из $$\calE\subseteq\LL(\calN,\calN')$$, если$$\begin{equation}\label{ортворт1} \forall\, \ket{\xi_1},\ket{\xi_2}\in\calM\space\forall\, X,Y\in\calE\: \left(\langle \xi_2|\xi_1\rangle =0\right) \Rightarrow \left(\langle \xi_2|Y^\dagger X|\xi_1\rangle=0 \right). \end{equation}$$

Определение 14.7. Физически реализуемое преобразование$$P\colon\LL(\calN')\to\LL(\calM)$$ называется исправляющим (для кода $$\calM$$ и пространства ошибок $$\calE$$ ), если$$\forall\,T\in \calE\cdot\calE^\dagger\: \exists\, c=c(T)\: \forall\,\rho\in\LL(\calM)\: \bigl(PT\rho=c(T)\rho\bigr).$$ Если при этом $$T$$ сохраняет след, то $$c(T)=1$$.

Теорема 14.2. Если код $$\calM$$ исправляет ошибки из $$\calE$$, то исправляющее преобразование существует.

Доказательство будет дано ниже. Обратное утверждение доказано в [4].

Пример 14.4. Тривиальный код типа $$(n,m)$$: пусть $$\calM= \BB^{\otimes m}\double\otimes\ket{0^{n-m}}$$, а $$\calE=\calE[m+1,\dots,n]$$, т.е. для кодирования используются первые $$m$$ q-битов, а ошибки действуют на остальные q-биты. Условие (14.8), очевидно, выполнено. В качестве исправляющего преобразования можно взять $$P=I_{\LL(\BB^{\otimes m})}\otimes R$$, где $$R\colon X\mapsto(Tr X)\ket{0^{n-m}}\bra{0^{n-m}}$$. Преобразование $$P$$ реализуется очень просто: выбрасываем последние $$n-m$$ q-битов и заменяем их на новые q-биты в состоянии $$\ket{0}$$. Практической пользы от такого кода, конечно, мало. Интересно, однако, что любой квантовый код, исправляющий ошибки, в определенном смысле похож на тривиальный (см. лемму 14.3 ниже).

Пример 14.5. Рассмотрим квантовый аналог кода с повторением. Пусть пространство $$\calM=\CC(\ket{0,\dots,0},\ket{1,\dots,1})$$. Рассмотрим два состояния $$\ket{\xi_1}=\ket{0,\dots,0}+\ket{1,\dots,1}$$ и $$\ket{\xi_2}=\ket{0,\dots,0}-\ket{1,\dots,1}$$. Ошибку выберем так: $$X=\id$$, $$Y=\sz[1]$$. Очевидно, что $$X,Y\in\calE(n,1)$$. При этом $$Y\ket{\xi_2}=X\ket{\xi_1}$$, что противоречит определению кода, исправляющего ошибки. Мы видим, что код с произвольно большим повторением не защищает даже от одной ошибки.

Ошибки вида $$\sx[1]$$ называются классическими, а ошибки вида $$\sz[1]$$ называются фазовыми.

В определении 14.6 речь шла только о парах ортогональных состояний. Давайте посмотрим, что получается на произвольных парах. Зафиксируем $$X,Y\in\calE$$ и обозначим $$Z=Y^\dagger X$$. Оказывается, что$$\begin{equation}\label{код-сохр-скаляр-произв} \forall\, \ket{\xi_1},\ket{\xi_2}\in\calM \: \langle \xi_2|Z|\xi_1\rangle =c(Z) \langle \xi_2|\xi_1\rangle, \end{equation}$$ где $$c(Z)$$ — некоторое комплексное число, не зависящее от $$\ket{\xi_1},\ket{\xi_2}$$. Действительно, пусть $$\ket{\eta_1},\dots, \ket{\eta_m}$$ — ортонормированный базис пространства $$\calM$$. По определению 14.6 $$\langle \eta_j|Z|\eta_k\rangle =0$$ при $$j\ne k$$, а $$\langle\eta_j|Z|\eta_j\rangle$$ не зависит от $$j$$, так как$$\langle\eta_j|Z|\eta_j\rangle - \langle\eta_k|Z|\eta_k\rangle = \langle\eta_j-\eta_k|Z|\eta_j+\eta_k\rangle + \langle\eta_k|Z|\eta_j\rangle - \langle\eta_j|Z|\eta_k\rangle =0.$$ (Все три слагаемых в правой части равенства равны нулю, так как входящие в них пары векторов ортогональны.)

Заметим, что если $$X,Y\in\calE(n,k)$$, то $$Z= Y^\dagger X\in\calE(n,2k)$$.

Определение 14.8. Код $$\calM$$ обнаруживает ошибки из $$\calE'\subseteq\LL(\calN)$$, если$$\forall\,\ket{\xi_1},\ket{\xi_2}\in\calM\: \forall\, Z\in\calE'\: \langle \xi_2|Z|\xi_1\rangle = c(Z)\langle \xi_2|\xi_1\rangle.$$ Кодовым расстоянием называется наименьшее число $$d=d(\calM)$$, при котором код не обнаруживает ошибки из $$\calE(n,d)$$.

Таким образом, код исправляет $$k$$ ошибок, если $$2k<d(\calM)$$.

Теперь мы перейдем к доказательству теоремы 14.2.

Лемма 14.3. Пусть квантовый код $$\calM\subseteq\calN$$ исправляет ошибки из $$\calE\subseteq\LL(\calN,\calN')$$. Тогда существует унитарное пространство $$\calF$$, изометрическое вложение $$V\colon\calM\otimes\calF\to\calN'$$ и линейное отображение $$f\colon\calE\double\to\calF$$, такие что$$\begin{equation}\label{встроенная-ошибка} \forall\,\ket{\xi} \in\calM\:\forall\,X\in\calE\: X\ket{\xi}=V\bigl(\ket{\xi}\otimes\ket{f(X)}\bigr). \end{equation}$$

Доказательство. Пусть $$\calE_0=\{X\in\calE: \forall\,\ket{\xi}\in\calM\ X\ket{\xi}=0\}$$. Рассмотрим фактор-пространство $$\calF=\calE/\calE_0$$ и естественное отображение $$f\colon\calE\to\calF$$. Линейное отображение $$V\colon\calM\otimes\calF\to\calN'$$, удовлетворяющее условию (14.10), строится каноническим образом; нужно лишь проверить его изометричность.

Скалярное произведение на пространстве $$\calF$$ можно задать при помощи функции $$с$$ из свойства кода (14.9): если $$\ket{\eta_1}=\ket{f(X)}$$ и $$\ket{\eta_2}=\ket{f(Y)}$$, то $$\langle\eta_2|\eta_1\rangle=c(Y^\dagger X)$$. Очевидно, что эта величина не зависит от выбора $$X$$ и $$Y$$. Ясно также, что $$\langle\eta|\eta\rangle>0$$, если $$\ket{\eta}\not=0$$. Формула (14.9) как раз и означает, что отображение $$V$$ является изометрическим.

Доказательство (теоремы 14.2). Представим пространство $$\calN'$$ как сумму взаимно ортогональных подпространств: $$\calN'=(\Im V)\oplus\calK$$, где $$V$$ — отображение из предыдущей леммы. Пусть $$W\colon\calK\to\calN'$$ — каноническое вложение, а $$R\colon\LL(\calK)\to\LL(\calM)$$ — произвольное физически реализуемое преобразование. Тогда мы можем определить$$P\colon\rho\mapsto\, Tr_\calF(V^\dagger\rho V) +R(W^\dagger\rho W),\qquad c\colon X\cdot Y^\dagger\mapsto\, \langle f(Y)|f(X)\rangle.$$ (Функция $$с$$ линейно продолжается на все пространство $$\calE\cdot\calE^\dagger$$ ).

Лемму 14.3 и доказательство теоремы 14.2 можно неформально изложить таким образом. Код, исправляющий ошибки, характеризуется тем, что ошибка не смешивается с закодированной информацией, т.е. остается в виде отдельного тензорного сомножителя. Исправляющее преобразование извлекает эту "встроенную ошибку" и выбрасывает ее в мусорную корзину.

Задача 14.3. Пусть код $$\calM\subseteq\BB^{\otimes n}$$ обнаруживает ошибки из $$\calE(A)$$. Докажите, что состояние $$\rho\in\LL(\calM)$$ можно восстановить, не используя q-битов из множества $$A$$.

Код Шора [40].

Опишем серию кодов со сколь угодно большим кодовым расстоянием. Они используют $$n=r^2$$ кодовых q-битов и кодируют один q-бит (т.е. $$\dim\calM=2$$ ), а кодовое расстояние $$d$$ равно $$r$$.

Поскольку количество кодовых q-битов — точный квадрат, удобно задавать базисные состояния в таком кодовом пространстве в виде матрицы. В этих обозначениях код Шора порождается векторами$$\begin{equation}\label{кодШора} \ket{\xi_\alpha}=\sum_{y_1,\dots, y_r\in\cb^r}^{} (-1)^{\alpha\sum_{j=1}^{r}y_j} \left.\Bigg| \hbox{\footnotesize\def\arraystretch{0.9} \begin{matrix} y_1\dots\dotsy_1\\ y_2\dots\dotsy_2\\ \hdotsfor{4}\\ y_r\dots\dotsy_r\\\end{matrix}}\right.\Bigg\rangle .\end{equation}$$

Для анализа кода Шора нам потребуется классификация операторов с помощью матриц Паули. Их, вообще говоря, три, но четвертой матрицей Паули будем считать единичную. Введем нестандартную индексацию матриц Паули:$${\arraycolsep=0.5mm \tabcolsep=0.5mm $$\def\arraystretch{0.9} \begin{aligned} \sigma_{00}= \hbox{$\leftp\begin{array}{*2 r} 10\\01 \end{array}\rightp$}; \sigma_{01}= \hbox{$\leftp\begin{array}{*2 r} 10\\0-1 \end{array}\rightp$}=\sz; \\ \sigma_{10}= \hbox{$\leftp\begin{array}{*2 r} 01\\10 \end{array}\rightp$}=\sx;\qquad \sigma_{11}= \hbox{$\leftp\begin{array}{*2 r} 0-\ii\\ \ii0 \end{array}\rightp$}=\sy. \end{aligned} $$ }$$

Матрицы Паули замечательны тем, что они эрмитовы и унитарные одновременно. Введенная индексация позволяет удобно записывать коммутационные соотношения между матрицами Паули$$\begin{equation}\label{Паули-комм} \sigma_{\alpha\beta}\sigma_{\alpha'\beta'}= (-\ii)^{\alpha\beta'-\alpha'\beta} \sigma_{\alpha\oplus\alpha',\beta\oplus\beta'},\quad \sigma_{\alpha\beta}\sigma_{\alpha'\beta'}= (-1)^{\alpha\beta'-\alpha'\beta} \sigma_{\alpha'\beta'}\sigma_{\alpha\beta}. \end{equation}$$ Множество индексов образует группу $$G=\ZZ_2\oplus\ZZ_2$$ или 2-мерное пространство над полем $$\FF_2$$.

Матрицы Паули образуют базис пространства $$\LL(\BB)$$:$$\LL(\BB)=\CC(\sigma_{00})\oplus\CC(\sigma_{01})\oplus \CC(\sigma_{10})\oplus\CC(\sigma_{11}).$$ Для пространства $$\BB^{\otimes n}$$ будет уже $$4^n$$ базисных операторов. Введем обозначение$$\sigma(f)= \sigma(\alpha_1,\beta_1, \alpha_2,\beta_2, \dots, \alpha_n,\beta_n) \bydef \sigma_{\alpha_1,\beta_1}\otimes\sigma_{\alpha_2,\beta_2}\otimes \dots \otimes\sigma_{\alpha_n,\beta_n}.$$ Здесь $$f\in G^n=\FF_2^{\,2n}$$.

Используя коммутационные соотношения, можно написать, с точностью до общего фазового множителя, $$\sigma(f)=c\sigma(f^{(x)})\cdot\sigma(f^{(z)})$$, где $$f^{(x)}=(\alpha_1,0,\alpha_2,0,\dots)$$ называется классической ошибкой, а $$f^{(z)}\double=(0,\beta_1,0,\beta_2,\dots)$$ — фазовой ошибкой.

Теперь проанализируем код Шора. В силу линейности определения достаточно ограничиться изучением базисных ошибок. Пусть $$Z\double\in\calE(r^2,k)$$, $$(k<r)$$ и $$Z=\sigma(f)=c \sigma(f^{(x)})\sigma(f^{(z)})$$. Поскольку $$|f|\leq k$$ ( $$|f|$$ — число ненулевых переменных в $$f$$ ), то $$|f^{(x)}|,\, |f^{(z)}|\le k<r$$.

Достаточно показать, что в этом случае$$\begin{equation}\label {соотношения-ортогональности} \langle\xi_1|Z|\xi_0\rangle =0,\quad \langle\xi_1|Z|\xi_1\rangle=\langle\xi_0|Z|\xi_0\rangle. \end{equation}$$

Рассмотрим два случая.

Случай 2 в действительности реализоваться не может, так как $$\sum_j\lambda_j\le k<r$$. В случае 3 все скалярные произведения обращаются в нуль, $$\bra{\xi_\alpha}Z\ket{\xi_{\alpha'}}=0$$. В случае 1 $$Z\ket{\xi_\alpha}=\ket{\xi_\alpha}$$, т.е. $$Z$$ действует на кодовом подпространстве тождественным образом. (Такая ошибка, по существу, не является ошибкой, поскольку ничего не портит). Следовательно, $$\bra{\xi_\alpha}Z\ket{\xi_{\alpha'}}= \langle\xi_\alpha|\xi_{\alpha'}\rangle$$.

Итак, код Шора обнаруживает $$r-1$$ ошибку; кодовое расстояние равно~ $$r$$.

Замечание. Код Шора основан на дуальности между классическими и фазовыми ошибками, которая выражается равенством $$\sigma^z=H\sigma^x H^\dagger$$. Внутри каждой строки $$y_1,\dots,y_r $$ реализован обычный повторительный код, исправляющий классические ошибки. Строки организованы в аналогичный код, отличающийся заменой базиса в каждом q-бите: $$\sum_{y_1,\dots,y_r}(-1)^{\alpha(\sum_j y_j)}\ket{y_1,\dots,y_r}= (H\otimes\dots\otimes H)\ket{\alpha,\dots,\alpha}$$. Этот код исправляет фазовые ошибки.

Симплектические (стабилизирующие) коды [26]

Это аналог классических линейных кодов. Квантовые симплектические коды устроены так же, только вместо контрольных сумм будут использоваться $$\sigma$$ -операторы ( $$\,\sigma(\alpha_1,\beta_1,\dots,\alpha_n,\beta_n)$$ в предыдущих обозначениях).

Зададим, например, таким способом код Шора. Для него $$\calN=\BB^{\otimes r^2}$$, $$\dim\calM=2$$. Кодовое подпространство порождено двумя векторами, см. (14.11).

Каким условиям удовлетворяют базисные векторы $$\calM$$?

Утверждение 14.4. Если $$\ket\xi$$ удовлетворяет условиям 1 и 2, то $$\ket\xi\double=c_0\ket\xi_0+c_1\ket\xi_0$$.

Прежде чем перейти к изучению более общих симплектических кодов, рассмотрим подробнее свойства $$\sigma$$ -операторов.

Как уже говорилось, $$\sigma$$ -операторы удобно индексировать элементами группы $$G=\left(\ZZ_2\right)^2$$. Будем обозначать мультииндекс $$\sigma$$ -оператора через $$\gamma=(\alpha_1,\beta_1,\dots,\alpha_n,\beta_n)\in G^n$$.

$$\sigma$$ -операторы образуют базис в $$\LL(\BB^{\otimes n})$$, более того, есть естественная $$G^n$$ -градуировка:$$\LL(\BB^{\otimes n})=\bigoplus_{\gamma\in G^n} \CC\big(\sigma(\gamma)\big).$$

Для $$\sigma$$ -операторов выполнены следующие соотношения$$\sigma(\gamma_1)\sigma(\gamma_2)=(-i)^{\tilde\omega(\gamma_1,\gamma_2)} \sigma(\gamma_1+\gamma_2)= (-1)^{\omega(\gamma_1,\gamma_2)}\sigma(\gamma_2)\sigma(\gamma_1),$$ где$$ \tilde\omega(\alpha^{\mathstrut}_1,\beta^{\mathstrut}_1,\dots, \alpha^{\mathstrut}_n,\beta^{\mathstrut}_n; \alpha'_1,\beta'_1,\dots,\alpha'_n,\beta'_n ) =\sum_{j=1}^{n}(\alpha^{\phantom{'}}_j\beta'_j -\alpha'_j\beta^{\phantom{'}}_j)\bmod 4,\\ \omega(\gamma_1,\gamma_2)=\tilde\omega(\gamma_1,\gamma_2)\bmod 2. {\looseness=1\tolerance=400$$

Рассмотрим унитарные преобразования — действия унитарных операторов $$X\mapsto UXU^\dagger$$. Такое действие не меняется при домножении $$U$$ на число, равное по модулю единице, поэтому группа унитарных преобразований имеет вид $$UT(\BB^{\otimes n})=\U(\BB^{\otimes n})/\U(1)$$. Отметим, что унитарные преобразования — это в точности автоморфизмы $$*$$ -алгебры $$\LL(\BB^{\otimes n})$$.

Нас интересуют такие преобразования, для которых $$U\sigma(\gamma)U^\dagger \double=\sigma(u(\gamma))\cdot c(\gamma)$$ ( $$u\colon G^n\to G^n$$ — некоторая функция). Оператор $$U\sigma(\gamma)U^\dagger$$ эрмитов, поэтому $$c(\gamma)=\pm 1$$, то есть мы можем написать$$\begin{equation}\label{симплект-преобр} U\sigma(\gamma)U^\dagger = (-1)^{v(\gamma)}\, \sigma(u(\gamma)),\qquad u\colon G^n\to G^n,\quad\, v\colon G^n\to\ZZ_2. \end{equation}$$ Группа таких преобразований называется расширенной симплектической группой и обозначается $$\ESp_2(n)$$. Операторы из этой группы будем называть симплектическими. Приведем примеры.

Можно показать, что $$|\ESp_2(1)|=24$$. Если учитывать фазовые множители, то получилась бы группа Клиффорда из $$24\cdot8=192$$ элементов.

Основные свойства введенного отображения $$u\colon G^n\to G^n$$ таковы:

Отображения с такими свойствами, как известно, называются симплектическими; они образуют симплектическую группу $$\Sp_2(n)$$. Таким образом, определен гомоморфизм $$\theta\colon \ESp_2(n)\to \Sp_2(n)$$.

Теорема 14.3. $$\Im\theta =\Sp_2(n)$$, $$\Ker\theta= G^n$$ (ядро состоит из $$\sigma$$ -операторов). Таким образом, $$\ESp_2(n)/G^n\double\cong\Sp_2(n)$$.

Для понимания доказательства желательно знать что-нибудь про расширения и когомологии групп [15]. Читателю, незнакомому с этими понятиями, будет предложен "обходной путь" (см. ниже).

Доказательство. Преобразование (14.14) должно быть автоморфизмом $$*$$ -алгебры $$\LL(\BB^{\otimes n})$$. Это имеет место тогда и только тогда, когда сохраняются правила умножения операторов $$\sigma(\gamma)$$. Это означает, что функция $$u$$ обладает указанными свойствами, а $$v$$ удовлетворяет уравнению$$\begin{equation}\label{кограница} v(x+y)-v(x)-v(y)=w(x,y), \end{equation}$$ где $$w(x,y)=\frac{\tilde\omega(u(x),u(y))-\tilde\omega(x,y)}{2}\in\ZZ_2$$.

В случае, когда $$u$$ — тождественное отображение, правая часть уравнения (14.15) равна нулю. Решениями являются все линейные функции. Это доказывает, что $$\Ker\theta= G^n$$.

Утверждение $$\Im\theta=\Sp_2(n)$$ равносильно тому, что уравнение (14.15) имеет решение при любом $$u$$ из $$\Sp_2(n)$$. Чтобы доказать это, заметим, что функция $$w$$ обладает следующими свойствами:

$$w(y,z)-w(x+y,\,z)+w(x,\,y+z)-w(x,y) = 0,$$

$$w(x,y) = w(y,x),$$

$$w(x,x) = 0.$$

Формула (14.16) — это уравнение коцикла. Оно означает, что функция $$w$$ задает структуру группы на декартовом произведении множеств $$G^n\times\ZZ^2$$ согласно правилу $$(x,p)\cdot(y,q)=(x+y,\,p+q+w(x,y))$$. Полученная группа (обозначим ее $$E$$ ) является расширением $$G^n$$ посредством $$\ZZ_2$$, т.е. определен гомоморфизм $$\lambda\colon E\to G^n$$, $$\lambda\colon(x,p)\mapsto x$$ с ядром $$\ZZ_2$$.

Уравнение (14.17) означает, что группа $$E$$ абелева. Наконец, уравнение (14.18) означает, что все элементы группы $$E$$ имеют порядок $$2$$ (или $$1$$ ). Следовательно, $$E\cong(\ZZ_2)^{2n+1}$$. Отсюда вытекает, что расширение $$E\to G^n$$ тривиально: существует гомоморфизм $$\mu\colon G^n\to E$$, такой что $$\lambda\mu={\rm id}_{G^n}$$. Записывая этот гомоморфизм в виде $$\mu\colon x\mapsto(x,\,v(x))$$, получаем решение уравнения (14.15).

Существует другой, несколько кустарный способ доказать, что $$\Im\theta =\Sp_2(n)$$. Рассмотрим следующие симплектические преобразования: $$(H\cdot H^\dagger)[j]$$, $$(K\cdot K^\dagger)[j]$$ и $$\left(\Lambda(\sx)\cdot\Lambda^\dagger(\sx)\right)[j,k]$$. (Напомним, что $$K=\begin{pmatrix} 10\\0\ii\end{pmatrix}$$ ). Их образы при гомоморфизме $$\theta$$ порождают всю группу $$\Sp_2(n)$$. (Намек на доказательство: любую пару векторов $$\gamma_1,\gamma_2\in G^n$$, такую что $$\omega(\gamma_1,\gamma_2)=1$$, можно перевести этими преобразованиями в $$(1,0$$, $$0,0,\dots)$$ и $$(0,1,0,0,\dots)$$.) На самом деле, таким способом можно получить и другой интересный результат. Указанные элементы группы $$\ESp_2(n)$$ порождают все матрицы Паули, т.е. ядро гомоморфизма $$\theta$$. Следовательно, верно такое утверждение.

Утверждение 14.5. Группа $$\ESp_2(n)$$ порождается элементами$$(H\cdot H^\dagger)[j],\ (K\cdot K^\dagger)[j],\ \left(\Lambda(\sx)\cdot\Lambda^\dagger(\sx)\right)[j,k].$$

Для примера посмотрим на действие оператора $$U= \Lambda(\sx)[1,2]$$. По определению имеем $$U \ket{a,b}=\ket{a,a\oplus b}$$. Действие $$U$$ на образующие алгебры $$\LL(\BB^{\otimes 2})$$:$$\begin{align*} U\sz_1U^\dagger=\sz_1,\\ U\sz_2U^\dagger=\sz_1\sz_2,\\ U\sx_2U^\dagger=\sx_2,\\ U\sx_1U^\dagger=\sx_1\sx_2. \end{align*}$$ Приведенные равенства можно без труда проверить прямым вычислением. Однако полезно привести объяснение на "пальцах". Оператор $$\sz$$ можно понимать как измерение значения соответствующего q-бита. Первые два равенства просто показывают, как меняются эти значения при замене базиса, задаваемой $$U$$. Третье равенство показывает, что изменение значения второго q-бита коммутирует с заменой базиса $$U$$. Четвертое — что изменение значения первого q-бита при неизменном втором бите в повернутом базисе означает одновременное изменение значений обоих q-битов в исходном базисе.

Дадим теперь определение симплектического кода. В пространстве $$\calN=\BB^{\otimes n}$$ мы выделим подпространство $$\calM$$ условиями $$X_j\ket\xi=\ket\xi$$ ( $$X_j$$ будем называть проверочными операторами ). Проверочные операторы будут иметь вид$$\begin{equation}\label{проверочные} X_j=(-1)^{\phi_j}\sigma(f_j), \quad f_j\in G^n, \quad \phi_j\in\ZZ_2. \end{equation}$$ Без ограничения общности можно считать, что $$\{f_j\}$$ линейно независимы. Потребуем еще, чтобы все операторы $$X_j$$ коммутировали. Поскольку $$X_jX_k=(-1)^{\omega(f_j,f_k)}X_kX_j$$, условие коммутирования означает, что $$\omega(f_j,f_k) =0$$.

Определение 14.9. Симплектический квантовый код задается условиями (14.19), где все $$X_j$$ коммутируют.

Итак, симплектическому квантовому коду соответствует изотропное подпространство $$F\subseteq G^n$$ ; изотропность означает, что для любых $$f,\,g\in F$$ выполнено $$\omega(f,g)=0$$. Поэтому размерность симплектического кода легко вычисляется.

Теорема 14.4. $$\dim\calM=2^{n-\dim F}$$.

Лемма 14.6. Любой симплектический код приводится преобразованиями из $$\ESp_2(n)$$ к стандартному виду, когда проверочными операторами являются $$\sigma^z[1],\dots,\sigma^z[s]$$, где $$s=\dim F$$.

Доказательство. Подпространство $$F\subseteq G^n$$ можно перевести отображением из $$\Sp_2(n)$$ в подпространство $$F'$$, состоящее из векторов вида $$(0,\beta_1,0,\beta_2,\dots,0,\beta_s,0,\dots,0)$$, где $$\beta_j$$ — произвольные. Согласно теореме 14.3, этому отображению соответствует некоторое унитарное преобразование $$U\cdot U^\dagger$$. Оно переводит кодовое подпространство в подпространство, заданное проверочными операторами $$\pm\sigma^z[j]$$ ( $$j=1,\dots,s$$ ). Применяя дополнительное преобразование вида $$\sigma(f)\cdot\sigma(f)^\dagger$$, все знаки можно сделать плюсами.

Теперь посмотрим, какие ошибки способен обнаруживать симплектический код. Напомним, что код обнаруживает ошибки из $$\calE(n,k)$$, если$$\begin{equation}\label{замечаетошибку} \forall\, \ket\xi,\ket\eta\in\calM\:\forall\, Z\in\calE(n,k)\: \langle\xi |Z|\eta\rangle =c(Z)\langle \xi|\eta\rangle \end{equation}$$ По соображениям линейности достаточно рассматривать лишь $$Z\double=\sigma(g)$$, $$|g|\leq k$$.

Пусть $$\ket\eta\in\calM$$, т.е. $$X_j\ket\eta=\ket\eta$$ для всех $$j$$, где $$X_j=(-1)^{\phi_j}\sigma(f_j)$$. Обозначим $$Z\ket\eta=\ket\psi$$, где $$Z=\sigma(g)$$. Как мы сейчас увидим, вектор $$\ket\psi$$ является собственным для всех проверочных операторов $$X_j$$, поэтому он либо принадлежит кодовому подпространству $$\calM$$, либо ему ортогонален. Подействуем проверочным оператором на $$\ket\psi$$:

$$\begin{align*} X_j\ket\psi=X_jZ\ket\eta= (-1)^{\omega(f_j,g)}ZX_j\ket\eta=(-1)^{\omega(f_j,g)}Z\ket\eta=\\= (-1)^{\omega(f_j,g)}\ket\psi. \end{align*}$$

Условие $$\ket\psi\in\calM$$ равносильно условию $$\omega(f_j,g)=0$$ для всех $$j$$. Такие $$g$$ образуют линейное подпространство, которое мы обозначим $$F_+$$, т.е. $$F_+\double=\{ g\in G^n: \forall\,f\in F\:\omega(f,g)=0\}$$.

Возможны следующие три случая:

Этими рассуждениями доказана следующая теорема.

Теорема 14.5. Кодовое расстояние для симплектического кода $$\calM$$$$d(\calM)=\min\{|f|: f\in F_+\setminus F\}.$$

Заметим отличие от классических линейных кодов. Там кодовое расстояние определяется как наименьшая норма вектора из подпространства с выкинутым нулем. А у симплектических кодов нуль раздувается до подпространства.

Задача 14.4. Постройте симплектический квантовый код типа $$(5,1)$$, исправляющий одну ошибку.

Задача 14.5. Докажите, что не существует квантового кода типа $$(4,1)$$, исправляющего одну ошибку.

Торические коды.

Приведем важный пример симплектического кода. Он строится так. Пусть есть квадратная решетка размера $$r\times r$$ на торе. Сопоставим каждому ее ребру по q-биту. Таким образом, всего имеется $$n=r^2$$ q-битов. Проверочные операторы будут двух типов.

Тип I задается вершинами. Выберем некоторую вершину $$s$$ и сопоставим ей проверочный оператор$$A^{(x)}_s=\sigma(f^{(x)}_s)=\prod_{j\in\,\mathrm {\text{звезда}}(s)}^{} \sigma^x_j.$$

Тип II задается гранями. Выберем некоторую грань $$u$$ и сопоставим ей проверочный оператор$$A^{(z)}_u=\sigma(f^{(z)}_u)=\prod_{j\in\, \mathrm {\text{граница}}(u)}^{} \sigma^z_j.$$

Операторы $$A^{(x)}_s$$ и $$A^{(z)}_u$$ коммутируют, поскольку граница и звезда всегда пересекаются по четному числу ребер. (Перестановочность операторов одного типа очевидна.)

Хотя мы указали $$r^2+r^2=2r^2$$ проверочных операторов (по одному на грань и на вершину), между ними есть соотношения. Произведение всех $$A^{(x)}$$ -операторов, как и произведение всех $$A^{(z)}$$ -операторов, равны тождественному. Можно показать, что других соотношений нет. Поэтому $$\dim F=2r^2-2$$, а $$\dim\calM=2^2$$. Поэтому торический код позволяет закодировать два q-бита. Посмотрим, чему равно кодовое расстояние для торического кода.

Для торического кода имеются естественные разложения$$F=F^{(x)}\oplus F^{(z)},\qquad F_+=F_+^{(x)}\oplus F_+^{(z)}$$ на подпространства, соответствующие проверочным операторам, состоящим только из $$\sigma_j^x$$, либо только из $$\sigma_j^z$$. Такие коды называются CSS кодами (по фамилиям авторов, впервые рассмотревших этот класс кодов [25, 44]). В случае торического кода элементы подпространств $$F^{(z)}$$, $$F_+^{(z)}$$ имеют вид $$(0,\beta_1,\dots,0,\beta_n)$$ ; им можно сопоставить 1-цепи, т.е. формальные линейные комбинации ребер с коэффициентами $$\beta_1,\dots,\beta_n\double\in\FF_2$$. Элементам подпространств $$F^{(x)}_{\ms},\ F_+^{(x)}$$ сопоставляются 1-коцепи. Рассмотрим вектор $$f^{(z)}_u\in F^{(z)}_{\ms}$$, отвечающий грани с номером $$u$$. Ему будет сопоставлена 1-цепь, являющаяся границей этой грани. Легко видеть, что пространство $$F^{(z)}$$ состоит из всех 1-границ. Аналогично, векторам $$f_s^{(x)}$$ будут сопоставляться 1-кограницы, порождающие все пространство 1-кограниц.

Возьмем произвольный элемент $$g\in F_+$$, $$g=g^{(x)}+g^{(z)}$$. Условия коммутирования запишутся следующим образом:$$ \omega(f_s^{(x)},g)=0\quad \Longleftrightarrow\quad \omega(f_s^{(x)},g^{(z)})=0, \\ \omega(f_u^{(z)},g)=0\quad \Longleftrightarrow\quad \omega(f_u^{(z)},g^{(x)})=0. $$ Чтобы выполнялось $$\omega(f_s^{(x)},g^{(z)}_{\ms})=0$$, нужно, чтобы в любой звезде было четное число ребер с ненулевыми весами из $$g^{(z)}$$. Другими словами, $$g^{(z)}$$ — это 1-цикл (с коэффициентами в $$\ZZ_2$$ ). Аналогично, $$g^{(x)}$$ должен быть 1-коциклом.

Итак, пространства $$F_+^{(z)}$$, $$F_+^{(x)}$$ состоят из 1-циклов и 1-коциклов, а пространства $$F^{(z)}$$, $$F^{(x)}$$ состоят из 1-границ и 1-кограниц. Следовательно, кодовое расстояние есть минимальная мощность (количество ненулевых коэффициентов) по циклам, не являющимся границами, и коциклам, не являющимся кограницами. Легко видеть, что этот минимум равен $$r$$ (нужны либо цикл, либо разрез, не гомологичные 0). Это означает, что торический код исправляет $$\lfloor (r-1)/2\rfloor$$ ошибок.

Будем обозначать коды описанного вида через $$\TOR(r)$$.

Замечание. Торические коды являются очень важным примером, обладающим рядом замечательных свойств. В частности, это коды с локальными проверками. Последовательность кодов называется кодами с локальными проверками, если выполнены следующие условия:

Такие коды представляют интерес для задачи построения вычислительных схем, устойчивых к ошибкам. При исправлении ошибок могут происходить новые ошибки. Но для кодов с локальными проверками схемы исправления ошибок имеют фиксированную глубину, поэтому одна ошибка при работе такой схемы портит ограниченное число q-битов.

Процедура исправления ошибок.

Определение 14.6 и теорема 14.2 указывают только на принципиальную возможность восстановить исходное состояние системы после действия ошибки. На примере симплектических кодов покажем, как реализовать процедуру исправления ошибки.

Рассмотрим частный случай, к которому все сводится. Пусть имеются две ошибки, заданные операторами $$X=\sigma(g_1)$$, $$Y=\sigma(g_2)$$. Тогда $$Z=Y^\dagger X= с\sigma(g_1-g_2)$$ ( $$|c|=1$$ ). Назовем синдромом ошибки $$g_1$$ вектор $$\left(\omega(g_1,f_1),\dots,\omega(g_1,f_s)\right)$$ (для $$g_2$$ — аналогично).

Возьмем вектор $$\ket\eta\in\calM$$. Обозначим $$\ket\psi=X\ket\eta$$. Проверочные операторы действуют на $$\ket\psi$$ так: $$X_j\ket\psi=(-1)^{\omega(g_1,f_j)}\ket\psi$$. Поэтому, измеряя собственные числа $$X_j$$ на состоянии $$\ket{\psi}$$, можно измерить синдром.

Если кодовое расстояние равно $$k$$, то выполнено$$\forall\,g_1,g_2\: \Bigl((|g_1|\leq k, |g_2|\leq k) \Rightarrow \big((g_1-g_2\in F)\vee(g_1-g_2\not\in F_+)\big)\Bigr).$$ Условие $$g_1-g_2\in F$$ означает эквивалентность ошибок $$g_1$$ и $$g_2$$, т.е. $$\sigma(g_1)\ket\eta=c\sigma(g_2)\ket\eta$$ для любого вектора $$\ket\eta$$ из кодового подпространства. Условие $$g_1-g_2\not\in F_+$$ равносильно тому, что синдромы ошибок $$g_1$$ и $$g_2$$ не совпадают. Итак, либо ошибки эквивалентны, либо их можно различить по синдрому. Следовательно, по синдрому можно определить ошибку с точностью до эквивалентности, т.е. по модулю подпространства $$F$$.

Теперь ясно, как нужно исправлять ошибку. После того как определен синдром, применим оператор, обратный к оператору восстановленной по синдрому ошибки. Получим состояние, отличающееся от исходного лишь на фазовый множитель. Вся процедура изображена на рис. 14.2.

Выше рассмотрен случай ошибки типа $$\sigma(g)$$. На самом деле ошибка состоит в действии преобразования матриц плотности вида$$T=\sum_{|h|\leq k,|h'|\leq k}^{} b_{h,h'} \sigma(h)\cdot\sigma(h')^\dagger.$$ В качестве упражнения читателю предлагается проверить, как работает приведенная выше схема в случае такого общего преобразования матриц плотности.

Задача 14.6. Постройте полиномиальный алгоритм определения ошибки по синдрому для торического кода.

Анионы (иллюстративный пример на основе торического кода).

На примере торического кода можно дать более точное представление об анионных системах, о которых говорилось во введении.

Итак, вновь рассмотрим квадратную сетку на торе (а можно и на плоскости — сейчас нас будет интересовать только ее центральная часть). Как и раньше, для каждой вершины $$s$$ и каждой грани $$u$$ рассмотрим проверочные операторы$$A^{(x)}_s=\prod_{j\in\,\mathrm {\text {звезда}}(s)}^{} \sigma^x_j, \quad A^{(z)}_u=\prod_{j\in\,\mathrm {\text {граница}}(u)}^{} \sigma^z_j.$$ Состояние кодового подпространства задается условиями $$A^{(x)}_s\ket\xi=\ket\xi$$, $$A^{(z)}_u\ket\xi=\ket\xi$$. Их можно переписать другим способом. Рассмотрим следующий гамильтониан — эрмитов оператор$$H=\sum_{s}(I-A^{(x)}_s)+\sum_{u}(I-A^{(z)}_u).$$ Этот оператор неотрицательный, причем его нулевое подпространство в точности совпадает с кодовым подпространством торического кода. Таким образом, векторы из кодового подпространства являются собственными и обладают наименьшей энергией (т.е. собственным числом гамильтониана). Такие векторы называются основными состояниями, а векторы из ортогонального дополнения — возбужденными состояниями.

Рассмотрим возбужденные состояния с наименьшей ненулевой энергией, когда нарушено ровно два условия (например, вершинных). (Число нарушенных условий каждого типа четное, поскольку $$\prod_s A^{(x)}_s \double=\prod_u A^{(z)}_u=I$$.) Тогда для двух вершин, в которых кодовые условия нарушаются, выполнено$$A^{(x)}_s\ket\eta=-\ket\eta, \quad A^{(x)}_p\ket\eta=-\ket\eta.$$ Как можно получить состояние $$\ket\eta$$ из кодового состояния $$\ket\xi$$? Соединим $$p$$ и $$s$$ решеточным путем $$C_1$$ и подействуем на $$\ket\xi$$ оператором $$W=\prod_{j\in C_1}^{}\sz_j$$. Этот оператор коммутирует с проверочными вершинными операторами для всех промежуточных вершин пути $$C_1$$, а в концах — антикоммутирует: $$WA^{(x)}_s=-A^{(x)}_s W$$. Положим $$\ket\eta=W\ket\xi$$ и покажем, что $$\ket\eta$$ удовлетворяет требуемым свойствам. Для вершины $$s$$ (аналогично и для $$p$$ ) имеем$$\ket\eta=W\ket\xi =WA^{(x)}_s\ket\xi=-A^{(x)}_s W\ket\xi=-A^{(x)}_s\ket\eta$$ ( $$A^{(x)}_s\ket\xi=\ket\xi$$, так как состояние $$\ket\xi$$ — кодовое).

Любое состояние системы можно построить из элементарных возбуждений двух типов, одни из которых "живут" на вершинах, другие — на гранях. Элементарное возбуждение — это просто нарушенное кодовое условие, но теперь мы думаем о нем как о частице. Частицы-возбуждения можно двигать, создавать и уничтожать. Пара возбуждений первого типа получается из основного (кодового) состояния действием оператора $$W$$, приведенного выше; пара возбуждений второго типа — действием оператора $$V=\prod_{j\in C_2}^{}\sx_j$$, где $$C_2$$ — путь, соединяющий две грани, как показано на рис. 14.3a). Как и раньше проверяется, что $$A^{(z)}_u(V\ket\xi)\double=-V\ket\xi$$.

Что случится, если двигать возбуждение одного типа (крестик) вокруг возбуждения второго типа (кружочка)? (См. рис. 14.3б).) Движение возбуждения описывается оператором $$\prod_{j\in C'}\sx_j=\prod_r A^{(x)}_{r}$$, зависящим от контура обхода $$C'$$ (здесь $$r$$ пробегает все грани внутри $$C'$$ ). Очевидно, что $$A^{(x)}_{r}\ket\psi=\ket\psi$$ для всех $$r\not=p$$. В результате мы получим$$\ket\psi\mapsto \prod_{j\in C'}^{}\sx_j\ket\psi = A^{(x)}_p\ket\psi = -\ket\psi.$$ То есть вектор состояния домножился на $$-1$$. Это и означает, что рассматриваемые возбуждения являются (абелевыми) анионами.

На торе можно двигать частицы по двум различным циклам, образующим базис в группе гомологий. Например, можно создать из основного состояния пару возбуждений одного типа, обнести одно из возбуждений по циклу и проаннигилировать со вторым возбуждением. Этот процесс описывается некоторым оператором, действующим на кодовом подпространстве, — произведением $$\sz_j$$ вдоль пути на решетке, либо $$\sx_j$$ вдоль пути на двойственной решетке. Поскольку существует два типа возбуждений, мы имеем 4 таких оператора: $$Y^{(z)}_1$$ и $$Y^{(x)}_2$$ соответствуют одному базисному циклу, а $$Y^{(z)}_2$$ и $$Y^{(x)}_1$$ — другому. Эти операторы действуют на два закодированных q-бита как $$\sz_i, \sx_i$$ ( $$i=1,2$$ ), потому что они обладают такими же коммутационными соотношениями: $$Y^{(x)}_i Y^{(z)}_i = -Y^{(z)}_i Y^{(x)}_i$$ (остальные пары коммутируют).