Oracle separation of QMA and QCMA with bounded adaptivity

The first progress on the question of an oracle separation of $\mathsf{QMA}$ and $\mathsf{QCMA}$ was made by Aaronson and Kuperberg [AK07], who showed that there is a quantum oracle, i.e., a blackbox unitary, relative to which $\mathsf{QMA}\neq\mathsf{QCMA}$. Later, Fefferman and Kimmel [FK18] showed that the separation also holds under what they called an “in-place permutation oracle”, which is still inherently quantum. Ideally, we would like to get these separations in the standard model of classical oracles: classical functions that a quantum algorithm may query in superposition. [BFM23] showed separations between $\mathsf{QMA}$ and $\mathsf{QCMA}$ in other non-standard oracle models.

Very recently, there has been some progress on this question, with two different variations of the standard classical oracle model. Natarajan and Nirkhe [NN23] showed an oracle separation relative to a “distributional oracle”. This essentially means that the classical oracle is drawn from a distribution, which the prover knows, but the specific instance drawn is not known to the prover. Therefore, the witness only depends on the distribution over the oracles, which makes it easier to show $\mathsf{QCMA}$ lower bounds. Following this, [LLPY23] showed a separation with a classical oracle that is fully known to the prover, but assuming the verifier is only allowed to access this classical oracle classically, i.e., the verifier is not allowed to make superposition queries (this makes the class similar to $\mathsf{MA}$ in terms of its query power and witness type). This model is also simpler to analyze because whatever information the verifier gets from the oracle by classically querying it, could also have been provided as the classical $\mathsf{QCMA}$ witness. [LLPY23] also gave an alternate construction of a distributional oracle separation, with a simpler proof than [NN23]. Their constructions are based on the relational problem used by Yamakawa and Zhandry [YZ22], in their result on quantum advantage without structure.

Closely related to the $\mathsf{QMA}$ vs $\mathsf{QCMA}$ question is the $\mathsf{BQP}_{/\mathrm{qpoly}}$ vs $\mathsf{BQP}_{/\mathrm{poly}}$ question. $\mathsf{BQP}_{/\mathrm{qpoly}}$ is the class of decision problems that are solvable by a polynomial-time quantum algorithm with access to polynomial-sized quantum advice, which depends non-uniformly on the length of inputs, but nothing else. $\mathsf{BQP}_{/\mathrm{qpoly}}$ is the class of decision problems solvable by a polynomial-time quantum algorithm with access to polynomial-sized classical advice. Most works which have found oracle separations for $\mathsf{QMA}$ vs $\mathsf{QCMA}$ in various oracle models, such as [AK07, NN23, LLPY23], have also found oracle separations between $\mathsf{BQP}_{/\mathrm{qpoly}}$ and $\mathsf{BQP}_{/\mathrm{poly}}$ with related constructions in the same oracle models.

The question of the relative power of classical vs quantum advice was recently resolved unconditionally (without oracles) for relational problems by Aaronson, Buhrman and Kretschmer [ABK23], who showed an unconditional separation between $\mathsf{FBQP}_{/\mathrm{qpoly}}$ and $\mathsf{FBQP}_{/\mathrm{poly}}$. $\mathsf{FBQP}_{/\mathrm{qpoly}}$ and $\mathsf{FBQP}_{/\mathrm{poly}}$ are the classes of relational problems analogous to $\mathsf{BQP}_{/\mathrm{qpoly}}$ and $\mathsf{BQP}_{/\mathrm{poly}}$ respectively. Their result was based on observing that separations between quantum and classical one-way communication complexity can be used to show separations between classical and quantum advice. The reason their result only works for the relation classes is that a separation in one-way communication complexity which satisfies the necessary conditions can only hold for relational problems. The specific relational problem used in [ABK23] is known as the Hidden Matching problem. But as was observed in [LLPY23], the Yamakawa-Zhandry problem [YZ22] also achieves the required communication separation, and could have been used instead. In light of this, the constructions in [YZ22] can viewed as a way to convert relational separations in one-way communication complexity, which correspond to relational separations for quantum vs classical advice, to separations for decision $\mathsf{QMA}$ vs $\mathsf{QCMA}$, and $\mathsf{BQP}_{/\mathrm{qpoly}}$ vs $\mathsf{BQP}_{/\mathrm{poly}}$, relative to classically accessible oracles. The construction is not blackbox — it does not work if the Hidden Matching Problem is used instead of the Yamakawa-Zhandry problem, though it plausibly might work with a parallel repetition of the former.

