М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 160
Текст из файла (страница 160)
(12.76) Заметим также, что по определению (12.75) размерность подпространства, на которое проектирует Рм, может быть не более 2"1 +'1, и поэтому Е(2 (р )) < 2п(У+я) (12.77) — 1/2 -1/2 Ем ы ~~~ РРм Р РРмР ~~1, РРм Р, (12.78) где А '/2 — обобщенный обратный оператор к А1/2, т. е.
данный оператор является обратным к А1/2 на носителе А и равен нулю в остальном пространстве. Отсюда следует, что 2„м Ем < 1, и мы можем определить еще один положительный оператор Ео =- 1 — 2„м Ем, чтобы завершить РОЧМ. Интуитивно понятно, что эта конструкция соответствует методу декодирования, описанному для двоичных симметричных каналов. В частности, с точностью до малых поправок Ем равен проектору Рм, и измерение Боба (Ем) соответствует, по существу, проверке, действительно ли состояние на выходе нз канала попадает в то пространство, на которое проектирует Рм, это пространство можно рассматривать как аналог сферы Хэмминга радиуса пр вокруг кодового слова, использованной для двоичного симметричного канала.
Основной частью доказательства того, что случайное кодирование работает, является получение верхней границы для средней вероятности ошибки р,р. Это подробно изложено во вставке 12.5. Полученный результат имеет вид 1 р, < — ~~~ 3 21(ом(1 — Р)) + ~ сг(РомРРм ) + 2г(ем(1 — Рм)) м м~м (12.79) Теперь используем понятие типичности, чтобы построить РОЧМ для операции декодирования Боба. Введем 12.3. Передача классической информации 677 Величина р,р определяется по отношению к конкретному набору кодовых слов. Мы вычислим математическое ожидание этой величины по всем случайным кодам.
По построению Е(ом) = йз", а пм и Рм — независимы при М' ф М; отсюда получаем Е(р,р) < 3 1г(й®" (1 — Р))+(2"л — 1) Фг(Рйз"РЕ(Р~))+Е(1г(вг(Х вЂ” Рг))). (12.80) Подстановка (12.73) в (12.76) дает Е(р,р) < 43+ (2"л — 1) 1г(Рй®"РЕ(Р~)). (12.81) Но Раз "Р < 2"1в~ ~ '~1 и из (12.77) имеем Е(аг(Рг) < 2"~й+'~, откуда Е(Ррр) ~ (46+ (2"л — 1)2 "~~~~~ й '~ (12 82) Если В < Я(о)Я, получаем Е(р,р) — ~ 0 при н -+ оо. Действительно, выбрав ансамбль (р, ру), при котором достигается максимум в (12.71), мы вялим, что неравенство должно быть справедливо при В < т(б). Следовательно, должна существовать последовательность кодов со скоростью передачи В, такая что р,р — ~ 0 при увеличении размера п кодового блока.
Отсюда следует, что для любого фиксированного е > 0 (заметьте, что здесь е имеет другой смысл по сравнению с тем, что был раньше!) при достаточно больших н е ~мрм < . (12.83) Очевидно, что для того, чтобы это выполнялось, по меньшей мере, половина сообщений М должна удовлетворять условию рм < 2е. Мы строим новый код, удаляя половину кодовых слов (кодовые слова с большой рм) из кода со скоростью В и р,р < е; в результате получается новый код с 2"л/2 = 2"~л '7") кодовыми словами и с р г < 2е для всех сообщений М.
Очевидно, что этот код также имеет асимптотическую скорость передачи В, и вероятность ошибки может быть сделана сколь угодно малой для всех (а не в среднем) кодовых слов при достаточно большом н. Итак, мы показали, что для любого В, меньшего г(б), определенного в (12.71), существует код, использующий факторизованные входные состояния, который позволяет передавать информацию по каналу о со скоростью В. Наше доказательство имеет тот же недостаток, что и доказательство теоремы Шеннона о кодировании для классического канала с шумом, использующее случайное кодирование, а именно, оно не обеспечивает конструктивную процедуру выполнения кодирования, но тем не менее демонстрирует существование кодов со скоростями вплоть до пропускной способности. Доказательство верхней границы Пусть В больше, чем т(б), определенной в (12.71).
Покажем, что Алиса не может надежно передавать информацию Бобу с такой скоростью по каналу б. Наша основная стратегия — предположить, что Алиса создает сообщения М, выбирая их случайным образом из набора (1,..., 2"л), и показать, что средняя, а следовательно и максимальная, вероятность ошибки Алисы ограничена снизу положительным числом. 678 Глава 12, Квантовая теория информации Вставка 12.6. Теорема ХШВ1 оценка величины ошибки Наиболее технически сложной частью доказательства теоремы ХШВ яв- ляется оценка р,р.
Здесь мы покажем в общих чертах, как это сделать; пропущенные шаги можно рассматривать как упражнения, которые необ- ходимо выполнить, чтобы полностью восстановить доказательство. Введем отображение ~Екм) ш Р~Екм). Тогда -1/2 Ем = ~~' ~~1, )Екм )(Ек м! М' КЕТУ -1/2 х ~~, ' ~Екм)(Екм~ ~~; ~~' !Екм )(Ем / (12 84) КЕТм М' КЕТМ Полагая -1/2 сем кум' кй = (Ек ~ ~~' ~ ~~Ек")(Ек м"~ ~Ек,') (12 86) М" К"ЕТм- среднюю вероятность ошибки можно записать как 1 р.,= —,„.~„~~-~ ~.
Лй <, Л, 1)' М 1 К К'ЕТм (12.86) Используя 2 к Лк — — 1 и опуская неположительные члены, мы ви/цлм, что м 1 рср ' 2рл Лк (1 оя~м,к),(м,к>) + ~) )Лкм (12 87) КЕТм Кйтм 1 РСР ~~ м Л (1- цм,к,<м,к,)+ ~ Л КЕТм КЯТм (12,88) Определим матрицу Г с элементами 71М КЛ1м к1 ш (Екф~Ек ), где индексы К б Тм и К' б Тм. Удобно работать в пространстве матриц с такими индексами; Е обозначает единичную матрицу в этом пространстве, а эр (шпур) — операция взятия следа по этим индексам.
Вычисления показывают, что Г1/2 = (а<мк1 1М к1), откуда следует, что сто < ( у<мк> 1М«1 ( 1. Используя (12.87), а также тот факт, что 1 — х2 = (1 + х)(1 — х) < 2(1 — х) при 0 < х < 1, получаем 12.3. Передача классической информации 679 Введем диагональную матрицу Л ив е 61а8(ЛКМ) и заметим, что 2(Е Гг1г) (Е Г~/г)г + (Е 1 ) (12.89) (Е Г)г(Е+ Г-ь1г)-г+ (Е Г) (12 90) < (Š— Г) + (Š— Г). (12.91) Следовательно, 2~ ~' Лкм(1 — п(м,кум,к>) = 2 эр(Л(Š— Г мг)) (12.92) М КЕТм ( р(Л(Š— Г) ) + р(Л(Š— Г)). (12.93) Вычисляя шнуры в правой части выражений, подставляя результаты в (12.88) и выполняя некоторые простые алгебраические действия, получаем 1 Рср 2мл 7 ~ ,'СЛК 2 — 2~[м,кум,к~+ ~ Ь~М,К1~М,К~!' к К'фк + ~~', 17(м,к1(м,к)! + ~, Лк М 'Ф М, К' Е Тм КЕТм (12,94) Используя соответствующие определения и выполняя простые алгебраи ческие действия, находим р,р ~ — „л ~~ 2 Сг(пм(1 — Р)) + гг(<тм(1 — Р)РМ(1 — Р)) 1 сг(Ром РРМ~ ) + сг(пм (1 — Рм)) М'Фм (12.95) Второе слагаемое меньше, чем Фг(ом(1 — Р)), что дает нужную оценку величины ошибки, (12.79).
2,М(1 — сг(омЕМ)) Рср = (12.96) Предположим, что Алиса кодирует сообщение М как рм = рмг чг... З рм (соответствующие входные состояния обозначаются через и вместо р), а Воб декодирует это сообщение, используя РОМ (Ем); без потери общности можно считать, что РО'ЧМ содержит элемент Ем для каждого сообщения и, возможно, дополнительный элемент Ео, чтобы выполнялось соотношение полноты ,'См Ем = 1. Это дает среднюю вероятность ошибки 880 Глава 12. Квантовая теория информации Из упр. 12.3 мы знаем, что В < 1о8(Н), где Н вЂ” размерность пространства со- стояний на входе канала, и поэтому РОМ (Ем) содержит не более Ю' + 1 элементов.
Из неравенства Фане следует, что Н(Рсэ) + Р~э 1о8(<1п) ) )Н(М~У), (12.97) где У вЂ” результата измерения над выходным состоянием Боба, и, таким обра- зом, пр,г1ой4 > Н(М) — Н(М:У) — Н(рер) = п — Н(М:У) — ' Н(рср). (12 98) Используя сначала границу Холево, а затем субаддитивность энтропии, полу- чаем (12.99) 2"л )' ( Е(~а) ~< 3=1 М (12,100) где йз— : 2 м ом/2"л. Каждый из п членов суммы в правой части не превышаег х(Е), так что Н(М У) < пх(Е). (12.101) Подстановка в (12.98) дает пр,р 1ойд > п(ВХ(Е)) — Н(р,р), и, следовательно, при большом п получаем Рср . > ( — х(Е)) (12.102) положительную нижнюю границу для средней вероятности ошибки при В > ~(Е), что завершает доказательство того, что с(Е) является верхней границей пропускной способности для факторизованного состояния.
Примеры Интересным следствием теоремы ХШВ является то, что любой квантовый кв нал можно использовать для передачи классической информации, если Е не является константой. Если Е не является константой, то существуют такие чистые состояния !9) и !ср), что Е(ф)(фО ф Е(/ср)(у/). Подставив ансамбль, состоящий из этих двух состояний с равными вероятностями —, в выражение (12.71) для пропускной способности факторизованного состояния, мы видим, что С00<Е) >Е( (~~)(~~) <")(~~)~ — -Е<Е<Ю<б!)) — ~Е<Е(м)«р!)) >0, 2 / 2 2 (12.103) где второе неравенство следует из строгой во гнутости энтропии (подразд. 11.3.5). 12.4.
Квантовая информация в квантовых каналах с шумом 681 Рассмотрим простой пример деполяризующего канала с параметром р, когда пропускная способность для факторизованного состояния может быть точно вычислена. Пусть (рз, ~«)~1) ) — ансамбль квантовых состояний одного кубита. Тогда имеем 2' (12.104) квантовое состояние с собственными значениями (1 + р)/2 и (1 — р)/2, откуда Я(Е(~Ф )(Ф О) = Н (12.105) где выражение справа не зависит от ~ф ). Следовательно, максимум в (12.71) достигается при максимальном значении энтропии Я(~,1Е(~ф )(ф ~)) в один бит, когда («)у) — ортонормированный базис (например, )О) и (1)) для пространства состояний одного кубита. При этом пропускная способность деполяризирующего канала с параметром р.
для факторизовалного состояния равна С00(Е) =1- Н 1 2 / (12.106) 'Упражнение 12.12. Используя доказательство теоремы ХШВ, докажите тео- рему Шеннона о кодировании для классического канала с шумом, упрощая доказательство там, где возможно. 12.4 Квантовая информация в квантовых каналах с шумом Сколько квантовой информации можно надежно передать по квантовому каналу с шумом? Проблема определения пропускной способностпи квантового канала для квантовой информации изучена хуже, чем проблема определения пропускной способности по квантовому каналу с шумом для классической информации. Мы представим здесь некоторые теоретико-информационные средства, которые были разработаны для изучения пропускной способности квантового канала для квантовой информации, включал важные квантовые теоретикоинформационвые аналоги неравенства Фано (вставка 12.2), неравенства обработки данных (подрэзд.