Новое исследование связывает мощность квантовых вычислений с безопасностью криптографических систем

Характеристика квантового преимущества. Автор: (KyotoU / Shirakawa lab)

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

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

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

Результаты работы были представлены на 57-м ежегодном симпозиуме ACM по теории вычислений, проходившем в Праге (Чехия) с 23 по 27 июня.

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

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

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

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

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

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

Дополнительная информация: Cryptographic Characterization of Quantum Advantage. Proceedings of the 57th Annual ACM Symposium on Theory of Computing, (2025). DOI: 10.1145/3717823.3718133

Источник: Kyoto University