Кулик Введение в теорию квантовых вычислений Книга1 2008

Правило 1.1 (см. и ср. [35, с.33; 62, с.51])

Вероятность перехода системы по траектории из одного положения (состояния) в другое положение (состояние) равна произведению вероятностей всех процессов, связывающих между собой состояния, принадлежащие данной траектории ▄

Правило 1.2 (см. и ср. [35, с.323; 62, с.41])

Вероятность перехода системы из начального положения (состояния) в конечное положение (состояние) равна сумме вероятностей переходов по всем возможным траекториям, связывающим эти положения (состояния) ▄

ОТМЕТИМ. Специалисты отмечают [35, с.59], что ДТ является достаточно удобным инструментом для решения задач теории вероятностей. Больше всего она подходит в том случае, когда есть последовательность событий, которые происходят в промежутках времени, следующих один за другим. Иногда реальную задачу можно представить как такую последовательность событий.

ВАЖНО ПОМНИТЬ (см. [35, с. 59]). С помощью теории вероятностей можно по заданным вероятностям элементарных событий вычислить вероятность некоторого конкретного сложного события. При этом на вопрос, откуда берутся сами вероятности элементарных событий, эта теория ответа не дает. В некоторых случаях эти вероятности можно получить с помощью другой теории — мате-

матической статистики.

ОТМЕТИМ [35, с.23]. Диаграммная техника требует рассматривать происходящие процессы с системой, как развивающиеся во времени. При этом пространство элементарных событий есть застывший и неизменный во времени набор элементарных событий.

Кроме диаграммной техники существует еще другой метод вычисления вероятности заданного сложного события с помощью дерева событий. При построении диаграммы переходов число ветвей (от числа интервалов и числа состояний) растет значительно медленнее, чем для дерева событий. Принято, что на диаграмме переходов все траектории для интересующего события (т.е. конечного состояния системы) сходятся в одной единственной точке.

Рассмотрим следующий пример.

161

Пример 1.35 (см. и ср. [35, с. 59-60])

Игральную кость (кубик) бросают три раза подряд и наблюдают за числом выпавших шестерок. При этом интересуются выпадением только 1-й шестерки при трех бросках кубика.

Построим дерево событий и диаграмму переходов и затем срав-

ним их между собой.

Для трех бросков идеального кубика, когда интересуются выпадением только 1-й шестерки, дерево событий (рис. 1.57а) и диаграмма переходов (рис. 1.57б) представлены на рис. 1.57.

На дереве событий (см. рис. 1.57а) приняты следующие обо-

значения: событие U – не выпало ни одной шестерки, а событие
V – выпало 3 шестерки. Событию, когда выпала только 1 шестер-
ка, соответствуют	3 точки G, M, Z на рис. 1.57а, а на рис. 1.57б
только одна точка	C, соответствующая конечному состоянию сис-

темы S1.

На диаграмме переходов (рис. 1.57б) приняты следующие обозначения. Состоянию Si соответствует число i выпавших шестерок для кубика. В начальный момент времени T0 число выпавших шестерок есть нуль, так как еще не было совершено ни одного броска кубика. Начальному состоянию системы S0 (точка O) соответствует выпадение ни одной шестерки. Если шестерка при очередном броске кубика не выпадает, то система остается в этом состоянии S0 на протяжении очередного интервала времени, например T1, T2

или T3.

Так как кубик правильный, то вероятности процессов при выпадении шестерки (одинаковы) и есть 1/6, а при невыпадении шестерки (т.е. выпадении любой другой цифры) есть 5/6. Значения этих вероятностей и показаны на диаграмме переходов и на дереве

событий.
Заметим, что	при построении диаграммы переходов на
рис. 1.57б число	ветвей растет в арифметической прогрессии
(т.е. 2, 4, 6,…), а	при построении дерева событий на рис. 1.57а это

число ветвей растет в геометрической прогрессии (т.е. 2, 4, 8,…). На этом закончим обсуждение данного примера▄

Рассмотрим далее достаточно простые и наглядные примеры вычисления вероятности перехода системы из одного состояния в другое с помощью диаграммной техники.

162

а)

1/6

5/6

1/6

5/6

1/6

5/6

б)

S (состояния)

S3

S2

1/6

5/6

S1

	1/6	1/6
S0	5/6	5/6
	O

1/6

5/6

1/6

5/6

1/6

5/6

1/6

5/6

1/6

5/6

1/6

5/6

1/6

5/6

V

G

M

Z

U

A

B

C

D

T (время)

T0

T1

T2

T3

Рис. 1.57. Дерево событий а) и диаграмма переходов б)

163

Пример 1.36 (см. [35, с. 32-33,44-45])

Четыре буквы разрезной азбуки М, М, А, А положены в мешок, откуда их вынимают наудачу (т.е. случайным образом) и располагают одну за другой в порядке, в котором они появляются. Требуется определить вероятность PМАМА появления слова МАМА.

Решение

1). Введем состояния системы: S0 – начальное; S1 – состояние неудачи, когда требуемое слово не получится; S2 – первая буква в слове М; S3 – две первых буквы в слове МА; S4 – три первых буквы в слове МАМ; S5 – четыре первых буквы в слове МАМА.

