М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 144
Текст из файла (страница 144)
608 Глава 10. Исправление квантовых ошибок Китаев [212, 213] предложил множество замечательных идей о том, как получить устойчивость к ошибкам с использованием топологическиз методов. Основная идея заключается в том, чтобы хранить информацию в топологии системы. Такая информация очень устойчива к шуму. Эти и многие другие красивые идеи были в дальнейшем развиты Бравым и Китаевым [57], а также Фридманом и Мейером [153]. Прескилл ]327] сделал очень хороший обзор по теме квантового исправления ошибок в целом, который включает замечательное описание топологического исправления ошибок, а также интригующие рассуждение о его связи е фундаментальными Вопросами черных дыр и квантовой гравитации. Многие группы установили различные пороговые значения для квантовых вычислений. Эти результаты получены при различных предположениях и приводят к существенно разным пороговым теоремам.
Пороговые теоремы Аароновой и Бен-Ора [1, 2], а также Китаева [214, 213] не требуют быстрых или надежных классических вычислений. Ааронова и Бен-Ор также показали, что для выполнения пороговой теоремы в каждый момент времени необходимо проведение параллельных вычислений [1]. При доказательстве пороговой теоремы Готтесман ]166] и Прескилл [330, 169] провели детальную оптимизацию пороговой величины.
Нилл, Лафлам и Зурек ]220, 221] доказали пороговую теорему для широкого класса моделей ошибки. Ааронова, Бен-Ор, Импальяццо и Нисан ]3] также показали, что для выполнения пороговой теоремы необходим постоянный расход свежих кубитов. Дальнейшие ссылки и исторические ма териалы могут быть найдены в перечисленных работах. В частности, каждая группа ссылается на работу Шора [356] об устойчивых к ошибкам квантовых вычислениях. Существует множество отличных обзоров квантовых вычислений, устойчивых к ошибкам, в которых основные идеи описываются гораздо более детально, чем мы, и с различных точек зрения.
В диссертация Аароновой [8] рассматриваются пороговая теорема и связанные с ней вопросы. Диссертация Готтесма на ]166] также содержит обзор устойчивых к ошибкам квантовых вычислений, причем особое внимание уделяется свойствам квантовых кодов и построению устойчивых к ошибкам конструкций для множества различных кодов. Нилл, Лафлам и Зурек сделали популярный обзор, посвященный пороговой теореме [220]. Прескилл написал две замечательные статьи [330, 328] о квантовом исправлении ошибок и об устойчивых к ошибкам квантовых вычислений. Глава 11 ЭНТРОПИЯ И ИНФОРМАЦИЯ Эишровил является ключевым понятием в квантовой теории информации, которое позволяет определить степень неопределенности в состоянии физической системы.
В настоящей главе мы рассмотрим основные определения и свойства энтропии в классической и квантовой теории информации. В главе встречаются разделы, содержащие подробные и довольно длинные математические доказательства. При первом чтении через эти разделы можно перескочить, возвращаясь к ним по мере необходимости.
11.1 Шенноновская энтропия Важнейшим понятием классической теории информации является шеинововская эив»ровил. Предположим, что нам стало известно значение случайной величины Х. Шенноновская энтропия Х является мерой количества информации, которое мы получаем, узнав значение Х. Можно также сказать, что энтропия Х является мерой иеовреда«еииос»ви величины Х до того, как нам стало известно ее значение. Эти две точки зрения дополняют друг друга; мы можем рассматривать энтропию как меру неопределенности до того как мы узнали значение Х, или как меру количества информации„которое мы получим яос«е того, как узнаем значение Х.
Интуитивно ясно, что энтропия случайной величины не должна зависеть от того, какие символы мы используем для описания множества значений, принимаемых случайной величиной. Например, ясно, что случайная величина, принимающая значения «орел» и «решка» (монета) с вероятностями 1/4 и 3/4, содержит то же самое количество информации, что и случайная величина принимающая значения О и 1 с вероятностями 1/4 и 3/4. По этой причине, энтропия случайной величины определяется как функция от вероятностей ее возможных значений и не зависит от выбора символов для описания этих значений.
Часто мы записываем энтропию как функцию распределения вероятностей рз,...,р„. Шеиноноескол энтропия этого распределения вероятностей определяется как Н(Х) ьэ Н(рм...,р„) ш — ~~> р 1ояр (11.1) Заметим,что в этом определении (также как и во всей книге) логарифм «1ой» берется по основанию два (тогда как 1п обозначает натуральный логарифм).
Этот выбор основания логарифма эквивалентен условию, что энтропия измеря- 39 квв аваев а ею~я 610 Глава 11. Энтропия и информация ется в «битахм Может возникнуть вопрос, что произойдет при р = О, поскольку 1ояО неопределен. Интуитивно понятно, что событие, которое никогда ие Вставка 11.1. Соотношение неопределенности с использованием энтропии Существует изящный способ переформулировать принцип неопределенности квантовой механики с помощью энтропии.
Напомним, что соотношение иеопределепиостей Гайзенберга (вставка 2.4) для стандартных отклонений Ь(С) и МР) наблюдаемых С и Р имеет вид (11.2) где ~«г) — состояние квантовой системы. Пусть С = 2 '«с)с)(с( и Р = 2 «НА(д~ — спектральные разложения С и Р. Определим /(С, Р) = шах«д ~(сф ! как максимальную степень совпадевия между собственными векторами операторов ~с) и р1). Например, для матриц Паули Х и Я мы имеем /(Х, Я) = 1/~/2.
Предположим, что квантовая система находится в состоянии ~ф). Пусть р(с) и р(п) — распределения вероятиостей результатов измерения С и Р, а Н(С) и Н(Р) — их энтропии. Соотношение неопределенности через энтропию имеет вид Н(С) + Н(Р) > 2)оя 1 (11.3) Доказательство этого результата довольно сложно (см. ссылки в рэзд. «История и дополнительная литератураэ), поэтому мы ограничимся доказательством более слабого неравенства (11.4) Н(С) + Н(Р) ) — 2 1ок Для доказательства заметим, что Н(С) + Н(Р) = — ~ р(с)р(д) 1ой(р(с)р(«()). (11.5) Оценим сверху величину р(с)р(Ы) = )(с)ф)(фф(~.
Пусть ф) — проекция ~ф) иа плоскость векторов )с) и (а), Л < 1 — норма вектора рР), д — угол между !с) и ф, а у — угол между рг) и ф, так что р(с)ря = ~(с/Ф)(4~фа = Лз сова (д — у) совз (у). Максимум этого выражения р(с)р(Н) = соэ«(д/2) достигается при Л = 1 и ~р = д/2, что можно записать в виде р(с)р(И) = (11.6) 11.1. Шенноновская энтропия 611 происходит, не дает вклада в энтропию, поэтому мы условимся, что 0 1ояО = О. Это равенство можно также получить, заметив, что 1пп, о х!о8 х = О. Почему энтропия определяется именно так? В упр. 11.2, предложенном далее в этом разделе, дается интуитивное подтверждение определения энтропии (11.1), основанное на «разумныхэ аксиомах, постулирующих свойства мер информации. Это интуитивное подтверждение достаточно убедительно, однако определение (11.1) имеет более глубокую мотивацию.
Дело в том, что энтропия, определенная таким образом, может быть использована для количественной оценки физических ресурсов, необходимых дяя хранения информации. Предположим, что имеется некоторый источник (скажем, радиоантенна), который выдаег инфорь1ацию, например, в виде последовательности битов.
Если Х— случайная величина, можно рассмотреть источник информации, который генерирует последовательность Хп Хэ,... независимых одинаково распределенных случайных величин. Хотя реальные источники информации не всегда можно описать таким образом, эта модель часто является хорошим приближением. Шеннон предложил следующую задачу: какие минимальные физические ресурсы необходимы для того, чтобы сохранять информацию, получаемую из такого источника, так, чтобы впоследствии можно было восстановить ее? Оказывается, что для хранения последовательности длины н требуется (в среднем) нН(Х) битов, где Н(Х) ээ Н(Х~) = Н(Хз) = ...— энтропия случайной величины Х, входящей в определение источника.
Этот результат известен как теорема Шеннона о кодировании дяя канала без шума Ее доказательство как для классического, так и для квантового случая приведено в гл. 12. Проиллюстрируем теорему Шеннона следующим примером. Пусть источник на каждом шаге генерирует один из символов 1, 2, 3 или 4. Если не пытаться сжать данные, можно просто отвести два бита памяти для хранения символа, полученного на каждом шаге.
Предположим теперь, что символы 1, 2, 3, 4 генерируются с вероятностями 1/2, 1/4, 1/8, 1/8 соответственно. Мы можем сжать полученные из источника данные, отводя меньшее число бит для запоминания наиболее часто встречающихся символов и используя ббльшее число бит для запоминания редко встречающихся символов. Один из вариантов сжатия выглядит так: символ 1 кодируется одним битом О, символ 2 кодируется битами 10, символ 3 кодируется битами 110, символ 4 кодируется битами 111. Если из источника была получена последовательность длины н, то после сжатия будем иметь строку бит средней длины з 1+ 4 ° 2+ е . 3+ з ° 3 = (7/4) ° н.
Заметим, что без сжатия мы имели бы строку длины 2н. Удивительно, что наш вариант сжатия согласуется с энтропией источника 612 Глава 11. Энтропия и информация Н(Х) = — 1/2 1о8 (1/2) — 1/4 1о8 (1/4) — 1/8 1о8 (1/8) — 1/8 1о8 (1/8) = 7/4! Оказывается, что любые попытки дальнейшего сжатия информации, полученной из источника, приведут к тому, что часть информации окажется безвозвратно утерянной, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
