Квантовый взлом подешевел на два порядка: почему алгоритм Шора реализуем уже в этом десятилетии

Каждый раз, когда вы открываете банковское приложение, отправляете сообщение в мессенджере или обновляете операционную систему, вашу безопасность охраняют алгоритмы шифрования RSA и криптография на эллиптических кривых (ECC). Их надежность базируется на простом математическом принципе: классическому процессору потребовались бы тысячи лет для подбора нужного ключа. Однако квантовый алгоритм Шора, математически описанный еще в 1994 году, способен решить эти задачи за считанные дни.

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

Новая работа исследователей из Калифорнийского технологического института и компании Oratomic доказала, что благодаря переходу на архитектуру нейтральных атомов и новые методы кодирования, требования к аппаратному обеспечению падают на два порядка. Для взлома самых распространенных криптографических стандартов теперь требуется не двадцать миллионов, а от 10 000 до 100 000 кубитов.

Чтобы понять, как физики добились такого радикального сокращения ресурсов, необходимо разобраться в механике квантовых ошибок и способах их исправления.

Проблема масштабирования и аппаратная избыточность

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

Для решения этой проблемы инженеры используют алгоритмы квантовой коррекции ошибок. Физики не полагаются на один нестабильный носитель информации. Они берут сотни или тысячи физических кубитов и математически связывают их в один «логический» кубит. Если часть физических носителей даст сбой, система восстановит данные по состояниям остальных.

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

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

Нелокальная связность: физика движущихся кубитов

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

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

Главный прорыв этой технологии заключается в динамическом изменении конфигурации. Оптические пинцеты могут перемещать атомы прямо во время вычислений. Это дает системе фундаментальное свойство — нелокальную связность.

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

Коды qLDPC и четыре зоны вычислений

Отказ от плоской сетки в пользу динамических перемещений позволяет использовать квантовые коды с малой плотностью проверок на четность (qLDPC). Эти коды выстраивают не двумерную плоскость, а сложный многомерный граф связей.

В архитектуре qLDPC проверки на ошибки пересекаются гораздо эффективнее. Благодаря этому эффективность кодирования возрастает в сотни раз. Если поверхностные коды имеют эффективность около 0,1%, то предложенные в статье коды qLDPC достигают показателя в 30%. В одном из блоков ученые смогли разместить 1224 защищенных логических кубита, потратив на это всего 4350 физических атомов.

Чтобы управлять таким массивом, исследователи спроектировали архитектуру, разделяющую квантовый компьютер на четыре специализированные зоны:

1. Зона памяти. Здесь атомы плотно упакованы и хранят квантовую информацию, пока она не требуется для вычислений.
2. Процессорная зона. Сюда лазеры переносят атомы для выполнения базовых логических вентилей.
3. Ресурсная зона (фабрика состояний). Для универсальных квантовых вычислений недостаточно простых операций. Требуются так называемые неклиффордовы вентили. Их очень сложно защитить от ошибок напрямую. Поэтому в ресурсной зоне система постоянно генерирует особые высокоточные «магические состояния» (состояния |CCZ⟩). Как только процессорной зоне требуется выполнить сложную операцию, она просто потребляет заранее подготовленное магическое состояние.
4. Операционная зона. Здесь расположены вспомогательные кубиты. Система измеряет их, чтобы выявить ошибки в рабочих кубитах, не разрушая при этом саму логическую информацию.

Новые сроки взлома криптографии

Объединив динамику нейтральных атомов, плотность кодов qLDPC и оптимизированные логические схемы, физики провели расчеты для взлома реальных криптографических стандартов.

Задача вычисления дискретного логарифма на эллиптической кривой (стандарт ECC-256, защищающий большинство современных протоколов передачи данных) оказалась наиболее уязвимой. Архитектура позволяет взломать этот ключ, используя от 10 000 до 26 000 физических кубитов. Благодаря возможности параллельного выполнения сложных вентилей, процесс взлома займет около 10 дней.

Стандарт RSA с ключом 2048 бит требует большего объема вычислений из-за архитектурных особенностей самих математических сумматоров. Тем не менее, и здесь требования резко снизились. Факторизация RSA-2048 потребует около 102 000 физических кубитов и примерно 97 дней непрерывных вычислений.

Интересно, что тактовая частота квантовых процессоров на нейтральных атомах значительно ниже, чем у сверхпроводников. Цикл измерения занимает около 1 миллисекунды, тогда как в сверхпроводящих чипах счет идет на микросекунды. Однако авторы доказали, что низкая скорость базового цикла полностью нивелируется способностью системы выполнять множество логических операций параллельно по всему массиву.

Переход к новой реальности

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

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

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

Источник: arXiv