Why haven't quantum computers factored 21 yet?
Почему квантовые компьютеры всё ещё не разложили 21 на множители?
В 2001 году удалось разложить 15, но к 2025-му 21 остаётся «недоступным». Это не из-за отсутствия прогресса, а из-за взрывного роста сложности схемы.
- Схема для 15 требует всего 21 запутывающий двух-кубитный гейт (6 CNOT/CPHASE + 2 Toffoli, каждый из которых эквивалентен 6 CNOT).
- Схема для 21 содержит 191 CNOT и 369 Toffoli, то есть ≈ 2405 запутывающих гейтов — в 115 раз больше.
Три причины такой разницы:
- Большинство констант при 15 равны 1, поэтому умножения «пропускаются».
- Первое умножение почти бесплатно, так как аккумулятор известен.
- Оставшееся умножение на 4 по модулю 15 сводится к двум CSWAP.
Для 21 все восемь умножений нужны, и каждое требует полноценного модульного умножения. Даже после агрессивной оптимизации схема остаётся на два порядка дороже.