[МУЗЫКА] [МУЗЫКА] Мы с вами посчитали вероятность измерения каждого конкретного хорошего 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 на множители. Спасибо за внимание.
