Quantum computers could surpass classical systems, if certain cryptographic puzzles remain unsolvable by classical systems.
Researchers from Kyoto University have identified a precise link between quantum computing’s potential and the field of cryptography. In a breakthrough study, they have defined the conditions under which quantum computers outperforming classical systems can be achieved.
Quantum computing harnesses the principles of quantum physics, including superposition and interference, to perform computations far faster than traditional machines. While the idea of quantum advantage has been widely discussed, its underlying conditions remain uncertain. Previous theories outlined possible scenarios for quantum advantage, but did not establish when or why it must occur.
The Kyoto team addressed this by exploring a specific class of interactive proofs called inefficient-verifier proofs of quantumness. These protocols allow a classical verifier to test whether a remote system has genuine quantum computational power, without needing quantum hardware themselves.
Their findings reveal that the existence of such proofs relies on a cryptographic structure known as a one-way puzzle, a type of problem that is easy to verify but hard to solve without special information. This connection forms the backbone of a new theoretical framework that merges quantum computational capability with cryptographic security.
Crucially, the study shows that quantum advantage can only exist if certain cryptographic primitives are secure. If quantum advantage fails to emerge, it could indicate that many cryptographic methods, including classical and post-quantum ones, are potentially insecure.
This equivalence between cryptographic hardness and quantum computational power provides a foundational tool for both future experiments and theoretical research. It also sharpens the criteria for validating claims of quantum advantage.
