Алгоритм Шора позволит квантовым компьютерам будущего быстро факторизовывать большие числа, нарушая многие протоколы онлайн-безопасности. Теперь учёные показали, как сделать это ещё быстрее.
Питер Шор не собирался ломать Интернет. Но алгоритм, который он разработал в середине 1990-х годов, грозил сделать именно это. В знаковой статье Шор показал, как гипотетический компьютер, использующий особенности квантовой физики, может разбивать большие числа на простые множители гораздо быстрее, чем любая обычная классическая машина.
Результат имел последствия, выходящие далеко за рамки математики. В то время жизненно важная компонента интернет-безопасности, называемая криптографией с открытым ключом, основывалась на гипотезе, что факторизация больших чисел настолько сложна в вычислительном отношении, что практически невозможна. Эта гипотеза до сих пор лежит в основе некоторых важных протоколов. Алгоритм Шора показал, что она окажется неверной в мире с мощными квантовыми компьютерами.
За последние 30 лет учёные оптимизировали алгоритм Шора, готовясь к тому дню, когда квантовая технология станет достаточно развитой, чтобы его можно было использовать. Но новый вариант, разработанный учёным Нью-Йоркского университета Одедом Регевом, быстрее в принципиально ином смысле. Впервые удалось улучшить взаимосвязь между размером факторизуемого числа и количеством квантовых операций, необходимых для его факторизации.
«Действительно удивительно, что кто-то, очевидно, смог улучшить сложность этого результата много-много лет спустя», — сказала Эшли Монтанаро. Она занимается квантовыми вычислениями в Бристольском университете.
Мартин Экеро, криптограф из Шведского национального управления безопасности коммуникаций, согласился с тем, что статья Регева интересна, но предупредил, что для преодоления современного уровня техники на практике потребуется дальнейшая оптимизация. «Оригинальные алгоритмы Шора уже удивительно эффективны, поэтому внести серьёзные улучшения не так уж и просто», — написал он в электронном письме.
Регев разработал свой новый алгоритм, дополнив алгоритм Шора методами из раздела криптографии, занимающегося многомерной геометрией.
«Я думал, что любой алгоритм, работающий по этой базовой схеме, будет обречён», — сказал Шор, прикладной математик, работающий сейчас в Массачусетском технологическом институте. «Но я был неправ.»
Поиск множителей
Квантовые компьютеры черпают свою мощь из своеобразного способа обработки информации. Классические компьютеры используют биты, каждый из которых всегда должен находиться в одном из двух состояний, обозначенных 0 и 1. Квантовые биты, или «кубиты», дополнительно могут находиться в комбинациях состояний 0 и 1 — явление, называемое суперпозицией. Также возможно объединить несколько кубитов в коллективное состояние суперпозиции: двухкубитная суперпозиция имеет четыре компоненты, которые могут выполнять разные вычисления одновременно, и количество таких компонент растёт экспоненциально по мере увеличения количества кубитов. Это позволяет квантовым компьютерам эффективно выполнять экспоненциальное множество различных вычислений параллельно.
Но есть одна загвоздка: чтение результата вычисления, выполненного в суперпозиции, показывает ответ только на ту часть, которая вычислена с помощью одной случайной компоненты. Чтобы воспользоваться преимуществами вычислений на основе суперпозиции, вы должны каким-то образом отобразить конечный результат в более простое состояние, в котором его можно будет безопасно прочитать. В большинстве случаев это невозможно, и поначалу никто не знал, как заставить это работать в любой задаче. «Очень немногие люди имели смелость подумать о квантовых вычислениях», — сказал Регев.
Затем, в 1994 году, Шор прочитал статью учёного Дэниела Саймона, в которой показано, как использовать квантовую суперпозицию для решения вымышленной проблемы. Шор придумал, как распространить результат Саймона на более общую и практическую задачу, называемую поиском периода. Математическая функция называется периодической, когда её выходные данные неоднократно проходят через одни и те же значения по мере увеличения входных данных; длина одного цикла известна как период функции.
Чтобы найти период заданной функции с помощью квантового компьютера, начните с создания очень большой суперпозиции, в которой каждая компонента вычисляет выходные данные функции для разных входных данных. Затем используйте метод Шора, чтобы преобразовать эту большую суперпозицию в более простое состояние и прочитать результат. В этот момент классический компьютер может взять на себя управление и быстро завершить вычисления. В целом, алгоритм Шора нахождения периода работает экспоненциально быстрее, чем любая классическая альтернатива, поскольку он одновременно вычисляет различные выходные данные периодической функции, используя суперпозицию.
Когда Шор искал применение своему квантовому алгоритму определения периода, он заново открыл ранее известную, но незамеченную математическую теорему: для каждого числа существует периодическая функция, периоды которой связаны с простыми множителями числа. Поэтому, если есть число, которое вы хотите факторизовать, вы можете вычислить соответствующую функцию, а затем решить проблему, используя поиск периода — «именно в этом квантовые компьютеры так хороши», — сказал Регев.
На классическом компьютере это был бы мучительно медленный способ факторизации большого числа — даже медленнее, чем перебор всех возможных множителей. Но метод Шора ускоряет процесс экспоненциально, превращая поиск периода в идеальный способ создания быстрого алгоритма квантовой факторизации.
Алгоритм Шора был одним из немногих ключевых ранних результатов, которые превратили квантовые вычисления из незаметной области теоретической информатики в огромную мощь, которой они являются сегодня. Но применение алгоритма на практике — непростая задача, поскольку квантовые компьютеры, как известно, подвержены ошибкам: помимо кубитов, необходимых для выполнения вычислений, им нужно множество других кубитов, выполняющих дополнительную работу, чтобы уберечь их от сбоя. В недавней статье Экеро и учёного из Google Крейга Гидни подсчитано, что для использования алгоритма Шора для факторизации стандартного 2048-битного числа (длиной около 600 цифр) потребуется квантовый компьютер с 20 миллионами кубитов. При этом современные квантовые машины насчитывают не более нескольких сотен кубитов.
Вот почему некоторые критически важные интернет-протоколы по-прежнему полагаются на то, насколько сложно факторизовать большие числа, но учёные не хотят слишком успокаиваться. Теоретические и технологические инновации могут ещё больше сократить необходимое количество кубитов, и нет никаких доказательств того, что алгоритм Шора оптимален — возможно, существует лучший алгоритм квантовой факторизации, который ещё никто не нашёл.
Если это так, сказал Регев, «мы должны узнать об этом как можно раньше, пока не стало слишком поздно».
Потерянный среди деревьев
Регев начал свою академическую карьеру в конце 1990-х годов, когда криптографы искали новую форму криптографии с открытым ключом, неуязвимую для алгоритма Шора. Самый многообещающий подход, называемый криптографией на основе решётки, основан на очевидной сложности вычислительных задач, связанных с многомерными массивами точек или решётками. Одна из таких задач сродни задаче поиска дерева, ближайшего к случайной точке леса.
«Если это стомерный лес, то это гораздо сложнее, чем если бы это был двумерный лес», — сказал Грег Куперберг, математик из Калифорнийского университета в Дэвисе.
Регев начал изучать решётчатую криптографию в качестве постдока, первоначально в качестве атакующего — он хотел провести стресс-тестирование нового подхода, найдя слабые места, которыми мог бы воспользоваться квантовый компьютер. Но он не смог добиться никакого прогресса и вскоре задумался, есть ли для этого более глубокая причина. В 2005 году он нашел способ превратить эти неудачные атаки в форму решётчатой криптографии, превосходящую все иные варианты.
«Одед великолепно справляется с решётками», — сказал Куперберг.
На протяжении многих лет, обучая алгоритму Шора многие поколения студентов, Регев задавался вопросом, могут ли методы, которые он использовал для атаки на решётчатую криптографию, действительно оказаться полезными в алгоритмах факторизации. Это потому, что один шаг на заключительном, классическом этапе алгоритма Шора сводится к поиску ближайшей точки в одномерной решётке. Эта одномерная задача тривиально проста, но сходство с аналогичной задачей в сотнях измерений, сложность которой лежит в основе решётчатой криптографии, было безошибочным.
«Если вы, как и я, занимаетесь решётками, вы думаете: «Хорошо, здесь есть какая-то решётка», — сказал Регев. «Но мне было неясно, как этим воспользоваться». В течение многих лет он обдумывал иные идеи новых алгоритмов квантовой факторизации, но так и не добился успеха. Затем прошлой зимой он вернулся к этой проблеме и решил выявить заманчивую связь между факторизацией и решётчатой криптографией. На этот раз он добился успеха.
Многие измерения
Регев знал, что ему нужно начать с обобщения периодической функции, лежащей в основе алгоритма Шора, с одного измерения на множество измерений. В алгоритме Шора эта функция включает в себя многократное умножение случайного числа, получившего название g, само на себя. Но период этой функции — количество раз, которое вы должны умножить на g, прежде чем выходные данные функции начнут повторяться — может быть очень большим. Это означает, что квантовый компьютер должен умножать большие числа в некоторых компонентах суперпозиции, которую он использует для вычисления периодической функции. Эти большие умножения — самая затратная в вычислительном отношении часть алгоритма Шора.
Аналогичная двумерная функция вместо этого использует пару чисел g1 и g2. Она включает в себя многократное умножение g1 само на себя, а затем повторное умножение на g2. Период этой функции также двумерен — он определяется количеством умножений g1 и умножений g2, которые вместе заставляют вывод функции повторяться. Существует множество различных комбинаций умножений g1 и g2, которые помогают получить хороший результат.
Регев проработал технические детали, чтобы обобщить алгоритм на произвольное количество измерений, а не только на два, но его первоначальные результаты не были обнадёживающими. Чтобы вычислить периодическую функцию во многих измерениях, квантовому компьютеру всё равно необходимо перемножить множество чисел. Каждое число не нужно было бы умножать столько раз, как в одномерном случае, но было бы больше различных чисел для умножения. В этом нет никакого выигрыша.
«Вы думаете: «Отлично, я только что сделал всё в больших измерениях, и время работы точно такое же, как у Шора», — говорит Регев. «На какое-то время я застрял на этом». Затем он понял, что можно обойти эту проблему, изменив порядок умножения. Вместо того чтобы постоянно привязывать числа к одному результату, который в ходе квантовых вычислений постепенно увеличивался, он начал с пар маленьких чисел, перемножил полученные результаты вместе и продолжил вычисления. Общее количество умножений не сильно изменилось, но теперь почти все они включают относительно небольшие числа, что ускоряет вычисления.
«Это имеет решающее значение», — сказал Винод Вайкунтанатан, криптограф из Массачусетского технологического института.
Поначалу казалось, что Регев просто заменил одну проблему на другую. Он ускорил квантовое вычисление периодической функции, увеличив число измерений, но последующие классические вычисления, необходимые для извлечения периода, теперь были похожи на определение местоположения ближайшей точки решётки в многомерном пространстве — задача, которую многие считали сложной. Аналогия с решётчатой криптографией, которая мотивировала его новый подход, казалось, обрекала его на провал.
Одним холодным мартовским утром перед поездкой на семинар в Принстонский университет Регев понял, что ждет коллегу, с которым вместе ездил на машине. «Я приехал рано, а он опоздал, чтобы забрать машину», — сказал Регев. Пока он сидел и ждал, к нему внезапно пришло озарение. «Это тот момент, когда всё встало на свои места, но понимание заняло какое-то время».
Всё сводилось к правильному количеству измерений. Когда размерность решётки была слишком мала, его алгоритм не мог в полной мере воспользоваться преимуществами ускорения за счет умножения меньших чисел. Когда она была слишком высокой, квантовые вычисления выполнялись быстро, но классическая часть требовала решения непомерно сложной решёточной задачи. Регев с самого начала знал, что для того, чтобы иметь хоть какой-то шанс на успех, ему придётся работать где-то посередине, но не было ясно, существует ли золотая середина. Тем мартовским утром он понял, как можно настроить его алгоритм, чтобы он быстро работал в нескольких десятках измерений.
Начертанные на песке
Улучшение было большим. Число элементарных логических шагов в квантовой части алгоритма Регева пропорционально n1.5 при факторизации n-битного числа, а не n2, как в алгоритме Шора. Алгоритм повторяет эту квантовую часть несколько десятков раз и объединяет результаты для построения многомерной решетки, из которой он может вывести период и факторизовать число. Таким образом, алгоритм в целом, возможно, не будет работать быстрее, но ускорение квантовой части за счет уменьшения количества необходимых шагов может облегчить его применение на практике.
Конечно, время, необходимое для запуска квантового алгоритма, — лишь одно из нескольких условий. Не менее важно и требуемое количество кубитов, которое аналогично памяти, нужной для хранения промежуточных значений во время обычных классических вычислений. Количество кубитов, которое требуется алгоритму Шора для факторизации n-битного числа, пропорционально n, тогда как алгоритм Регева в его исходной форме требует количества кубитов, пропорционального n1.5 — большая разница для 2048-битных чисел.
В классических вычислениях скорость обычно является более важным фактором, чем память, поскольку классические биты чрезвычайно надежны: вы можете сохранить файл на своем компьютере и не беспокоиться о его случайном изменении, когда вы откроете его снова. Исследователям квантовых вычислений не всегда так везёт.
«Наши кубиты постоянно пытаются развалиться, и мы хотим не дать им развалиться», — сказал Гидни. «Похоже на то, как будто ты пытаешься писать на песке, а ветер уносит его». Это означает, что дополнительные кубиты, необходимые для алгоритма Регева, могут быть серьезным недостатком.
Но статья Регева — это ещё не конец истории. Две недели назад Вайкунтанатан и его аспирант Сейун Рагаван нашли способ сократить использование памяти алгоритмом. Их вариант алгоритма Регева, как и оригинальный алгоритм Шора, требует количества кубитов, пропорционального n, а не n1.5.Экеро написал в электронном письме, что эта работа «намного приближает нас к реализации, которая будет более эффективной на практике».
Более общий урок из нового алгоритма Регева, помимо последствий для факторизации, заключается в том, что исследователи квантовых вычислений всегда должны быть открыты для сюрпризов, даже в проблемах, которые изучались десятилетиями.
«Этот вариант моего алгоритма не был обнаружен в течение 30 лет и появился совершенно неожиданно», — сказал Шор. «Вероятно, ещё предстоит найти множество иных квантовых алгоритмов».
Автор перевода @arielf
НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.
