Decoding quantum advantage

Kyoto, Japan -- Experts say quantum computing is the future of computers. Unlike conventional computers, quantum computers leverage the properties of quantum physics such as superposition and interference, theoretically outperforming current equipment to an exponential degree.

When a quantum computer is able to solve a problem unfeasible for current technologies, this is called the quantum advantage. However, this edge is not guaranteed for all calculations, raising fundamental questions regarding the conditions under which such an advantage exists. While previous studies have proposed various sufficient conditions for quantum advantage, the necessity of these conditions has remained unclear.

Motivated by this uncertainty, a team of researchers at Kyoto University has endeavored to understand the necessary and sufficient conditions for quantum advantage, using an approach combining techniques from quantum computing and cryptography, the science of coding information securely.

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.

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.