Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 93
Текст из файла (страница 93)
Классические коды с такимисвойствами очень хорошо изучены. 1 •В частности, рассмотрим снова код Хэмминга [5, 3, 3] 4 . Его матрицуконтроля четности (в нетрадиционном представлении) можно представитьв виден=(1w w1 о)01ww1'(7.193)что также является генерирующей матрицей дуального ему, линейного самоортогонального кода [5, 2, 4] 4 . По сути, этот [5, 2, 4] 4 код с 4 2 = 161См., например, Е. J. MacWilliams, N. J. А. Sloane,The Theory of Error-Correcting Codes,Company, Amsterdam, New York, Oxford (1977); [перевод: Ф. Дж. МакН.Д,ж.А.Оюэн, Теория кодов, исправляющих ошибки. - М.: Связь, 1979. - Прим.North HollandВильяме,ред.]PuЬlishing7.14.ХОРОШИЕ КВАНТОВЫЕ КОДЫ71кодовыми словами в точности является стабилизатором квантового кода[[5, 1, 3]].Отождествляя1=Х, LV=Z,мы примимаем две строки матрицы Н в качестве генераторов стабилизатора М 1 , М 2 .
Код, дуальный кодуХэмминга, является линейным, поэтому линейные комбинации строк принадлежат коду. Складывая строки и умножая результат наw,получаем(7.194)что представляет собой М 4 . А если к М 4 мы добавим М 2 и умножим наw,то найдем(7.195)что представляет собой М 3 .Код [[5, 1, 3]] является одним из примеров достаточно общей конструкции. Рассмотрим субкод С на GF( 4)n, который является аддитивным(замкнутым относительно сложения) и самоортогональным (содержащимся в дуальном ему коде) относительно симплектического внутреннего произведения. Этот GF(4)-код может быть отождествлен со стабилизаторомn. Если GF(4)-код содержит 2n-k кодовых слов,двоичного КККО длиныто КККО имеетkзакодированных кубитов. Расстояниемминимальный вес вектора изДругим примером самоортогонального линейногодуальный коду Хэмминга тdКККО являетсяC.l \С.GF( 4 )-кода является=3сn = ~(4 3 - 1) = 21.Код Хэмминга имеет(7.196)4n-m кодовых слов, а дуальный ему код- 4m=26кодовых слов.
Мы непосредственно получаем КККО с параметрами[[21, 15, 3]]'(7.197)который может исправить одну ошибку.7.14.Хорошие квантовые кодыСемейство кодов [[п,k, d]]является хорошим, если оно содержит коды,чья «скорость» R = k / n и «вероятность возникновения ошибки» р = t / n(где t = (d-1)/2) стремятся к иенулевым пределам при n-> оо.
Мы можемиспользовать формализм стабилизатора, чтобы доказать «квантовую границу Гилберта-Варшамова», которая демонстрирует сушествование хорошихквантовых кодов. В сущности, хорошие коды можно выбрать невырожденными.72ГЛАВА7Мы дадим только набросок доказательства, не выполняя точно требуемые вычисления. Пусть Е = {Еа}- множество ошибок, которые необходимо исправить, а Е( 2 ) = {Е!Еь} -множество произведений пар элементов Е. Тогда, чтобы построить невырожденный код, который может исправлять ошибки из Е, мы должны найти такой набор генераторов стабилизатора, чтобы некоторый генератор антикоммутировал с каждым элементом t;(Z).Чтобы увидеть, может ли выполнить эту работу k-кубитовый код длины n, начнем с множества S(n-k) всех абелевых подгрупп группы Паулисn- kгенераторами.
Будем постепенно отбрасывать подгруппы, которыеявляются неподходящими стабилизаторами для исправления ошибок вt;,а затем посмотрим, останется ли что-нибудь.Каждая нетривиальная ошибка Еа коммутирует с долей""' l/2n-k всехсодержащихся в S(n-k) групп, так как она должна коммутировать с каждымизn- kгенераторов группы. (Существует малая поправка к этой доле, которой можно пренебречь при большихn.)Всякий раз, когда мы добавляемк t;(Z) еще один элемент, должна быть отброшена доля 2k-n всех кандидатов в стабилизаторы.
Когда t;( 2) полностью собрана, мы в худшем случаеотбросили долю(7.198)всех содержащихся в S(n-k) подгрупп (где IE(z) 1 -количество элементовв t;( 2)). До тех пор, пока эта доля меньше единицы, выполняющий этуработу стабилизатор будет существовать при большихЕсли мы хотим исправить t=n.pn ошибок, то t;(z) должно содержатьоператоры с весом, не превышающим2t,что позволяет сделать оценку(7.199)Следовательно, существуют стабилизирующие коды, исправляющиеошибок, с асимптотическим значениемR = kjn,pnопределяемым неравенством(7.200)Это (асимптотическая) форма квантовой границы Гилберта-Варшамова.Отсюда следует, что должны существовать коды с иенулевой скоростью, которые защищают от ошибок, возникающих с любой вероятностьюр< Pav ':::' 0,0946. Для кода, который может защититьного оператора с весом( pn,емая границей Рейнса, равнаот каждого ошибочмаксимальная вероятность ошибки, допуска1/6.7.15.НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИ73Хотя хорошие квантовые коды существуют, явная конструкция семейств хороших кодов представляет собой совсем друтую проблему.
Действительно, ни одной такой конструкции не известно.7.15.Некоторые коды, исправляющие многократныеошибки7.15.1.Каскадные кодыВсе КККО, которые мы явно сконструировали до настоящего момента,имеютd = 3 (или d= 2) и, следовательно, могут исправить (в лучшем случае) одну ошибку. Теперь мы опишем несколько примеров кодов с большимрасстоянием.Наиболее простым способом построения кодов, которые могут исправить большее количество ошибок, является каскадное соединение кодов,способных исправить одну ошибку.
Каскадный код представляет собой код=внутри кода. Предположим, что мы имеем два КККО с k1, [[n 1 , 1,d 1 ]]код 0 1 и [[n 2 , 1, d 2 ]]-код 0 2 . Представим принадлежащее 0 2 кодовое словодлиныn2,построенное в виде когерентной суперпозиции произведенийсостояний, в которых каждый кубит находится в одном из состояний JO)или J1). Теперь, используя код 0 1 , заменим каждый кубит закодированнымсостоянием длиныn 1 ; то есть заменимРезультатом является код с длиной n =меньшим, чемd = d1 d 2 .наJO)JO),аn 1n 2 , k = 1Будем называть код02J1) на JI) кода 0 1 .и с расстоянием не«внешним», а01-«внутренним».Собственно, мы уже обсуждали один пример такой конструкции: 9-кубитовый код Шора.
В этом случае внутренним кодом является трехкубнтовый код повторения с генераторами стабилизатораZZl,а внешним-lZZ,(7.201)трехкубитовый «фазовый код» с генераторами стабилизатораXXl,lXX(7.202)(коД повторения, повернутый иреобразованием Адамара). Стабилизаторкаскадного кода строится следующим образом. Прежде всего, в него включаются генераторы внутреннего кода.
В рассматриваемом примере это парыгенераторов, которые действуют на каждый из трех кубитов, содержащихсяв данном блоке внешнего кода, то естьZ 1 Z 2 , Z 2 Z 3 и так далее - всегошесть генераторов. Затем добавляются генераторы внешнего кода. В рассматриваемом случае это:X:XI,i:X:X,(7.203)74гдеГЛАВА 7i = 111, аХ=ХХХ, то есть пара генераторов повернутого преобразованием Адамара кода повторенияно с операторами(7.202),1иХ, замененными на закодированные операторы внутреннего кода. Вы легко распознаете в них восемь генераторов стабилизатора обсуждавшегося ранее кодаШора. В этом случае внутренний и внешний коды имеют единичное расстояние (например,Z11коммутирует со стабилизатором внутреннего кода),>однако каскадный код имеет расстояние3 d = d 1 d 2 = 1.
Это случилосьпотому, что код был так искусно сконструирован, что закодированные операции внутреннего кода с весами1и 2не коммутируют со стабилизаторомвнешнего кода. (Все было бы иначе, если бы мы состыковали код повторения с самим собой, а не с фазовым кодом!)Каскадное соединение кодастояниемс самим собой дает код с рас[[5, 1, 3]]d = 9 (способный исправить четыре ошибки); n = 25 являетсяминимальной длиной любого известного кода при[[п,1, 9]]приn = 23,24 согласовывался быk = 1иd = 9.(Кодс границей Рейнса, но неизвестно, существует ли на самом деле такой код).Стабилизатор каскадного кодаимеет[[25, 1, 9]]24 генератора.
Двадцатьиз них получаются как четыре генератора М 1 2 3 4 , действующие на каждыйиз пяти субблоков внешнего кода, а оставшиес~'четыре- это закодированные операторы М 1 2 3 4 внешнего кода. Отметим, что стабилизатор содержит элементы с ве~~~ четыре (элементы стабилизатора, действующие накаждый из пяти внутренних кодов); следовательно, код вырожденный. Этотипичный пример каскадного кода.Нет причин ограничиваться двухуровневым каскадированием кодов.Из L КККО с параметрамииерархический код всего сLможно построить11 ]], ...уровнями кодов внутри кодов; он имеет длину[[n ,1,d,[[nL,1,dL]](7.204)и расстояние(7.205)В частности, путем L-кратного каскадирования кода[[5, 1, 3]]можно построить код с параметрами(7.206)Строго говоря, это семейство кодов не может защитить от количества ошибок, пропорционального их длине. Скорее, отношение количества ошибоккоторые могут быть исправлены, к длине.f.,.,.,n_!_2n(~)L5t,равно'(7.207)7.15.НЕКОТОРЫЕ КОДЫ, ИСПРАВЛЯЮЩИЕ МНОГОКРАТНЫЕ ОШИБКИчто стремится к нулю при большом75L.
Но расстояние d может оказаться обманчивой мерой того, как хорошо работает код. Вполне достаточно, чтобывосстановление, отказывая лишь для некоторых способов выбораошибок, оставалось успешным для типичных способов выбораных кубитов. Действительно, при большомисправитьpnnир>pnt<<pnошибочО каскадные коды могуттипичных ошибок.Фактически, тот способ, которым обычно используются каскадные коды, не в полной мере реализует их возможности исправления ошибок.
Чтобы быть конкретнее, рассмотрим код[[5, 1, 3]]в случае, когда каждый изпяти кубитов независимо подвергается действию деполяризующего каналас вероятностью ошибки р (то есть каждая из ошибок Х, У,Zвозникаетс вероятностью р/3). Несомненно, восстановление будет успешным, еслив блоке возникнет меньше двух ошибок. Следовательно, как в разделе7.4.2,вероятность сбоя можно ограничить неравенствомPrail= P(l) ~ ( ~) Р2 = 10Р 2 ·Теперь рассмотрим работу каскадного кода(7.208)[[25, 1, 9]]. Чтобы облегчитьсебе жизнь, выполним восстановление простым (но неоптимальным) способом. Сначала произведем восстановление в каждом из пяти субблоков,измеряя М 1 , 2 , 3 , 4 , чтобы получить синдромы содержащихся в них ошибок.После этого измерим генераторы стабилизатора М 1 2 3 4 внешнего кода,чтобы получить его синдром и, если он обнаруживает'о'~ибку, к одному изсубблоков применим один из закодированных операторов Х, У илиZ.Для внешнего кода восстановление будет успешным, если повреждено не более одного из субблоков, а вероятность p(l) повреждения субблокаограниченанеравенством(7.208); таким образом, для кода [[25, 1, 9]] вероятность отказа процедуры восстановления ограничена сверху(7.209)Очевидно, что это не самая лучшая процедура, поскольку причиной сбоямогут стать четыре ошибки, если они окажутся по две в двух разных субблоках.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
