Узнайте что такое алгоритм Шора, который доказывает, что квантовые вычисления чрезвычайно мощнее классических способов.
Каждый, кто заинтересован в изучении квантовых вычислений, не мог не слышать об алгоритме факторизации Шора. Это один из немногих хрестоматийных квантовых алгоритмов, что означает, что он остается одним из редких примеров квантового вычислительного превосходства.
Другими словами, алгоритм может вычислить что-то квантово, что труднее и медленнее вычисляется классически. Фактически, этот конкретный алгоритм может вычислить то, что по всем практическим соображениям и целям, насколько мы знаем, невозможно сделать классически в любом полезном масштабе.
Что такое квантовые компьютеры? Как скоро они будут у нас?
Что такое алгоритм Шора?
Алгоритм факторизации Шора выделяется среди других алгоритмов. Для этого есть две причины.
Во-первых, он может факторизовать числа экспоненциально быстрее, чем любой известный классический алгоритм.
Хотя все хрестоматийные квантовые алгоритмы имеют вычислительные преимущества, алгоритм Шора является одним из немногих элитных алгоритмов с экспоненциальным ускорением, а также одним из немногих элитных алгоритмов, имеющих практическое применение.
Самое важное то, что его потенциал факторизации чисел за разумные временные рамки напрямую угрожает самым популярным криптосистемам в мире.
Значение этого невозможно переоценить. Шифрование RSA, защищающее финансовые транзакции по всему миру, работает путем перемножения двух огромных простых чисел.
Простые числа нельзя разделить на целые числа, кроме самих себя и числа один. Их произведения настолько велики, что не существует ни одного известного способа эффективно разложить их на множители классическим способом.
Подумайте о факторизации как об обратном умножении, определяя используемые простые числа, что позволяет несанкционированно расшифровывать интернет-сообщения.
Что такое закон Мура: двигатель технологического прогресса
В этой статье блога обсуждаемый алгоритм иногда упоминается как алгоритм факторизации Шора, а не просто алгоритм Шора, поскольку существует также квантовый код коррекции ошибок, носящий имя Шора, с одноименным названием, который был открыт в результате публикации алгоритма факторизации. Для этой статьи, чтобы избежать двусмысленности, знайте, что алгоритм Шора и алгоритм факторизации Шора относятся к одному и тому же алгоритму.
Что такое алгоритм Шора в квантовых вычислениях?
Алгоритм факторизации Шора вынес квантовые вычисления на внимание общественности. Его угрозы заставили национальные правительства, целые отрасли и широкую общественность обратить внимание на эту относительно новую технологию.
Десятилетия спустя этот алгоритм остается эталоном квантовых алгоритмов. В течение длительного времени прилагаются значительные усилия для защиты глобальных финансовых систем, национальной безопасности и всех других сфер использования криптографии, если уж на то пошло.
Существует очевидная геополитическая опасность того, что кто-либо, особенно государственный субъект, разовьет достаточную квантовую вычислительную мощность для использования алгоритма Шора до того, как квантово-безопасные криптосистемы смогут быть повсеместно развернуты.
Почти так же важно, что алгоритм Шора привел к современным инвестициям миллиардов долларов в квантовые технологии, включая квантовые вычисления. Спустя три десятилетия после открытия алгоритма продолжается поиск других практических приложений, для которых можно реализовать экспоненциальное ускорение.
Если по крайней мере один алгоритм может достичь этого, то, по мнению ученых, должны быть и другие. После всех этих лет наиболее вероятные кандидаты черпают идеи из алгоритма Шора.
Как работает алгоритм Шора?
Факторизация чисел по алгоритму Шора начинается с выбора случайного целого числа, меньшего, чем число, которое нужно факторизовать. Затем классически рассчитанный наибольший общий делитель (НОД) этих двух чисел, случайного и искомого, используется для определения того, не было ли уже случайно учтено искомое число. Для меньших чисел это возможно.
Для больших чисел может потребоваться суперкомпьютер. А для чисел, которые считаются криптографически защищенными, понадобится квантовый компьютер.
Роль квантового компьютера заключается в том, чтобы определить период числа, которое нужно факторизовать. Результаты вычислений определяют, нужно ли проверять новое случайное целое число или уже найдены искомые факторы. После того, как целевое число было учтено, роль алгоритма Шора завершается
На высоком уровне весь этот процесс может показаться довольно простым. И на высоком уровне это так и есть. Однако, если подробно объяснить каждый шаг, то его можно разбить на серию лекций. Реализация алгоритма может быть выполнена после завершения краткого руководства, но полное понимание алгоритма может занять много часов обучения.
Как реализуется алгоритм Шора?
Алгоритм Шора не прост в реализации. Прежде всего, алгоритм состоит из трех основных компонентов: один использует классические вычисления, один использует квантовые вычисления и еще один использует классические вычисления. В целом, алгоритм имеет шесть важных шагов, как описано выше.
Однако, добавляя к этой сложности, квантовый компонент алгоритма факторинга Шора имеет четыре подкомпонента, каждый из которых сам по себе мог бы иметь целую статью для объяснения. И хотя два из этих квантовых подкомпонентов относительно легко объяснить, другие два являются невероятно важными квантовыми подпрограммами. На самом деле, это, пожалуй, две наиболее значимые квантовые подпрограммы.
Один из самых важных квантовых подкомпонентов называется квантовой оценкой фазы (QPE). Важно то, что она выполняет модулярную арифметику, необходимую для нахождения периода числа, которое нужно разложить на множители. Другими словами, именно отсюда происходит факторинговая мощность алгоритма Шора.
Другой ключевой квантовый подкомпонент называется обратным квантовым преобразованием Фурье (iQFT). Проще говоря, iQFT берет непосредственно предшествующий ему квантовый результат модулярной арифметики и преобразует его в классическую информацию, которая может быть получена из квантовой схемы с помощью процесса, известного как измерение.
В общем, алгоритм факторизации Шора начинается с нескольких классических шагов. Затем квантовый компонент находит период числа, которое должно быть разложено на множители. Это делается с помощью квантовой модулярной арифметики, результат которой преобразуется из квантовой информации в классическую, чтобы ее можно было использовать. И, наконец, есть еще несколько классических шагов. Если ответ не найден, и число, соответственно, нельзя разложить на множители, алгоритм полностью корректируется и повторяется.
Сколько кубитов требуется для алгоритма Шора?
Чтобы ответить на этот вопрос, необходимо различать физические и логические кубиты. Все современные кубиты – это физические кубиты. Они чрезвычайно “зашумлены”, то есть подвержены ошибкам. Результаты квантовых вычислений любой значимости не позволяют отличить правильные ответы от неправильных. Каждое возможное решение имеет одинаковую вероятность быть правильным, что равнозначно отсутствию ответов вообще.
Именно здесь в игру вступают логические кубиты. Физические кубиты должны быть соединены и структурированы таким образом, чтобы они вместе обеспечивали достаточную коррекцию ошибок друг для друга, чтобы считаться “отказоустойчивыми” вместе. В этот момент эти коллективы кубитов становятся известными как “логические кубиты”, или иногда как “совершенные кубиты”.
Эти логические кубиты являются абстракциями. Сегодня квантовая схема с пятью кубитами представляет пять очень шумных, подверженных ошибкам физических кубитов. Разработчики квантовых алгоритмов ближайшего будущего захотят, чтобы эти пять кубитов представляли логические, отказоустойчивые, безошибочные кубиты.
Оценки относительно того, сколько физических кубитов понадобится для представления одного логического кубита, различаются, но разумным числом для работы является 1000. Большинство считает, что квантовому компьютеру понадобится около 1000 физических кубитов для представления одного логического кубита.
Чтобы оценить, насколько это сложно, самый большой квантовый компьютер на сегодня имеет только 127 физических кубитов. И хотя IBM намерена представить 1000-кубитное устройство к следующему году, это все еще только 1000 физических кубитов. До создания первого логического кубита остается еще много работы.
Оценки количества кубитов, необходимых для алгоритма факторинга Шора, значительно различаются. Во-первых, как уже отмечалось, необходимо различать оценки для логических кубитов и оценки для физических кубитов. В зависимости от целей исследователя, количество необходимых кубитов можно уменьшить, пожертвовав временем выполнения и глубиной схемы.
С другой стороны, количество кубитов можно значительно увеличить, уменьшив время выполнения и глубину схемы. Различия заключаются в том, что меньшее количество кубитов станет доступным быстрее, тогда как самое быстрое время выполнения будет наиболее выгодным. Ниже приведены несколько оценок.
В статье Дэвида Бекмана, Амалавояла Н. Чари, Шрикришны Девабхактуни и Джона Прескилла “Эффективные сети для квантового факторинга” от 1 августа 1996 года авторы подсчитали, что факторизация K-битного числа займет K3 времени и потребует 5K+1 логических кубитов.
Таким образом, факторизация 2,048-битного числа, означающая взлом RSA-шифрования, займет 8,6 миллиардов времени и потребует 10,241 логических кубитов, или примерно 10 миллионов физических кубитов. К сожалению, неясно, сколько времени займет 8,6 миллиардов, поскольку разные технологии работы с кубитами работают с разной скоростью.
Затем в статье Стефана Борегара “Схема для алгоритма Шора с использованием 2n+3 кубитов” от 21 февраля 2003 года авторы подсчитали, что для факторизации K-битного числа понадобится 2n+3 логических кубитов.
Таким образом, для факторизации 2048-битного числа понадобится всего 4099 логических кубитов, или примерно 4 миллиона физических кубитов. Опять же, сегодня не существует нулевых логических кубитов. Однако эта статья все же приблизила алгоритм факторизации Шора к реализации.
Затем в книге Архимеда Павлидиса и Димитриса Гизопулоса “Быстрая архитектура квантового модулярного возведения в степень для алгоритма факторизации Шора” (pp0649-0682), опубликованной в мае 2014 года, авторы предложили реализацию 9n+2, добавив значительное количество кубитов для уменьшения глубины схемы. Для раскрытия 2048-битного RSA-шифрования требуется 18 434 логических кубитов или примерно 18 миллионов физических кубитов.
Одной из причин минимизации глубины схемы является то, что со временем кубиты теряют “связность”. Чем дольше выполняется схема, что частично определяется глубиной схемы, тем больше шума может просочиться в систему и тем больше ошибок может появиться в результатах. Даже сегодня одним из способов уменьшить количество ошибок является минимизация глубины кода.
Совсем недавно, 13 апреля 2021 года, в статье под названием “Как за 8 часов вычислить 2048-битное целое число RSA, используя 20 миллионов зашумленных кубитов”, авторы Крейг Гидни и Мартин Экер подсчитали, что для взлома RSA-шифрования требуется примерно 20 000 логических кубитов, или примерно 20 миллионов физических кубитов. Авторы идут еще дальше и оценивают время выполнения для своей конфигурации всего в восемь часов.
Сравните это с оценкой времени, необходимого самым мощным в мире суперкомпьютерам для взлома шифрования RSA, значительно превышающего время жизни человека, и мощность алгоритма Шору становится понятной. Для других оценок количества кубитов для алгоритма Шора, обратитесь к ссылкам на эту статью.
Опять же, время работы алгоритма Шора обратно пропорционально количеству доступных логических кубитов. Оно также зависит от используемой технологии кубитов, поскольку разные квантовые компьютеры выполняют операции с очень разной скоростью.
Чем меньше кубитов требуется, тем дольше будет работать алгоритм, но тем быстрее современные криптосистемы становятся устаревшими. И наоборот, чем больше кубитов, тем быстрее современные криптосистемы будут взломаны. Но, к счастью, эти дни еще далеки.
Как запустить алгоритм Шора?
Никак.
Самое большое число, которое на сегодняшний день удалось вычислить с помощью алгоритма Шора – 21. А наименьшее возможное число, которое можно вычислить с помощью алгоритма – 15. Это очень узкий диапазон по двум причинам. Во-первых, алгоритм Шора требует большого количества кубитов, как было сказано выше, а большого количества кубитов не существует.
Во-вторых, современные кубиты являются “зашумленными”, что означает, что они чрезвычайно подвержены ошибкам. Глубина схемы, необходимая алгоритму, дает результаты с таким количеством ошибок, что невозможно отличить правильные решения от неправильных.
Другими словами, RSA и другие потенциально уязвимые криптосистемы безопасны. Пока что. NIST продолжает работать над выбором пост-квантового стандарта, иначе известного как “квантово-безопасный” стандарт, который, как мы надеемся, будет широко внедрен задолго до того, как появится достаточно отказоустойчивых кубитов, чтобы реализовать эту угрозу.
Несмотря на длительный период времени и работу, проводимую для уменьшения риска, алгоритм факторизации Шора остается таким же хорошим способом повышения осведомленности о квантовых вычислениях сегодня, как и тогда, когда он был впервые открыт.
Руководители во всех отраслях должны беспокоиться о потенциальных рисках для конфиденциальных коммуникаций и данных, и этот риск является настоящим. Надеемся, что в процессе они узнают о десятках других потенциальных вариантов использования квантовых вычислений, которые когда-то могут принести значительную пользу их предприятиям.
Источник: https://www.classiq.io
