License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CCC.2023.22
URN: urn:nbn:de:0030-drops-182928
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/18292/
Natarajan, Anand ;
Nirkhe, Chinmay
A Distribution Testing Oracle Separating QMA and QCMA
Abstract
It is a long-standing open question in quantum complexity theory whether the definition of non-deterministic quantum computation requires quantum witnesses (QMA) or if classical witnesses suffice (QCMA). We make progress on this question by constructing a randomized classical oracle separating the respective computational complexity classes. Previous separations [Aaronson and Kuperberg, 2007; Bill Fefferman and Shelby Kimmel, 2018] required a quantum unitary oracle. The separating problem is deciding whether a distribution supported on regular un-directed graphs either consists of multiple connected components (yes instances) or consists of one expanding connected component (no instances) where the graph is given in an adjacency-list format by the oracle. Therefore, the oracle is a distribution over n-bit boolean functions.
BibTeX - Entry
@InProceedings{natarajan_et_al:LIPIcs.CCC.2023.22,
author = {Natarajan, Anand and Nirkhe, Chinmay},
title = {{A Distribution Testing Oracle Separating QMA and QCMA}},
booktitle = {38th Computational Complexity Conference (CCC 2023)},
pages = {22:1--22:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-282-2},
ISSN = {1868-8969},
year = {2023},
volume = {264},
editor = {Ta-Shma, Amnon},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18292},
URN = {urn:nbn:de:0030-drops-182928},
doi = {10.4230/LIPIcs.CCC.2023.22},
annote = {Keywords: quantum non-determinism, complexity theory}
}
Keywords: |
|
quantum non-determinism, complexity theory |
Collection: |
|
38th Computational Complexity Conference (CCC 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
10.07.2023 |