Toward Separating QMA from QCMA with a Classical Oracle
Mark Zhandry · 2024
Read Toward Separating QMA from QCMA with a Classical Oracle by Mark Zhandry (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2411-01718.txt.
Description
Abstract QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes.
Catalog record
| CREATOR | Mark Zhandry |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 71 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2411-01718
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Toward Separating QMA from QCMA with a Classical Oracle Mark Zhandry Abstract QMA is the class of languages that can be decided by an efficient quantum verifier given a quantum witness, whereas QCMA is the class of such languages where the efficient quantum verifier only is given a classical witness. A challenging fundamental goal in quantum query complexity is to find a classical oracle separation for these classes. In this work, we offer a new approach towards proving such a separation that is qualitatively different than prior work, and show that our approach is sound assuming a natural statistical conjecture which may have other applications to quantum query complexity lower bounds. 1 Introduction Do quantum witnesses offer more power than classical witnesses? Slightly more precisely, there are two natural ways to generalize {\sf NP} from the classical setting to the quantum setting: {\sf QMA} (for Quantum Merlin-Arthur) is the set of languages decidable by efficient quantum algorithms with quantum witnesses, whereas {\sf QCMA} (for Quantum Classical Merlin-Arthur) is the set of languages decidable by efficient quantum algorithms with classical witnesses. A long-standing fundamental question, first raised by [ AN02 ] , is whether or not these two generalizations of {\sf NP} are the same. As an unconditional separation between {\sf QMA} and {\sf QCMA} is out of reach given the state of complexity theory, the community has focused on proving oracle separations. The first such separation [ AK07 ] gives a quantum oracle; that is, an oracle that implements a unitary operation and which can be queried on quantum states. A major open question has been whether there is a classical oracle separation; that is, an oracle that implements a classical function, but is accessible in superposition. Classical oracle separations are considered more standard in the community. An early candidate classical oracle separation was given by [ Lut11 ] , but no proof was given. More recently, there have been several results making progress towards this goal by proving separations under different restrictions on how the oracle is accessed. [ FK18 ] show a separation assuming the classical oracle is an “in-place permutation oracle”, a non-standard modeling where the oracle irreversibly permutes the input state. [ NN23 ] show a separation, assuming the witness is required to be independent of certain choices made in constructing the oracle. A very recent line of work has used quantum advantage relative to unstructured oracles [ YZ22 ] to separate {\sf QMA} from {\sf QCMA} : [ Liu23 , LLPY24 ] give a separation assuming the verifier can only make classical oracle queries, and more recently [ BDK24 ] give a separation which allows the verifier quantum queries, but assumes the adaptivity of the queries is sub-logarithmic. A standard classical oracle separation that makes no constraints on how the oracle is accessed or how the witness is created still remains open. The central challenge in separating {\sf QMA} from {\sf QCMA} relative to a classical oracle seems to be the following. Consider a language in {\sf QMA}\setminus{\sf QCMA} , and consider measuring the {\sf QMA} witness in the computational basis. The resulting classical string must not be accepted by the {\sf QMA} verifier, since otherwise we would then have a classical witness for the language, putting it in {\sf QCMA} . Therefore, in some sense, the {\sf QMA} verifier needs to verify that the witness is in superposition. In order to allow for such verification using only a classical oracle, existing approaches require highly structured oracles. But then to actually prove the language is outside of {\sf QCMA} , we need a quantum query complexity lower-bound, and unfortunately the techniques we have are often not amenable to highly structured oracles. Additionally, any witness would naturally be treated as a form of oracle-dependent advice about the oracle, and most quantum query complexity techniques are not very good at distinguishing between quantum advice and classical advice. In other words, if a typical technique succeeded at proving a language is outside of {\sf QCMA} , then if it cannot distinguish quantum vs classical advice, it would likely also show that the language is outside {\sf QMA} as well, thus failing to give a separation. Our Work. We give a new approach for separating {\sf QMA} from {\sf QCMA} relative to a classical oracle. Like prior work, we are unable to prove our oracle separation unconditionally. However, our separation appears much less structured than the prior work (though this is an intuitive statement rather than a formal one), and appears much more amenable to existing quantum query complexity techniques. In particular, we prove under a natural conjecture about k -wise independent distributions that our separation indeed works. We believe our work adds to the evidence that {\sf QMA} and {\sf QCMA} are indeed distinct relative to classical oracles, and may offer a new path toward a proof. 1.1 Our Separating Oracles Our basic idea is the following. An instance in our language will correspond to a subset S\subseteq[N] where N is exponentially-sized. S will be chosen to only contain a negligible fraction of [N] , but still be super-polynomial sized. We will provide a classical oracle (accessible in superposition) that decides membership in S . We will often simply call this oracle S . Next, we choose a random state |\psi\rangle=\sum_{y\in S}\alpha_{y}|y\rangle with support on the set S . The state |\psi\rangle will be our witness state for the {\sf QCMA} instance. An incomplete verification for |\psi\rangle proceeds by simply checking that |\psi\rangle has support contained in S . Essentially, |\psi\rangle is acting as a {\sf QMA} witness that S is non-empty. But there is also a simple {\sf QCMA} witness for this fact: any classical value y\in S . We will instead attempt to turn |\psi\rangle into a witness that S is super-polynomial sized. To do so, we will add a second oracle U which essentially attests to |\psi\rangle being a superposition over super-polynomially-many points. Intuitively, we want to show that U can distinguish between |\psi\rangle and any state whose support is only polynomial-sized. To construct U , let |\hat{\psi}\rangle denote the quantum Fourier transform (QFT) of |\psi\rangle . We observe that if |\psi\rangle has support on a single point y , then |\hat{\psi}\rangle will have uniform amplitude on all points in [N] (though with complex phases on these points). On the other hand, for random |\psi\rangle with support on the large set S , the amplitudes on different points will vary. Concretely, while the expected squared-amplitude on any point z\in[N] is 1/N , there is a reasonable chance that it could be, say, smaller than 1/2N or larger than 2/N . We will choose U to be a subset of [N] consisting of points where |\hat{\psi}\rangle has squared-amplitude somewhat larger than 1/N . We can then have, say, the total squared-amplitude of |\hat{\psi}\rangle on points in U be roughly 3/4 while |U|/N is only roughly 1/2 . In this case, the QFT of a classical string y will have squared-amplitude on U of only 1/2 . Thus, U enables distinguishing |\psi\rangle from a classical input. We will therefore give out an oracle for deciding membership in U . The verifier will first confirm that |\psi\rangle has