Тридцать лет спустя: ускорение квантового факторинга | Журнал Кванта

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

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

За последние 30 лет ученые-компьютерщики оптимизировали алгоритм Шора, готовясь к тому дню, когда квантовая технология достигнет достаточной зрелости, чтобы его можно было использовать. Но новый вариант, от ученого-компьютерщика Нью-Йоркского университета Одед Регев, быстрее в принципиально новом смысле. Впервые удалось улучшить взаимосвязь между размером факторизуемого числа и количеством квантовых операций, необходимых для его факторизации.

«Действительно удивительно, что кому-то, очевидно, удалось улучшить сложность этого результата много-много лет спустя», — сказал Эшли Монтанаро, исследователь квантовых вычислений из Бристольского университета. «Это действительно интересно».

Мартин Экеро, криптограф из Шведского национального управления безопасности коммуникаций, согласился с тем, что статья Регева интересна, но предупредил, что для преодоления современного уровня техники на практике потребуется дальнейшая оптимизация. «Оригинальные алгоритмы Шора уже удивительно эффективны, поэтому внести серьезные улучшения не так уж и просто», — написал он по электронной почте.

Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией.

«Я думал, что любой алгоритм, работающий по этой базовой схеме, будет обречен», — сказал Шор, прикладной математик, работающий сейчас в Массачусетском технологическом институте. "Но я был неправ."

Поиск факторов

Квантовые компьютеры черпают свою мощь из своеобразного способа обработки информации. Классические компьютеры используют биты, каждый из которых всегда должен находиться в одном из двух состояний, обозначенных 0 и 1. Квантовые биты, или «кубиты», дополнительно могут находиться в комбинациях состояний 0 и 1 — явление, называемое суперпозицией. Также возможно объединить несколько кубитов в коллективное состояние суперпозиции: двухкубитная суперпозиция имеет четыре компонента, которые могут выполнять разные вычисления одновременно, и количество таких компонентов растет экспоненциально по мере увеличения количества кубитов. Это позволяет квантовым компьютерам эффективно выполнять экспоненциально множество различных вычислений параллельно.

Но есть подвох: Чтение результата вычисления, выполненного в суперпозиции, показывает ответ только на часть, вычисленную с помощью одного случайного компонента. Чтобы воспользоваться преимуществами вычислений в суперпозиции, вы должны каким-то образом отобразить конечный результат в более простое состояние, в котором его можно будет безопасно прочитать. В большинстве случаев это невозможно, и поначалу никто не знал, как заставить это работать при любой проблеме. «Очень немногие люди имели смелость подумать о квантовых вычислениях», — сказал Регев.

Затем в 1994 году Шор прочитал бумага ученый-компьютерщик Дэниел Саймон, который показал, как использовать квантовую суперпозицию для решения надуманной проблемы. Шор придумал, как распространить результат Саймона на более общую и практическую задачу, называемую поиском периода. Математическая функция называется периодической, когда ее выходные данные неоднократно проходят через одни и те же значения по мере увеличения входных данных; длина одного цикла известна как период функции.

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

Когда Шор искал применение своему квантовому алгоритму определения периода, он заново открыл ранее известную, но малоизвестную математическую теорему: для каждого числа существует периодическая функция, периоды которой связаны с простыми множителями числа. Поэтому, если есть число, которое вы хотите учесть, вы можете вычислить соответствующую функцию, а затем решить проблему, используя поиск периода — «именно в этом квантовые компьютеры так хороши», — сказал Регев.

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

Алгоритм Шора был одним из немногих ключевых ранних результатов, которые превратили квантовые вычисления из малоизвестной области теоретической информатики в огромную мощь, которой они являются сегодня. Но применение алгоритма на практике — непростая задача, поскольку квантовые компьютеры, как известно, подвержены ошибкам. Дополнительная работа чтобы они не потерпели неудачу. А Недавняя статья Экеро и исследователь Google Крейг Гидни По оценкам, для использования алгоритма Шора для факторизации стандартного 2,048-битного числа (длиной около 600 цифр) потребуется квантовый компьютер с 20 миллионами кубитов. Сегодняшние современные машины насчитывают не более нескольких сотен.

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

Если это так, сказал Регев, «мы должны узнать об этом как можно раньше, пока не стало слишком поздно».

Потерянный среди деревьев

Регев начал свою академическую карьеру в конце 1990-х годов, когда криптографы искали новую форму криптографии с открытым ключом, не уязвимую для алгоритма Шора. Наиболее перспективный подход, названный криптография на основе решетки, полагается на кажущуюся сложность вычислительных задач, связанных с многомерными массивами точек или решетками. Одна из таких задач сродни задаче поиска дерева, ближайшего к случайной точке леса.

«Если это стомерный лес, то это гораздо сложнее, чем если бы это был двухмерный лес», — сказал Грег Куперберг, математик из Калифорнийского университета в Дэвисе.

Регев начал изучать решетчатую криптографию в качестве постдока, первоначально в качестве злоумышленника — он хотел провести стресс-тестирование нового подхода, найдя слабые места, которыми мог бы воспользоваться квантовый компьютер. Но он не смог добиться никакого прогресса и вскоре задумался, есть ли для этого более глубокая причина. В 2005 году он нашел способ превратить эти неудавшиеся атаки в форма криптографии на основе решетки превосходит все остальные варианты.

«Одед великолепно справляется с решетками», — сказал Куперберг.

