Hacker News Digest

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

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

• Обсуждение в основном вращается вокруг вопроса, действительно ли достигнуто "квантовое превосходство" и что именно это означает, с учетом того, что квантовые компьютеры пока не могут решать практические задачи, а эксперименты часто оказываются переоцененными из-за несоответствия между заявлением и реальностью.
• Участники обсуждения подчеркивают, что квантовые компьютеры пока не могут угрожать Bitcoin или другим криптовалютам, потому что квантовые компьютеры еще не могут взломать криптографию, а также то, что криптовалюты в целом могут адаптироваться к будущим угрозам.
• Также обсуждается, что заявления о "квантовом превосходстве" часто оказываются преувеличенными, и что квантовые компьютеры пока не могут решать практические задачи.
• Участники также обсуждают, что квантовые компьютеры могут быть использованы для моделирования квантовой физики, что является их естественной задачей, и что это может быть полезно для науки и промышленности.
• В целом, участники обсуждения скептически настроены к заявлениям о "квантовом превосходстве", но в то же время признают, что квантовые компьютеры могут быть полезны для науки и промышленности, если они будут развиваться дальше.

Почему квантовые компьютеры всё ещё не разложили 21 на множители?

В 2001 году удалось разложить 15, но к 2025-му 21 остаётся «недоступным». Это не из-за отсутствия прогресса, а из-за взрывного роста сложности схемы.

• Схема для 15 требует всего 21 запутывающий двух-кубитный гейт (6 CNOT/CPHASE + 2 Toffoli, каждый из которых эквивалентен 6 CNOT).
• Схема для 21 содержит 191 CNOT и 369 Toffoli, то есть ≈ 2405 запутывающих гейтов — в 115 раз больше.

Три причины такой разницы:

1. Большинство констант при 15 равны 1, поэтому умножения «пропускаются».
2. Первое умножение почти бесплатно, так как аккумулятор известен.
3. Оставшееся умножение на 4 по модулю 15 сводится к двум CSWAP.

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

• Квантовые компьютеры пока не факторизуют даже 21 без «подсказок»; эксперименты с 15 обошлись лишь потому, что задача свелась к сдвигам.
• Для RSA-2048 оценивается ≈ 7 млрд Toffoli-гейтов и миллионы логических кубитов с коррекцией ошибок; RSA-1024 всё ещё вне досягаемости.
• Реальные препятствия — экспоненциальный рост шума и количества физических кубитов, а не просто масштабирование схемы.
• Основной практический путь — квантовая химия и симуляция, а не взлом криптографии; «пост-квантовые» алгоритмы уже снижают мотивацию строить «крипто-разрушители».
• Общий вывод: полезные квантовые вычисления в XXI веке возможны, но факторизация крупных RSA-ключей остаётся гипотетической.