Elisa Bäumer, Vinay Tripathi, et al.
APS March Meeting 2024
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.
Elisa Bäumer, Vinay Tripathi, et al.
APS March Meeting 2024
Pauline J. Ollitrault, Abhinav Kandala, et al.
PRResearch
Petar Jurcevic, Luke Govia
APS March Meeting 2023
Max Rossmannek, Fabijan Pavošević, et al.
ACS Fall 2023