На протяжении многих лет, обучая алгоритму Шора последовательным поколениям студентов, Регев задавался вопросом, могут ли методы, которые он использовал для атаки на решетчатую криптографию, действительно оказаться полезными в алгоритмах факторизации. Это потому, что один шаг на заключительном, классическом этапе алгоритма Шора сводится к поиску ближайшей точки в одномерной решетке. Эта одномерная задача тривиально проста, но сходство с аналогичной задачей в сотнях измерений, сложность которой лежит в основе решетчатой ​​криптографии, было безошибочным.

«Если вы, как и я, занимаетесь решетками, вы думаете: «Хорошо, здесь есть какая-то решетка», — сказал Регев. «Но мне было неясно, как этим воспользоваться». В течение многих лет он обдумывал другие идеи новых алгоритмов квантового факторинга, но так и не добился успеха. Затем прошлой зимой он вернулся к этой проблеме и решил выявить заманчивую связь между факторингом и решетчатой ​​криптографией. На этот раз он добился успеха.

Дополнительные измерения

Регев знал, что ему нужно начать с обобщения периодической функции, лежащей в основе алгоритма Шора, с одного измерения на множество измерений. В алгоритме Шора эта функция включает в себя многократное умножение случайного числа, получившего название g, с собой. А вот период этой функции — количество раз, которое нужно умножить на g прежде чем вывод функции начнет повторяться — может быть очень большим, а это означает, что квантовый компьютер должен умножать большие числа в некоторых компонентах суперпозиции, которую он использует для вычисления периодической функции. Эти большие умножения являются наиболее затратной в вычислительном отношении частью алгоритма Шора.

Аналогичная двумерная функция вместо этого использует пару чисел: g₁ и g₂. Он предполагает умножение g₁ сам с собой много раз, а затем многократно умножая на g₂. Период этой функции также двумерен — он определяется числом g₁ умножения и g₂ умножения, которые вместе приводят к повторению вывода функции. Существует множество различных комбинаций g₁ и g₂ умножения, которые сделают свое дело.

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

«Вы думаете: «Отлично, я только что сделал все в больших измерениях, и время работы точно такое же, как у Шора», — говорит Регев. «На какое-то время я застрял в этом». Затем он понял, что можно обойти эту проблему, изменив порядок умножения. Вместо того, чтобы постоянно прикреплять числа к одному продукту, который в ходе квантовых вычислений постепенно увеличивался, он начал с пар маленьких чисел, перемножил полученные продукты вместе и двинулся вверх. Общее количество умножений не сильно изменилось, но теперь почти все они включают относительно небольшие числа, что ускоряет вычисления.

«В этом вся разница в мире», — сказал Винод Вайкунтанатан, криптограф в Массачусетском технологическом институте.

Поначалу казалось, что Регев просто заменил одну проблему другой. Он ускорил квантовое вычисление периодической функции, увеличив число измерений, но последующие классические вычисления, необходимые для извлечения периода, теперь были похожи на определение местоположения ближайшей точки решетки в многомерном пространстве — задача, которую многие считали решающей. быть жестким. Аналогия с решетчатой ​​криптографией, которая мотивировала его новый подход, казалось, обрекала его на провал.

Одним холодным мартовским утром перед поездкой на семинар в Принстонский университет Регев обнаружил, что ждет коллегу, с которым ездил на машине. «Я приехал рано, а он опоздал, чтобы забрать машину», — сказал он. Пока он сидел и ждал, к нему внезапно пришла последняя часть головоломки. «Это тот момент, когда все встало на свои места, но какое-то время все шло не так».

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

Писать на песке

Улучшение было глубоким. Число элементарных логических шагов в квантовой части алгоритма Регева пропорционально n^1.5 при факторинге n-битное число, а не n² как в алгоритме Шора. Алгоритм повторяет эту квантовую часть несколько десятков раз и объединяет результаты для построения многомерной решетки, из которой он может вывести период и факторизовать число. Таким образом, алгоритм в целом, возможно, не будет работать быстрее, но ускорение квантовой части за счет уменьшения количества необходимых шагов может облегчить его применение на практике.

Конечно, время, необходимое для запуска квантового алгоритма, — лишь одно из нескольких соображений. Не менее важно и необходимое количество кубитов, которое аналогично памяти, необходимой для хранения промежуточных значений во время обычных классических вычислений. Количество кубитов, необходимое алгоритму Шора для факторизации n-битное число пропорционально n, а алгоритм Регева в исходном виде требует количества кубитов, пропорционального n^1.5 — большая разница для 2,048-битных чисел.

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

«Наши кубиты постоянно пытаются развалиться, и мы пытаемся не дать им развалиться», — сказал Гидни. «Это похоже на то, как будто ты пытаешься писать на песке, а ветер уносит его». Это означает, что дополнительные кубиты, необходимые для алгоритма Регева, могут быть серьезным недостатком.

Но статья Регева — это не конец истории. Две недели назад Вайкунтанатан и его аспирант Сейун Рагаван нашли способ сократить использование памяти алгоритмом. Их вариант Алгоритма Регева, как и оригинальный алгоритм Шора, требуется количество кубитов, пропорциональное n , а не n^1.5. Экеро написал в электронном письме, что эта работа «намного приближает нас к реализации, которая будет более эффективной на практике».

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

«Этот вариант моего алгоритма не был обнаружен в течение 30 лет и появился совершенно неожиданно», — сказал Шор. «Вероятно, еще предстоит найти множество других квантовых алгоритмов».

Примечание редактора: Одед Регев получает финансирование от Фонд Симонс, который также финансирует этот редакционно независимый журнал. Решения о финансировании Фонда Саймонса не влияют на наше покрытие. Более подробная информация доступен здесь.

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