М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 131
Текст из файла (страница 131)
11. Важность границы ВаршамоваГильберта заключается в том, что она гарантирует существование хороших кодов при условии, что не слишком большое количество битов (х) кодируется не слишком маленьким количеством битов (и). Доказательство границы Варшамова-Гильберта достаточно просто и оставлено в качестве упражнения. Упражнение 10.23. Докажите границу Варшамова-Гильберта. Мы завершим наш обзор теорик классического исправления ошибок вве. дением понятия двойственности.
Пусть С вЂ” (и, х)-код с порождающей матрицей С и проверочной матрицей Н. Можно построить другой код, С~, двойственный коду С с порождающей матрицей Н и проверочной матрицей Сг. Другими словами, код, двойственный коду С, содержит все возможные кодовые слова сообщения у, каждое из которых ортогонально всем сообщениям кода С. Код называется слабо самодвойственным, если С С Сл и строго самодвойственным, если С = С .
Построение двойственного кода естественным образом возникает в теории исправления квантовых ошибок и является основой построения важного класса квантовых кодов — СЯЯ кодов. Упражнение 10.24. Покажите, что код с порождающей матрицей С слабо самодвойственный тогда и только тогда, когда С~С = О. 'Упражнение 10.25. Пусть С вЂ” линейный код. Покажите, что если х Е С"., вес( 1) = ~С~, а если х ф С, то Еэес( — 1) " = 0 10.4.2 Коды Кальдербанка — Шора — Стыни Наш первый пример большого класса квантовых кодов исправляющих ошибки — коды Кальдербавка-Шора-Стина, также называемые СЯЯ кодами. СЯЯ коды являются важным подклассом симплектиЧеских кодов. 10.4.
Построение квантовых кодов 553 Пусть С~ и Сз — классические линейные ]и, в1] и (и, йз]-коды, такие, что Сз С См а С~ и Сзх могут исправйть $ ошибок. Построим квантовый [и, й~ — йз]- код СЯЯ(Смсе), способный исправлять ошибки в ~ кубитах, СЯЯ код С~ по Сз, следующим образом. Допустим, что х е С1 — любое кодовое слово из См Введем квантовое состояние ]х + Сз): (10.64) — ( — 1)~*~"~ь2]х+ д+ е1). /]Се] „,, (10.65) Для обнаружения классической ошибки удобно ввести вспомогательную систему из достаточного количества кубитов для хранения синдрома кода Съ Все вспомогательные кубиты вначале находятся в состоянии ]О) .
Мы используем обратимое вычисление, чтобы применить проверочную матрицу Н1 кода См преобразовав состояние ]х+д+е1)]0) в ]х+д+е1)]Н1(х+д+е1)) = ]х+д+е1)]Н|е1) (так кэк член х + д 1 С1 уничтожается проверочной матрицей). В результате этой Операции получим состояние ( — 1)~*+"~" ]х+ д+ е1)]Н1е1). ~Л з]„,с, (10.66) 'Упражнение 10.26.
Пусть Н вЂ” проверочная матрица. Объясните, как выполнить преобразование ]х) ]О) — 1 ]х) ]Нх), используя схему, соснжщую только где + означает побитовое сложение по модулю 2. Пусть х' — элемент С1 такой, что х — х' б Сз. Легко видеть, что ]х + Сз) = ]х' + Сз), и, следовательно, состояние ]х + Сз) зависит только от класса смежности С1(сш в котором находится х. Это объясняет обозначение, которое мы использовали для ]х+ Сз). Кроме того, если х и х' принадлежат к разным классам смежности по Сз, то не существует таких д, д' е Сз, для которых х + д = х + д' и, следовательно, ]х+ Сз) и ]х'+ Сз) — ортонормированные состояния. Определим квантовый код СЯЯ(Сы Сз) как линейную оболочку состояний ]х+ Сз) для всех х е Сь Число классов смежности Сз в С1 равно ]С1]/]Се], так что размерность СЯЯ(Сыск) равна ]С1Цсз] = 2ь' "' и, следовательно, СЯЯ(Смсе) является ]п,йь — йз]- кодом.
Мы можем использовать классические свойства С1 и Сзх для обнаружения и исправления квантовых ошибок. Действительно, с помощью кода СЯЯ(См Сз) можно исправить до 4 классических и фазовых ошибок, используя свойства С1 и Сзь соответственно. Предположим, что классическая ошибка описывается и-битовым вектором ем в котором единицы расположены в местах, где произошла ошибка, а нули в остальных местах. Фазовая ошибка описывается и-битовым вектором еъ Если исходное состояние было ]х+ Сз), то испорченное ошибками состояние равно 554 Глава 10.
Исправление квантовых ошибок из элементов СКОТ. Обнаружение ошибки производится измерением вспомогательного состояния. В результате измерения получаем Н«еь Исключение вспомогательной системы дает ( — 1)~*+"~"!х+ у+ е~). (10.67) Зная синдром ошибки Н~ем можно определить ошибку ем так как код С~ может исправлять до 8 ошибок. Исправление выполняется простым применением элементов НОТ к кубитам, соответствующим ненулевым позициям в еь После исправления получаем состояние — Е(- )'*'"'"!*+ р) (10.68) Д!С !„ Чтобы обнаружить фазовую ошибку, мы применяем элемент Адамара к кэж дому кубиту. При этом получаем состояние А!Сз!2" .
„,и (10.69) где сумма берется по всем возможным и битовым ю Введя обозначение з' = з+ ез, получим ЛГ! 2" ( — 1)~*~яр» /з'+ ез). (10.70) Легко показать (см. УпР. 10.25), что если з' Е Сз~, то 2 „еп,(-1)"' = !Сз!, а если з' ф Сз~, то 2 „еп,( — 1)" * = О. Поэтому можно переписать состояние следующим образом: с ~ ( — 1)™/з +ее). (10.71) Это выражение очень похоже на то, которое было получено для случая классической ошибки, заданной вектором ез! Как и при исправлении классической ошибки, мы вводим вспомогательную систему и обратимым образом применяем проверочную матрицу Нг для кода Сэ~, чтобы определить синдром Нзез. Затем, исправив «классическую ошибку» ез, получаем состояние 2"/!Сз! нес'~ (,' ~; (-1)*''!з).
(10.72) После этого применяем элемент Адамара к каждому кубиту. Мы можем получить непосредственно этот результат; тот же результат получается, если применить элементы Адамара к состоянию (10.71) с ез = О. Так как элемент Адамара совпадает с обратным элементом Адамара, вернемся к состоянию (10.68) с ез = 0: 10.4. Построение квантовых кодов 555 — ]в+ д), ч ]Се] вел (10.73) т.
е. к исходному закодированному состоянию. Важным применением СЯЯ кодов является доказательство квантового аналога границы Варшамова-Гильберта, гарантирующей существование хороших квантовых кодов. В пределе больших и квантовый ]и, л]-код, способный исправлять ошибки в 1 и менее кубитах, существует для некоторых й, таких, (10.75) с параметрами и и с, эквивалентен коду СЯЯ(Сы Сз) в том смысле, что оба кода имеют одинаковые свойства исправления ошибок.
Такой код будем называть в дальнейшем СЯЯ,„(См Сэ); он будет полезен нам при изучении квантового распределения ключей в подрэзд. 12.6.5. Код Сшнна Важный пример СЯЯ кода можно построить, используя [7,4, 3]-код Хэмминга с проверочной матрицей 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 (10.76) Обозначим этот код через С, и введем С~ ш С и Сэ ш С~.. Чтобы использовать С~ и Сэ для построения СЯЯ кода, проверим сначала, что Сэ с Сь — > 1 — 2Н( — ), (10.74) Таким образом, существует хороший квантовый код, исправляющий ошибки, если только не пытаться кодировать и кубитами слишком большое число кубитов й. Доказательство границы Варшамова — Гильберта для СЯЯ кодов гораздо сложнее, чем в классическом случае из-за ограничений на классические коды С~ и Сз.
Оно оставлено в-качестве задачи в конце главы. Итак, С~ и Сэ — классические линейные ]и, й~] и ]и, лэ]-коды соответственно, такие, что Сэ С См а С~ и Сэь способны исправлять ошибки в 4 или менее битах. СЯЯ(См Сз) — квантовый ]и, й~ — /сз]-код, способный исправлять произвольные ошибки не более, чем в $ кубитах. Для обнаружения и исправления ошибок требуются только элементы Адамара и Сг10Т, причем их количество линейно зависит от размера кода. Число элементов, выполняющих кодирование и декодирование, также линейно зависит от размера кода.
Мы не обсуждаем этот вопрос здесь, в более общем виде он будет рассмотрен в подразд. 10.5.8. 'Упражнение 10.27. Покажите, что код, заданный формулой 556 Глава 10. Исправление квантовых ошибок По определению, проверочная матрица кода Сз = С равна транспонированной порождающей матрице кода С~ = С: 1 0 0 0 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 0 0 0 0 1 1 1 1 Н[С]=С[С]т= (10.77) [Оь) = — ]0000000) + [1010101) + [ОП0011) 1 ~/8 + [П00110) + [0001111) + [1011010) + [0111100) + ]1101001) . (10.78) Чтобы определить другое кодовое слово кода Стина, нужно найти элемент Сы не содержащийся в Сз.
Таким элементом, например, является (1, 1, 1, 1, 1, 1, 1). Для [1ь) получаем: [1ь) = — ]1111111) + [0101010) + [1001100) 1 ч'8 + [0011001) + [1110000) + [0100101) + [1000011) + [0010110) . (10.79) эгпражиение 10.28. Проверьте, что транспонированная матрица (10.77) является порождающей матрицей [7,4,3]-кода Хэмминга. Сравнивая матрицы (10.77) и (10.76), мы видим, что линейная оболочка строк Н[Сз] строго содержит линейную оболочку строк Н[Сз], и, так как соответствующие коды являются ядрами этих матриц, мы делаем вывод, что Сз с Сь Кроме того, поскольку Сзл = (С".)". = С и С~ и Сэь имеют кодовое расстояние 3 и способны исправлять ошибки в одном бите.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
