М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 156
Текст из файла (страница 156)
В случае Е(Х) ф О легко получить результат, введя величины У; = — Х,. — Е(Х), У гя Х вЂ” Е(Х). (12.39) которые независимы и одинаково распределены, причем Е(У) = О и Е(Уг) < оо. Дальнейшее доказательство повторяет рассуждения, приве- денные выше. Упражнение 12.5 (сжатие данных переменной длины с нулевой ошибкой). Рассмотрим следующий эвристический подход для схемы сжатия данных переменной длины. Пусть хм...,х„— данные на выходе после и обращений к стационарному источнику с энтропией Н(Х). Если последовательность хг,...,х„типичная, посылаем иН(Х) — битовый номер этой типичной последовательности. Если последовательность хм...,х„— нетипичная, посы- 12.2.
Сжатие данных 659 лаем несжатое 1оя бп — битовое представление денной последовательности (напомним, что б — размер алфавита). На основе нашего эвристического предположения докажите, что этот источник может быть сжат в среднем до Я бит на каждый символ данных на выходе источника для любых Н ) Н(Х) с нулевой вероятностью ошибки.
и Род б куб итов и !од б и 5 (р) Рис. 12.3. Квантовое сжатие данных Преобразование скатия С", окимая квантовый источник р, переводит и 1ояИ кубитов в пЯ(р) кубитов Состояние источника корректно восстанавливается с помощью преобразования развертывания гУп «г 12.2.2 Теорема Шумахера о кодировании для квантового канала без шума Принципиальной особенностью квантовой теории информации является то, что квантовые состояния рассматриваются как информация и изучаются с теоретико-информационной точки зрения.
В этом разделе мы дадим определение квантового источника информации и изучим вопрос, до какой степени может быть сжата созданная источником «информация», т. е. квантовые состояния. Как определить понятие квантового источника информации? Как и в случае классического источника информации, когда совершенно не очевидно, как это сделать наилучшим образом. Можно привести несколько разных определений, не все из которых эквивалентны. Определение, которое мы будем использовать, основано на том, что мы хотим сжимать и развертывать запутанные состояния.
Более формально (стационарный) квантовый источник будет описываться гильбертовым пространством Н и матрицей плотности р в этом пространстве. Мы предполагаем, что р — состояние системы, являющейся частью большей системы, которая находится в чистом состоянии. Схема сжатия в 1/Н рэз для данного источника состоит из двух семейств квантовых преобразований С" и З", аналогичных операциям сжатия и развертывания, используемым в классическом случае. С" — преобразование сжатия, переводящее состояния из Не" в состояния 2нл-мерного пространства, сжатого пространстпвсь Мы можем представить сжатое пространство пН кубитами. Э" — преобразование развертывания, которое переводит состояния сжатого пространства в состояния исходного пространства состояний. Таким образом, комбинированное преобразование «сжатие-развертывание» вЂ” это З" о С". Ныпим критерием надежности является то; что в пределе больших и точность воспроизведения запутанности г'(реп,ггп о С") должна стремиться к единице.
Основная идея квантового сжатия данных проиллюстрирована на рис. 12.3. 660 Глава 12. Квантовая теория информации Основным техническим понятием, на котором основана квантовая теорема о кодировании для канала без шума, является квантовый аналог понятия типичных последовательностей. Приведем оператор плотности р, связанный с квантовым источником информации, к диагональному виду р = ~ р(х)(х)(х(, (12.40) ! 1 ( 1 — 1оя — Я(р)~ <е, и 1.р(х )р(хг) "р(х»)У (12.41) с-типичное состояние — это состояние ~х~)~хг)... ~хп), для которого последовательность хм..., х„— является с-типичной.
Определим с-пгипичнос подпросгпрансгпео как пространство, порожденное всеми с-типичными состояниями ~хг) ~хг)... ~х„). Обозначим с-типичное подпространство через Т(п, с) и проектор на с-типичное подпространство через Р(п, с). Отметим, что Р(п,с) = у ~х1)(хг! З ~хг)(хг~ Э... ~х„)(х„!. (12.42) я,я - типичная Теперь теорема о типичных последовательностях может быть преобразована в эквивалентную квантовую форму, иначе говоря, в теорему о типичном под- пространстве.
Теорема 12.5 (теорема о типичном подпространстве). 1. Пусть с > О. Тогда для любого б > 0 и достаточно больших и Фг(Р(п,с)ре") > 1 — б. (12.43) 2. Для любого фиксированного с > 0 и б > 0 при достаточно больших и размерность Т(п,с), ~Т(п,с)~ = сг(Р(п,с)) удовлетворяет неравенствам (1 — б)2п~л® '~ < !Т(п,с)/ < 2"~~®+Я~. (12.44) 3. Пусть Я(в) — проектор на любое подпространство в Не" размерности не более 2"л, где величина В < Я(р) фиксированная. Тогда для любого б > 0 и достаточно больших п Сг(Я(п)реп) < б. (12.45) где ~х) — ортонормированный базис и р(х) — собственные значения р.
Эти собственные значения имеют те же свойства, что и распределения вероятностей: они неотрицательны и их сумма равна единице. Более того, Н(р(х)) = Я(р). Следовательно, имеет смысл рассмотреть с-типичную последовательность хм..., х„, для которой как и в классическом случае, 12.2. Сжатие данных 661 В каждом случае результат может быть непосредственно получен при помощи закона больших чисел, но мы предпочитаем использовать теорему о типичных последовательностях, чтобы подчеркнуть тесную связь с методами, использованными в доказательстве теоремы Шеннона о кодировании для канала без шума.
Доиазатпельсптео. Часть 1. Отметим, что Гг(Р(ит с)р™ = ) р(хг)р(хз)... р(хп). (12.46) ют - типичнэя Результат непосредственно вытекает из части 1 теоремы о типичных последовательностях. Часть 2. Непосредственно еле,зует из части 2 теоремы о типичных последовательностях. Часть 3.
Разобьем левую часть (12.45) на след по типичному подпространству и след по нетипичному подпространству Фг(Я(п)ре") = сг(Я(п)ре"Р(п,с)) + гг(Я(п)ре" (1 — Р(п,с))), (12.47) и оценим каждый член отдельно. Для первого члена получаем ре".Р(п, с) = Р(п, с) ре"Р(п, с), (12.48) поскольку Р(п, с) — проектор, который коммутирует с ре". Однако, Гг(Я(п)Р(п,с)ре"Р(п,с)) < 2"Я2 "~збй '1, (12.49) поскольку собственные значения Р(п, с) ре" Р(п, с) ограничены сверху значением 2"<з<~~'>. Мы виднм, что при и -+ оо первое слагаемое (12.47) стремится к нулю. Отметим, что Я(п) < 1.
Поскольку Я(п) и ре" (1 — Р(и, с)) — положительные операторы, получаем О < Фг(Я(и)ре" (1 — Р(п, е))) < сг(ре" (1 — Р(п, с))) — ~ О при п — + оо, так что второе слагаемое тоже стремится к нулю при больших п, что и требовалось доказать. Используя теорему о типичном подпространстве, нетрудно доказать квантовый аналог теоремы Шеннона о кодирования для канала без шума. Основные идеи доказательства аналогичны, однако, оно несколько сложнее из-за появления некоммутирующвх операторов, которые не имеют классических аналогов. Теорема 12.6 (теорема Шумахера о кодировании для канала без гпума).
Пусть (Н, р) — стационарный квантовый источник. Если Н > Я(р), то существуег надежная схема сжатия в 1/В раз для источника (Н, р). Если Н < Я(р), то любая такая схема сжатия не надежна. Доказаптеаьстпео. Пусть Н > Я(р) и с > О такое, что Я(р) + с < Н. В соответствии с теоремой о типичном подпространстве для любого б > О и при достаточно больших и имеем 1г(ре"Р(и, с)) > 1 — б, и аппп(Т(п, с)) < 2™. Пусть Н, "— любое 2"и-мерное 662 Глава 12. Квантовая теория информации С"(и) ге Р(п, с)пР(п, а) + ~ ~АитАч (12.50) где А; ы (0)(1) и (1) — ортонормированный базис для ортогонального дополнения к типичному подпространству. Преобразование декодирования Р": Н, "— Нэ", по определению, тождественно на Н,", Р" (а) = и.
Из этих определений для кодирования и декодирования следует, что Р(рээ,'Рэ ОСИ) =! гг(рзпр(п, е)уз + Е ! Иг(рвиА»у2 > )гт(ри"Р(п,с))~~ > )1 — Ю)~ > 1 — 25, (12.51) (12.52) (12.53) где предпоследнее неравенство следует из теоремы о типичном подпространстве. Однако, 5 может быть сколь угодно малым для достаточно больших п, и, следовательно, существует надежная схема сжатия (С",З") при скорости передачи В, когда Я(р) < В.
Чтобы доказать обратное утверждение, предположим, что В < Я(р). Без потери общности допустим, что преобразование сжатия отображает из Нэ" на 2 "л-мерное подпространство с соответствующим проектором Я(п). Пусть Су— элементы преобразования сжатия С" и Р» — элементы преобразования развертывания З". Тогда имеем Р(ри",З" оС") = ~~~ ~гг(Р»Сур™)~ . 1» (12.54) Каждый из операторов С~ действует в подпространстве с проектором Б(п), так что Сз = Я(п)С»ь Пусть Я»(п) — проектор на подпространство, в которое подпространство Я(п) отображается при помощи Р», так что имеем Я" (п)Р»Я(п) = Р»Б(п) и, следовательно, Р»С = Р»Я(п)С, = Б»(п)Р»Б(п)С1 = Я"(п)Р»С, откуда Р( Эп Рэ, Сэ) ~ ~~ ~1 (Р„С 9»Я»( ))~з (12.55) гильбертово пространство, содержащее Т(п, с) .
Кодирование производится следующим обрезом. Сначала выполняется измерение, которое описывается полным набором ортогональных проекторов Р(п, е) и Х вЂ” Р(п,с); соответствующие результаты мы обозначаем 0 и 1. Если результат измерения О, больше ничего не делаем и данное состояние остается в типичном подпространстве. Если на выходе 1, заменяем данное состояние системы некоторым стандартным состоянием ~0), выбранным из типичного подпространства; неважно, какое состояние используется. Следовательно, кодирование является отображением С": Ни" -+ Н, "в 2"и-мерное подпространство Н,", имеющим представление в виде операторной суммы 12.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
