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

Loading...

Из курса от партнера Saint Petersburg State University

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

24 оценки

Explore Related Videos

At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you

Saint Petersburg State University

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

24 оценки

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

Из урока

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

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

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

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

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

Познакомьтесь с преподавателями

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

[МУЗЫКА]

[МУЗЫКА] Мы

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

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

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