Unlike previous work, prove an oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$ relative to a bona fide regular oracle with regular (quantum) queries. Our catch is, instead, that we only allow the algorithms bounded adaptivity.

Bounded adaptivity means that the number of rounds of queries made by the algorithms is small, although there can be polynomially many queries in each round. Although our result is not formally stronger than those of [NN23] and [LLPY23], we feel our result is intuitively closer to a full $\mathsf{QMA}$-$\mathsf{QCMA}$ separation, as it allows the full power of classical proofs and some of the power of quantum queries. Our main result is formally stated below.

In the above statement, $\mathsf{QMA}^{\mathcal{O},r}$ is the class of decision problems solvable by QMA algorithms that have oracle access to $\mathcal{O}$, and make at most $r$ batches of parallel queries to $\mathcal{O}$; $\mathsf{QCMA}^{\mathcal{O},r}$ is defined analogously. The parameter $n$ is the efficiency parameter (so the number of queries is $\operatorname{poly}(n)$).

We shall formally define the query versions of QMA and QCMA, and the $r$-round QCMA query complexity $\mathrm{QCMA}^{r}$ later.

Our construction for the query complexity separation is a somewhat simplified version of the construction in [LLPY23], which is based on the Yamakawa-Zhandry problem. [YZ22] and [Liu23] showed that there exists a relational problem $R_{f}$, indexed by functions $f:[n]\times\{0,1\}^{m}\to\{0,1\}$, for $m=\Theta(n)$, such that given oracle access to a quantum advice $\ket{z_{f}}$, a quantum algorithm on any input $x\in\{0,1\}^{n}$, and on average over $f$, can find a $u$ such that $(x,u)\in R_{f}$¹¹1The Yamakawa-Zhandry relation is a $\mathsf{TFNP}$ relation, which means that the $u$-s are of $\operatorname{poly}(n)$ length, and a $u$ such that $(x,u)\in R_{f}$ exists for every $x$.. On the other hand, no quantum algorithm can find such an $u$ for most $x$, when given only a classical advice $z_{f}$, and classical query access to $f$. Using this relation $R_{f}$, for a subset $E\subseteq\{0,1\}^{n}$, we construct the following oracle:

The 1-instances of the problem $F_{N}$ that will separate $\mathsf{QMA}$ and $\mathsf{QCMA}$ in the query complexity model will be $O[f,\emptyset]$, and the 0-instances will be $O[f,E]$ for $|E|\geq\frac{2}{3}\cdot 2^{n}$, for a large subset of all functions $f$. This is essentially the same construction that is used in [LLPY23], except they also use an additional oracle $G$ for a random function from $\{0,1\}^{n}$ to $\{0,1\}^{n}$, which $O$ also depends on.

Note that the query complexity lower bound we obtain for QCMA is of a different nature than the one obtained in [LLPY23]: we need to lower bound (bounded-round) quantum query algorithms instead of only classical query algorithms, and we focus on the worst-case rather than average-case setting. In order to get an oracle separation for Turing machines from a separation in query complexity, one needs to use a diagonalization argument; because our result is set up a bit differently than in previous work, we reprove the diagonalization argument for our setting in Appendix A.

Finally, we emphasize that the bounded adaptivity limitation of our result is because we allow the full power of classical proofs and also quantum queries. If one were to drop the power of classical proofs (resulting in the class $\mathsf{BQP}$), or if one were to drop the power of quantum queries (resulting in, essentially, $\mathsf{MA}$), it would follow from [LLPY23] that close variants of $F_{N}$ cannot be solved even without the bounded-round restriction. We conjecture their lower bounds apply to $F_{N}$ as well.

We briefly describe the techniques used to obtain the query complexity result. We start by observing that the oracle $O[f,\emptyset]$ is essentially just a verification oracle for the Yamakawa-Zhandry relation. Therefore, there is a quantum witness and a quantum algorithm that can distinguish $O[f,\emptyset]$ and $O[f,E]$ by using this witness, with only one query, with probability $1-2^{-\Omega(n)}$ over $f$. The witness for the yes instance $O[f,\emptyset]$ is simply the quantum advice for the Yamakawa-Zhandry problem, which finds a $u$ for any $x$ with probability $1-2^{-\Omega(n)}$ over $f$. The quantum algorithm finds a $u$ for a random $x$ using the witness, and queries the oracle. Since the no instances return 0 on any $(x,u)$ for most $x$, this algorithm can distinguish $O[f,\emptyset]$ and $O[f,E]$ for $1-2^{-\Omega(n)}$ fraction of the $f$-s.

