[МУЗЫКА]
[МУЗЫКА] Мы
с вами посчитали вероятность измерения каждого конкретного хорошего y.
Давайте теперь посмотрим, сколько всего хороших y есть у нас в наличии.
Для этого давайте вспомним, как мы определили хороший игрек?
Это A * Θy принадлежит отрезку от −π до π.
Вспомним также, что θy = 2π
* ry по модулю N / N.
Если мы это домножим на A, тут будет еще A,
и это должно быть ≤ π и ≥ −π.
Разделим это все, например, для начала на 2π.
−1/2 ≤...
Здесь мы A можем поделить на N, получится у нас 1 на r.
ry (N) /
r ≤ 1/2.
И r давайте перенесем, то есть домножим все это неравенство на r.
yr (N)
≤ r/2 и ≥ −r/2.
Если мы избавимся от модуля, то получится,
что ry
≤ какое-то
Nk + r/2
и ≥ Nk − r/2 для
какого-то значения k.
Получается, что ry должно попадать,
если мы нарисуем, вот у нас, например, точка Nk,
в окрестность шириной r точки Nk.
Мы можем показать,
что для любого k yk,
удовлетворяющий этому условию, во-первых, существует.
Поскольку окрестность шириной r, то очевидно существует такой y,
который домноженный на r, попадет в эту окрестность.
Более того, такой y единственный.
Существует единственный yk.
Также мы можем заметить, что y0 = 0,
и 0 же по модулю N равен yr,
потому что yr = N.
Получается, что таких разных y,
которые удовлетворяют всем этим неравенствам, всего r штук.
Для каждого из них вероятность его измерения равна вот этому значению.
Мы можем домножить ее на r и получить вероятность
измерения хорошего в принципе y.
И эта вероятность 4/π² — это почти половина.
Мы с вами выяснили,
что в результате применения алгоритма Шора мы с достаточно хорошей вероятностью
сможем померить в нашем входном регистре так называемый хороший y.
Это y, удовлетворяющий вот этим неравенствам.
Пришла пора объяснить, почему эти y хорошие.
Давайте разделим это неравенство на N и на r.
Здесь у нас будет y / N,
здесь k / r
+ 1 / 2N,
и k /
r − 1 / 2N.
Получается, что вот у нас есть число y / N,
и в окрестности шириной 1
/ N у нас здесь есть еще число k / r,
несущее в себе некоторую информацию о нашем искомом периоде r.
Давайте посмотрим, почему эта информация полезна.
Предположим, что есть два числа r1
и r2 ≤ √N.
Посмотрим, как далеко могут находиться друг от
друга дроби со знаменателями в виде этих чисел.
Приводим к общему знаменателю,
[БЕЗ СЛОВ]
и это точно ≥ 1
/ r1 r2.
r1 r2 ≤
N, и значит это ≥ 1 / N.
Таким образом, в окрестность, шириной 1 / N,
не может попасть два числа со знаменателем, меньшим чем √N.
А мы помним, что наше r < √N.
И соответственно, число такого вида как k / r в этой окрестности единственное.
Осталось его найти и сделать это можно, например, методом непрерывной дроби.
Разберем пример.
Пусть n = 10,
тогда N = 2 в десятой степени = 1024.
И, запустив алгоритм Шора, мы померили,
например, число y = 139.
Таким образом, в окрестности точки
139/1024, в окрестности
шириной 1/1024 существует интересующее нас
число со знаменателем меньшим чем √1024.
Давайте запишем эту дробь по-другому, развернем ее.
Это 1 / 1024 /
139.
[БЕЗ СЛОВ] Это так называемый метод непрерывной дроби.
Вот эта дробь направо у нас будет расти таким образом,
и 1/7 — это первая наша оценка.
1/7 +
1/139/ 51
[БЕЗ СЛОВ] /
2 + 37/51.
Закрываем эту часть, получаем 1
/ 7,5 или 2 / 15.
2/15 — наша следующая оценка.
Идемте дальше.
[БЕЗ СЛОВ]
[БЕЗ СЛОВ] [БЕЗ
СЛОВ] [БЕЗ СЛОВ]
[БЕЗ СЛОВ] [БЕЗ
СЛОВ] [БЕЗ
СЛОВ] +
51 − 37 = 14/ 37-х.
Можем (вот это вот закрываем) домножить на 3.
Здесь получится 3,
здесь 21 + 1.
А, то есть 3/22.
3/22 — наша следующая оценка.
Мы можем заметить, что число 3/22 находится
от числа 139/1024 на
расстоянии < 1/1024.
Кроме того, 22
< √1024,
соответственно получается, что искомое нами число r делится на число 22.
Итак, мы с вами сегодня разобрали алгоритм Шора,
который с вероятностью 1/2 позволяет находить хороший y,
который, в свою очередь, позволяют находить делители числа r,
которые являются периодом функции, зная которые с вероятностью 1/2,
мы можем разложить большое число N на множители.
Спасибо за внимание.
