Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 94

Так как код имеет расстояниеd= 9, существует лучшая процедура,которая всегда будет успешно исправлять четыре ошибки, так что рС 2 ) будетиметь порядок р 5 , а не р4 . Тем не менее, эта неоптимальная процедураимеет то преимущества, что она очень легко обобщается (и анализируется)в случае многоуровнего соединения.Действительно, при наличииLуровней каскадного соединения вос­становление начинается на самом глубоком внутреннем уровне и прокла-76ГЛАВА7дывает путь наружу. Решая рекуррентную систему неравенств(7.210)с начальным условием р(о) = р, мы приходим к выводу, что(7.211)(здесь С =10).Нетрудно видеть, что до тех пор, пока р< 1/10,вероят­ность сбоя можно сделать сколь утодно малой, добавляя к коду достаточноеколичество уровней.Мы можем записать(7.212)где р 0 =1/10- оценка пороговой (тоесть допустимой) вероятности ошиб­ки (ниже мы получим лучшие коды и лучшие оценки этого порога).

Отме­тим: чтобы получитьp(L) <Емы можем выбрать размер блокаn=(7.213)5L; так что(7.214)В принципе, каскадный код может дать сбой на высоком уровне при гораздоменьшем, чемn/10,количестве ошибок, но они должны быть распределе­ны весьма специальным образом, что совсем не характерно для большогоn.Каскадное кодирование неизвестного квантового состояния может вы­полняться уровень за уровнем. Например, чтобы закодировать а!О)в блоке [[25, 1, 9]], мы можем сначала приготовить состояние а!О)+ bl1)+ bll)в пятикубитовом блоке, используя описанную ранее схему кодирования,а также приготовить четыре пятикубитовых блока в состоянии !О/.

Состоя­ние а!О)можно закодировать на следующем уровне, снова выполняя+ bii/эту же схему, но теперь со всеми вентилями, замененными на закодирован­ные, действующие на пятикубитовые блоки. Обсуждение конструкции этихзакодированных вентилей можно найти в приложении.7.15.7.15.2.НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИ77Торические кодыТорические коды представляют собой еще одно семейство кодов, ко­торые, как и каскадные, работают гораздо лучше, чем этого можно былобы ожидать, учитывая значения их расстояний. Их описывает профессорКитаев (который их и открыл). 17.15.3.Коды Рида-МаллераДругим способом построения кодов, которые могут исправить множе­ство ошибок, является осуществление КШС-конструкции.

Вспомним, на­пример, частный случай этой конструкции, в котором используется клас­сический код С, содержащийся в дуальном ему коде (в таком случае го­ворят, что С является «слабо самодуальным» кодом). В КШС-конструкциис каждым смежным классом С вC_L ассоциируется кодовое слово. Такимlln, k, d]], где n- длина кода С, d(по крайней мере) расстояние кода С , а k = dimC_L- dimC. Следо­образом, мы получаем квантовый кодвательно, для построения КШС-кодов, исправляющих множество ошибок,необходимы слабо самодуальные классические коды с большим минималь­ным расстоянием.Один из классов слабо самодуальных классических кодов представля­ют собой коды Рида- Маллера. Хотя эти коды не особенно эффективны, ониочень удобны, поскольку достаточно легко кодируются.

Несложно понятьтакже принцип их работы и математическую структуру. 2Чтобы подготовиться к построению кодов Рида-Маллера, рассмотримбулевы функции на т битахf : {0, 1}m~{0, 1}.(7.215)Существует 2 2 "' таких функций, образующих множество, которое можнорассматривать как двоичное векторное пространство размерностилезно ввести базис в этом пространстве. Вспомним (см. раздел2m.6.1),По­чтолюбая булева функция имеет дизъюнктивную нормальную форму. Так какNOTбита х равно1-х, аOR двуххvу=битов х и у можно записать какх +у-ху,(7.216)1Детальное описание торических кодов можно найти в статье: А.Kitaev, Paиlt-tolerantanyons, Ann.