We now consider the uniform distribution over these good $f$-s, which has $\Omega(2^{n})$ min-entropy. If there was a classical witness function depending on $f$, of size $k$, that made a quantum algorithm accept $O[f,\emptyset]$ for these $f$-s, then there would exist a fixed witness string $w$ that would make $O[f,\emptyset]$ accept for $2^{-k}$ fraction of $f$-s. The quantum algorithm depends on the witness, but if we fix the witness string $w$, the algorithm is fixed, and we can then ignore the dependence of the algorithm on the witness.

We now attempt to remove rounds of the quantum query algorithm, starting with the first round, while keeping the behavior of the algorithm the same on as many oracles as possible. Every time we remove a round, we restrict our attention to a smaller set of oracles, all of which are consistent with a growing partial assignment we assume is given to us. At the end, the quantum algorithm will have no rounds left, and hence will make no queries; we want the set of oracles $O[f,\emptyset]$ on which the behavior is preserved to be non-empty, because then we can conclude that the algorithm cannot distinguish $O[f,\emptyset]$ and $O[f,E]$ for some large erased set $E$ (since it now makes no queries).

To remove the first round of the query algorithm, we start by considering the the uniform distribution over the $2^{-k}$ fraction of good $f$-s such that $O[f,\emptyset]$ is accepted by $w$. This distribution has $\Omega(2^{n})-k$ min-entropy, and therefore, by a result of [GPW17, CDGS18], it can be written as a convex combination of finitely many $(l,1-\delta)$-dense distributions, for some small $l$ and $\delta$. $(l,1-\delta)$-dense distributions are a concept that was first introduced in the context of communication complexity; an $(l,1-\delta)$-dense distribution over $N$ coordinates in which $l$ coordinates are fixed, and the rest of the coordinates have high min-entropy in every subset. (Here we are using the same terminology from [GPW17, CDGS18] for dense distributions; the terminology we use in our actual proof will be slightly different — see Section 4.2.) We restrict our attention to such a distribution, and try to preserve the behavior of the quantum algorithm only within a subset of its support.

Some coordinates are fixed in the $(l,1-\delta)$ distribution, which make the probability over this distribution of the event $(x,u)\in R_{f}$ non-negligible, for some $(x,u)$ pairs. The quantum algorithm can potentially learn a lot about $f$ by querying the oracle $O[f,\emptyset]$ for these pairs. Therefore, we shall fix the coordinates of $f$ that are fixed by $(x,u)$ being in $R_{f}$. Here is where we use the fact that the Yamakawa-Zhandry relation is what we shall call slippery. This essentially means that given a small number of fixed coordinates for $f$, the number $(x,u)$ pairs that have non-negligible probability is not too high, and the number of extra coordinates fixed by these $(x,u)$ pairs being in $R_{f}$ is also not too high. The Yamakawa-Zhandry relation being slippery essentially follows from it using a code that has good list recoverability properties. (The Hidden Matching relation, or its parallel repetition, are not slippery by this definition, and so our construction does not work with these.)

Using the slippery property, we can increase the size of the partial assignment by not too much, and via a hybrid-like argument [BBBV97], we can ensure that the first round of the quantum algorithm does not learn much from queries outside this partial assignment. We then restrict our attention to oracles consistent with this partial assignment; on those, we can simulate the first round of the algorithm without making real queries (we simply use the known partial assignment and guess “0” on the rest of the oracle positions, which are highly unlikely to be 1). This way, we get a quantum algorithm with one fewer round, which mimics the original algorithm on a small (but not too small) set of oracles.

Continuing this way, we eliminate all rounds of the algorithm while still maintaining a non-empty set of oracles on which the behavior is preserved. Each such oracle can be “erased”, turning a $1$-input into a $0$-input, so we only need the final $0$-round algorithm to preserve the behavior of the original algorithm on at least one input. Using this technique, we can handle up to $o(\log n/\log\log n)$ rounds of $O(\operatorname{poly}n)$ non-adaptive quantum queries each.

We expect our techniques for the $\mathsf{QMA}$ vs $\mathsf{QCMA}$ separation may also work for a $\mathsf{BQP}_{/\mathrm{qpoly}}$ vs $\mathsf{BQP}_{/\mathrm{poly}}$ separation with boundedly adaptive oracle queries, using the same problem that is described in [LLPY23]. Their oracle in the query complexity setting is given by a random function $G$, which the $\mathsf{BQP}$ algorithm has to compute given oracle access to

