Quantum Advantage has Few Complexity Implications
Source: arxiv.org/abs/2611.05303
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)…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.05303
curl -X POST /api/v1/records/arxiv/2611.05303/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.05303/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'