М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 159
Текст из файла (страница 159)
Рис. 12.8. Модель кодирования для классичвского источника информации лри наличии шума, иногда на»мвавмая моделью «источник-канал». Особенностью рассмотренной теоремы о кодировании для канала с шумом является то, что понятие классического источника информации не используется! Напомним, что ранее мы дали определение классического источника информации как последовательности независимых и одинаково распределенных 'Упражнение 12.10.
Предположим, что Фт и ЛГэ — два дискретных канала без памяти, такие, что алфавит на входе канала Л~~ совпадает с алфавитом на выходе канала Фэ. Покажите, что 12.3. Передача классической информации 673 случайных величин. Можно нетривиально объединить это понятие источника информации с теоремой о кодировании для канала с шумом, чтобы получить так называемую теорему о кодировании «источник-канал». Основная идея проиллюстрирована на рис. 12.8. Предположим, что источник информации имеет энтропию Н(Х). Используя теорему Шеннона о кодировании для канала без шума, можно сжать информацию от источника так, что потребуется только пН(Х) битов для ее представления.
Эту операцию иногда называют кодированием источника. Сжатые данные на выходе источника используются, в свою очередь, как сообщение на входе канала с шумом. Для передачи со скоростью В, меньшей пропускной способности, требуется пН(Х)(Я обращений к каналу, чтобы без искажений передать сжатые данные получателю, который может развернуть их, чтобы восстановить исходные данные от источника. Возможна ли более совершенная схема для передачи информация от источника по каналу с шумом? Можно ли предложить что-нибудь более эффективное, чем двухступенчатый метод сжатия — кодирования и декодирования- развертывания? Оказывается, что нет, и описанный метод кодирования «источник-канал», на сэмом деле, оптимален, но доказательство этого факта не входит в наши намерения.
В конце главы в равд. «История и дополнительная литература» можно найти ссылки на работы, в которых проведены более детальные исследования. 12.3.2 Связь по квантовым каналам с шумом Предположим, что вместо классического канала связи с шумом Алиса и Воб используют квантовый канал связи с шумом. Более точно, у Алисы есть некоторое сообщение М, которое она хочет послать Бобу. Она кодируег это сообщение как и в классическом случае, но теперь сообщение кодируется квантаенл« состоянием, которое посылается по квантовому каналу с шумом.
Только в том случае, если кодирование будет проведено надлежащим образом, можно надеяться, что Боб сможет определить, каково было сообщение Алисы, с малой вероятностью ошибки. Более того, желательно, чтобы скорость, с которой Алиса посылает Бобу информацию, была как можно более высокой. Другими словами, мы хотим вычислить пропускную способность клантового канала с и»ул«сл«для классической информации. Эта задача до сих пор полностью не решена, однако многое уже сделано, и в данном разделе мы рассмотрим некоторые полученные результаты.
Известно, как вычислить пропускную способность для канала Е, если предположить, что Алиса кодируег свое сообщение, используя фактаоригоеанное состояние вида р1 Эра чг..., где рм рг,... являются возможными входными состояниями для одного обращения к каналу Е. Мы назовем пропускную способность с таким ограничением пропускной способностью для фактариеоеанного состояния и обозначим ее как С<Ц(Е), чтобы указать, что входные состояния для двух или более обращений к данному каналу не могут быть запутаны. Отметим, что эта ограниченная модель связи между Алисой и Бобом позволяет Бобу декодировать, используя измерения запутанных выходных состояний для 674 Глава 12. Квантовая теория информации нескольких обращений к каналу, что весьма существенно.
Единственным (и весьма досадным) ограничением является то, что Алиса должна приготовить входные данные в виде факторизованного состояния. Многие исследователи полагают, хотя это не доказано, что использование запутанных входных состояний не увеличивает пропускную способность. Пропускную способность для факторизованного состояния можно вычислить с помощью теоремы ХолевоШумахера-Вестморланда (ХШВ). Подобно теореме Шеннона о кодировании для классического канала с шумом теорема ХШВ обеспечивает эффективные средства вычисления пропускной способности канала Е для факторизованного состояния с шумом и в некоторых случаях позволяет даже получить точное выражение.
Теорема 12.6 (теорема Холево — Шумахера — Вестморланда). Пусть Е— квантовое преобразование, сохраняющее след. Введем величину Х(Е) вз шах (~. ш) ,'~ „рую -~ р1Е(Е(руУ (12.71) где максимум берется по всем ансамблям (р, р ) возможных входных состояний рд для канала. Тогда Х(Е) — пропускная способность канала Е для факторизованиого состояния, т. е. Х(Е) = С~Ц(Е). Максимум в (12.71) берется по неограниченному набору ансамблей состояний. На самом деле, мы используем результаты приведенного ниже упражнения, чтобы ограничить этот набор ансамблями чистых состояний, содержэзцими не более и" элементов, где д — размерность пространства входных состояний Упражнение 12.11.
Покажите, что максимум в выражении (12.71) может быть достигнут при использовании ансамбля чистых состояний. Покажите далее, что достаточно рассмотреть только ансамбли вз не более, чем й' чистых состояний, где й — размерность пространства входных состояний канала. Доказательство теоремы ХШВ включает несколько идей и его легко понять, разбив на небольшие части.
Случайное кодирование Предположим, что р — набор возможных входных состояний для канала Е и пусть од гв Е(рд) — соответствующие состояния на выходе. Мы применим метод случайного кодирования, подобный описанному ранее для двоичного симметричного канала, разрешив Алисе и Бобу передавать кодовые слова, которые являются произведениями заданных состояний ру. Пусть р — распределение вероятностей по индексам ), т. е. априорное распределение. Алиса хочет послать Бобу сообщение М, выбранное из набора (1,...,2"л). Каждому возможному сообщению М Алиса ставит в соотвествие кодовое слово Рм, ч Рм, Э ° Э рм„, где Мм..., М„выбраны из набора индексов Я. (Это не означает, что Мм..., М„являются десятичным представлением М или чемнибудь в том же роде!) Для каждого сообщения М Алиса выбирает М1 случайно с распределением р .
Аналогичным образом она выбирает Мэ и так далее 12.3. Передача классической информации 675 йг(оэ"(1 — Р)) < б. (12.73) Для заданного сообщения М мы также определим понятие е-типичного подпространства для ам, основываясь на том, что типичное ом является тензорным произведением приблизительно яр~ копий пм прэ копий аз и т. д. Введем обозначение Я кэ "> . РЗЯ(о ). ПРеДположим, что оу имеет спектРальное Разложение 2 ь Лл ~Е „) (Е., Д, так что ом = Я Лкм~Екм)(Екм к (12.74) 43' до М„. Введем обозначение рм ы рм, З...
® рм„. Соответствующие состояния на выходе просто обозначим как о вместо р, так что, например, пм, = 8(рм,) и о'м = оэ"(рм). Боб, получив некоторое состояние ом (соответствующее посланному Алисой сообщению М), производит измерение, пытаясь определить, что это было за сообщение. Поскольку мы интересуемся лишь статистикой измерений, а не состоянием системы Боба после измерения, достаточно описать данное измерение, используя формализм РОЧМ. Мы предполагаем, что для каждого возможного сообщения М Боб имеет соответствующий РОЧМ-элемент Ем. Воб может иметь один (или более) РОЧМ-элементов, которые не соответствуют ни одному сообщению, посланному Алисой.
Очевидно, что все они могут быть суммированы в один РОЧМ-элемент Еэ, удовлетворяющий равенству Еэ = 1 — ~ м~о Ем. Вероятность того, что Боб успешно ццентифицирует М, равна эг(амЕм), и, следовательно, вероятность ошибки, сделанной при идентификации сообщения М, рлл ке 1 — ЫпмЕм). Мы хотим доказать существование кодов с большой скоростью передачи, таких, что веРоатность ошибки Рлм мала длЯ всех сообщений М. Дла этого используем довольно хитрый и противоречащий интуиции трюк, придуманный Шенноном для решения классической задачи. Предположим, что Алиса создает сообщения М, выбирая их случайным образом из набора (1,..., 2"л), и анализирует среднюю вероятность ошибки Ем Рм Ем(1 — п(пмЕм)) рсэ 2пн 2"'л Первый шаг доказательства — показать, что существуют коды с большой скоростью передачи, для которых р„р — + О при больших и.
После того, как это будет сделано, мы используем трюк Шеннона, чтобы показать, что существуют коды, примерно с той же скоростью передачи, для которых рлм близка к нулю для всех М. Мы начнем с построения набора РОЧМ-элементов 1Ем), который позволяет Бобу очень хорошо (хотя, возможно, не оптимально) декодировать выходные состояния пм. Основополагающей идеей нашего построения, как и для классического двоичного симметричного канала, является идея типичности.
Пусть е > О. Определим й как 4г ы 2 рог~ и пусть Р— проектор на етипичное подпространство для оп". Из теоремы о типичном подпространстве следует, что для любых б > О и достаточно больших и 676 Глава 12. Квантовая теория информации где К = (К1,..., К„), и для удобства использованы обозначения Лкм ж Лм' Л~~' ... Лк~" и [Екм) вз [Ек')[Ек')... [Екм"). Определим Рм как проектор на пространство, порожденное всеми [Екм) такими, что 1 1 — 1о8 — — Я~ < е. Лк (12.75) (Полезно обозначить через Тм набор всех К, для которых это условие выполняется.) Аналогично доказательству теоремы о типичных последовательностях закон больших чисел утверждает, что для любых б ) 0 и достаточно больших и мы имеем Е(Фг(омРм)) > 1 — 6, где математическое ожидание берется по распределению кодовых слов рм (для фиксированного сообщения М), обусловленному случайным кодированием, и, следовательно, для каждого М Е[сг(о'м(1 Рм))) < о.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