and a quantum or classical advice. Here $R^{\prime}_{f}$ is a modified $1$-out-of-$n$ version of the Yamakawa-Zhandry problem, which has better completeness properties, but is similar to the original problem otherwise. Clearly this problem can be solved in $\mathsf{BQP}_{/\mathrm{qpoly}}$ by using the quantum advice for the Yamakawa-Zhandry problem. It cannot be solved on input $x$ with any classical advice and with access to an oracle that outputs $\bot$ for every $(x,u)$. In order to show a $\mathsf{BQP}_{/\mathrm{poly}}$ lower bound for this problem, one needs that there exist many $x$-s such that a quantum algorithm with classical advice cannot distinguish $O[f,G]$ from a version of $O[f,G]$ that is erased on those $x$-s. Since $O[f,G]$ essentially serves as a verification oracle for $R^{\prime}_{f}$, we expect that when the quantum algorithm has bounded rounds, a proof very similar to our $\mathsf{QCMA}$ lower bound will work.

The final goal is, of course, to be able to show both these results without a bound on the number of rounds of oracle queries the quantum algorithm makes. As mentioned earlier, we fail to do this because the slipperiness parameters of the relation we picked are not good enough, and our methods would work to separate $\mathsf{QMA}$ and $\mathsf{QCMA}$ with an analogous problem definition where the Yamakawa-Zhandry relation is replaced by a different relation $R_{f}$ that has the appropriate slipperiness property.

We now expand more on the required strong slipperiness property. Let $R_{f}$ be a family of $\mathsf{TFNP}$ relations on $\{0,1\}^{n}\times\{0,1\}^{m}$ indexed by $f\in\{0,1\}^{N}$, where $m=\operatorname{poly}(n)$ and $N=\Omega(2^{n})$. We further assume $R_{f}$ satisfies the property that if $(x,u)\in R_{f}$, then there is a polynomial-sized partial assignment $p$ for $f$ which certifies this, i.e., $(x,u)\in R_{f}$ $\forall f\supseteq p$. Let $\mathcal{P}\subseteq\{0,1,*\}^{N}$ denote the set of polynomial-sized partial assignments for $f$. We define the extended version $\widetilde{R}$ of the family of relations $R_{f}$ as follows:

Since $p$ is polynomial-sized, if we consider the uniform distribution over $\{0,1\}^{N}$, $\Pr[p\subseteq f]$ is exponentially small. Now consider a partial assignment $q$ for $f$ with size at most $s(n)$; we fix the bits in $q$ and generate the other bits of $f$ uniformly at random, which can make the probability of some other partial assignments $p$ non-negligible. The slipperiness property is concerned with the total support of all partial assignments $p$ such that $\Pr[p\subseteq f|q\subseteq f]$ is non-negligible, and $(p,x,u)\in\widetilde{R}$. We say $\widetilde{R}$ is $(\eta,s(n),t(n))$-slippery if for all $s(n)$-sized $q$, the total support of all $p$-s such that $\Pr[p\subseteq f|q\subseteq f]\geq\eta$ and $(p,x,u)\in\widetilde{R}$ is at most $t(n)$. See Definition 13 for a more formal definition.

Our techniques show that the following conjecture implies an oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$.

Assuming Conjecture 3 is true, the oracle function separating $\mathsf{QMA}$ and $\mathsf{QCMA}$ would be distinguishing $O[f,\emptyset]$ and $O[f,E]$, for $|E|\geq\frac{2}{3}\cdot 2^{n}$, which we have defined earlier, using a relation $R_{f}$ that satisfies the conjecture. (The Yamakawa-Zhandry relation does not seem to satisfy the conjecture; we can only prove it is $(\eta,s(n),t(n))$-slippery, with $t(n)$ bigger than $s(n)$.)

We further note that any family of relations $R_{f}$ that satisfies Conjecture 3 must give an exponential separation between quantum and randomized one-way communication complexity, with the communication setting being that Alice gets input $f$, Bob gets input $x$, and Bob has to output $u$ such that $(x,u)\in R_{f}$.²²2Strictly speaking, condition 1 of the conjecture only implies that there exists a one-way communication protocol, in which Alice sends the state $\ket{z_{f}}$, which works on average over $x$ and $f$, whereas we usually require worst-case success in communication complexity. However, we can restrict to the set of $x$ and $f$ for which the algorithm $\mathcal{A}$ works, in order to get the communication problem. This is because, if there was a polynomial-sized classical message $w_{f}$ that Alice could send to Bob in the communication setting, then $w_{f}$ could also serve as a QCMA proof. Therefore, it seems that the slipperiness condition could also be used for lower-bounding one-way randomized communication complexity (although weaker slipperiness parameters than in the conjecture would also suffice for this).

