Title: Oracle separation of QMA and QCMA with bounded adaptivity
| Speaker: | Srijita Kundu |
| Affiliation: | University of Waterloo |
| Location: | MC 5501 |
Abstract: It is a long-standing open problem in quantum complexity theory whether the two possible quantum analogs of NP are equivalent. QMA is defined as the class of decision problems that are solvable by a polynomial-time quantum algorithm that has access to a polynomial-sized quantum proof, whereas QCMA is the class of decision problems that are solvable by a polynomial-time quantum algorithm that only has access to the polynomial-sized classical proof. In other words, the QMA vs QCMA question asks: are quantum proofs more powerful than classical proofs?
These classes were first separated relative to a quantum oracle by Aaronson and Kuperberg (2007), and since then, there have been other separations shown in different non-standard oracle models. But a separation of QMA and QCMA in the standard setting of a classical oracle remains elusive. Building on some recent progress on this question, we give a classical oracle separation between QMA and QCMA for quantum algorithms that have bounded adaptivity in their oracle queries. Bounded adaptivity means that the number of rounds of oracle calls is small, though each round may involve polynomially many queries. Our construction uses the search problem that was recently introduced by Yamakawa and Zhandry (2022) to get a separation between BQP and BPP relative to a random oracle. To prove our results, we introduce a property of search problems called slipperiness, which may be useful to get a fully general classical oracle separation between QMA and QCMA.
This talk is based on joint work with Shalev Ben-David.