[NN23] A Distribution Testing Oracle Separation between QMA and QCMA

Authors: Anand Natarajan, Chinmay Nirkhe | Venue: CCC 2023 (Quantum 2024) | Source

Abstract

We give a distribution testing oracle separation between QMA and QCMA — the first separation using a classical (rather than quantum unitary) oracle. The separating problem tests connectivity of a random graph encoded by a distributional classical oracle. The key restriction is that the honest prover’s quantum witness depends only on the distribution over oracles, not the specific oracle sample, preventing a classical witness from working. This represents an important step toward a fully standard classical oracle separation between QMA and QCMA.

BibTeX

Copy

@inproceedings{NN23,
  author    = {Anand Natarajan and Chinmay Nirkhe},
  title     = {A Distribution Testing Oracle Separating {QMA} and {QCMA}},
  booktitle = {38th Computational Complexity Conference (CCC 2023)},
  series    = {LIPIcs},
  volume    = {264},
  pages     = {22:1--22:27},
  year      = {2023},
  url       = {https://arxiv.org/abs/2210.15380}
}