Quantum advantage coexist with easy classical problems and limited security impact
Quantum Advantage has Few Complexity Implications
Computational ComplexityCryptography and Security
Summary
This paper studies how proving that a computer is truly quantum (a quantum advantage) does not necessarily mean that some classical computer problems become hard or cryptographic tasks become possible. The authors show that there can be examples where quantum proofs of quantumness exist even if famous classical problems can be solved easily. They also demonstrate situations where certain quantum state preparations are possible even when related complexity classes are equal. Their findings suggest that quantum advantages do not automatically imply new classical or quantum security features.
What this means in practice
- •For cryptography engineers: Avoid relying on proofs of quantumness as a basis for classical or quantum cryptographic security proofs that require oracle separation.
- •For quantum protocol designers: Recognize that oblivious state preparation protocols do not guarantee post-quantum cryptographic one-way functions through relativizing arguments.
A theory result. No direct application yet.
Authors
Eli Goldin, Alex Lombardi, Tomoyuki Morimae
Abstract
We consider the complexity implications of proofs of quantumness and (quantum verifier) oblivious state preparation. We show that both of these objects can coexist with the easiness of nondeterministic computation. That is, we give evidence that proofs of quantumness can exist when $\mathsf{P} = \mathsf{NP}$ and that (quantum verifier) oblivious state preparation can exist when $\mathsf{BQP} = \mathsf{QCMA}$. In particular, we give a classical oracle relative to which (1) $\mathsf{P}^\mathcal{O} = \mathsf{NP}^\mathcal{O}$ (2) $\mathsf{BQP}^\mathcal{O} = \mathsf{PSPACE}^\mathcal{O}$ (3) Proofs of quantumness exist. In particular, there exists a language in $\mathsf{IP}^\mathcal{O} \subseteq \mathsf{BQP}^\mathcal{O}$ which is hard on average against $\mathsf{P}^\mathcal{O}/poly$. We give a unitary oracle such that (1) $\mathsf{BQP}^\mathcal{O} = \mathsf{QCMA}^\mathcal{O}$ (2) Quantum verifier oblivious state preparation exists. These oracle separations directly imply a number of related consequences. For example, our first result implies that proofs of quantumness cannot be used to construct classical or quantum cryptography with a relativizing proof. Our second result implies that quantum computation/classical communication oblivious transfer cannot be used to construct post-quantum one-way functions with a relativizing proof.