Phys. (NY) 303(1) рр.2-30 (2003), quant-ph/9707021.Kitaev, С. Laumann, Topological phases and qиапtит compиtation, cond-qиапtит compиtation ЬуСм. также лекции: А.-Прим. ред.mat/0904.2771.2См., наnример, Е. J. MacWilliams, N. J. А. S1oane, Тhе Theory of E1·ror-Correcting Codes,North HollandPuЬlishiпgCompany, Amsterdam, New York, Oxford (1977), chapter 13;перевод:Ф. Дж. Мак-Вильяме, Н.

Дж. А. Слоэн, Теория l(одов. исправШ!ЮЩИХ ошибки.- М.: Связь,гл.13.1979,ГЛАВА787то любая булева функция может быть представлена в виде полинома отxm_ 1 , xm_ 2 , •.. , х 1 , х 0 .состоит из 2m функцийдвоичных переменныхства полиномовmБазис векторного простран­(7.217)(где каждый моном представляет собой произведение различных сомно­жителей, так как х 2 = х).

Каждую такую функциюдвоичной строкой длины2m,fможно представитьзначение которой в позиции, обозначеннойдвоичной строкой Xm_ 1 , Xm_ 2 , ... , х 1 , х 0 , равно f(xm-1, Xm_ 2 , •.. , х 1 , х 0 ).Например, дляm= 31 = (11111111),= (10101010),х 1 = (11001100),х 2 = (11110000),х 0 х 1 = (10001000),х 0 х 2 = (10100000),х 1 х 2 = (11000000),х 0 х 1 х 2 = (10000000).х0(7.218)Подпространство этого векторного пространства получается, еслиограничить степень полинома доrили менее. Это подпространство яв­ляется кодом Рида- Маллера (или РМ-кодом) и обозначаетсядлина равнаn = 2m,R( r, m).Егоа его размерность(7.219)Некоторые частные случаи, представляющие интерес:• R(O, m) -код повторения длины2m.• R( m-1, m) - код, дуальный коду повторения, пространство всех строкчетного веса длины• R(1,3)-2m.код, натянутый на 1,х 0 ,х 1 ,х 2 с параметрами n=8, k=4;это уже обсуждавшийся расширенный код Хэммин­фактически,га[8,4,4].• В более общем случае R( m - 2, m) при любом m ~ 3 представляетсобой расширенный код Хэмминга с d = 4.

Выкалывая его (убираяпоследний бит из каждого кодового слова), мы получим совершенныйкод Хэмминга[n =2m -1,k = n- m,d=3].7.15. НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИ79• R(1,т) имеет d = zm-l = ~n и k = т. Он дуален расширенномукоду Хэмминга и известен как «код Рида-Маллера первого порядка».Он сам по себе представляет значительный практический интерес, бла­годаря его большому расстоянию и особой простоте процедуры деко­дирования.Применяя метод индукции по т, можно вычислить расстояние кодаR(r, т).Сначала мы должны определить, какФункцию отxm, ...

, х0R(r, т+ 1)связан сR(r, т).можно записать как(7.220)еслиfимеет степеньРассматриваяfr, тогда g должна иметь степенькак вектор длины 2m+1, имеем 1r,астепеньh-f = (g\g) + (h\0),гдеg, h -векторы длиной2m.r -1.(7.221)Рассмотрим расстояние междуf!' = (g'/g') + (h'/0).и(7.222)h = h' и f =/=- f' это расстояние равно wt(f - f') = 2 · wt(g - g') ;?: 2 · dist(R(r, т)); при h =/=- h' оно по крайней мере wt(h -h')) ;;:: dist(R(r-1, т)). Если d(r, т) обозначает расстояние кода R(r, т),Прито можно видеть, чтоd(r, т+ 1) = min[2d(r, т); d(r- 1, т)].(7.223)Теперь с помощью индукции по т можно показать, что d(r, т) =1) = zl-r при r =О, 1; R(1, 1)представляет собой пространство всех строк длины два, а R(O, 1)- код по­= 2m-r. Во-первых, проверим, что d(r, т=вторения длины два.

Предположим теперь, что при всех т ~ М и О ~расстояниеd= zm-r.Тогда мы делаем вывод, что при всех1~r~тr ~ т(7.224)1Здесь символ Cfig) обозначает следующую конструкцию: есливектор-строка длины n, а g == Cf1, / 2 .. · , fп, gl, 92 ... , 9m)f = (!1, / 2 ... , fп) (g 1 , g 2 .•• , 9т) - вектор-строка длины m, то Cfig) =- вектор-строка длины n + m.

