М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 157
Текст из файла (страница 157)
Сжатие данных 663 Используя неравенство Коши-Шварца, получаем Р(ре",Р оС") ( ~ МРьС ре"С)Тфбг(Я~(п)ре"). уь (12.56) Применяя часть 3 теоремы о типичном подпространстве, убеждаемся, что Фг(У'(и) ре") ( д для любого 5 > 0 и достаточно больших и. Более того, при до- казательстве теоремы о типичном подпространстве подразумевается, что необ- ходимый размер п не зависит от й. Таким образом, Р(ре",Э" оС") (б~~ бг(0ьСбре"С)Я ьь =5, (12.57) (12.58) Вставка 12.4.
Сжатие Шумахера Рассмотрим стационарный квантовый источник, который характеризуется матрицей плотности кубита (12.59) Он может быть, например, малой частью большой запутанной системы. Другой подход к рассмотрению данного источника (см. равд. 9.3) состоит в следующем. Источник создает состояние фс) = !О) или !41) = (!0) + !1))/~/2 с одинаковыми веРоатностами, Равными э (см. УпР.
12.8). МатРицУ плотности р можно привести к диагональному виду р!0) (О! + (1 — р)!1) (1!, где !0) = сов в (0) + в1п в !1) )1) = гйп ув)0) + сов в !1), и р = (3+ б8(я/8))/4. В этом базисе блок из и кубитов может быть записан как состояние (12.60) хе(бб б,б .51,П.. П поскольку С" и З" сохраняют след. Так как 5 может быть произвольным, Г(р~", Р" о С") — ~ 0 при п -+ оо, и поэтому схема сжатия не надежна. ° Теорема Шумахера не только утверждает сущесглеоваипе надежной схемы сжатия, но и указывает, как ее построить. Для этого нужно эффективно осуществить отображение С": Не'" — ~ Н, "в 2"л-мерное типичное подпространство Н,". Классические методы сжатия, такие как кодирование перечислением, кодирование Хафмана и арифметическое кодирование, могут применяться только с одним строгим ограничением: схема кодирования должна быть полностью обратоимоб, а начальное состояние должно быть полностью уничтожено в процессе создания сжатого состояния согласно теореме о невозможности копирования.
Простой пример, иллюстрирующий квантовое сжатие, приведен во вставке 12.4. 664 Глава 12. Квантовая теория информации Из теоремы 12.6 следует, что нужно передавать только те ~Х), для которых вес Хэмминга приблизительно равен пр (т. е. базис для типичного подпространства), чтобы можно было воспроизвести начальное состояние с большой точностью. Это легко понять, поскольку ~ (О~грьЯ = сов(я/8) (для й = (0,1)) намного больше, чем ((1)грь)! = вш(к/8), и для Х с большим весом Хэмминга коэффициенты Сх очень малы. Как же все-таки реализовать такую схему сжатия? Опишем один приближенный способ.
Предположим, что у нас есть квантовая схема У„, которая переставляет базисные состояния ~Х), упорядочивая их в соответствии с весом Хэмминга. Например, для п = 4 это выглядит так 0000 -+ 0000 1000 -+ 0100 1001 -+ 1000 10П -+ 1100 0001 -+ 0001 0011 -+ 0101 1010 -+ 1001 1101 -+ 1101 0010 -+ 0010 0101 -+ 0110 1100 -+ 1010 1ПО -+ 1110 0100 — > 0011 ОПО -~ 0111 ОП1 -~ 10П 1П1 -+ 1111 Такое преобразование, которое можно осуществить, используя только скот и элементы Тоффоли, обратимо упаковывает типичное подпространство в последние (младшие) пН(р) кубнтов.
Чтобы завершить схему, необходим также квантовый элемент Ъ", который преобразует состояния ~0), (1) отдельного кубита в (О), )1). Тогда схемой сжатия будет С" = (Ъ'Г)е"У„г"е", и необходимо послать только младшие пН(р) кубитов с выхода С", чтобы с большой точностью восстановить последовательность состояний из источника, применяя схему, обратную к данной схеме. Более эффективная схема кодирования упаковала бы только состояния с весом Хэмминга пр в младшие пН(р) кубитов пространства; это можно сделать, используя, например, квантовую версию арифметического кодирования. ЪГпражнение 12.6.
Получите в явном виде выражение для Сх через Х в обозначениях вставки 12.4. Опишите, как построить квантовую схему для реализации У„при произвольных п. Сколько элементарных операций для этого потребуется в зависимости от п? вгпражнение 12.? (схема сжатия данных). Опишите в общих чертах схему надежного сжатия п кубвтов с р = р(0) (0~ + (1 — р))1) (1~ в пЯ кубитов для любого Я > Я(р) = Н(р). вГпражиение 12.8 (сжатие ансамбля квантовых состояний). Предположим, что вместо определения квантового источника на основе матрицы плотности р и точности воспроизведения запутанности, мы приняли определение (стационарного) квантового источника как ансамбля (р., ~гр )) квантовых состояний, и что последовательные обращения к данному источнику независимы; источник выдает состоЯние ~г/О) с веРоЯтностью Ру. В этом слУчае говоРЯт, что 12.3.
Передача классической информации 665 схема «сжатие-развертывание» (С",Рь) надежна, если средняя по ансамблю стпепснь совпадения приближается к 1 при и — » со: Р = — ~ря...р „Ярт,(Р" оС Ир )), х (12.61) где,7 = (уь..., у„) и рт к« ~ф,)(тдя)9...
З~тР~;,)(«Р.„(. Пусть р = 2, рД>~)Я1~. Покажите, что при таком определении степени совпадения существует надеж- ная схема сжатия при скорости передачи В, если 1» > Я(р). 12.3 Передача классической информации по квантовым каналам с шумом Если что-то плохое может случиться, оно случаетася Приписывается Эдварду Мерфи, младшему 12.3.1 Связь но классическому каналу с шумом Многие из основополагающих идей кодирования для канала с шумом, как кван- тового, так и классического, можно понять, изучая двоичный симметричный Время от времени все мы испытываем некоторые трудности, разговаривая по телефону. Мы говорим «плохая связь», когда не можем понять собеседника на другом конце телефонной линии. Это один из примеров общего явления, называемого таум, которое в некоторой степени наблюдается во всех системах обработки информации. Как описано в гл.
10, коды, исправляющие ошибки, могут быть использованы для борьбы с шумом, что позволяет осуществлять надежную связь и точные вычисления даже в присутствии достаточно сильных помех. Если имеется канал связи М с шумом, то возникает интересный вопрос — сколько информации можно надежно передать по этому каналу. Например, может оказаться, что применение подходящего кода, исправляющего ошибки, позволяет передать 500 бит, пересылая по каналу 1000 бит, с большой вероятностью восстановления данных при любой ошибке, вносимой каналом.
Мы говорим, что такой код имеет скорость передачи 500/1000 = 1. Основная проблема теории информации состоит в том, чтобы определить максимум скорости передачи, обеспечивающей надежную связь по каналу Лт, т. е. величину, которую называют пропускной способностью канала. Для классических каналов связи с шумом пропускную способность можно вычислить, используя замечательный результат, известный как теорема Шеннона о кодировании для канала с иьумом. В подрвзд.
12.3.1 мы начнем рассмотрение приема и передачи классической информации в присутствии шума с обсуждения некоторых основных идей, лежащих в основе теоремы Шеннона о кодировании для канела с шумом. Однако, мы не будем особенно вдаваться в детали, поскольку в подразд. 12.3.2 подробно рассмотрим общие принципы решения проблемы, когда две стороны пытаются осуществить передачу классической информации, используя квантовый канал с шумом! 666 Глава 12. Квантовая теория информации канал. Напомним (рэзд.
10.1), что двоичный симметричный канал — это канал с шумом, по которому передается один бит информации, причем шум изменяет бит с вероятностью р > О, а с вероятностью 1 — р бит передается без ошибки, как показано на рис. 12.4. Сколько информации мы можем надежно передать, используя двоичный симметричный канал? Применяя коды, исправляющие ошибки, можно надежно передавать информацию по каналу, используя большее количество бит, чем в самом сообщении. Мы докажем, что максимальная скорость, с которой информация может быть надежно передана по каналу, есть 1 — Н(р), где Н( )— энтропия Шеннона.
1 -р о о Рис. 12.4. Двоичный симметричный канал Что понимать под «надежной передачей информацииа? Это хороший вопрос, поскольку различные ответы приводят к разным значениям скорости передачи. Мы используем следующее определение надежности: допустим, что входные данные можно закодировать в большие блоки, и потребуем, чтобы вероятность ошибки при использовании данного кода, стремилась к нулю с увеличением размера блока. Другое возможное определение надежности: предположим, что данные можно закодировать в большие блоки так, что вероятность ошибки становится точно равной нулю.
К сожалению, это определение слишком оптимистично и приводит к нулевой пропускной способности для двоичного симметричного канала! Аналогично, если нельзя кодировать информацию большими блоками, пропускная способность оказывается равной нулю. Удивительно (и совсем не очевидно), что даже при нашем более слабом определении надежности может быть достигнута ненулевая скорость передачи информации. Нужны хорошие идеи, чтобы показать, что это возможно. Случайное кодирование для двоичного с метричного канала Предположим, что мы хотим передать пВ битов информации, используя и раз двоичный симметричный канал. Мы докажем, что существует код, исправляющий ошибки, который обеспечивает передачу информации с малой вероятностью ошибки при больших п и В < 1 — Н~р). Прежде всего используем метод случайного кодировання для построения кода, исправляющего ошибки.
Пусть (д,1 — д)-некоторое фиксированное распределение вероятностей для 12.3. Передача классической информации 667 Крупный и пространств кодового слова Радиус сферы Хеннинга пр Переданное кодовое слово Рис. 12.5. Лредполохгим, что кодовое слово вг длины и передается по двоичному симметрично- му каналу Тогда типичные данные на выходе иа канала являются элементами сферы Хвмминга радиуса пр вокруг кодового слова. (Этот рисунок-крупный план рис. 12Д ) возможных входных данных канала (О и 1).
(Это распределение часто называется априорным распределением данного кода. Выбор данного распределения — всего лишь технический прием, обеспечивающий работу метода случайного кодирования; случайность в распределении не следует путать со случайностью в канале.) Мы выбираем кодовое слово х = (хм..., х„), просто взяв х = О с вероятностью д и х. = 1 с вероятностью 1 — д независимо для каждого 1 = 1,...,и. Повторяем зту процедуру 2нл раз, создавая при этом кодовую книгу С с 2"л записямн; обозначим кодовые слова в С как хт. Может оказаться, что мы построили плохой код, например такой, в котором все кодовые слова будут состоять из строки, заполненной и нулями, что, очевидно, бесполезно для передачи информации. Тем не менее, оказывается, что в среднем эта процедура случайного кодирования дает достаточно хороший код, исправляющий ошибки.
Чтобы понять это, посмотрим, как в канале изменяется одно кодовое слово. Поскольку все кодовые слова построены одним и тем же способом, можно рассмотреть первое х'. Какое действие оказывает, двоичный симметричный канал на хт 7 В кодовом слове длины и мы ожидаем приблизительно пр измененных битов, так что с большой вероятностью выходные данные будут иметь расстояние Хэмминга порядка пр от кодового слова х1, как показано на рис, 12.5. Мы говорим, что такие выходные данные лежат на сфере Хэмминга радиуса пр вокруг х'. Эта сфера состоит приблизительно из 2"н<Р~ элементов р = хт ет е, где е — ошибка, происходящая в канале, ет означает побитовое сложение по модулю 2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
