Алгоритм Шора. Часть 2

Loading...

From the course by Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

Saint Petersburg State University

Квантовые вычисления (Quantum computing)

20 оценки

О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.

From the lesson

Алгоритм Шора

В этом модуле мы разберем самый известный квантовый алгоритм - алгоритм Шора, позволяющий эффективно раскладывать составное число на множители.

Квантовое преобразование Фурье21:12

Алгоритм Шора. Часть 115:50

Алгоритм Шора. Часть 211:00

Meet the Instructors

Сысоев Сергей Сергеевич
кандидат физико-математических наук
Кафедра системного программирования

[МУЗЫКА]

[МУЗЫКА] Мы

с вами посчитали вероятность измерения каждого конкретного хорошего 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 на множители.

Спасибо за внимание.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

Загрузить из App Store

Загрузить в Google Play