Квантовый Прорыв: Почему Число 21 Сложнее 15?

За кулисами квантового прорыва: Почему число 21 - это не 15

Нью-Йорк, 9 октября 2025 - В фоне постоянных заголовков о достижениях в квантовых вычислениях, обещающих революционные перемены, часто упускается из виду базовый парадокс: хотя число 15 уже успешно раскладывали на множители в 2001 году, квантовые компьютеры до сих пор не смогли повторить этот трюк с числом 21. Этот, казалось бы, незначительный скачок от 15 к 21 на деле демонстрирует не только огромные инженерные трудности, но и нюансы алгоритма Шора, лежащего в основе большинства заявленных успехов.

Как отмечает исследователь Крейг Гидни в своём разборе «Почему квантовые компьютеры до сих пор не разложили 21 на множители?», проблема кроется не в отсутствии мощности, а в архитектурной неэффективности, вызванной математическими свойствами числа. Для разложения 21 требуется около 2405 квантовых гейтов, в то время как для 15 хватило лишь 21 гейта. Такое увеличение сложности в 115 раз подчёркивает разрыв между демонстрационными экспериментами и реальными вычислительными задачами.

Алгоритм Шора: От «чуда» к реальности

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

Основная доля стоимости квантового алгоритма факторизации уходит на серию условных модульных умножений. Для разложения n-битного числа N алгоритм Шора выполняет условное умножение аккумулятора на m_k = g^{2^k} mod N для каждого k < 2n, где g - случайно выбранное значение, взаимно простое с N. Именно здесь возникает «бутылочное горлышко».

Почему 15 проще, чем 21: Три математических фактора

Существует три ключевых причины, из-за которых факторизация числа 15 оказалась существенно дешевле, чем 21, с точки зрения требуемого количества гейтов:

1. Умножения на 1: При работе с 15 и выборе g = 2 большую часть констант, умножаемых далее, составляет 1 (например, [2, 4, 1, 1, 1, 1, 1, 1]). Умножения на 1 фактически не требуют никаких операций на квантовом процессоре, что значительно упрощает схему. Для 21 (при g = 2) последовательность выглядит иначе: [2, 4, 16, 4, 16, 4, 16, 4, 16, 4] - здесь нет умножений на 1, что в четыре раза повышает базовую стоимость.

2. Эффект «первое бесплатно»: Первое условное умножение в алгоритме Шора почти бесплатно, если его вход заранее равен 1. Для 15 это сокращает приблизительно 50 % умножений, тогда как для 21, где операций больше, тот же эффект снижает общие затраты лишь на 10 %.

3. Особая структура 15: Число 15 обладает уникальным свойством: 15 = 2⁴ - 1. Это позволяет реализовать умножение на 2 по модулю 15 с помощью простого циклического сдвига. Умножение на 4, являющееся двойным умножением на 2, также можно выполнить аналогично. Такое свойство отсутствует у 21, что значительно усложняет соответствующие операции и заставляет использовать лишь два вентиля CSWAP. Напротив, умножение на 4 или 16 по модулю 21 требует более сложных схем с до 41 вентилем Тоффоли, что приводит к увеличению стоимости в 20-кратном размере.

Все перечисленные факторы вместе объясняют сто-кратный рост сложности факторизации 21 по сравнению с 15, что, по мнению Гидни, является главной причиной того, что до сих пор ни один квантовый компьютер не справился с этой задачей.

Иллюзии прорыва и «квантовый читинг»

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

Так, в статье 2013 года «Oversimplifying quantum factoring» Джон Смолин, Грэм Смит и Александр Варго упрекают демонстрации, которые по сути являются аналогом «подбрасывания монеты», поскольку заранее задают параметры вычислений так, чтобы получить известный результат. Скотт Ааронсон, признанный квантовый информатик, также предостерегает от подобных «мотт-и-бейли» аргументов, когда сложность проблемы игнорируется в угоду псевдо-результатов, получаемых с помощью вариационных или упрощённых техник.

Промежуточные устройства и путь вперёд

Первая успешная факторизация 15 была выполнена в 2001 году командой IBM на квантовом компьютере, основанном на ядерном магнитном резонансе (ЯМР). Если эту реализацию не учитывать, то, по мнению экспертов, следующей значимой вехой в реальном выполнении умножений стал эксперимент 2015 года с ионными ловушками.

Современные квантовые машины, именуемые NISQ (Noisy Intermediate-Scale Quantum) устройства, страдают от высокого уровня ошибок и ограниченного числа кубитов. Это значит, что для практического применения алгоритма Шора к большим числам понадобится не только существенное увеличение количества кубитов, но и внедрение надёжной коррекции квантовых ошибок. Оценки показывают, что для факторизации RSA-чисел в 2048 бит за приемлемое время потребуется порядка 20 миллионов шумных кубитов.

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