Metraipolis › archive › dc_264d4016bb68

Quantum Advantage has Few Complexity Implications — arXiv:2611.05303

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.05303
License (as archived)
CC0-1.0
Archived
2026-11-04T21:49:48.041Z
SHA-256 of the archived text
5a29302e81decbdc58d21f6b7efdfb106a2ca0e4ea8545d8fba0f41bdd0c35c6
Stable URL of this page
https://metraipolis.com/documento/dc_264d4016bb68

How to cite

Quantum Advantage has Few Complexity Implications — arXiv:2611.05303 — arXiv (en), https://arxiv.org/abs/2611.05303 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_264d4016bb68 (Metraipolis archive dc_264d4016bb68, sha256 5a29302e81decbdc58d21f6b7efdfb106a2ca0e4ea8545d8fba0f41bdd0c35c6)
BibTeX
@misc{dc264d4016bb68,
  title = {Quantum Advantage has Few Complexity Implications — arXiv:2611.05303},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.05303},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_264d4016bb68; sha256 5a29302e81decbdc58d21f6b7efdfb106a2ca0e4ea8545d8fba0f41bdd0c35c6},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05303. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2611.05303 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T21:38:19.542Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).