World's first proof that quantum advantage and cryptographic security are equivalent from a cryptographic perspective

A research group consisting of Doctoral Student Yuki Shirakawa and Associate Professor Tomoyuki Morimae at Kyoto University's Yukawa Institute for Theoretical Physics, and Senior Distinguished Researcher Takashi Yamakawa from NTT Social Informatics Laboratories (also Affiliate Associate Professor at the same institute) has proven the necessary and sufficient conditions for "quantum computational advantage"—the concept that quantum computers are faster than classical computers—from the new perspective of cryptography. This research result was presented at "STOC 2025," an international conference on theoretical computer science, on June 27.

It is expected that difficult problems that require enormous computational time on classical computers could potentially be solved at high speed by quantum computers (quantum advantage). However, this does not always exist. The research group believes that clear answers to the questions "under what conditions does quantum advantage exist?" and "what is necessary for it to exist?" are essential for understanding the performance of quantum computers and leveraging their capabilities.

Mathematically, when both the proposition "if A then B" and its converse "if B then A" hold simultaneously, A is a necessary and sufficient condition for B, and B is a necessary and sufficient condition for A. To demonstrate quantum computer advantage, both these necessary and sufficient conditions must be satisfied.

Previously, quantum advantage has been defined according to the problems to be solved, such as sampling problems and search problems, and its existence has been proven. However, these were merely sufficient conditions, and it was not clearly understood whether these conditions were truly the necessary conditions.

From this background, in this research, to make the theoretical foundation of quantum advantage more robust, the group tackled the fundamental problem of "what are the necessary and sufficient conditions for quantum advantage?" Specifically, they studied the security of a cryptographic function called "one-way puzzles" that has been proposed in the quantum cryptography field in recent years and the existence of quantum advantage, mathematically proving that both are equivalent.

This cryptography consists of puzzles created by quantum computers that cannot be solved by classical computers. Equivalence means that if the cryptographic function is secure, tasks demonstrating quantum advantage can be constructed, and if it exists, secure cryptographic functions can be constructed.

This achievement was realized by integrating techniques and concepts developed in quantum computational theory and cryptographic theory respectively, and proposing a new framework that connects two seemingly unrelated concepts: "quantum advantage" and "cryptographic security."

The group particularly focused on an interactive protocol called "inefficient-verifier proofs of quantumness (IV-PoQ)." This is a mechanism that allows a verifier without a quantum computer to interact with a prover who has a quantum computer and verify whether their counterpart truly possesses quantum computational capabilities.

The group mathematically proved that the necessary and sufficient conditions for the existence of this protocol match the security of the cryptographic function called "one-way puzzles," theoretically demonstrating that quantum advantage and cryptographic security are equivalent.

The research group states that the significance of this achievement lies not only in clarifying the necessary and sufficient conditions for quantum advantage, but also in the expectation that this close relationship existing between the quantum computational theory field and the cryptographic theory field will mutually affect both fields.

One point of significance is that future experimental demonstrations of and theoretical research on quantum advantage will be conducted on a more robust cryptographic theoretical foundation. Another is that this result means "if quantum advantage does not exist, the security of many cryptographic functions currently considered secure would collapse."

Notably, the security collapse would extend not only to quantum cryptography but also to cryptography on classical computers (currently widely used) and post-quantum cryptography (the widespread adoption of which is urgently needed), making this a very important implication for the information security field.

Journal Information
Publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
Title: Cryptographic Characterization of Quantum Advantage
DOI: 10.1145/3717823.3718133