Шпаргалка: Архитектура алгоритма Шора

Цель: Найти два нетривиальных простых (простые числа) сомножителя для большого составного числа N. В примере ниже: N = 15 (для примера берем маленькое число, но на деле числа гигантские). Иными словами — нам нужно «расколоть» большущее число на два простых множителя.

Возникает вопрос, а нафига нам вообще этим заниматься? Какие-то числа раскладывать на множители. А всё очень просто, вся современная криптография (пароли счетов в банках, на сайтах и т.д.) основываются на том, что гигантские число, это ваш зашифрованный пароль, точнее множество таких чисел. А вот простые сомножители этих чисел, это те самые буквы пароля, который вы придумываете для вашего WIFI или счета в банке.

Это сильное упрощение, но суть именно такова. Здесь кроется математическая фишка — мы можем за долю секунды перемножить два гигантских числа, любой обычный комп справится с этим буквально за пару десятков/сотен тактов, но вот чтоб обратно разложить полученное число, обычному компьютеру придётся просто перебирать варианты, и на это у него уйдут миллиарды миллиардов лет (это без преувеличения) даже если это будут суперкомпьютеры.

Однако и тут может возникнуть вопрос — а как же тогда наши телефончики узнают что пароль правильный, ведь они же всё это будут считать миллиарды лет? Вполне логичный вопрос, а ответ проще некуда.

Роутеру ничего не нужно разгадывать и перебирать, он выполняет вычисления только в «легкую» сторону. Когда вы вводите пароль на телефоне, телефон знает секретный «ключ». Роутер отправляет вашему телефону математическую загадку основанную на записанном у него пароле. Телефон тоже знает этот пароль, он мгновенно щелкает эту загадку и возвращает роутеру готовый ответ. Роутер просто сравнивает ответ. Если совпало — «добро пожаловать», если нет — «от ворот поворот». То есть роутер не ищет иголку в стоге сена, он просто проверяет, смог ли ваш телефон её найти. А телефон её находит на том простом основании, что он (в отличии от хакера) знает изначальный пароль (мы же этот пароль сами вводили в роутер при настройке и в телефон при первом подключении).

Здесь так же стоит отметить, что наше гигантское число должно быть составным (то есть состоящим из нескольких простых чисел), но при этом оно должно быть произведением ровно двух очень больших простых чисел.


Этап 1. Циклы остатков (Леонард Эйлер, 18 век).

Суть: Если взять случайное число a (взаимно простое с N) и последовательно возводить его в степени по модулю N, остатки начнут циклически повторяться. Длина этого цикла — это период r.

Математика Эйлера доказывает, что в периоде r зашифрован секретный код делителей числа.

Математический пример: Выбираем случайное a = 7, возводим в степень и вычисляем по модулю 15:



Как только встретили единицу, значит после неё цикл повторится.

Полученный период: r = 4, последовательность остатков — (7, 4, 13, 1, 7, 4, 13 ...).


Этап 2. Формула деления через период (Гэри Миллер, 1976 г).

Суть: Чисто классический алгоритм. Если период r — чётное число, то выражение (a^r — 1) можно разложить по формуле разности квадратов на две скобки — (a^{r/2} — 1) и (a^{r/2} + 1).

Миллер доказал, что эти скобки с вероятностью больше 50% делят общее число N на его истинные простые множители через вычисление Наибольшего Общего Делителя (НОД).

Наш период r = 4 (он чётный, это главное условие). Теперь делаем промежуточный расчёт: делим наш период пополам (4 / 2 = 2) и возводим наше случайное число 7 в эту степень. Получаем: (7^2 = 49). От этого числа мы теперь отнимаем и прибавляем единицу, чтобы получить две скобки Миллера. Первая скобка — (49 — 1 = 48), вторая скобка — (49 + 1 = 50).

Применяем обычный алгоритм Евклида для поиска НОД с исходным числом 15 — НОД(48, 15) = 3 (число 15 три раза помещается в 48 и остаток 3), НОД(50, 15) = 5 (число 15 три раза помещается в 50 и остаток 5). В результате наше 15 успешно расколото на 3 и 5 (два простых числа являющиеся сомножителями).


Этап 3. Параллелизм суперпозиции (Дэвид Дойч, 1985 г).

Суть: Это физический фундамент квантового процессора. Обычный компьютер вычисляет остатки Эйлера (этап 1) строго по очереди (сначала (7^{1}), потом (7^{2}), потом (7^{3})...). Короче говоря, он тупо перебирает варианты, по другому обычные компьютеры не умеют. Если число огромное, на это уйдут миллиарды лет.

Квантовый компьютер вводит кубиты в состояние суперпозиции, записывая в регистр сразу все числа (x) одновременно.

Функция модулярной экспоненциации (f(x) = a^x N) считается всего один раз, но благодаря физике квантовых состояний ответ вычисляется для миллиардов аргументов параллельно.

Квантовый пример — кубиты переходят в состояние…



Данные вычислены, но они «размазаны» волновыми амплитудами. Напрямую измерить их нельзя (выпадет случайный мусор).


Этап 4. Модифицированное волновое сито (Питер Шор, 1994 г).

Суть: Сердце квантового ускорения алгоритма. Шор переписал формулу дискретного преобразования Фурье (см. ниже) под квантовые вентили (QFT).

QFT превращает числовые значения кубитов в квантовые волны. Волны «неправильных» ответов сталкиваются в противофазе и уничтожают друг друга (деструктивная интерференция). Волны «правильных» ответов, кратных скрытому периоду (r из этапа 1), попадают в резонанс и усиливают друг друга (конструктивная интерференция). Хоть как-то, отдалённо, представить себе это, можно посмотрев известный эксперимент с двумя щелями и пролетающими через них фотонами.

Математический пример (концептуальный). QFT трансформирует состояние суперпозиции, переводя его из плоскости чисел в плоскость частот. Все ложные варианты схлопываются в ноль. На выходе мы получаем идеальный волновой пик вероятности, указывающий на частоту, жестко привязанную к периоду:



Далее специальный считывающий импульс (например, лазерный или микроволновый) проходит сквозь кубиты, фиксирует их состояние и мгновенно передает эти данные на обычный компьютер. Обычный комп выводит результат на экран в виде графика, где среди шума горит один мощный волновой пик. Компьютер видит этот пик, распознает, что наш период (r = 4), и моментально передает этот чистый период классическому блоку Миллера (этап 2), который тут же выдает готовый ответ.






Роль Жозефа Фурье в квантовом мире или «важное математическое примечание».

Фурье открыл фундаментальный закон природы — любой сложный повторяющийся сигнал (или функцию) можно разложить на сумму простых гармонических волн.

На этом принципе сегодня работает сжатие MP3, обработка звука и картинок. Шор понял, что в квантовом компьютере данные — это не просто строчки цифр. Из-за суперпозиции они ведут себя как настоящие физические волны со своими гребнями и впадинами. Без Фурье квантовый компьютер выдавал бы нам гигантское облако из миллионов случайных чисел. Нам пришлось бы миллиард лет перебирать их вручную, чтобы нащупать закономерность.

С Фурье Шор перевёл абстрактную математическую формулу Фурье на язык квантовых лазеров и магнитных импульсов (вентилей). Это волновое сито (QFT) заставило «лишние» числа сталкиваться в противофазе и уничтожать друг друга, а правильный период — срезонировать и ярко подсветиться на экране. Жозеф Фурье дал алгоритму Шора «глаза». Без его волновой математики квантовый компьютер оставался бы сверхмощным вычислителем, который считает всё одновременно, но не способен показать человеку правильный ответ.


Это всё, всем спасибо )))