nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

Шор, дай я попробую!

Специально для d_integral и 2born решил перевести на русский язык статью Скотта Ааронсона Shor, I'll do it, в которой он буквально на пальцах объясняет алгоритм Шора для быстрого нахождения простых множителей с помощью квантового компьютера. Там все основано на модулярной арифметике) Итак:


Шор, дай я попробую!
Скотт Ааронсон

В последнее время я много рассказывал о том, как квантовые алгоритмы не могут работать. Но на прошлой неделе J.R. Minkel, редактор Scientific American, попросил меня написать короткий рассказ о том, как же они тогда работают? - чтобы он мог повесить на сайте SciAm ссылочку. "Хорошо!" - ответил я, моментально забыв о ликбезов по квантовым алгоритмам, которые уже есть в сети. Итак, я поставил себе следующую задачу: объяснить алгоритм Шора, не используя ни единой треугольной скобочки, да и вообще ничего сложнее простой арифметики.

Хорошо, положим, что вы хотите взломать криптосистему RSA, чтобы ограбить парочку банков, прочитать почту своей бывшей, да мало ли для чего еще. Мы все знаем, что взлом RSA сводится в конечном итоге к нахождению множителей большого числа N. К сожалению, мы также знаем, что "попробовать все возможные множители одновременно", а затем выбрать нужный, не получится. Что бы ни говорила сотня популярных журналов, но квантовые компьютеры так не работают. Конечно, вы можете с их помощью "попробовать все возможные множители одновременно" - но когда вы измерите результат, вы получите случайный множитель, который скорее всего будет не тем, который нужен.

Другими словами, если мы хотим получить быстрый алгоритм разложения на множители, мы должны обнаружить некоторую структуру, скрытую в этой задаче, некоторое математическое свойство, которое выделяет данную задачу из класса "поиск иголки в стоге сена".

К счастью, проблема разложения на множители имеет уйму особенностей. Вот одна из них: если я назову вам положительное целое число, вы можете не знать, как оно раскладывавается на простые множители, но вы можете быть уверены: это разложение единственно! Для сравнения: если я дам вам Судоку и попрошу решить, а приори вы не будете знать, есть ли у него в точности одно решение, или 200 миллионов, или вовсе не одного. Конечно, знание, что иголка в стоге сена строго одна, не сильно поможет нам в ее поиске! Но эта единственность - подсказка, что в проблеме поиска множителей могут быть другие приятные математические особенности, только подходи и бери! Оказывается, так оно и есть.

Мы будем использовать то свойство, что задачу разложения на множители можно свести к другой задаче, поиску периода. Самое время сделать небольшое лирическое отступление и кратко рассказать о теории чисел. Давайте рассмотрим мою любимую с 5 лет последовательность целых чисел, степени двойки.

2,4,8,16,32,64,128,256,512,1024, ...

Теперь взглянем на степени двойки "по модулю 15" (mod 15), другими словами, остаток от деления на 15 от каждого из приведенных выше чисел.

2, 4, 8, 1, 2, 4, 8, 1, 2, 4, …

Как видите, степени двойки по модулю 15 представляют собой периодическую последовательность, с периодом (т.е сколько чисел надо пройти, прежде чем она начнет повторяться), равным 4. Другой пример: возьмем степени двойки по модулю 21:

2,4,8,16,11,1,2,4,8,16, ...

В этот раз мы получили последовательность с периодом 6.

Вы можете спросить: существует ли общее правило, способное предсказать этот период? Вдруг математики хоть что-нибудь придумали по этому поводу?

Еще как придумали - есть красивая закономерность, обнаруженная Эйлером в 1760-х. Пусть N будет произведением двух простых чисел, p и q, и рассмотрим последовательность

x mod N, x2 mod N, x3 mod N, x4 mod N, ...

Тогда, если x не делится ни на p, ни на q, данная последовательность будет иметь период, который делит нацело число (p-1)(q-1).

Например, если N=15, то его простые множители p=3 и q=5, значит, (p-1)(q-1)=8. И действительно, период последовательности был равен 4, что делит 8 нацело. Если N=21, то p=3 и q=7, и (p-1)(q-1)=12. Все верно: период был равен 6, что делит 12 нацело.

Теперь давайте сделаем шаг назад и подумаем, что все это значит. А значит это, что если бы мы смогли найти период последовательности

