М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 154
Текст из файла (страница 154)
12.1. Различение квантовых состояний и доступная информация 651 у = Н((1+ сое(0))/2), как уже ранее отмечалось. Заметим, что когда 0 ВВ т/2, существует некоторая конечная вероятность того, что Боб сделает ошибку в своем предположении. Эта вероятность становится тем больше, чем ближе 0 к нулю. Наконец, когда 0 = 0 и два состояния неразличимы, нижняя граница показывает, что, как мы и ожидали, вероятность ошибки Боба, по крайней мере, 1~, что не лучше, чем если бы он действовал наугад. Упражнение 12.3. Используйте границу Холево для доказательства того, что и кубитов не могут быть использованы для передачи более чем и битов классической информации.
ж а.е в >159 гг а е е.| ег ел ел ел м е,г е.а м В/и Рис. 12.2. Нижняя граница вероятности ошибки Баба в случае, когда Алиса приготавливает состояние )О) или совВ)0) + вгпВ)г). Нижняя грзницз получена с использованием нерзеенствв Фзно и границы Холево. Этз граница равна нулю при В = гг/2, когда состояния можно нздежно различить. Упражнение 12.4. Предположим, что Алиса посылает Бобу равномерную смесь четырех чистых состояний )х,) =)о), >х > у' - )>о> е гв >), >х > = у' - )>о> е ,Гг: н >г>), >х > =>/- '>>о> е г "'л>1>). (12.20) (12.21) (12.22) (12. 23) Покажите, что максимум взаимной информации между результатом измере- ния Боба и состоянием, приготовленным Алисой, меньше одного бита.
Известна РОМ, которая достигает яз 0,415 бит. Можете ли вы построить ее или даже лучшую, которая достигает границы Холево? 662 Глава 12. Квантовая теория информации Вставка 12.2. Неравенство Фаио Допустим, что мы хотим узнать значение случайной величины Х, основываясь на знании другой случайной величины У. Интуитивно мы предполагаем, что условная энтропия Н(Х~У) определяет, насколько точно мы можем это сделать. Неравенство Фаио делает наше интуитивное предположение строгим и устанавливает гранину точности, с которой мы можем определить Х при известном У.
Предположим, что Х гв 7(У) — некоторая функция У, которую мы используем в качестве нашего наилучшего предположения об Х. Пусть р, ш р(Х ф Х) — вероятность того, что наше предположение неверно. Тогда неравенство Фано устанавливает, что Н(р,) + р, 1о8((Х! — 1) ) Н(Х(У), (12.16) где Н( ) — двоичная энтропия и ~Х( — число возможных значений Х.
Количественно неравенство показывает, что если Н(Х(У) велика (т. е. сравнима по величине с 1о8(~Х~ — 1)), то вероятность р, совершения ошибки должна быть также велика. Чтобы доказать неравенство Фано, определим «перемениую ошибкиэ, Е аэ 1, если Х ф Х и Е = — О, если Х = Х. Заметим, что Н(Е) = Н(р,). Используя цепное правило для условных энтропий, получаем Н(Е, Х~У) = Н(Е(Х, У) + Н(Х~У). Но Е полностью определена, если известны Х и У, так что Н(Е~Х, У) = 0 и, следовательно, Н(Е, Х(У) = Н(Х(У).
Вновь используя цепное правило для энтропий, находим Н(Е, Х~У) = Н(Х~Е, У) + Н(Е(У). Применение дополнительных условий уменьшает энтропию, так что Н(Е~У) < Н(Е) = Н(р,), и, следовательно, Н(Х~У) = Н(Е, Х(У) < Н(Х~Е, У) + Н(р,). Доказательство неравенства Фано завершается оцениванием Н(Х~Е, У) следующим образом (мы опустили несколько простых алгебраических деталей, которые вы легко восстановите): Н(Х~Е, У) = р(Е = 0)Н(Х(Е = О,У) + р(Е = 1)Н(Хф = 1, У), (12.17) < р(Е = 0) х О+ р, 1о8ОХ( — 1) = р, 1об()Х) — 1), (12.18) где неравенство Н(Х!Е = 1, У) < 1о8((Х! — 1) следует из того факта, что при Е = 1 имеем Х ф У и Х может принимать не больше, чем ~Х(— 1 значений, что ограничивает энтропию Х, и, следовательно, условную энтропию Х величиной 1о8((Х! — 1). Подставляя Н(Х~Е, У) < р, 1о8((Х) — 1) в Н(Х(У) < Н(Х~Е, У) + Н(р,), получаем неравенство Фано Н(Х(У) < Н(р,) + р, 1о8(~Х ~ — 1). 12.2 Сжатие данных Элементарный динамический процесс — сжатие данных — рассматривается как в классической, так и в квантовой теории информации.
В самом общем виде 12.2. Сжатие данных 653 проблема сжатия данньгх заключается в том, чтобы определить, какие минимальные физические ресурсы требуются для хранения информации источни кар Это одна из фундаментальных проблем теории информации. Оказывается, что методы решения этой проблемы как в классической, так и в квантовой теории информации имеют гораздо большую область применения, чем собственно сжатие данных. В этом разделе мы детально изучим как квантовое, так и классическое сжатие данных. 12.2.1 Теорема Шеннона о кодировании для канала без шума Теорема Шеннона о кодировании для канала без шума количественно определяет степень, до которой можно сжать информацию, создаваемую источником классической информации.' Что мы понимаем под источником классической информации? Возможны разные модели такого источника.
Простая и очень важная модель источника — это последовательность случайных величин Хм Хз,..., значения которых представляют собой данные на выходе источника. Удобно предположить, что эти случайные величины принимают значения из конечного алфавита символов, хотя обобщения на бесконечные алфавиты тоже возможны. Более того, будем считать, что случайные величины Х; независимы и одинаково распределены; такой источник информации называется стпационарным. В реальном мире подобные источники не часто встречаются. Легко увидеть, что буквы в английском тексте не располагаются независимо друг от друга; между буквами существует сильная корреляция.
Например, буква «Ь» встречается после буквы «1» гораздо чаще, чем можно ожидать, основываясь на общей частоте, с которой буква «Ь» встречается в обычном английском тексте. Мы говорим, что появления букв «1» и «Ь» не являются независимыми, между ними есть корреляция. Тем не менее, на практике многие источники информации (включая английский текст) мамаю рассматривать как стационарные, и методы, разработанные для стационарного источника, могут быть обобщены на более сложные источники.
Прежде чем перейти к техническим деталям теоремы Шеннона, используем простой пример, чтобы интуитивно понять результат. Пусть стационарный источник информации выдает биты Хы Хз, Хз,..., каждый из которых может быть равен нулю с вероятностью р и единице с вероятностью 1 — р. Основная идея, на которой основана теорема Шеннона, разделить возможные последовательности значений хы..., х„случайных величин Хы..., Х„, на типичные последовательности, которые встречаются с большой вероятностью, и нетипичные последовательности, которые встречаются редко. Как это делается? Мы предполагаем, что при больших и с большой вероятностью доля символов «0» на выходе источника будет равна р, а доля символов «1» будет равна 1 — р.
Последовательности хы..., х„, для которых это предположение справедливо, т Задача о сжатии ииформации зквивалеитиа задаче о кодировании информации для передачи по каналу без шума. При этом степень сжатия соответствует скорости передачи В дальнейшем более общий термин «скорость передачи» будет использоваться для количеств«киото описания степени сжатии — Прим. ред. 654 Глава 12. Квантовая теория информации называются типичными последовательносп|ими. Используя предположение о стационарности для данного источника, получим р(х|,...,х„) = р(х|)р(хэ) ... р(х„) и| р""(1 — р)~ »1" (12,24) для типичных последовательностей.
Возьмем логарифм от обеих частей выра- жения: — 1ояр(хы..., х„) ж — пр!оя р — п(1 — р) 1оя(1 — р) = пН(Х), (12.25) где Х вЂ” случайная величина, распределенная в соответствии с распределением источника, и Н(Х) = — р 1оя(р) — (1 — р) 1оя(1 — р) — энтропия данного источника, называемая скоростью создания сообщений. Таким образом, р(х|,..., х„) 2 "~(~>, откуда видно, что может быть не больше 2" Я|а1 типичных последовательностей, поскольку полная вероятность всех типичных последовательностей не может быть больше единицы.
Теперь у нас есть средства, чтобы понять простую схему сжатия данных. Предположим, что данные на выходе источника х|,..., х„. Чтобы сжать эти данные, мы должны убедиться, действительно ли последовательность х|,..., х„ типичная. Если нет, мы считаем, что произошла ошибка.
К счастью, при больших п это случается очень редко, поскольку почти все последовательности типичные в пределе больших и. Если на выходе типичнан последовательность, мы ее сжимаем. Поскольку существует не больше 2 "Я<х1 типичных последовательностей, требуется только пН(Х) битов, чтобы однозначно задать типичную последовательность. Мы выбираем некоторую схему кодирования типичных последовательностей и производим сжатие выходю |к данных источника до соответствующей строки пН(Х) битов, описывающей встретившуюся типичную последовательность; позже эта строка может быть развернута. При больших п данная схема работает корректно с вероятностью, приближающейся к единице. Эта схема вызывает несколько критических замечаний: (а) Схема имеет маленькую, но конечную вероятность сбоя.
В немного более сложных схемах используются похожие идеи, чтобы исключить возможность совершения ошибки. (6) Чтобы произвести сжатие, мы должны подождать до тех пор, пока источник не выдаст большое число п символов. Существуют варианты данной схемы, которые позволяют производить обработку по мере того, как источник выдает символы.
(в) Ие предложена явная схема, преобразующая выходные данные источника в сжатые последовательности. Однако небольшим усложнением алгоритма эта проблема может быть решена. (г) Конкретная процедура сжатия данных зависит от распределения выходных данных источника. А если это распределение неизвестно? В этом случае можно воспользоваться алгоритмами универсальноео сжатия. Читателю, интересующемуся этими и другими вопросами, мы рекомендуем обратиться к книге Ковера и Томаса, ссылка на которую дана в равд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