In this section, we review the formal definitions of QMA, QCMA, computationally-efficient QMA, and bounded-round QCMA in the context of query complexity.

We will use the term “$T$-query quantum algorithm” without referring to the number of rounds to indicate $T$ rounds with $1$ query in each.

With these definitions, we show in Appendix A that Theorem Theorem 2 implies Theorem Theorem 1.

A Reed-Solomon error-correcting code $\operatorname{RS}_{q,\gamma,k}$ over $\operatorname{\mathbb{F}}_{q}$, with degree parameter $0<k<q-1$ and generator $\gamma\in\operatorname{\mathbb{F}}^{*}_{q}$, is defined as

where $\operatorname{\mathbb{F}}_{q}[x]_{\deg\leq k}$ is the set of polynomials over $\operatorname{\mathbb{F}}_{q}$ of degree at most $k$.

Let $q-1=mn$, for some integers $m$ and $n$. The $m$-folded version $\operatorname{RS}^{(m)}_{q,\gamma,k}$ of $\operatorname{RS}_{q,\gamma,k}$ is a mapping of the code to the larger alphabet $\operatorname{\mathbb{F}}_{q}^{m}$ as follows:

Note that the alphabet of $\operatorname{RS}^{(m)}_{q,\gamma,k}$ is $\operatorname{\mathbb{F}}_{q}^{m}$.

This corollary is proved simply by checking that the equations (1)–(2) are satisfied with this choice of parameters. The choice of parameters is in fact the same as those as [YZ22]. Therefore, the above code satisfies the other conditions required for the [YZ22] quantum algorithm to succeed in evaluating the relation $R_{C,f}$ defined in the next section.

Fix a code $C$ for which Theorem 16 holds, with $c=\log n$. We shall henceforth refer to $R_{C,f}$ as only $R_{f}$ for this $C$. For a subset $E\subseteq\{0,1\}^{n}$, define the oracle $O[f,E]\colon\{0,1\}^{n}\times\{0,1\}^{nm}\to\{0,1\}$ as

Recall that a non-adaptive quantum algorithm works on $T$ query-input registers and $T$ query-output registers plus an additional work register $W$, so that its basis states look like

To clear up notational clutter, we will use $\vec{i}\in[N]^{T}$ to represent a tuple of $T$ indices in $[N]$. Moreover, for a string $x\in\{0,1\}^{N}$ and for $\vec{i}\in[N]^{T}$, we will define $x_{\vec{i}}\coloneqq(x_{\vec{i}_{1}},x_{\vec{i}_{2}},\dots,x_{\vec{i}_{T}})$. The basis states can then be written $\ket{\vec{i}}\ket{\vec{b}}\ket{W}$, and the action of the query unitary $U^{x}$ to the string $x$ is to map $\ket{\vec{i}}\ket{\vec{b}}\ket{W}\to\ket{\vec{i}}\ket{\vec{b}\oplus x_{\vec{i}}}\ket{W}$, extended linearly to the rest of the space. (Here $\oplus$ denotes the bitwise XOR of the two strings of length $T$.)

Define $\Pi_{\vec{i}}\coloneqq\ket{\vec{i}}\bra{\vec{i}}\otimes I_{\vec{b},W}$ to be the projection onto basis states with $\vec{i}$ in the query-input registers. For $i\in[N]$, define $\Pi_{i}\coloneqq\sum_{\vec{i}\ni i}\Pi_{\vec{i}}$ to be the projection onto basis states with $i$ occurring in one of the query-input registers. The projections $\Pi_{\vec{i}}$ are onto orthogonal spaces, though the projections $\Pi_{i}$ are not. Observe that $\sum_{\vec{i}}\Pi_{\vec{i}}=I$, and that $\sum_{i}\Pi_{i}=\sum_{i}\sum_{\vec{i}\ni i}\Pi_{\vec{i}}=\sum_{\vec{i}}\sum_{i\in\vec{i}}\Pi_{\vec{i}}=T\cdot I$. Moreover, since the oracle unitary $U^{x}$ does not change the query-input registers, $U^{x}$ commutes with both $\Pi_{\vec{i}}$ and $\Pi_{i}$. Another convenient property is that if $x_{\vec{i}}=y_{\vec{i}}$ for two strings $x,y\in\{0,1\}^{N}$, then $\Pi_{\vec{i}}(U^{x}-U^{y})=0$; this holds because both $U^{x}$ and $U^{y}$ map $\ket{\vec{i}}\ket{\vec{b}}\ket{W}$ to the same vector when $x_{\vec{i}}=y_{\vec{i}}$. Using these properties, we have the following lemma.