Учёные раскрыли криптографический код, лежащий в основе квантового превосходства

Исследователи из Киотского университета обнаружили, что квантовое превосходство существует только при условии безопасности определённых криптографических задач. Эта неожиданная связь между квантовыми вычислениями и криптографией меняет наше понимание обеих областей и может поставить под угрозу криптосистемы, считавшиеся безопасными. Фото: Shutterstock

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

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

Чтобы прояснить этот вопрос, команда учёных из Киотского университета исследовала необходимые и достаточные условия квантового превосходства, объединив методы квантовых вычислений и криптографии — науки о защите информации.

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

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

«Мы смогли определить необходимые и достаточные условия квантового превосходства, доказав эквивалентность между его существованием и безопасностью определённых квантовых криптографических примитивов», — поясняет ведущий автор Юки Ширакава.

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

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

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

Команда ожидает, что дальнейшие исследования расширят характеристику других типов квантового превосходства и приведут к более общей теоретической модели.

Источники: sciencedaily.com, материалы предоставлены Киотским университетом.

Томоюки Моримаэ, Юки Ширакава, Такаши Ямакава. Криптографическая характеристика квантового превосходства. Труды 57-й ежегодной ACM-симпозиума по теории вычислений, 15 июня 2025. DOI: 10.1145/3717823.3718133