Quantum Advantage has Few Complexity Implications

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 P = NP and that (quantum verifier) oblivious state preparation can exist when BQP = QCMA. In particular, we give a classical oracle relative to which (1) PO = NPO (2) BQPO = PSPACEO (3) Proofs of quantumness exist. In particular, there exists a language in IPO ⊆ BQPO which is hard on average against PO/poly. We give a unitary oracle such that (1) BQPO = QCMAO (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.

Constant-round quantum advantage in communication complexity for total functions
Atsuya Hasegawa, François Le Gall
arXiv12 Oct 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
An Exponential Sample-Complexity Advantage for Coherent Quantum Inference
Zhaoyi Li, Elias Theil, Aram W. Harrow +1
arXiv29 Sep 2026PreprintarXiv licenceFull textQuantum physics & quantum informationarXiv
Quantum Advantage of Permutation-Invariant Functions in Communication Complexity
Yunqi Huang, Zekun Ye
arXiv4 Oct 2026PreprintCC BY 4.0Full textQuantum physics & quantum informationarXiv
Advantage of Sample Complexity in Quantum PAC Learning Requires Inverse Access to State-Preparation Unitaries
Natsuto Isogai, Satoshi Yoshida, Mio Murao
arXiv27 Oct 2026PreprintarXiv licenceFull textStatistics Quantum physics & quantum informationarXiv
Exponential advantage in continuous-variable quantum state learning
Eugen Coroi, Changhun Oh
npj Quantum Information12 Oct 2026Peer-reviewedCC BY-NC-ND 4.0Full text1 citedQuantum physics & quantum informationCrossref

Cite

BibTeX RIS

BibTeX

@misc{goldin2026quantum,
  title = {{Quantum Advantage has Few Complexity Implications}},
  author = {Eli Goldin and Alex Lombardi and Tomoyuki Morimae},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.05303},
  eprint = {2611.05303},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.05303},
  note = {CC BY-SA 4.0},
}

RIS

TY  - UNPB
TI  - Quantum Advantage has Few Complexity Implications
AU  - Eli Goldin
AU  - Alex Lombardi
AU  - Tomoyuki Morimae
PY  - 2026
DA  - 2026/11/03
PB  - arXiv
DO  - 10.48550/arxiv.2611.05303
UR  - https://arxiv.org/abs/2611.05303
AB  - 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 P = NP and that (quantum verifier) oblivious state preparation can exist when BQP = QCMA. In particular, we give a classical oracle relative to which (1) P^O = NP^O (2) BQP^O = PSPACE^O (3) Proofs of quantumness exist. In particular, there exists a language in IP^O ⊆ BQP^O which is hard on average against P^O/poly. We give a unitary oracle such that (1) BQP^O = QCMA^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.
ER  -

Abstract

Related

Cite