О квантовых вычислениях много пишут и говорят, особенно в последнее время. Причины такого интереса вполне очевидны - потребность в новом поколении вычислительных устройств назрела уже давно, и квантовый компьютер - первый кандидат на то, чтобы стать этим новым поколением. Для работы с новыми, только возникающими технологиями требуются специалисты, разбирающиеся в основах этих технологий - инженеры, физики, математики, алгоритмисты... Это - те люди, которые, возможно, станут у истоков новой эры и смогут поучаствовать в осуществлении очередного грандиозного шага в развитии человечества. Затронуть все аспекты темы квантовых вычислений в рамках одного MOOC не представляется возможным, поэтому данный курс охватывает только одну их область - анализ и проектирование квантовых алгоритмов. Прослушав курс, вы: 1. Разберетесь с моделью квантовых вычислений и поймете, что такое квантовый компьютер с точки зрения алгоритмиста и математика. 2. Познакомитесь с простыми (и не очень простыми) квантовыми алгоритмами и получите начальные навыки их проектирования. 3. Просто получите удовольствие, всегда сопровождающее познание чего-то нового. Команда курса желает вам успехов в освоении материала. Мы будем искренне рады, если знания, полученные вами здесь, помогут вам в достижении новых теоретических и практических результатов.
Алгоритм Шора. Часть 1
Loading...
Из курса от партнера Saint Petersburg State University
Квантовые вычисления (Quantum computing)
20 оценки
Из урока
Алгоритм Шора
В этом модуле мы разберем самый известный квантовый алгоритм - алгоритм Шора, позволяющий эффективно раскладывать составное число на множители.
Познакомьтесь с преподавателями
Сысоев Сергей Сергеевичкандидат физико-математических наук
Кафедра системного программирования
[МУЗЫКА]
[МУЗЫКА]
Переходим к алгоритму Шора.
У нас есть функция,
[ШУМ]
отображающая n бит в n бит.
И у этой функции существует
период: [ШУМ]
[ШУМ] для любого j,
такого, что вот это значение входит в область определения функции.
И мы также будем предполагать, что период существенно меньше,
чем N, которое у нас равно 2 в степени n,
и существенно больше, чем 1.
Например, r может быть меньше либо равен √N.
Нам нужно искать этот период,
и схема квантового устройства, она очень сильно напоминает схему устройства
в алгоритме Саймона, когда мы искали период в кольце z2.
Давайте вспомним эту схему.
[ШУМ] Итак,
у нас по-прежнему два регистра: x и y.
К x мы применяем преобразование Адамара.
Потом мы действуем нашим оператором Uf,
меряем второй регистр, регистр значений функций.
После чего здесь у нас, в задаче Саймона был оператор Адамара и измерения.
В нашем нынешнем случае вместо оператора Адамара
в этот квадратик мы поставим квантовой преобразование Фурье.
Давайте посмотрим, что даст нам применение этой схемы.
В задаче Саймона вместо x мы подавали 0,
и вместо y тоже подавали 0.
После действия оператора Адамара
на x мы получали сумму всех возможных входов
для функции f.
И 0 на месте значений функции.
После чего мы действовали оператором Uf и получали
для каждого x значение f(x).
[ШУМ]
[ШУМ] Теперь
мы меряем регистр, который содержит значения функций
и получаем значение функции от какого-то конкретного x, скажем x'.
И в регистре, в первом — там, где у нас сгруппированы все входы для функции,
— мы получаем все прообразы f(x').
То есть мы получаем
[ШУМ] такое состояние.
То есть у нас будет не x0, а x'.
[ШУМ]
[ШУМ]
[ШУМ] Здесь
у нас появилось некоторое число A.
A, грубо говоря, = N / r,
то есть это сколько раз у нас помещается период
нашей функции f в ее области определения.
Более строго число A можно определить, например,
следующим образом: [ШУМ]
[ШУМ] [ШУМ]
[ШУМ] [ШУМ]
N − r.
Согласно схеме, мы померили регистр y,
получили там значение f от какого-то x0.
И, соответственно, в регистре x у нас получилась суперпозиция всех возможных
прообразов этого значения: x0, x0 + любое целое количество периодов.
Теперь по схеме нам надо подействовать на это квантовым преобразованием Фурье.
Давайте это сделаем.
[ШУМ]
[ШУМ]
[ШУМ]
[ШУМ]
[ШУМ] Итак,
мы это сделали.
И теперь давайте посмотрим на коэффициент при каком-то конкретном y,
например, y* — мы выбрали какой-то произвольный
базисный вектор и смотрим, чему равен коэффициент при нем.
Соответственно, вот эта сумма у нас уходит и получается,
что коэффициент равен 1 / √A√N.
Вот это вот мы можем
вынести за вот эту сумму, поскольку здесь нет параметра j.
[ШУМ] И
наша сумма по j.
[ШУМ]
[ШУМ] Так,
это у нас коэффициент.
И, поскольку мы здесь y обозначили как y*, здесь тоже можно дописать *.
Вот такой коэффициент у нас при каждом y.
Вероятность измерения каждого из y — это квадрат модуля коэффициента при нем.
Соответственно, вероятность измерения y* будет = 1 / AN.
Модуль комплексной экспоненты, как всегда — 1,
и дальше модуль нашей суммы
[ШУМ] в
квадрате.
Мы с вами выписали вероятность измерения любого конкретного y.
Давайте введем обозначение угла
θy вот следующим образом: это 2πry|N| / N.
Тогда вот эту сумму под модулем мы можем переписать
следующим образом: e в
степени θy × i ×
j, а j = от 0 до A − 1.
И мы можем с вами заметить, что это опять сумма геометрической прогрессии,
которая, соответственно, равна e в степени
A θyi − 1
/ e в степени θyi − 1.
Нас будет интересовать оценка модуля этой суммы.
В первую очередь заметим.
что знаменатель наш
оценивается модулем θy.
Чтобы это продемонстрировать, давайте рассмотрим единичную
окружность на комплексной плоскости.
e в степени θyi — вот когда это у нас угол θy,
Это e в степени θyi, это — 1.
e в степени θyi − 1 — это вот эта вот хорда.
А θy — это дуга.
Хорда ≤ дуги — это то, что у нас здесь написано.
Далее мы будем рассматривать хорошие y — это такие,
для которых A|θy|
∈ [0, π].
И для таких хороших θy мы покажем,
что |e в степени Aθyi
− 1| ≥
2A |θy| / π.
Давайте сделаем замену переменной.
Через x мы обозначим A |θy|.
Тогда вот это выражение у нас получается.
|(e в степени xi) − 1|
= по формуле Эйлера раскладываем e в степени
xi — это |cos x − 1
+ i sin x| — нам нужен модуль этого
выражения — =
√(cos x − 1)²
+ sin²x
= дальше
раскрываем скобки, получается cos² + sin² = 1,
еще + 1 вылезет из этой скобки,
получается √2 − 2cos x.
[БЕЗ СЛОВ] Мы можем
расписать это через косинус двойного угла,
в частности двойка — это у нас √2cos²
x/2 + 2sin² x/2.
Дальше cos x мы рассматриваем как cos двойного угла,
получается − 2cos² x/2
+ 2sin² x/2,
косинусы уходят и у нас получается √4 sin² x/2,
то есть 2 sin x/2,
что должно быть ≥ 2x
/ π
на отрезке от 0 до π.
Давайте посмотрим на вот эту и на вот эту функцию на отрезке от 0 до π.
[БЕЗ СЛОВ] Эта
в 0 = 0,
в π = 2, [БЕЗ
СЛОВ] Линейная
функция у нас.
Теперь 2sin x/2 в 0 = 0;
в π — sin π/2 = 1 и она тоже равна 2.
Но синус на вот этом отрезке — выпуклый вверх.
Поэтому мы плюсуем синус вот так и таким образом показываем,
что неравенство, которое мы хотели доказать, выполняется на всем отрезке.
Итак, мы с вами выписали вероятность для каждого конкретного y.
После этого мы назвали с вами хорошими y такие, для
которых выполняется вот это вот свойство: Aθy принадлежит отрезку от −π до π.
И показали, что для таких вот хороших y эта сумма может быть оценена следующим
образом: она распадается на числитель и знаменатель, числитель больше либо равен,
чем вот это число; знаменатель меньше либо равен, чем модуль θ.
И таким образом, все вместе для хороших y мы можем оценить
следующим образом: здесь числитель мы возводим в квадрат,
получается (4A²|θy|²)
/ π² и делим на |θy|².
|θy|² сокращается,
этот квадрат сокращается с этим A,
A / N ≈ 1 / r.
Получается 1 / r * 4
/ π² [БЕЗ СЛОВ]
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
