М. Нильсен, И. Чанг - Квантовые вычисления и квантовая информация (1156771), страница 176
Текст из файла (страница 176)
Квантовая теория информации статей по вопросам экспериментальной реализации квантовых криптографических систем. Чтобы получить представление об этом, рекомендуем обратиться к работе Хьюза, Альда, Лютера, Моргана и Шауэра [174]; Мюллер, Збинден и Гизин [300] продемонстрировали квантовую криптографию под Женевским озером. Эксперимент, описанный во вставке 12.7, провели Бетун и Риск [67, 68] из 1ВМ, и мы благодарим их за предоставленную схему экспериментальной установки. Выполнено большое число доказательств надежности различных протоколов распределения квантовых ключей при разных условиях. Следует особо отметить (исчерпывающее, но довольно сложное) доказательство надежности протокола ВВ84, сделанное Майерсом [278]. Бихам, Бойер, Брассар, ван де Грааф и Мор также обсудили атаки на протокол ВВ84 [21].
Более простое доказательство с использованием ЭПР состояний в предположении безошибочных квантовых вычислений дано Ло и Чу [237]; это протокол, с которого мы начали подрэзд. 12.6.5. Ло [259] упростил его, предложив начинать с измерения скорости возникновения ошибок, а затем уже передавать данные о ключе. Еще более простым (и красивым!) доказательством в подраэд. 12,6.5 мы обязаны Шору и Прескиллу [366], которые также дали 11% оценку, упомянутую в подразд.
12.6.5. Наше представление этого доказательства также сильно выиграло после обсуждения его с Готтесманом. Приложение 1 НЕКОТОРЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ ВЕРОЯТНОСТЕЙ р(У у~х х)-Р( У) р(Х =х) (П1.1) где р(Х = х, У = у) — вероятность того, что Х = х и У = у, Когда р(Х = х) = О, будем считать, что р(У = у~Х = х) = О. Мы часто используем обозначение р(у~х), неявно подразумевая выражения «У = э и «Х = м Случайные переменные Х и У называются независимыми, если р(Х = х, У = у) = р(Х = х)р(У = у) для всех х и у.
Обратите внимание, что если Х и У вЂ” независимые переменные, то р(у~х) = р(у) для любых х и у. Формула Байеса связывает условные вероятности для Х при заданном У и для У при заданном Х: р(х(у) = р(у(х) †. р(х) 1(У)' (П1.2) Вероятность р(у) в этом выражении часто переписывают с использованием обсуждающейся ниже формулы полной вероятности. в'пражнение П1.1.
Докажите формулу Вайеса. Одним из наиболее важных и часто используемых результатов теории вероятностей является формула полной вероятности. Она утверждает, что если Х и У вЂ” две случайные переменные, то вероятности для величины У могут быть записаны в терминах вероятностей для Х и условных вероятностей для У при заданном Х: «п Приложение содержит небольшое количество элементарных определений и фактов из теории вероятностей.
Предполагается, что читатель в какой-то мере зна. ком с этим материалом. Если же ему не известно ни одно из приводимых ниже утверждений, то следует потратить время на то, чтобы доказать их самостоятельно (следите за встречающимися в тексте упражнениями). Основное понятие теории вероятностей — случайнал персменнвл. Случайная переменная Х может принимать значение х из некоторого набора с вероятностью р(Х = х). Мы используем прописные буквы для обозначения случайных переменных, а строчныŠ— для значений, которые могут принимать эти переменные. Мы часто используем обозначение р(х) вместо р(Х = х), неявно подразумевая выражение «Х = э.
В этой книге мы имеем дело только со случайными переменными, которые могут принимать значения из конечного набора. Иногда удобно рассматривать случайные величины, принимающие векторныс значения, например из множества («, «): 1 = 1,..., тм,1 = 1,..., тз. Условная вероятность того, что У = у, если известно, что Х = х, задается формулой 740 Приложение 1. Некоторые сведения из теории вероятностей р(у) = ~у р(р]з)р(х), (П1.3) где суммирование ведется по всем значениям х, которые может принимать, переменная Х.
упражнение П1.2. Докажите формулу полной вероятности. Математпическое ожидание, или среднее случайной переменной, определяется формулой Е(Х) ш У р(з)з, (П1.4) где суммирование ведется по всем значениям з, которые может принимать переменная Х. з првжнение П1.3. Докажите, что существует такое значение я > Е(Х), для которого р(з) > О. з пражнеиие П1.4. Докажите, что Е(Х) — линейная функция переменной Х. з пражнение П1.5. Докажите, что для независимых случайных переменных Х и У выполняется равенство Е(ХУ) = Е(Х)Е(У). Дпсперсил случайной переменной Х определяется выражением чаг(Х) ьз Е[(Х вЂ” Е(Х))з] Е(Хг) Е(Х)з (П1.5) Квадратпичное отпклонение Ь(Х) =,/~(Х) — это мера разброса случайной переменной относительно своего среднего значения.
Неравенство Чебэииева описывает более точно, в каком смысле стандартное отклонение является мерой разброса значений случайной переменной, которые она может принимать. Оно утверждает, что для случайной переменной с ненулевой дисперсией и произвольного Л > 0 выполняется неравенство р([х — е(х)] > ль(х)) < —,. 1 (П1.6) Другими словами, вероятность того, что случайная величина примет значение, отличающееся от среднего более чем на Л стандартных отклонений, уменьшается при стремлении Л к бесконечности.
з пражнеиие П1.6. Докажите неравенство Чвбышева. В основном тексте книги использовано много других утверждений из теории вероятностей, включая неравенсшво Чернова, неравенство Фано и закон больших чисел. История и дополнительная литература Существует много превосходных изданий, посвшценных теории вероятностей. Следует выделить книгу Гримметта и Штизакера [173], посвященную основным идеям теории вероятностей и стохастических процессов.
Более чистая математическая трактовка дана во введении в современную теорию вероятностей Вильямса [418]; особое внимание здесь уделено красивой теории мартингалов. Наконец, глубоким введением в теорию вероятностей является классический двухтомник Феллера [147, 148]. Приложение 2 ТЕОРИЯ ГРУПП При изучении квантовых вычислений и квантовой информации в ряде случаев полезно использовать теорию групп.
Обобщения алгоритмов нахождения порядка элемента, разложения на множители и нахождения периода (гл. 5) основаны на задаче о скрытой подгруппе; формализм стабилизаторов, использованный при описании исправления квантовых ошибок в гл. 10, базируется на некоторых элементарных поыятиях теории групп. В теории чисел, рассматриваемой в Приложении 4, использованы свойства группы г.„*. Кроме того, квантовые схемы, к которым мы обращаемся на протяжении всей книги, являются примером применения групп Ли. В данном Приложении приводится обзор осыовных элементарных фактов из теории групп. Мы вводим много фундаментальных понятий и важных определений, но не пытаемся объяснить все сразу, поскольку теория групп — весьма обширная наука. П2.1 Основные определения Группой (С, ) называют непустое множество С с бинарной операцией умножения «», обладающей следующими свойствами: замкнутость (дг дз Е С для любых дпдз Е С); ассоциативность ((д1 дг) дз = д1 (дг дз) для любых дпдз, дз Е С); существование единицы (есть такой элемеыт е Е С, что для любого д Е С выполняется равенство д ° е = е д = д); существование обратного (длялюбогод Е С имеется такойэлементд ' Е С, что д д ' =д ~ д = е).
Мы часто опускаем знак «» и вместо д1 ° дз пишем просто д1дз, а также говорим о группе С без явного указания на опеРацию умножения этой группы, но эта операция обязательно должна быть определена. Группа С называется конечной если число ее элементов конечно. Порядком конечной группы С называется число ее элементов (обознается ~С~).
Группа С называется абелевой, если д1дз = дзд1 для любых дпдз Е С. Простым примером коыечыой абелевой группы является адцитивная группа г „остатков по модулю и с операцией «умножения», задаваемой обычным сложением по модулю и. Легко проверить, что эта операция удовлетворяет аксиомам замкнутости и ассоциативности; существует «едиыичный» элемент (0), так как х + 0 = х (шоб и) для любого х; для каждого элемента х Е С существует обратный, равный и — х, поскольку х + (и — х) = 0 (пюд и).
Порядком элемента д Е С называется наименьшее положительное целое число г, для которого д" (т. е. г раз умноженный сам на себя элемент д) равно единичному элементу е. Подгруппой Н группы С называют подмножество множества С, которое само образует группу с той же самой операцией умножения, которая вводилась в С. 742 Приложение 2. Теория групп Теорема П2.1 (теорема Лагранжа).
Если Н вЂ” подгруппа конечной группы С, то (Н( делит )С(. 'Упражнение П2.1. Докажите, что для любого элемента д конечной группы существует такое положительное целое число г, что д' = е. Другими словами, для любого элемента такой группы можно определить его порядок. Упражнение П2.2. Докажите теорему Лагранжа. Упражнение П2.3. Покажите, что порядок элемента д Е С делит ~С~.
Элемент дг соаряжен с элементом дг, если существует такой элемент Ь б С, что дг = Ьд~й г (очевидно, что в этом случае и элемент дз сопряжен с элементом дг). Подгруппа Н группы С называется нормальной, если д гНд = Н для любого д е С. Классом сопряженных элементов С элемента х в группе С называется множество С, ьз (д 'хд ) д е С). Упражнение П2.4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
