Researchers use cryptography to gain insights into the mechanisms behind quantum speed-ups.
Quantum computing is widely regarded by experts as the next major leap in computer technology. Unlike traditional computers, which process information in binary (0s and 1s), quantum computers make use of unique principles from quantum physics. These include phenomena like superposition and interference, which could enable quantum machines to tackle certain problems far more efficiently than even the most advanced classical systems.
When a quantum computer successfully handles a task that would be practically impossible for current computers, this achievement is referred to as quantum advantage. However, this advantage does not apply to all types of problems, which has led scientists to explore the precise conditions under which it can actually be achieved. While earlier research has outlined several conditions that might allow for quantum advantage, it has remained unclear whether those conditions are truly essential.
To help clarify this, researchers at Kyoto University launched a study aimed at identifying both the necessary and sufficient conditions for achieving quantum advantage. Their method draws on tools from both quantum computing and cryptography (the science of securely encoding information), creating a bridge between two fields that are often viewed separately.
Connecting Cryptography and Quantum Proofs
Specifically, the team focused on interactive protocols called inefficient-verifier proofs of quantumness, which allow a verifier without a quantum computer to interact with a quantum prover and verify that it indeed possesses quantum computational power. In their study, the team demonstrated that the existence of these proofs depends on the existence of a certain cryptographic primitive called a one-way puzzle.
By integrating these methods, the team introduced a novel framework uniting the seemingly unrelated concepts of quantum advantage and cryptographic security. As a result, the team was able to completely characterize quantum advantage for the first time.
“We were able to identify the necessary and sufficient conditions for quantum advantage by proving an equivalence between the existence of quantum advantage and the security of certain quantum cryptographic primitives,” says corresponding author Yuki Shirakawa.
The results imply that when quantum advantage does not exist, then the security of almost all cryptographic primitives — previously believed to be secure — is broken. Importantly, these primitives are not limited to quantum cryptography but also include widely-used conventional cryptographic primitives as well as post-quantum ones that are rapidly evolving.
Implications for Future Research and Security
The established equivalence between quantum computing and cryptography also provides a stronger cryptographic foundation for future experimental demonstrations of quantum advantage, as well as for ongoing theoretical investigations in the field.
“Quantum advantage is a highly expected and actively studied concept, but it is still not fully understood. Our study represents a significant step toward a deeper understanding of this property,” says Shirakawa.
The team expects that future research will extend characterization to other types of quantum advantage and lead to a more general theoretical framework.
Reference: “Cryptographic Characterization of Quantum Advantage” by Tomoyuki Morimae, Yuki Shirakawa and Takashi Yamakawa, 15 June 2025, STOC ’25: Proceedings of the 57th Annual ACM Symposium on Theory of Computing.
DOI: 10.1145/3717823.3718133
Never miss a breakthrough: Join the SciTechDaily newsletter.
Follow us on Google and Google News.
1 Comment
Ok noted