arXiv preprint ·
Quantum Advantage has Few Complexity Implications
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Quantum Physics
Semidirect sums of tensors and the matrix multiplication exponent
Towards the Query Complexity of Sampling under Strong Log-Concavity and Log-Sobolev Inequalities
State Evolution and Universality of Iterated Linear Programs for the Binary Perceptron
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product Bounds
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion Constraints
Get the few papers worth your time in Quantum Physics every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.