2). Построим диаграмму, укажем вероятности процессов и выясним, какие траектории могут иметь место (рис. 1.58).

S

S5

1

A

(МАМА)

S4

1/2

(МАМ)

S3

0

(МА)

2/3

1/2

S2

1/3

(М)

1/2

1

1

1

D

S1

(неудача)

1/2

S0

O

T

T0

T1

T2

T3

T4

Рис. 1.58. Диаграмма переходов (слово МАМА)

3). Имеется только 1 траектория из точки O в точку A ( O → A ). Тогда искомая вероятность есть PМАМА=(1/2)·(2/3)·(1/2)·1=1/6.

4). И тем самым задача решена▄

164

Пример 1.37 (см. [35, с. 50-52])

В случае бросания 2-х игральных костей (кубиков) сумма выпавших очков заключена между 2 и 12. Сумма в 9 очков может быть получена из цифр 1, 2, 3, 4, 5, 6 двумя возможными способами: 9=3+6=4+5. Сумма в 10 очков также может быть получена двумя способами: 10=4+6=5+5. Требуется определить, какая сумма появляется чаще, 9 или10, илижеонипоявляютсяодинаковочасто?

Решение

1). Введем состояния системы Si, где i – сумма выпавших очков, причем начальное состояние есть S0, а конечные – S9 и S10.

2). Будем полагать, что результат бросания 2-х правильных кубиков эквивалентен 2-м бросаниям одного правильного кубика. Построим диаграмму (для суммы 9, см. рис. 1.59а и для суммы 10, см. рис. 1.59б), укажем вероятности процессов и выясним, какие траектории могут иметь место (рис. 1.59). Кубик правильный, а значит, все вероятности процессов одинаковы и есть 1/6.

3). Требуется определить вероятности P9 и P10, где P9 – вероятность перехода ( O → A, см. рис. 1.59а) системы из начального положения (т.е. состояния S0) в конечное положение (т.е. в состояние S9), а P10 – вероятность перехода ( O → D, см. рис. 1.59б) систе-

мы из начального положения S0 в конечное положение S10.

4). Вычислим P9. Согласно диаграмме (рис. 1.59а) из точки O в точку A можно прийти только по 4 следующим траекториям:

траектория 1: { S0, S6, S9 }; траектория 2: { S0, S5, S9 }; траектория 3: { S0, S4, S9 }; траектория 4: { S0, S3, S9 }.

Применяем Правило 1.1 для вычисления вероятности перехода системы по каждой траектории. В данном случае эти вероятности одинаковы и есть Pтраектории=(1/6)·(1/6)=1/36.

Применяем Правило1.2 длявычисления вероятности P9 перехода системы из состояния S0 в состояние S9. В данном случае эта веро-

ятность есть P9=P( O →A )=(1/36)+(1/36)+(1/36)+(1/36)=4/36=1/9.

5). Вычислим P10. Согласно диаграмме (рис. 1.59б) из точки O в точку D можно прийти только по 3 траекториям. Из Правила 1.2

следует, что P10=P (O →D) =(1/36)+(1/36)+(1/36)=3/36=1/12. 6). Получаем, что P9>P10.

7). И тем самым задача решена▄

165

а) Сумма в 9 очков

S

S10

S9

S8

S7

S6

S5

S4

S3

S2

S1

S0 O

T0 T1

б) Сумма в 10 очков

S10

A

S9

S8

S7

S6

S5

S4

S3

S2

S1

S0

T

T2

S

D

OT

T0 T1 T2

Рис. 1.59. Диаграммы переходов для 2-х кубиков

166

Пример 1.38

Ковбой Джон 3 раза стреляет из кольта по консервной банке. Вероятность его удачного выстрела (т.е. попадания в банку) есть p=0.5 . Требуется найти вероятность того, что в банке будет ровно одна пробоина (см. [35, с. 35]).

Решение (см. [35, с. 35-37] и ср. с решением из Примера 1.29) 1). Введем состояния системы Si, где i – число пробоин в банке,

причем начальное (точка O) есть S0, а конечное – S1 (точка C). 2). Построим диаграмму, укажем вероятности процессов и выясним, какие траектории могут иметь место (рис. 1.60). При 1-м

выстреле возможны следующие 2 исхода:

•с вероятностью p в банке появится одна пробоина;

•с вероятностью (1/2)=1–p пробоина в банке НЕ появится; Все вероятности процессов одинаковы и есть 1/2.

3). Требуется определить вероятность P1 – вероятность перехода системы ( O → C, см. рис. 1.60) из состояния S0 в S1 (точка C).

4). Вычислим P1. Согласно диаграмме (рис. 1.60) из точки O в точку C можно прейти только по 3-м следующим траекториям:

траектория 1: { S0, S1, S1, S1 };

траектория 2: { S0, S0, S1, S1 };

траектория 3: { S0, S0, S0, S1 }.

Применяем Правило 1.1 для вычисления вероятности перехода системы по каждой траектории. В данном случае эти вероятности одинаковы и есть Pтраектории=(1/2)·(1/2)·(1/2)=1/8.