x mod N, x2 mod N, x3 mod N, x4 mod N, ...

то мы узнали бы кое-что о простых множителях числа N! Конкретнее, мы узнали бы делитель (p-1)(q-1). Да, это не так здорово, как узнать p и q непосредственно, но это уже кое-что. Даже больше, чем кое-что. Оказывается, мы можем узнать несколько делителей числа (p-1)(q-1), пробуя разные случайные значения x, после чего с высокой долей вероятности мы узнаем и само значение (p-1)(q-1). А зная его и проделав еще пару трюков, мы найдем сами p и q, нужные нам простые множители.

Так в чем же ложка дегтя? Ну, хотя последовательность

x mod N, x2 mod N, x3 mod N, x4 mod N, ...

и начнет однажды повторяться, но число шагов может быть столь же большим, как и само число N - а оно может иметь сотни и тысячи разрядов! Поэтому нахождение периода не приводит к быстрому классическому методу факторизации.

Ага, но ведь у нас есть квантовый компьютер! (Или, по крайней мере, представим, что он у нас есть.) Тогда появляется надежда. В частности, мы могли бы сделать мощнейшую квантовую супепозицию всех чисел нашей последовательности: x mod N, x2 mod N, x3 mod N и т.д. Тогда, может, найдется такая квантовая операция, которая найдет ее период.

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

Смотрите: если мы взглянем на квантовые вычисления в терминах "параллельных вселенных" (а принимать ли такую точку зрения - выбор за вами), нет никакой возможности заметить одну-единственную вселенную, отличную от остальных. Такой глас вопиющего в пустыне будет заглушен мощным хором живущих неподалеку, одевающих брюки Dockers, вселенных-конформистов. Однако, мы вполне можем обнаружить общее свойство всех вселенных, вместе взятых, свойство, которое появится как результат параллельных вычислений всех участвующих вселенных.

(Заметка: для вашей же безопасности, не пытайтесь объяснить вышеизложенное популярным писателям из школы "квантовые вычисления = бесконечное распараллеливание". Они могут сдуться, как вампиры на солнечном свете)

Итак, задача вовсе не безнадежна! Но прежде чем идея с нахождением периода заработает, нужно ответить на 2 вопроса:

1. Можно ли с помощью квантового компьютера быстро создать суперпозицию из x mod N, x2 mod N, x3 mod N и т.д?

2. Допустим, такая суперпозиция у нас получилась, а как же теперь узнать период?

Разберемся сначала с первым вопросом. Мы определенно можем сделать суперпозицию из всех целых чисел r, от 1 до N. Но можно ли, при данном r, быстро сосчитать xr mod N? Если r равно, скажем, 300 квадриллионам, то неужто придется помножать x на себя все 300 квадриллионов раз? Это было бы слишком медленно, и, к счастью, не требуется. Вместо этого мы можем проделать операцию под названием "повторное возведение в квадрат". Проше всего показать на примере.

Допустим, N=17, x=3 и r=14. Первый шаг - представить r как сумму степеней двойки:

r=23+22+21.

Тогда,



Нам достаточно возводить x в квадрат, результат снова в квадрат, и еще, и еще, а потом нужные степени перемножить.

Заметим также, что все вычисления можно делать по модулю N, что позволит числам оставаться маленькими на промежуточных шагах. Получаем результат:

314 mod 17 = 2.

Хорошо, мы умеем создавать квантовую суперпозицию всех пар целых чисел (r, xr mod N), где r меняется от 1 до N. Осталось понять, как из этой суперпозиции вычленить период последовательности?

Вот мы и приходим к сути вопроса, к той части алгоритма Шора, которая целиком основана на квантовой механике. Чтобы узнать период последовательности, Шор использует штуку под названием квантовое преобразование Фурье, или QFT (Quantum Fourier Transform). Моя задача - объяснить вам QFT, не используя никакой математики. Хм....

Попробую так. Как у многих ученых-компьютерщиков, у меня есть очень странные часы. Знаете этот известный эксперимент, когда люди неделями сидели в закрытом помещении без смены дня и ночи, и в итоге переходили с цикла в 24 часа на 25-, 26- или 28-часовой день? Для меня это нормальная жизнь. Сегодня я встану в 9 утра, завтра в 11, после завтра в час дня, и так далее. Так и буду ходить по кругу, если только не помешают занятия или назначенные встречи. (Я все время так жил в Беркли.)