Вывод выражения (7.221)для вектора-строки длины 2m+I, изображающей булеву функцию (7.220), а также подроб­ности вычисления расстоянияЕ.d(r,т) кода Рида-МаллераR(r, m)можно найти в книге:J. MacWilliams, N. J. А. S1оапе, The Тheory ofError-Correcting Codes, North Hollaпd PuЬ\ishingCompany, Amsterdam, New York, Oxford (1977), chapter 13; перевод: Ф.Дж.Мак-Вильямс,Н.Дж.А.Слоэн, Теория кодов, исправляющих ошибки.- М.: Связь, 1979, гл. 13.- Прим.ред.80ГЛАВА 7+ 1, т+ 1) представляет2m+\ и что d(O, т+ 1) == 2m+I, так как R(O, т+ 1) является кодом повторения длины 2m+l.

Этозавершает индуктивный шаг и доказывает, что d(r, т) = 2m-r.Отсюда, в частности, следует, что R( т - 1, т) имеет расстояние два,поэтому дуальным коду R(r, т) является R(т- r- 1, т). Прежде всего,заметим, что сумма биномиальных коэффициентов (';) (О~ j ~т) равна2m, так что R( т - r - 1, т) имеет правильную размерность, чтобы иметьсмысл Rj_(r, т). Тогда этого достаточно, чтобы показать, что R(т- rТакже ясно, что d(т+ 1, т+ 1) =1, таккак R(тсобой пространство всех двоичных строк длины-1, т) содержится в R(r, т). Но еслиfЕR(r, т),аgЕ R(т-то их произведение является полиномом степени не выше твательно, принадлежит R(т-1, т).- 1Каждый вектор в R(т-четный вес, поэтому внутреннее произведениеf ·gr -1, т),и, следо­1, т)имеетобращается в нуль;следовательно, g принадлежит дуальному пространству Rj_(r, т).

Это показывает, чтоRj_(r, т)= R(т- r- 1, т).(7.225)Именно благодаря этому замечательному свойству дуальности коды Рида­Маллера хорошо подходят для КШС-конструкции квантовых кодов.В частности, код Рида- Маллера является слабо самодуальным приr ~т- r -1, или 2r~ т -1, и самодуальным при2r=т -1. В последнемслучае его расстояние равно(7.226)а количество закодированных битов-_1_n _ 2m-lk -2При т =3, 5, 7 эти(7.227)осамодуальные коды имеют параметры[8, 4, 4]'(Как уже отмечалось, код[32, 16, 8]'[8,4,4][128, 64, 16] оявляется расширенным кодом Хэмминга.)С ними связаны квантовые коды с параметрами([8, о, 4]]'(7.228)[[32, о, 8]]'(k=О)[[128, о, 16]](7.229)и так далее.Для того чтобы получить квантовый код сk=1, достаточновыколотьсамодуальный код Рида- Маллера, то есть удалить из него один изn = 2m7.15.НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИ81битов (какой бит удалить, значения не имеет). Результатом этой операцииявляется классический код с параметрами n =2m- 1, d = 2(m+l)/ 2= J2(n+ 1)- 1 и k= (n-1=+ 1)/2.

Более того, дуальным этому выколото­му коду является его четный субкод. (Четный субкод состоит из тех РМ­кодовых слов, для которых удаляемый при выкалывании бит равен нулю,а из самодуальности РМ-кода следует, что они ортагональны всем словам(с четным инечетным весами) выколотого кода.) Из этих выколотых кодовс помощью КШ С-конструкции мы получаем квантовые коды с параметрами(k = 1)[[7, 1, 3]],[[31, 1, 7]],[[127, 1, 15]](7.230)и так далее. Код Хэмминга [7, 4, 3] получается при выкалывании РМ-кода[8, 4, 4], а КККО, соответствующий коду [7, 1, 3], естественно, является ко­дом Стина.

Эти КККО имеют расстояние, возрастающее как квадратныйкорень их длины.Эти коды сk = 1не самые эффективные из известных КККО. Темне менее, они представляют особый интерес, так как их свойства особенноподходят для применения помехоустойчивых квантовых вентилей на зако­дированную информацию (см.