[МУЗЫКА] [МУЗЫКА] Переходим к алгоритму Шора. У нас есть функция, [ШУМ] отображающая 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 / π² [БЕЗ СЛОВ]