Вот мой вопрос. Я сказал вам, что сегодня проснулся в 5 часов вечера. Можете ли вы узнать из одного только этого факта, насколько длинный мой "день": 25 часов, 26.3 часа или еще какой-то?

Ответ: не особенно. Можно смело предположить, что я живу не по нормальному 24-часовому циклу, иначе я бы просыпался утром, а не в 5 вечера. Но любой другой период - 25 часов, 26 часов, 28 часов - любой из них заставит мой режим плавать по суткам, так что не будет ничего удивительного увидеть меня просыпающимся в 5 вечера в какой-то конкретный день.

Теперь я попрошу вас представить, что моя комната уставлена стрелочными часами. Это очень странные часы: у одних стрелка совершает оборот за 17 часов, у других - за 26 часов, у третьих - за 24.7 часа, и таких разных часов очень много. (Для простоты, считаем, что у них есть только часовая стрелка.) И еще под каждыми часами висит картонка, а в нее воткнута канцелярская кнопка. Когда я только въехал, каждая кнопка располагалась ровно посередине картонки. Но каждый день, когда я просыпался, я первым делом двигал каждую кнопку на один сантиметр в том направлении, куда в этот момент указывала стрелка соответствующих часов.

Новый вопрос: сможете ли вы, глядя на мои канцелярские кнопки, выяснить продолжительность моего "дня"?

Я утвердаю, что это возможно. Предположим, что я живу по 26-часовому распорядку. Что произойдет с кнопкой под 24-часовыми часами? Нетрудно видеть, что она будет совершать периодическое движение: конечно, она чуть-чуть будет смещаться, но через каждые 12 дней она будет возвращаться ровно на середину поля, оттуда, откуда и начинала. Одно утро я сдвину ее вправо, во второе - вправо и вверх, в следующий раз - вверх, и так далее, и в конце концов различные сдвиги погасят друг друга.

С другой стороны - снова считая, что я живу по 26-часовому распорядку - а что произойдет с кнопкой под 26-часовыми часами? Ответ будет другим, ведь по этим часам я буду просыпаться всегда в одно и то же время! Они будут смотреть в одну сторону, поэтому я буду двигать кнопку все дальше и дальше от центра, пока она вообще не дойдет до края!



Выходит, что просто взглянув, какая из кнопок ушла дальше других от центра, вы можете узнать, по какому распорядку я живу. Т.е вы можете узнать "период" моей жизни.

И это, в общих чертах, и есть квантовое преобразование Фурье. Более строго, QFT - это линейное преобразование (а еще точнее: унитарное), отображающее один вектор комплексных чисел на другой вектор комплексных чисел. Во входном векторе каждое ненулевое число соответствует времени, когда я просыпаюсь, нули во все остальные моменты. Выходной вектор - это положения всех кнопок под моими часами (о которых можно говорить как о точках на комплексной плоскости). В итоге мы получаем линейное преобразование, которое из квантового состояния, кодирующего периодическую последовательность, получает квантовое состояние, выражающее период этой последовательности.

Можно думать обо всем этом в терминах интерференции. Я имею в виду, что ключевой момент квантовой механики, та вещь, что делает ее столь отличной от классической теории вероятности - что если обычные вероятности всегда положительны, то амплитуды в квантовой механике могут быть положительными, отрицательными и даже комплексными. И поэтому, амплитуды получения того или иного ответа могут "интерферировать деструктивно" и подавить друг друга.

Именно это и происходит в алгоритме Шора. Каждая "параллельная вселенная", соответствующая элементу последовательности, вносит свой вклад в амплитуду каждой "параллельной вселенной", соответствующей каждому возможному периоду последовательности. Уловка в том, что для всех периодов, кроме истинного, эти вклады будут указывать в разную сторону и в конце концов вычтут друг друга. Только амплитуды для "правильного" периода сложатся синфазно, т.е будут смотреть в одном направлении. И ровно поэтому, проведя измерения, мы получим правильный ответ с высокой вероятностью.

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

Оригинал
Tags: красивые решения, математика, статьи
Subscribe

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 11 comments

  • Нахождение двух самых отдалённых точек

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

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…