Применяем Правило 1.2 для вычисления вероятности P1 перехода системы из состояния S0 в состояние S1. В данном случае эта

вероятность есть P1=P (O → C) =(1/8)+(1/8)+(1/8)=(3/8)=0.375 .

5). Получаем, что P1 =0.375 .

6). И тем самым задача решена▄

ВАЖНО ПОМНИТЬ. Диаграммная техника тесно связана с квантовыми вычислениями и особенно с амплитудой вероятности [33], рассматриваемой далее. Более сложное ее развитие связано с интегралами по траекториям [62], применяемыми в физике.

167

S (состояния)

S3

			p
S2			1/2
		p	p
S1		1/2	1/2
	p	p	p
S0	1/2	1/2	1/2
	O

A

B

C

D

T (время)

T0

T1

T2

T3

Рис. 1.60. Диаграмма переходов для 3-х выстрелов из кольта

ОТМЕТИМ [35, с.37]. Диаграмма переходов на рис. 1.60 является достаточно избыточной для решения Примера 1.36. На практике иногда имеет смысл использовать несколько упрощенную (так называемую частную) диаграмму, содержащую только необходимые траектории для получения конечного результата.

ОТМЕТИМ. Те процессы, которые невозможны (т.е. не могут иметь место и, как правило, имеют нулевую вероятность), обычно на диаграмме стрелками не показывают. В основе Правил 1.1, 1.2 лежат теоремы сложения и умножения вероятностей.

Перейдем к рассмотрению такого очень важного понятия как измерение состояния классической системы.

168

Диаграмма переходов вероятностных логических элементов Рассмотрим подробнее элемент R — вероятностный логический элемент НЕ, который представлен на рис. 1.61а.

а)

б)

A R B

в)

R R

Рис. 1.61. Логический элемент НЕ

Этот логический элемент случайно преобразует входной сигнал A (т.е. 0 или 1) в выходной сигнал B (т.е. 0 или 1) в соответствии со следующими вероятностями pAB:

p00 — вероятность преобразования 0 в 0; p01 — вероятность преобразования 0 в 1; p10 — вероятность преобразования 1 в 0; p11 — вероятность преобразования 1 в 1;

1

причем ∑{pAB}=1. Иногда такой элемент специалисты [33]

B=0

называют случайным переключателем. Работа этого вероятностного элемента подчиняется классическим законам физики.

В случае, когда p01 = p10 = 0, p00 = p11 = 1, данный элемент является уже детерминированным и в точности совпадает с ЛЭ НЕ

(рис. 1.61б), рассмотренным ранее. В других случаях данный элемент является устройством со случайным поведением.

Если имеется несколько таких вероятностных ЛЭ, например, как на рис. 1.61в, то они работают независимо друг от друга (т.е. логика работы одного элемента никак не зависит от работы другого такого же элемента, соединенного с ним в одной комбинационной схеме).

Рассмотрим следующий пример.

169

Пример 1.39

Два вероятностных логических элемента НЕ соединены так, как

на рис. 1.61в. Вероятности pAB известны p01 = p10 = p00 = p11 = 0.5 . Требуется построить диаграмму переходов и найти вероятность

того, что на выходе будет 1, если на вход подан 0 (см. и ср. [33]).

Решение

1). Введем состояния системы Si, где i – число 0 или 1, причем начальное (точка O) есть S0, а конечное – S1 (точка C).

2). Построим диаграмму, укажем вероятности процессов и выясним, какие траектории могут иметь место (рис. 1.62).

Все вероятности процессов одинаковы и есть 1/2.

3). Требуется определить вероятность P01 – вероятность перехода системы ( O → C, см. рис. 1.62) из состояния S0 в S1 (точка C).

4). Вычислим P01. Согласно диаграмме (рис. 1.62) из точки O в точку C можно прейти только по 2-м следующим траекториям:

траектория 1: { S0, S1, S1 };

траектория 2: { S0, S0, S1 }.

Применяем Правило 1.1 для вычисления вероятности перехода системы по каждой траектории. В данном случае эти вероятности одинаковы и есть Pтраектории= p01 p11 = p00 p01 =(1/2)·(1/2)=1/4.

Применяем Правило 1.2 для вычисления вероятности P01 перехода системы из состояния S0 в состояние S1. В данном случае эта веро-

ятность есть P01 =P (O → C) =(1/4)+(1/4)=(1/2) или

P01 =p01 p11 + p00 p01 = p01(p11 + p00)= p01(0.5 + 0.5)= p01 · 1= p01.

5). Получаем, что P01 =0.5 .

6). Аналогично для P00 =P (O → D) можно вычислить, что

Pтраектории= p01 p10 = p00 p00 =(1/2)·(1/2)=1/4. P00 =P (O → D) =(1/4)+(1/4)=(1/2) или

P00 =p01 p10 + p00 p00 = p00(0.5 + 0.5)= p00 · 1= p00.

А также, что

P10 =P (I → D)=(1/4)+(1/4)=(1/2)= p10. P11 =P (I → C )=(1/4)+(1/4)=(1/2)= p11.

7). И тем самым задача решена▄

170