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).