spacing=nonfrench

# Oracle separation of QMA and QCMA with bounded adaptivity

Shalev Ben-David
University of Waterloo
<EMAIL_ADDRESS>Srijita Kundu
University of Waterloo
<EMAIL_ADDRESS>
###### Abstract

We give an oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$ for
quantum algorithms that have bounded adaptivity in their oracle queries; that
is, the number of rounds of oracle calls is small, though each round may
involve polynomially many queries in parallel. Our oracle construction is a
simplified version of the construction used recently by Li, Liu, Pelecanos,
and Yamakawa (2023), who showed an oracle separation between $\mathsf{QMA}$
and $\mathsf{QCMA}$ when the quantum algorithms are only allowed to access the
oracle classically. To prove our results, we introduce a property of relations
called _slipperiness_ , which may be useful for getting a fully general
classical oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$.

###### Contents

  1. 1 Introduction
    1. 1.1 Previous work
    2. 1.2 Our results
    3. 1.3 Our techniques
    4. 1.4 Discussion and further work
  2. 2 Preliminaries
    1. 2.1 QMA and QCMA in query complexity
    2. 2.2 Error-correcting codes
  3. 3 The Yamakawa-Zhandry Problem
  4. 4 QMA vs QCMA
    1. 4.1 Construction and QMA protocol
    2. 4.2 Useful notation and lemmas
    3. 4.3 QCMA lower bound
  5. A Diagonalization argument
    1. A.1 QMA and QCMA for Turing machines
    2. A.2 From query separation to oracle separation

##  1 Introduction

It is a long-standing open problem in quantum complexity theory whether the
two possible quantum analogs of the complexity class $\mathsf{NP}$ are
equivalent. $\mathsf{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_ witness, whereas $\mathsf{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_ witness. In other
words, the question asks: are quantum proofs more powerful than classical
proofs?

While the inclusion $\mathsf{QCMA}\subseteq\mathsf{QMA}$ is easy to see, the
question of whether these two classes are actually equal, which was first
posed by Aharonov and Naveh [AN02], remains unanswered. Indeed, an
unconditional separation between these classes is beyond currently known
techniques.

An easier, but still unsolved, problem is to show an oracle separation between
$\mathsf{QMA}$ and $\mathsf{QCMA}$. This is because oracle separations in the
Turing machine model can be shown by means of separations in the much simpler
model of _query complexity_ , where similar separations between complexity
classes are routinely shown (for example, a recent oracle separation between
$\mathsf{BQP}$ and $\mathsf{PH}$ was provided in [RT19]). The problem of
finding an oracle separation between $\mathsf{QMA}$ and $\mathsf{QCMA}$ has
been a longstanding focus of the quantum computing community; it boils down to
asking whether quantum proofs are more powerful than classical proofs in the
query model.

###  1.1 Previous work

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.

###  1.2 Our results

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.

######  Theorem 1.

There is an oracle $\mathcal{O}\colon\\{0,1\\}^{*}\to\\{0,1\\}$ such that
$\mathsf{QCMA}^{\mathcal{O},r}\neq\mathsf{QMA}^{\mathcal{O},r}$, for $r=o(\log
n/\log\log n)$.

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)$).

######  Theorem 2.

There is a function family $F=\\{F_{N}\\}_{N\in I}$ which is efficiently
computable in 1-round query $\mathsf{QMA}$, but for which the growth rate of
$\mathrm{QCMA}^{r}(F_{N})$ for $r=o(\log\log N/\log\log\log N)$ as
$N\to\infty$ is not in $O(\operatorname{polylog}(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}$111The 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:

$O[f,E](x,u)=\begin{cases}1&\text{ if }(x,u)\in R_{f}\land x\notin E\\\
0&\text{ otherwise}.\end{cases}$

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.

###  1.3 Our techniques

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.

###  1.4 Discussion and further work

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

$O[f,G](x,u)=\begin{cases}G(x)&\text{ if }(x,u)\in R^{\prime}_{f}\\\
\bot&\text{ otherwise,}\end{cases}$

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:

$\widetilde{R}=\\{(p,x,u):p\text{ is the minimal partial assignment s.t.
}(x,u)\in R_{f}\,\forall f\supseteq p\\}.$

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}$.

######  Conjecture 3.

There exists a family of $\mathsf{TFNP}$ relations $R_{f}$ such that

  1. 1.

There exists a polynomial-time algorithm $\mathcal{A}$, and for each $f$, a
$\operatorname{poly}(n)$-sized quantum state $\ket{z_{f}}$ such that, given
access to $x$ and $\ket{z_{f}}$, $\mathcal{A}$ can find $u$ such that
$(x,u)\in R_{f}$, with probability at least $1-2^{-\Omega(n)}$ over uniform
$x,f$.

  2. 2.

There exists a function $s(n)=2^{o(n)}$ such that for all polynomial functions
$p(n)$, the extended relation $\widetilde{R}$ is
$\left(1/p(n),s(n),t(n)\right)$-slippery for some $t(n)$ such that
$\log(t(n))=o(\log(s(n)))$.

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}$.222Strictly 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).

##  2 Preliminaries

###  2.1 QMA and QCMA in query complexity

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

######  Definition 4 (Bounded-round quantum query algorithm).

For $r,T,n\in\operatorname{\mathbb{N}}$, give the following definition of a
quantum query algorithm $Q$ acting on $n$ bits, using $r$ rounds, with $T$
queries in each round. The algorithm will be a tuple of $r+1$ unitary
matrices, $Q=(U_{0},U_{1},\dots,U_{r})$. These unitary matrices will each act
on $T$ “query-input” registers of dimension $n$, $T$ “query-output” registers
of dimension $2$, an “output” register of dimension $2$, and a work register
of arbitrary dimension.

For each $x\in\\{0,1\\}^{n}$, let $U^{x}$ be the oracle unitary, which acts on
the query-input and query-output registers by mapping

$\ket{i_{1}}\ket{b_{1}}\ket{i_{2}}\ket{b_{2}}\dots\ket{i_{T}}\ket{b_{T}}\to\ket{i_{1}}\ket{b_{1}\oplus
x_{i_{1}}}\ket{i_{2}}\ket{b_{2}\oplus
x_{i_{2}}}\dots\ket{i_{T}}\ket{b_{T}\oplus x_{i_{T}}}$

for all $i_{1},\dots,i_{T}\in[n]$ and all $b_{1},\dots,b_{T}\in\\{0,1\\}$. We
extend $U^{x}$ to other registers via a Kronecker product with identity, so
that $U^{x}$ ignores the other registers.

The action of the algorithm $Q$ on input $x\in\\{0,1\\}^{n}$, denoted by the
Bernoulli random variable $Q(x)$, will be the result of measuring the output
register of the state

$U_{r}U^{x}U_{r-1}U^{x}\dots U^{x}U_{1}U^{x}U_{0}\ket{\psi_{init}},$

where $\ket{\psi_{init}}$ is a fixed initial state.

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.

######  Definition 5 (Query algorithm with witness).

Let $Q$ be a $r$-query quantum algorithm on $n$ bits with $T$ queries in each
round. For any quantum state $\ket{\phi}$ and any $x\in\\{0,1\\}^{n}$, let
$Q(x,\ket{\phi})$ be the random variable corresponding to the measured output
register after the algorithm terminates, assuming the initial state contained
$\ket{\phi}$ in the work register (with ancilla padding) instead of being
$\ket{\psi_{init}}$. That is, $Q(x,\ket{\phi})$ is a Bernoulli random variable
corresponding to the measurement outcome of the output register of the final
state

$U_{r}U^{x}U_{r-1}U^{x}\dots U_{1}U^{x}U_{0}\ket{\phi}\ket{pad}.$

######  Definition 6 (Query QMA and QCMA).

Let $f$ be a possibly partial Boolean function on $n$ bits, and let $Q$ be a
quantum query algorithm on $n$ bits with $T$ total queries. We say that $Q$ is
a QMA algorithm for $f$ with witness size $k$ if the following holds:

  1. 1.

(Soundness.) For every $x\in f^{-1}(0)$ and every $k$-qubit state
$\ket{\phi}$, we have $\Pr[Q(x,\ket{\phi})=1]\leq\epsilon$.

  2. 2.

(Completeness.) For every $x\in f^{-1}(1)$, there exists a $k$-qubit state
$\ket{\phi}$ such that $\Pr[Q(x,\ket{\phi})=1]\geq 1-\delta$.

Here, $\epsilon$ and $\delta$ govern the soundness and completeness of $Q$; by
default, we take them both to be $1/3$. We denote the QMA query complexity of
$f$ by $\mathrm{QMA}_{\epsilon,\delta}(f)$, which is the minimum possible
value of $T+k$ over any QMA algorithm for $f$ with the specified soundness and
completeness.

We say that $Q$ is a QCMA algorithm for $f$ if the same conditions hold,
except with the witness state $\ket{\phi}$ quantifying over only classical
$k$-bit strings in both the soundness and completeness conditions. We define
$\mathrm{QCMA}_{\epsilon,\delta}(f)$ analogously to
$\mathrm{QMA}_{\epsilon,\delta}(f)$, and we omit the subscripts when they are
both $1/3$.

######  Definition 7 (Bounded round query QMA and QCMA).

We define $r$-round QMA and QCMA in exactly the same way as the above
definition, except the query algorithms are required to have at most $r$
rounds. We use $\mathrm{QMA}^{r}_{\varepsilon,\delta}(f)$ and
$\mathrm{QCMA}^{r}_{\varepsilon,\delta}(f)$ to denote the $r$-round QMA and
QCMA query complexities of $f$ respectively.

######  Definition 8 (Function family).

A _function family_ is an indexed set $F=\\{f_{n}\\}_{n\in I}$ where
$I\subseteq\operatorname{\mathbb{N}}$ is an infinite set and where each
$f_{n}$ is a partial Boolean function
$f_{n}\colon\operatorname{Dom}(f_{n})\to\\{0,1\\}$ with
$\operatorname{Dom}(f_{n})\subseteq\\{0,1\\}^{n}$.

######  Definition 9 (Efficiently computable QMA).

Let $F=\\{f_{n}\\}_{n\in I}$ be a function family. We say that $F$ is in
_efficiently computable query $\mathsf{QMA}$_ if there is a polynomial-time
Turing machine which takes in the binary encoding $\langle n\rangle$ of a
number $n\in I$ and outputs a QMA verifier $Q$ by explicitly writing out the
unitaries of $Q$ as quantum circuits (with a fixed universal gate set). The
verifier $Q$ must be sound and complete for $f_{n}$. Efficiently computable
bounded-round QMA is defined analogously.

In other words, $\mathrm{QMA}(f_{n})$ must be $O(\operatorname{polylog}(n))$,
and moreover, the different algorithms for $f_{n}$ must be uniformly generated
by a single polynomial-time Turing machine.

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

###  2.2 Error-correcting codes

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

$\operatorname{RS}_{q,\gamma,k}=\\{(f(\gamma),\ldots
f(\gamma^{q})):f\in\operatorname{\mathbb{F}}_{q}[x]_{\deg\leq k}\\},$

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:

$\operatorname{RS}^{(m)}_{q,\gamma,k}=\\{((x_{1},\ldots,x_{m}),\ldots,(x_{q-m},\ldots,x_{q})):(x_{1},\ldots,x_{q})\in\operatorname{RS}_{q,\gamma,k}\\}.$

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

######  Definition 10.

We say that a code $C\subseteq\Sigma^{n}$ is combinatorially
$(\zeta,\ell,L)$-list recoverable if for any subsets $S_{i}\subseteq\Sigma$
such that $|S_{i}|\leq\ell$, we have,

$\left|\\{(x_{1},\ldots,x_{n})\in C:|\\{i:x_{i}\in
S_{i}\\}|\geq(1-\zeta)n\\}\right|\leq L.$

######  Lemma 11 ([Rud07, YZ22]).

For a prime power $q$ such that $mn=q-1$, any generator
$\gamma\in\operatorname{\mathbb{F}}_{q}^{*}$, and degree $k<q-1$,
$\operatorname{RS}^{(m)}_{q,\gamma,k}$ is $(\zeta,\ell,q^{s})$-list
recoverable for some $s\leq m$ if there exists an integer $r$ such that the
following inequalities hold:

$\displaystyle(1-\zeta)n(m-s+1)$
$\displaystyle\geq\left(1+\frac{s}{r}\right)(mn\ell k^{s})^{1/(s+1)}$ (1)
$\displaystyle(r+s)\left(\frac{mn\ell}{k}\right)^{1/(s+1)}$ $\displaystyle<q.$
(2)

######  Corollary 12.

Let $m$ be $\Theta(n)$ integer such that $nm+1=q$ is a prime power. Let
$k=\frac{5}{6}mn$ and let $c,d$ be constants. Then
$\operatorname{RS}_{q,\gamma,k}$ is $(c\log n/n,2^{(\log n)^{d}},2^{(\log
n)^{d+1}})$-list recoverable.

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.

##  3 The Yamakawa-Zhandry Problem

For a function $f:[n]\times\\{0,1\\}^{m}\to\\{0,1\\}$ and a linear code
$C\subseteq\\{0,1\\}^{nm}$, define the relation
$R_{C,f}\subseteq\\{0,1\\}^{n}\times\\{0,1\\}^{nm}$

$R_{C,f}=\\{(x,u)=(x_{1}\ldots x_{n},u_{1}\ldots u_{n}):(u_{1}\ldots u_{n}\in
C)\land(\forall i\,f(i,u_{i})=x_{i})\\}.$

We shall typically work with $m=\Theta(n)$. We shall usually work with a fixed
code $C$, in which case we shall omit the subscript $C$ from $R_{C,f}$.

Let $\mathcal{P}\subseteq\\{0,1,*\\}^{n2^{m}}$ denote the set of polynomial-
sized partial assignments for functions
$f:[n]\times\\{0,1\\}^{m}\to\\{0,1\\}$. We define the extended version
$\widetilde{R}_{C}$ of $\\{R_{C,f}\\}_{f}$ over
$\mathcal{P}\times\\{0,1\\}^{n}\times\\{0,1\\}^{nm}$ as follows:

$\widetilde{R}_{C}=\\{(p,x,u):p\text{ is the minimal partial assignment s.t.
}(x,u)\in R_{C,f}\,\forall f\supseteq p\\}.$

In particular, $(p,x,u)$ is in $\widetilde{R}_{C}$ when $p$ is the partial
assignment $(f(i,u_{i})=x_{i})_{i}$, which is $n$ bits.

######  Definition 13.

Let $\widetilde{R}_{n}$ be a sequence of relations on
$\mathcal{P}_{n}\times\\{0,1\\}^{n}\times\\{0,1\\}^{\operatorname{poly}(n)}$,
where $\mathcal{P}_{n}$ consists of fixed polynomial-sized partial assignments
for $N=2^{\Omega(n)}$-bit strings, and $\operatorname{poly}(n)$ is some fixed
polynomial. We say $\widetilde{R}_{n}$ is $(\eta,s(n),t(n))$-slippery w.r.t.
distribution $\mu$ on $f$ if for any partial assignment $q$ on $N$ bits with
size at most $s(n)$, if we fix the bits of $q$ in $f$ and generate the other
bits of $f$ according to $\mu$ (conditioned on $q$), we will have

$\left|\bigcup_{\begin{subarray}{c}(p,x,u)\in\widetilde{R}_{n},\\\
\Pr_{f\sim\mu}[p\subseteq f|q\subseteq
f]\geq\eta\end{subarray}}\operatorname{supp}(p)\right|\leq t(n).$

We omit mentioning the distribution $\mu$ explicitly if it is the uniform
distribution.

######  Lemma 14.

When $C$ is a code with parameters from Corollary 12, then for any constants
$c,d$, $\widetilde{R}_{C}$ is $(\frac{1}{n^{c}},2^{(\log n)^{d}},2^{(c+2)(\log
n)^{d+1}})$-slippery.

###### Proof.

Let $q$ be a partial assignment of size $2^{(\log n)^{d}}$. For each
$i\in[n]$, let $S_{i}=\\{v:(i,v)\text{ is fixed in }q\\}$. Clearly for each
$i$, $|S_{i}|\leq 2^{(\log n)^{d}}$. By Corollary 12,

$C_{q}=\left|\\{u_{1}\ldots u_{n}\in C:|\\{i:u_{i}\in S_{i}\\}|\geq n-c\log
n\\}\right|\leq 2^{(\log n)^{d+1}}.$

Let us count the number of $(p,x,u)$ tuples that could be in
$\widetilde{R}_{C}$ conditioned on $q$, for which $u$ is in $C_{q}$. In fact
we only need to count the number of $(x,u)$ pairs that could be in $R_{C,f}$,
since $p$ is completely fixed by $x$ and $u$. Each $u$ has at most $c\log n$
many locations that are not fixed by $q$, and $x$ can take any value in those
$c\log n$ locations, which means there are $2^{c\log n}$ many possible $x$-s
for each $u$. Therefore, the number of $(x,u)$ pairs is $2^{(\log
n)^{d+1}}\cdot 2^{c\log n}$. Consider the $(p,x,u)$ corresponding to each such
$(x,u)$. Since $x$ has $c\log n$ many locations unfixed by $q$, and $p$ only
fixes those locations, we have for each such $p$, $\Pr[p\subseteq f|q\subseteq
f]\geq\frac{1}{n^{c}}$. In fact the $(p,x,u)$ tuples we have counted with
$u\in C_{q}$ are the only ones that satisfy $(p,x,u)\in\widetilde{R}_{C}$
conditioned on $q$, and $\Pr[p\subseteq f|q\subseteq f]\geq\frac{1}{n^{c}}$.
Since the total support of each $p$ is $n$, we have,

$\left|\bigcup_{\begin{subarray}{c}(p,x,u)\in\widetilde{R}_{n},\\\
\Pr_{f}[p\subseteq f|q\subseteq
f]\geq\frac{1}{n^{c}}\end{subarray}}\operatorname{supp}(p)\right|\leq 2^{(\log
n)^{d+1}}\cdot 2^{c\log n}\cdot n\leq 2^{(c+2)(\log n)^{d+1}}.$

∎

######  Corollary 15.

If $\mu$ is a distribution such that for all partial assignments $p$ with
$|p|=n$, we have $\mu[p]\leq\frac{k}{2^{n}}$ (where $\mu[p]$ is the
probability mass of strings consistent with $p$), then $\widetilde{R}_{C}$
from Lemma 14 is also $(\frac{k}{n^{c}},2^{(\log n)^{d}},2^{(c+2)(\log
n)^{d+1}})$-slippery w.r.t. $\mu$.

###### Proof.

Since $\mu[p]\leq\frac{k}{2^{n}}$ for all $p$, partial assignments that have
probability at least $\frac{k}{n^{c}}$ against $\mu$ conditioned on $q$ have
probability at least $\frac{1}{n^{c}}$ against the uniform distribution
conditioned on $q$. Now we can apply Lemma 14. ∎

######  Theorem 16.

There exists a code $C$ such that

  1. 1.

$\widetilde{R}_{C}$ is $(\frac{1}{n^{c}},2^{(\log n)^{d}},2^{(c+2)(\log
n)^{d+1}})$-slippery for any constant $d$.

  2. 2.

There exists a quantum advice $\ket{z_{f}}$ with polynomially many qubits, and
a polynomial-time quantum algorithm $\mathcal{A}$ that has access to
$\ket{z_{f}},x$, and makes no queries to any oracle, such that for any
$x\in\\{0,1\\}^{n}$,

$\Pr_{f\sim U}[(u\leftarrow\mathcal{A}(\ket{z_{f}},x))\land((x,u)\in
R_{C,f})]\geq 1-2^{-\Omega(n)},$

where the probability is over uniformly random functions
$f:[n]\times\\{0,1\\}^{m}\to\\{0,1\\}$, and the internal randomness of
$\mathcal{A}$.

###### Proof.

Item 1 is due to Lemma 14. As stated before, the problem $\widetilde{R}_{C}$,
and the choice of parameters for the code $C$ in Lemma 14, is the same as
[YZ22]. Therefore, item 2 is due to [YZ22, Liu23].333The quantum algorithm in
[YZ22] makes some non-adaptive quantum queries (not depending on $x$), and
does not take an advice state. The modified algorithm, which instead takes an
advice state (which is essentially the state of the algorithm in [YZ22] after
its non-adaptive queries) and makes no queries, was described in [Liu23]. ∎

##  4 QMA vs QCMA

In this section, we prove Theorem 2. Theorem 17 will define the function
$F_{N}$ and show that it is in QMA, and Theorem 21 will show that it is not in
QCMA.

###  4.1 Construction and QMA protocol

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

$O[f,E](x,u)=\begin{cases}1&\text{ if }(x,u)\in R_{f}\land x\notin E\\\
0&\text{ otherwise}.\end{cases}$

######  Theorem 17.

There exists an efficient uniform collection of query QMA protocols (generated
uniformly by a polynomial time Turing machine) which uses $1$ query and
polynomial witness size, and which outputs 0 on all oracles $O[f,E]$ with
$|E|\geq(2/3)\cdot 2^{n}$, and outputs 1 on $O[f,\emptyset]$ for
$1-2^{-\Omega(n)}$ fraction of $f$-s.

###### Proof.

The quantum witness for the algorithm will be quantum advice state for $R_{f}$
from Theorem 16. The quantum algorithm works as follows: it samples a
uniformly random $x\in\\{0,1\\}^{n}$, and runs the procedure from Theorem 16
to find a $u$ such that $(x,u)\in R_{f}$. Note that this requires no queries
to the oracle. Then it queries the oracle at $(x,u)$ and returns the query
output. If the oracle is $O[f,\emptyset]$ and the actual state $\ket{z_{f}}$
from Theorem 16 is provided as witness, then due to Theorem 16 we have,

$\Pr_{f\sim U}[\mathcal{A}^{O[f,\emptyset]}(\ket{z_{f}})=1]\geq
1-2^{-\Omega(n)}.$

On the other hand, if the oracle is $O[f,E]$ for $|E|\geq\frac{2}{3}\cdot
2^{n}$, no matter what witness is provided, and what $u$ is obtained from this
witness, the oracle outputs 0 on $(x,u)$ for $\frac{2}{3}$ of the $x$-s. Since
the algorithm samples a uniformly random $x$ and queries it with some $u$ for
every $f$, we have for every $f$,

$\Pr[\mathcal{A}^{O[f,E]}(\ket{z_{f}})=1]\leq\frac{1}{3}.\qed$

#### Defining the function $F_{N}$.

We now define the following partial query function with input size
$2^{n}\times 2^{mn}$: its $1$-inputs are all the oracles $O[f,\emptyset]$ for
which the algorithm from Theorem Theorem 17 accepts with probability at least
$2/3$, and its $0$-inputs are $O[f,E]$ for which $O[f,\emptyset]$ is a
$1$-input and $|E|\geq(2/3)\cdot 2^{n}$. Note that these oracles correspond to
the inputs “$x$” of the query problem. This defines a family $F_{N}$ of query
tasks with $N=2^{n}\times 2^{mn}$, and Theorem 17 showed that this family is
in efficiently-computable QMA.

###  4.2 Useful notation and lemmas

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

$\ket{i_{1}}\ket{b_{1}}\ket{i_{2}}\ket{b_{2}}\dots\ket{i_{T}}\ket{b_{T}}\ket{W}.$

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.

######  Lemma 18 (Hybrid argument for nonadaptive queries).

For any strings $x,y\in\\{0,1\\}^{N}$ and any quantum state
$\ket{\psi}=\sum_{\vec{i},\vec{b},W}\alpha_{\vec{i},\vec{b},W}\ket{\vec{i}}\ket{\vec{b}}\ket{W}$,
we have

$\|U^{x}\ket{\psi}-U^{y}\ket{\psi}\|_{2}^{2}\leq 4\sum_{i:x_{i}\neq
y_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}.$

###### Proof.

We write the following, with justification afterwards.

$\displaystyle\|U^{x}\ket{\psi}-U^{y}\ket{\psi}\|_{2}^{2}$
$\displaystyle=\left\|\sum_{\vec{i}}\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\right\|_{2}^{2}$
$\displaystyle=\sum_{\vec{i}}\|\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\|_{2}^{2}$
$\displaystyle=\sum_{\vec{i}:x_{\vec{i}}\neq
y_{\vec{i}}}\|\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\|_{2}^{2}$
$\displaystyle\leq\sum_{\vec{i}}\sum_{i\in\vec{i}:x_{i}\neq
y_{i}}\|\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\|_{2}^{2}$
$\displaystyle=\sum_{i:x_{i}\neq y_{i}}\sum_{\vec{i}\ni
i}\|\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\|_{2}^{2}$
$\displaystyle=\sum_{i:x_{i}\neq y_{i}}\left\|\sum_{\vec{i}\ni
i}\Pi_{\vec{i}}(U^{x}-U^{y})\ket{\psi}\right\|_{2}^{2}$
$\displaystyle=\sum_{i:x_{i}\neq
y_{i}}\|\Pi_{i}(U^{x}-U^{y})\ket{\psi}\|_{2}^{2}$
$\displaystyle=\sum_{i:x_{i}\neq
y_{i}}\|(U^{x}-U^{y})\Pi_{i}\ket{\psi}\|_{2}^{2}$ $\displaystyle\leq
4\sum_{i:x_{i}\neq y_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}.$

In the first line, we used $\sum_{\vec{i}}\Pi_{\vec{i}}=I$. In the second, we
used the orthogonality of the images of the projections $\Pi_{\vec{i}}$. In
the third, we used $\Pi_{\vec{i}}(U^{x}-U^{y})=0$ when
$x_{\vec{i}}=y_{\vec{i}}$.

In the fourth line, we replaced the sum over $\vec{i}$ containing at least one
$i$ with $x_{i}\neq y_{i}$ with a weighted sum, where the weight of $\vec{i}$
is the number of $i\in\vec{i}$ such that $x_{i}\neq y_{i}$; this weight is $0$
when $x_{\vec{i}}=y_{\vec{i}}$ and at least $1$ when $x_{\vec{i}}\neq
y_{\vec{i}}$. This weight can be represented as a sum over $i\in\vec{i}$ with
$x_{i}\neq y_{i}$, since we are counting $\vec{i}$ once for each such $i$ in
the tuple.

The fifth line flips the order of the sums, and the sixth uses orthogonality
of the images of $\Pi_{\vec{i}}$ to put the sum back inside the squared norm.
The seventh line is the definition of $\Pi_{i}$, and the eighth holds since
$\Pi_{i}$ commutes with $U^{x}$ and $U^{y}$. Finally, the last line follows
either from the triangle inequality, or from the fact that the spectral norm
of $(U^{x}-U^{y})$ is at most $2$ (since $U^{x}$ and $U^{y}$ are unitary). ∎

For an oracle $x\in\\{0,1\\}^{n}$ and a block $B\subseteq[N]$, use $x[B]$ to
denote the string $x$ with queries in $B$ erased; that is, $x[B]_{i}=x_{i}$ if
$i\notin B$, and $x[B]_{i}=0$ for $i\in B$. Next, we use this hybrid argument
in combination with a Markov inequality to show that if a distribution $\mu$
over $\\{0,1\\}^{n}$ has a set of queries $B\in[N]$ that nearly always return
zero for oracles sampled from $\mu$, then for any non-adaptive quantum
algorithm, there exists a large set of oracles (measured against $\mu$) such
that the algorithm does not detect whether any subset of $B$ is erased.

######  Lemma 19 (Nonadaptive algorithms don’t detect oracle erasures).

Fix $\ket{\psi}$ representing the state of a quantum algorithm before a batch
of non-adaptive queries. Let $\mu$ be a distribution over $\\{0,1\\}^{N}$, and
let $\epsilon>0$. Let $B=\\{i\in[N]:\Pr_{x\sim\mu}[x_{i}=1]\leq\epsilon\\}$.
Then there exists a set $S\subseteq\\{0,1\\}^{N}$ such that $\mu[S]\geq 1/2$
and for all $x\in S$ and all subsets $B_{1},B_{2}\subseteq B$, we have

$\|U^{x[B_{1}]}\ket{\psi}-U^{x[B_{2}]}\ket{\psi}\|_{2}\leq\sqrt{8\epsilon T}.$

###### Proof.

We write the following, with justification afterwards.

$\displaystyle\operatorname*{\mathbb{E}}_{x\sim\mu}\left[\sum_{i:x_{i}\neq
x[B]_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{x\sim\mu}\left[\sum_{i\in
B}x_{i}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\right]$ $\displaystyle=\sum_{i\in
B}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\operatorname*{\mathbb{E}}_{x\sim\mu}[x_{i}]$
$\displaystyle\leq\epsilon\sum_{i\in B}\|\Pi_{i}\ket{\psi}\|_{2}^{2}$
$\displaystyle\leq\epsilon\sum_{i\in[N]}\|\Pi_{i}\ket{\psi}\|_{2}^{2}$
$\displaystyle=\epsilon\sum_{i\in[N]}\sum_{\vec{i}\ni
i}\|\Pi_{\vec{i}}\ket{\psi}\|_{2}^{2}$ $\displaystyle=\epsilon
T\sum_{\vec{i}}\|\Pi_{\vec{i}}\ket{\psi}\|_{2}^{2}$ $\displaystyle=\epsilon
T.$

The first line follows by noting that $x_{i}\neq x[B]_{i}$ can only happen if
both $i\in B$ and $x_{i}=1$; we replace the sum over $i:x_{i}\neq x[B]_{i}$
with the sum over $i\in B$, and multiply the summand by the indicator for
$x_{i}=1$, which is $x_{i}$ itself.

The second line is the result of pushing the expectation inside the sum, and
observing that the norm does not depend on $x$ and can be factored out of the
expectation. The third line follows from the definition of $B$: we know that
for all $i\in B$, the probability of $x_{i}=1$ is at most $\epsilon$. The
fourth replaces the sum over $B$ with that over $[N]$. The fifth uses the
definition of $\Pi_{i}$, and exchanges the sum over $\vec{i}$ with the squared
norm using orthogonality. The sixth line follows by noting that each $\vec{i}$
appears exactly $T$ times in this double sum. Finally, the last line follows
by pushing the sum inside the squared norm (using orthogonality), and
recalling that $\sum_{\vec{i}}\Pi_{\vec{i}}=I$, together with the fact that
$\ket{\psi}$ is a unit vector.

Given this bound on the expectation, we can apply Markov’s inequality to
conclude that at least half the strings $x$ (weighted by $\mu$) must satisfy
$\sum_{i:x_{i}\neq x[B]_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\leq 2\epsilon T$.
Let $S$ be the set of such strings $x$; then $\mu[S]\geq 1/2$. Observe that
for any $x\in S$ and any $B_{1},B_{2}\subseteq B$, the set
$\\{i:x[B_{1}]_{i}\neq x[B_{2}]_{i}\\}$ is a subset of $\\{i:x_{i}\neq
x[B]_{i}\\}$. We now apply Lemma 18 to get

$\|U^{x[B_{1}]}\ket{\psi}-U^{x[B_{2}]}\ket{\psi}\|_{2}^{2}\leq
4\sum_{i:x[B_{1}]_{i}\neq x[B_{2}]_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\leq
4\sum_{i:x_{i}\neq x[B]_{i}}\|\Pi_{i}\ket{\psi}\|_{2}^{2}\leq 8\epsilon T.$

The desired result follows by taking square roots. ∎

We will need some properties of distributions on $\\{0,1\\}^{N}$. For such a
distribution $\mu$, let
$\operatorname{RU}(\mu)\coloneqq\max_{x\in\\{0,1\\}^{N}}\log_{2}(2^{N}\mu[x])$
be the max relative entropy of $\mu$ relative to the uniform distribution. We
will generally be interested in distributions $\mu$ such that
$\operatorname{RU}(\mu)$ is small (say, $\operatorname{polylog}N$), which
means that no input $x\in\\{0,1\\}^{N}$ has probability $\mu[x]$ much larger
than $2^{-N}$.

For a partial assignment $p$, let $\mu[p]$ be the probability mass of strings
in $\\{0,1\\}^{N}$ which are consistent with $p$. Let $|p|$ be the size of $p$
(the number of revealed bits in $p$). We define the density of $\mu$ to be
$\operatorname{density}(\mu)\coloneqq
1-\max_{p}\frac{\log_{2}(2^{|p|}\mu[p])}{|p|}$, with the maximum taken over
partial assignments $p$. The density of the uniform distribution is $1$.

For a partial assignment $p$, we let $\mu|_{p}$ denote the distribution $\mu$
conditioned on the sampled input being consistent with $p$.

######  Lemma 20 (Densification).

Let $\mu$ be a distribution over $\\{0,1\\}^{N}$, and let $\delta\in(0,1)$.
Then there exists a partial assignment $p$ such that

  1. 1.

$|p|\leq\operatorname{RU}(\mu)/\delta$

  2. 2.

$\operatorname{RU}(\mu|_{p})\leq\operatorname{RU}(\mu)/\delta$

  3. 3.

$\operatorname{density}(\mu|_{p})>1-\delta$, where the density is measured on
the bits not fixed by $p$.

###### Proof.

Let $p$ be the largest partial assignment for which $\mu[p]\geq
2^{-(1-\delta)|p|}$. Then

$2^{-(1-\delta)|p|}\leq\mu[p]=\sum_{x\supseteq p}\mu[x]\leq 2^{N-|p|}\cdot
2^{-(N-\operatorname{RU}(\mu))}=2^{\operatorname{RU}(\mu)-|p|},$

so $\delta|p|\leq\operatorname{RU}(\mu)$, from which the first item follows.
Next,

$\operatorname{RU}(\mu|_{p})=\max_{x}\log_{2}(2^{N}\mu|_{p}[x])=\max_{x\supseteq
p}\log_{2}(2^{N}\mu[x]/\mu[p])\leq\operatorname{RU}(\mu)+\log_{2}(1/\mu[p])$
$\leq\operatorname{RU}(\mu)+\log_{2}(2^{(1-\delta)|p|})=\operatorname{RU}(\mu)+(1-\delta)|p|\leq\operatorname{RU}(\mu)+(1-\delta)\operatorname{RU}(\mu)/\delta=\operatorname{RU}(\mu)/\delta,$

which gives the second item. Finally, to upper bound the density of
$\mu|_{p}$, let $q$ be a partial assignment on a set of indices disjoint from
that of $p$. By the maximality of $p$, we must have $\mu[p\cup
q]<2^{-(1-\delta)(|p|+|q|)}$. Now,

$\log_{2}(2^{|q|}\mu|_{p}[q])=\log_{2}(2^{|q|}\mu[q\cup
p]/\mu[p])<\log_{2}(2^{|q|}2^{-(1-\delta)(|p|+|q|)}/2^{-(1-\delta)|p|})=\delta|q|.$

From this it follows that $\operatorname{density}(\mu|_{p})>1-\delta$, as
desired. ∎

###  4.3 QCMA lower bound

######  Theorem 21.

There is no bounded-round, polynomial-cost QCMA protocol for the family
$F_{N}$ defined in Section 4.1. More formally, consider any family of QCMA
protocols for the query problems $F_{N}$. If the number of rounds for these
QCMA protocols grows slower than $o(\log\log N/\log\log\log N)$, then either
the number of queries or the witness size must grow like $\log^{\omega(1)}N$.

###### Proof.

Consider a QCMA verifier for the query task $F_{N}$. Let $k=k(N)$ denote the
witness size for this verifier; we can assume for contradiction that
$k(N)=O(\operatorname{polylog}(N))=O(\operatorname{poly}n)$. Since the witness
is a classical string, there are only $2^{k}$ witnesses over which we
quantify. Since each $1$-input $O[f,\emptyset]$ has some witness accepting it,
we conclude that at least one witness $w$ of size $k$ is a valid witness for
at least a $2^{-k}$ fraction of the $1$-inputs, and hence also for at least a
$2^{-k}(1-2^{-\Omega(n)})$ fraction of all oracles $O[f,\emptyset]$ (including
those not in the domain of $F_{N}$). This is because the fraction of $f$s for
which the quantum algorithm does not succeed with probability at least $2/3$
is at most $2^{-\Omega(n)}$. We can assume $2^{-k}(1-2^{-\Omega(n)})\geq
2^{-2k}$.

Let $S$ be the set of $f$ such that $O[f,\emptyset]$ is accepted by the
algorithm given witness $w$. Let $\mu$ be the uniform distribution over $S$,
and observe that $\operatorname{RU}(\mu)\leq 2k$. Let $Q$ be the quantum
algorithm which hard-codes the witness $w$ into the verifier; then $Q$ accepts
all oracles $O[f,\emptyset]$ for $f\in\operatorname{supp}(\mu)$ and rejects
all oracles $O[f,E]$ if $|E|\geq(2/3)2^{n}$.

We now proceed by iteratively removing rounds of $Q$. We define a sequence of
quantum algorithms $Q=Q_{0},Q_{1},\dots,Q_{r-1},Q_{r}$, where $Q_{\ell}$ has
$r-\ell$ rounds of $T$ queries each; at the beginning, $Q_{0}=Q$ has $r$
rounds, and at the end, $Q_{r}$ makes no queries. We also define a
corresponding sequence of distributions
$\mu=\mu_{0},\mu_{1},\dots,\mu_{r-1},\mu_{r}$, each of which will be uniform
over a set of functions $f$; this set will grow smaller with each round.

To define $(Q_{\ell+1},\mu_{\ell+1})$ given $(Q_{\ell},\mu_{\ell})$, we
proceed in several steps.

  1. 1.

First, use Lemma 20 with $\delta=1/n$ to find a partial assignment $q$ with
$|q|\leq n\operatorname{RU}(\mu_{\ell})$,
$\operatorname{RU}(\mu_{\ell}|_{q})\leq n\operatorname{RU}(\mu_{\ell})$, and
with $\mu_{\ell}|_{q}$ being $(1-\delta)$-dense on the bits not used by $q$.

  2. 2.

Second, use Lemma 19 with $\epsilon=1/3200r^{2}T$ on the distributions of
oracles $O[f,\emptyset]$ when $f$ is sampled from $\mu_{\ell}|_{q}$. The state
$\ket{\psi}$ in the lemma will be the state of the algorithm $Q$ just before
the first batch of $T$ queries. The lemma gives a set
$S\subseteq\operatorname{supp}(\mu_{\ell}|_{q})$ with $\mu_{\ell}|_{q}[S]\geq
1/2$. It has the property that for all $f\in S$ and all sets $B_{1},B_{2}$
containing pairs $(x,u)$ with
$\Pr_{f\sim\mu_{\ell}|_{q}}[O[f,\emptyset](x,u)=1]\leq\epsilon$, we have
$\|U^{O[f,B_{1}]}\ket{\psi}-U^{O[f,B_{2}]}\ket{\psi}\|_{2}\leq 1/20r$.
Condition $\mu_{\ell}|_{q}$ on the set $S$ to get a distribution
$\mu^{\prime}_{\ell}$.

Note that $O[f,B_{1}]$ is an abuse of notation, since normally we erase inputs
$x$ to $f$ from the oracle, yet $B_{1}$ is a set of pairs $(x,u)$. We will use
this abuse of notation throughout; if we write $O[f,B]$ where $B$ is a set of
pairs, we mean to erase those pairs from the oracle, while if $B$ is a subset
of $\operatorname{Dom}(f)$, we mean to erase the pairs $(x,u)$ for $x\in B$
and all $u$ from the oracle.

  3. 3.

Third, use the slippery property from Corollary 15 on $q$ to conclude that the
number of bits used by partial assignments $p$ for which
$(p,x,u)\in\tilde{R}_{C}$ and $\Pr_{f\sim\mu^{\prime}_{\ell}}[p\subseteq
f|q\subseteq f]\geq\epsilon/4$ is small. Recall that $(p,x,u)\in\tilde{R}_{C}$
means that the condition $O[f,\emptyset](x,u)=1$ is equivalent to $p\subseteq
f$ for all $f$; such certifying $p$ have $|p|=n$. Corollary 15 can be applied
because $\epsilon/4$ is larger than $1/n^{c}$ for $c=\log n$, since we are
choosing $r=o(\log n/\log\log n)$ and $T\leq O(2^{\log^{2}n}/\log n)$. Now,
since $\mu_{\ell}|_{q}$ is $(1-\delta)$-dense outside of $q$, the probability
of a partial assignment $p$ against $\mu_{\ell}|_{q}$ is at most
$2^{\delta|p|}$ times the probability against the uniform distribution
conditioned on $q$. Here $|p|=n$ and $\delta=1/n$, so the probability against
$\mu_{\ell}|_{q}$ is at most twice that against the uniform distribution
conditioned on $q$. Moving from $\mu_{\ell}|_{q}$ to $\mu_{\ell}^{\prime}$
conditions on a set $S$ of probability at least $1/2$, so it can increase the
probability of $p$ by at most a factor of $2$. Hence the probability of $p$
against $\mu^{\prime}_{\ell}$ is overall at most 4 times its probability
against the uniform distribution. By Corollary 15, we conclude the total
number of bits used by partial assignments $p$ for which
$\Pr_{f\sim\mu_{\ell}^{\prime}}[O[f,\emptyset](x,u)=1]\geq\epsilon$ is small.
Let $Z$ be the set of all such bits.

Our next modification to $\mu_{\ell}^{\prime}$ will be to fix the bits in $Z$
to the highest-probability partial assignment (measured against
$\mu_{\ell}^{\prime}$), and let $\mu_{\ell}^{\prime\prime}$ be
$\mu_{\ell}^{\prime}$ conditioned on that partial assignment being consistent
with the sampled function $f$.

  4. 4.

Finally, set $\mu_{\ell+1}=\mu_{\ell}^{\prime\prime}$. Also set $Q_{\ell+1}$
to be the quantum algorithm which is the same as $Q_{\ell}$, except that the
first batch of queries is made to a fake oracle instead of a real one. The
fake oracle is defined as follows: on queries $(x,u)$ for which
$O[f,\emptyset](x,u)$ is fixed for all
$f\in\operatorname{supp}(\mu_{\ell+1})$, return this value
$O[f,\emptyset](x,u)$; on queries $(x,u)$ for which this value is not fixed
for $f\in\operatorname{supp}(\mu_{\ell+1})$, return $0$. Note that the fake
oracle does not depend on the true input oracle $O[f,E]$, so queries to it can
be implemented by $Q_{\ell+1}$ with making queries to the real oracle. This
replaces the first round of $Q_{\ell}$, so $Q_{\ell+1}$ has one less round.

Our approach will work as follows: we start with a function
$f\in\operatorname{supp}(\mu_{r})$, and find a large set $E$ of inputs $x$ for
which $(x,u)$ were not fixed by $\operatorname{supp}(\mu_{r})$. We will then
argue that the quantum algorithms in the sequence cannot distinguish the
oracles $O[f,\emptyset]$ and $O[f,E]$. This is clear for the last algorithm
$Q_{r}$, since it makes no queries. We work backwards to show that each
algorithm $Q_{r-1}$, $Q_{r-2}$, up to $Q_{0}$ also cannot substantially
distinguish between these two oracles. This gives a contradiction, since we
know $Q$ accepts the oracle $O[f,\emptyset]$, yet $O[f,E]$ is a $0$-input.

In order to find $f$ and $E$, we first show that $\operatorname{RU}(\mu_{r})$
is not too large. Recall that $\operatorname{RU}(\mu_{0})\leq 2k$. We will
show that $\operatorname{RU}(\cdot)$ did not increase too much in each of the
$r$ iterations that got us from $\mu_{0}$ to $\mu_{r}$. In one iteration, we
defined $\mu_{\ell+1}$ from $\mu_{\ell}$ in $3$ steps. The first step moved
from $\mu_{\ell}$ to $\mu_{\ell}|_{q}$ with
$\operatorname{RU}(\mu_{\ell}|_{q})\leq n\operatorname{RU}(\mu_{\ell})$. The
second step conditioned the latter distribution on a set $S$ of probability
mass at least $1/2$, which can only increase $\operatorname{RU}(\cdot)$ by
$1$, so $\operatorname{RU}(\mu_{\ell}^{\prime})\leq
n\operatorname{RU}(\mu_{\ell})+1$.

The third step found the set of all bits fixed in partial assignments $p$
which certify some $(x,u)$ as evaluating to $1$, and picked the highest-
probability partial assignment on those bits. The maximum increase in
$\operatorname{RU}(\cdot)$ is the number of bits that were fixed in this way.
This number comes from Theorem 16, and depends on the number of bits fixed in
$q$; when $|q|=2^{(\log n)^{d}}$, the number we are looking for is
$2^{(c+2)(\log n)^{d+1}}$, so we can express this as $2^{(c+2)(\log
n)(\log|q|)}$. We had $|q|\leq n\operatorname{RU}(\mu_{\ell})$ and $c=\log n$.
It is not hard to see that this additive increase dominates
$n\operatorname{RU}(\mu_{\ell})+1$; assuming everything is large enough (e.g.
$\log n$ is sufficiently large, and $\operatorname{RU}(\mu_{\ell})$ is at
least $n^{2}$, which is without loss of generality by restricting the original
$\mu_{0}$ to a smaller set if necessary), we can get the final upper bound
$\operatorname{RU}(\mu_{\ell+1})\leq 2^{(3+\log
n)^{2}\log\operatorname{RU}(\mu_{\ell})}$.

In other words, $\log\operatorname{RU}(\mu_{\ell})$ increases by a factor of
at most $(3+\log n)^{2}$ in each iteration, starting at
$\log\max\\{2k,n^{2}\\}\leq(3+\log n)\log k$ (assuming $k\geq 2$). We
therefore have $\log\operatorname{RU}(\mu_{r})\leq(3+\log n)^{2r+1}\log k$.

We next essentially apply another iteration (without the second step) to
$\mu_{r}$. Using Lemma 20, we find a partial assignment $q^{\prime}$ such that
$\mu_{r}|_{q^{\prime}}$ is $(1-\delta)$-dense outside of $q^{\prime}$, with
$\delta=1/n$. We then apply Theorem 16 to conclude there are few pairs $(x,u)$
with $\Pr_{f}[O[f,\emptyset](x,u)=1]\geq 1/2$, and hence few pairs $(x,u)$
with $\Pr_{f}[O[f,\emptyset](x,u)=1]=1$ when $f$ is sampled from
$\mu_{r}|_{q^{\prime}}$; the number of such pairs is at most $2^{(3+\log
n)^{2r+3}\log k}$. Using $k=O(\operatorname{poly}(n))$ and $r=o(\log
n/\log\log n)$, this means that there are at most $2^{o(n)}$ pairs $(x,u)$
that are fixed to $1$ for all the oracles $O[f,\emptyset]$ for
$f\in\operatorname{supp}(\mu_{r}|_{q^{\prime}})$. Therefore, there are
$2^{n-o(n)}$ many inputs $x$ such that for all $u$, the pair $(x,u)$ is not
fixed to $1$ by $\operatorname{supp}(\mu_{r}|_{q^{\prime}})$. Let $E$ be the
set of such $x$; then $|E|\geq(2/3)2^{n}$. Let
$\hat{f}\in\operatorname{supp}(\mu_{r}|_{q^{\prime}})$ be arbitrary.

We now know that $Q$ accepts $O[\hat{f},\emptyset]$ and that $O[\hat{f},E]$ is
a $0$-input. We also know that $Q_{r}$ cannot distinguish
$O[\hat{f},\emptyset]$ and $O[\hat{f},E]$, since it makes no queries. Now, let
$B=\\{(x,u):x\in E,O[\hat{f},\emptyset](x,u)=1\\}$. Moreover, let $B_{\ell}$
be the set of pairs $(x,u)$ which had
$\Pr_{f\sim\mu_{\ell-1}|_{q}}[O[f,\emptyset](x,u)=1]\leq\epsilon$ in iteration
$\ell$ (where $q$ is the partial assignment from step 1 of iteration $\ell$).
Note that the pairs not in $B_{\ell}$ are all fixed in all the oracles in the
support of $\mu_{\ell}$, because we choose values for the bits used by their
proving partial assignments $p$. This means that $B\subseteq B_{\ell}$ for all
$\ell$. Also, let $O_{\ell}$ be the oracle used by $Q_{\ell}$ to simulate the
first query batch of $Q_{\ell-1}$. Recall that $O_{\ell}(x,u)$ returns $0$
unless $(x,u)$ is fixed to $1$ in all $O[f,\emptyset]$ for
$f\in\operatorname{supp}(\mu_{\ell})$. Since the support of $\mu_{\ell}$
decreases as a subset in each iteration, the bits fixed in $\mu_{\ell}$ are
also fixed in $\mu_{r}$, and hence also agree with $\hat{f}$. This means that
$O_{\ell}$ can be written as an erased oracle $O[\hat{f},A_{\ell}]$ for some
set $A_{\ell}$ of pairs $(x,u)$ that were not fixed in $\mu_{\ell}$; in other
words, $A_{\ell}\subseteq B_{\ell}$.

We now note the oracle $O[\hat{f},E]$ is the same as $O[\hat{f},B]$.
Additionally, since $B,A_{\ell}\subseteq B_{\ell}$, we have by Lemma 19,

$\|U^{O[\hat{f},B]}\ket{\psi}-U^{O[\hat{f},A_{\ell}]}\ket{\psi}\|_{2}\leq
1/20r$

where $\ket{\psi}$ is the state right before the first query of the algorithm
$Q_{\ell-1}$. This can also be written

$\|U^{O[\hat{f},E]}\ket{\psi}-U^{O_{\ell}}\ket{\psi}\|_{2}\leq 1/20r.$

Now, applying additional unitary matrices does not change the $2$-norm, and
$Q_{\ell}$ replaces only the first query of $Q_{\ell-1}$ with $O_{\ell}$ and
applies the same unitaries as $Q_{\ell-1}$ in all other rounds. If we use
$Q_{\ell}(O)$ to denote the final state of $Q_{\ell}$ on the oracle $O$, we
therefore get

$\|Q_{\ell}(O[\hat{f},E])-Q_{\ell-1}(O[\hat{f},E])\|_{2}\leq 1/20r.$

By triangle inequality, we then get

$\|Q(O[\hat{f},E])-Q_{r}(O[\hat{f},E])\|_{2}\leq 1/20.$

Since $\emptyset\subseteq B_{\ell}$ for all $\ell$, the same argument also
works to show that

$\|Q(O[\hat{f},\emptyset])-Q_{r}(O[\hat{f},\emptyset])\|_{2}\leq 1/20,$

and of course we also have $Q_{r}(O[\hat{f},\emptyset])=Q_{r}(O[\hat{f},E])$
since $Q_{r}$ makes no queries. A final application of the triangle inequality
gives us

$\|Q(O[\hat{f},E])-Q(O[\hat{f},\emptyset])\|_{2}\leq 1/10.$

Since measuring the output qubit of $Q(O[\hat{f},\emptyset])$ gives $1$ with
probability at least $2/3$, it is not hard to show that this implies measuring
the output qubit of $Q(O[\hat{f},E])$ gives $1$ with probability above $1/2$.
This gives the desired contradiction, since the latter is a $0$-input. ∎

## References

  * [ABK23] Scott Aaronson, Harry Buhrman and William Kretschmer  “A Qubit, a Coin, and an Advice String Walk Into a Relational Problem”, 2023  DOI: 10.48550/arXiv.2302.10332
  * [AK07] Scott Aaronson and Greg Kuperberg  “Quantum versus Classical Proofs and Advice”  In _Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07)_ , 2007, pp. 115–128  DOI: 10.1109/CCC.2007.27
  * [AN02] Dorit Aharonov and Tomer Naveh  “Quantum NP - A Survey”, 2002  DOI: 10.48550/arXiv.quant-ph/0210077
  * [BBBV97] Charles H. Bennett, Ethan Bernstein, Gilles Brassard and Umesh Vazirani  “Strengths and Weaknesses of Quantum Computing”  In _SIAM Journal on Computing_ 26, 1997, pp. 1510–1523  DOI: 10.1137/S0097539796300933
  * [BFM23] Roozbeh Bassirian, Bill Fefferman and Kunal Marwaha  “On the Power of Nonstandard Quantum Oracles”  In _18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)_ 266, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, pp. 11:1–11:25  DOI: 10.4230/LIPIcs.TQC.2023.11
  * [CDGS18] Sandro Coretti, Yevgeniy Dodis, Siyao Guo and John Steinberger  “Random Oracles and Non-uniformity”  In _Advances in Cryptology – EUROCRYPT 2018_ Cham: Springer International Publishing, 2018, pp. 227–258
  * [FK18] Bill Fefferman and Shelby Kimmel  “Quantum vs. Classical Proofs and Subset Verification”  In _43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)_ 117, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, pp. 22:1–22:23  DOI: 10.4230/LIPIcs.MFCS.2018.22
  * [GPW17] Mika Göös, Toniann Pitassi and Thomas Watson  “Query-to-communication lifting for BPP”  In _Proceedings of the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS)_ , 2017  DOI: 10.1109/FOCS.2017.21
  * [Liu23] Qipeng Liu  “Non-uniformity and Quantum Advice in the Quantum Random Oracle Model”  In _Advances in Cryptology – EUROCRYPT 2023_ Cham: Springer Nature Switzerland, 2023, pp. 117–143
  * [LLPY23] Xingjian Li, Qipeng Liu, Angelos Pelecanos and Takashi Yamakawa  “Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle”, 2023  DOI: 10.48550/arXiv.2303.04298
  * [NN23] Anand Natarajan and Chinmay Nirkhe  “A Distribution Testing Oracle Separating QMA and QCMA”  In _38th Computational Complexity Conference (CCC 2023)_ 264, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023, pp. 22:1–22:27  DOI: 10.4230/LIPIcs.CCC.2023.22
  * [RT19] Ran Raz and Avishay Tal  “Oracle Separation of BQP and PH”  In _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2019  Phoenix, AZ, USA: Association for Computing Machinery, 2019, pp. 13–23  DOI: 10.1145/3313276.3316315
  * [Rud07] Atri Rudra  “List Decoding and Property Testing of Error Correcting Codes”, 2007  URL: https://cse.buffalo.edu/faculty/atri/papers/coding/thesis.html
  * [YZ22] Takashi Yamakawa and Mark Zhandry  “Verifiable Quantum Advantage without Structure”  In _2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)_ , 2022, pp. 69–74  DOI: 10.1109/FOCS54457.2022.00014

##  Appendix A Diagonalization argument

###  A.1 QMA and QCMA for Turing machines

In this section, we formally define $\mathsf{QMA},\mathsf{QCMA}$, the oracle
classes and bounded-round oracle classes corresponding to these.

######  Definition 22 (Oracle-querying quantum verifier circuit).

An _oracle-querying quantum verifier circuit (OQQV_ is the following type of
quantum circuit. It takes in three types of input sets of qubits: one set of
qubits representing the input string $x$; a second set of qubits representing
a witness state; and a third set of ancilla qubits. It has gates from a
universal gate set, but it can additionally use a special oracle gate. The
oracle gate can take in any number $k$ of qubits, and gives $k$ qubits as
output.

For any oracle $\mathcal{O}\colon\\{0,1\\}^{*}\to\\{0,1\\}$, the behavior of
the oracle gates in a quantum verifier circuit that is instantiated with
oracle $\mathcal{O}$ is as follows: each $k$-qubit basis state is mapped
$\ket{y}\to(-1)^{\mathcal{O}(y)}\ket{y}$ by the $k$-qubit oracle gate.

If $C$ is an OQQV, $x$ is an input, $\ket{\phi}$ is a witness, and
$\mathcal{O}$ is an oracle, then let $C^{\mathcal{O}}(x,\phi)$ denote the
Bernoulli random variable which is the measurement outcome of the first output
qubit of the circuit $C$ when run on input $x$, witness $\phi$, and zeroes for
the ancilla qubits, assuming the oracle gates of $C$ apply the oracle
$\mathcal{O}$.

######  Definition 23 (Soundness and Completeness).

Let $\mathcal{O}\colon\\{0,1\\}^{*}\to\\{0,1\\}$ be an oracle, let
$n\in\operatorname{\mathbb{N}}$, let $C$ be an OQQV with $n$ input qubits, and
let $f$ be a partial function from $\\{0,1\\}^{n}$ to $\\{0,1\\}$.

  1. 1.

We say that $C$ is _$\mathsf{QMA}$ -sense sound_ for $f$ relative to
$\mathcal{O}$ if for every input $x\in f^{-1}(0)$ and every state $\ket{\phi}$
(on a number of qubits equal to the witness size of $C$), we have
$\Pr[C^{\mathcal{O}}(x,\phi)=1]\leq 1/3$. The constant $1/3$ is called the
$\mathsf{QMA}$-sense soundness of $C$.

  2. 2.

We say that $C$ is _$\mathsf{QCMA}$ -sense sound_ for $f$ relative to
$\mathcal{O}$ if the same condition holds, but only for all classical strings
$\ket{\phi}$ instead of all pure states. Note that $\mathsf{QMA}$-soundness
implies $\mathsf{QCMA}$-soundness.

  3. 3.

We say that $C$ is _$\mathsf{QMA}$ -sense complete_ for $f$ relative to
$\mathcal{O}$ if for every input $f^{-1}(1)$, there exists a state
$\ket{\phi}$ (on the right number of qubits) such that
$\Pr[C^{\mathcal{O}}(x,\phi)=1]\geq 2/3$. The constant $1-2/3$ is called the
$\mathsf{QMA}$-sense completeness of $C$.

  4. 4.

We say that $C$ is _$\mathsf{QCMA}$ -sense complete_ for $f$ relative to
$\mathcal{O}$ if the same condition holds with a classical witness: for every
$x\in f^{-1}(1)$, there exists a classical string $\ket{\phi}$ that the
circuit accepts. Note that $\mathsf{QCMA}$-sense completeness implies
$\mathsf{QMA}$-sense completeness.

######  Definition 24 (Oracle QMA and QCMA).

A $\mathsf{QMA}$ protocol for a language $L\subseteq\\{0,1\\}^{*}$ relative to
an oracle $\mathcal{O}$ is a polynomial-time Turing machine $M$ which, on
input $0^{n}$, outputs an OQQV $C$ which is $\mathsf{QMA}$-sense sound and
complete for the indicator function of $L\cap\\{0,1\\}^{n}$. A $\mathsf{QCMA}$
protocol for $L$ relative to $\mathcal{O}$ is the same but with
$\mathsf{QCMA}$-sense soundness and completeness.

The class $\mathsf{QMA}^{\mathcal{O}}\subseteq\mathcal{P}(\\{0,1\\}^{*})$ is
the set of all languages $L$ for which there is a $\mathsf{QMA}$ protocol
relative to $\mathcal{O}$. Similarly, the class $\mathsf{QCMA}^{\mathcal{O}}$
is the set of all languages for which there is a $\mathsf{QCMA}$ protocol
relative to $\mathcal{O}$.

Observe that $\mathsf{QCMA}^{\mathcal{O}}\subseteq\mathsf{QMA}^{\mathcal{O}}$.
This is because if we had a $\mathsf{QCMA}$ protocol for $L$ relative to
$\mathcal{O}$, we could modify each OQQV it outputs to make the circuit
“measure” the witness before proceeding (by making an untouched copy of each
qubit of the witness). After this modification, the $\mathsf{QCMA}$-sense
soundness will imply $\mathsf{QMA}$-sense soundness, so the resulting OQQV
will be $\mathsf{QMA}$-sense sound and complete. A Turing machine can
implement this modification, and such a TM will be a $\mathsf{QMA}$ protocol
for $L$ relative to $\mathcal{O}$.

######  Definition 25 (Bounded round QMA and QCMA).

We define a bounded-round OQQV circuit in the natural way (a quantum circuit
that has polynomially many oracle gates in parallel in each ”round”, and a
bounded number of such rounds).

For a function $r\colon\operatorname{\mathbb{N}}\to\operatorname{\mathbb{N}}$,
we define $\mathsf{QMA}^{O,r}$ to be the $r$-bounded-round version of
$\mathsf{QMA}$ relative to the oracle $O$; this measure allows $\mathsf{QMA}$
protocols which, on input $0^{n}$, generate an OQQV circuit which uses at most
$r(n)$ rounds of queries to the oracle and is otherwise a valid $\mathsf{QMA}$
oracle. We define $\mathsf{QCMA}^{O,r}$ similarly.

###  A.2 From query separation to oracle separation

######  Theorem 26.

Theorem 2 implies Theorem 1.

###### Proof.

Let $F=\\{f_{n}\\}_{n\in I}$ be a funcion family which is efficiently
computable in $\mathsf{QMA}^{1}$ but for which the growth rate of
$\mathsf{QCMA}^{r}(f_{n})$ as $n\to\infty$ is not in
$O(\operatorname{polylog}(n))$, for $r=o(\log\log n/\log\log\log n)$. Let
$R(n)$ be some $o(\log n/\log\log n)$ function. We need to construct an oracle
$\mathcal{O}\colon\\{0,1\\}^{*}\to\\{0,1\\}$ and a language
$L\subseteq\\{0,1\\}^{*}$ such that $L\in\mathsf{QMA}^{\mathcal{O},R}$ but
$L\notin\mathsf{QCMA}^{\mathcal{O},R}$.

We interpret the oracle $\mathcal{O}$ as taking as input either a pair of
positive integers $(n,i)$, or else a single integer $n$ (the encoding will
specify the formatting unambiguously). On inputs $n$, the oracle
$\mathcal{O}(n)$ behaves like an indicator for the set $I$, returning $1$ if
$n\in I$ and $0$ if $n\notin I$. On input $(n,i)$, if $n\in I$, the oracle
will return $x^{n}_{i}$, where $x^{n}$ is a specific string in
$\operatorname{Dom}(f_{n})$ that we will choose later. If $n\notin I$, the
oracle returns arbitrarily (its behavior won’t matter). The oracle’s behavior
on inputs that are incorrectly formatted is also arbitrary. This completes the
specification of the oracle $\mathcal{O}$, except for the choice of strings
$x^{n}$ for $n\in I$ (one string from the domain of each $f_{n}$ function).

The language $L$ will contain the encodings $\langle n\rangle$ of all $n\in I$
for which $f_{n}(x^{n})=1$. We’ve now specified both the language $L$ and the
oracle $\mathcal{O}$ except for the choice of strings $x^{n}$.

We note that regardless of the choice of strings $x^{n}$, we will have
$L\in\mathsf{QMA}^{\mathcal{O},R}$. To see this, observe that using Definition
9 we can get a polynomial-time Turing machine $M$ which takes in $\langle
n\rangle$ and returns a $\operatorname{polylog}(n)$-sized $R$-round OQQV
$C_{n}$ which, assuming it runs on an oracle $\mathcal{O}$ that encodes the
string $x$, will accept some witness if $f(x)=1$ and reject all witnesses if
$f(x)=0$. This Turing machine maps $\langle n\rangle$ to an OQQV circuit, but
we can convert it to a classical circuit which maps $\langle n\rangle$ to an
OQQV circuit for all $\langle n\rangle$ of a fixed size – that is, for all $n$
in an interval $[2^{k},2^{k+1})$. We could then collapse this circuit-
outputting-a-circuit into a single OQQV circuit, which takes in $\langle
n\rangle$ and a witness (and ancillas) and, after making queries to
$\mathcal{O}$in $R$ rounds, decides whether to accept or reject the witness.
Moreover, these OQQV circuits can be generated uniformly by a Turing machine
that takes a size $0^{k}$ as input and generates in polynomial time the
circuit which handles all $n\in[2^{k},2^{k+1})$. We can also easily modify
these OQQV circuits to have them query $\mathcal{O}(n)$ to ensure that $n\in
I$ before proceeding (rejecting otherwise). The resulting Turing machine is an
$R$-round $\mathsf{QMA}$ protocol for $L$ relative to $\mathcal{O}$, so
$L\in\mathsf{QMA}^{\mathcal{O},R}$.

It remains to select the inputs $x^{n}$, one per function $f_{n}$, in a way
that ensures $L\notin\mathsf{QCMA}^{\mathcal{O},R}$. We do so by
diagonalization. Enumerate all pairs $(M,\alpha)$ where $M$ is a candidate
$\mathsf{QCMA}^{R}$ protocol (i.e. a Turing machine that outputs $R$-round
OQQV circuits) and $\alpha$ is a growth rate in $O(\operatorname{poly}(n))$
(we can assume the function $\alpha(n)$ is always $n^{c}+c$ for some positive
integer $c$, to ensure that $\alpha(n)$ can be efficiently computable and that
there are countably many such growth rates).

We fix choices $x^{n}$ using an iterative procedure. At each step of the
iteration, there will be some cutoff $N\in\operatorname{\mathbb{N}}$ such that
$x^{n}$ has been fixed for all $n<N$, but $x^{n}$ has not yet been fixed for
all $n\geq N$. Each step $t$ of the procedure will eliminate the possibility
that for the $t$-th pair $(M,\alpha)$ in our enumeration, $M$ is a
$\mathsf{QCMA}^{R}$ protocol for $L$ relative to $\mathcal{O}$ which runs in
$\alpha(k)$ steps on inputs of size $k$ and produces an OQQV $C_{k}$ which
takes in a witness of size at most $\alpha(k)$ and makes at most $\alpha(k)$
queries to the oracle.

To handle the pair $(M,\alpha)$, we find the first $f_{n}$ such that $n\geq N$
and $\mathsf{QCMA}^{r}(f_{n})>2\alpha(|\langle n\rangle|)$. Note that
$|\langle n\rangle|=O(\log n)$, so $2\alpha(|\langle n\rangle|)$ is a growth
rate in $O(\operatorname{polylog}(n))$; therefore, there must be infinitely
many $f_{n}$ for which $\mathsf{QCMA}^{r}(f_{n})$ satisfies this condition.

Run $M(0^{k})$ for $\alpha(k)$ steps, where $k=|\langle n\rangle|$; if it does
not terminate, we consider the pair $(M,\alpha)$ handled, and move to the next
pair. We can thus assume it terminates, so let $C_{k}$ be the OQQV it outputs.
If $C_{k}$ takes in witnesses of size more than $\alpha(k)$ or if it makes
more than $\alpha(k)$ queries or $r(k)$ many rounds of queries to the oracle,
we again consider the pair $(M,\alpha)$ handled. We can thus assume $C_{k}$
uses witnesses of size at most $\alpha(k)$ and makes at most $\alpha(k)$
queries to the oracle in $r(k)$ rounds.

The circuit $C_{k}$, when given input $\langle n\rangle$, defines a query
$\mathsf{QCMA}^{r}$ protocol of cost at most $2\alpha(k)$: it takes in a
witness of size at most $\alpha(k)$ and makes at most $\alpha(k)$ queries in
$r$ rounds to the oracle. We note that the behavior of this query algorithm
might depend on the values of $\mathcal{O}$ that are outside of the input to
$f_{n}$; that is, on the values of $\mathcal{O}$ on oracle queries
$\mathcal{O}(m,i)$ for $m\neq n$. To ensure that the query algorithm is well-
defined, we fix all values of $\mathcal{O}$ that $C_{k}$ might query, except
for the values at $\mathcal{O}(n,i)$ (which will still encode an input
$x\in\operatorname{Dom}(f_{n})$). Note that $C_{k}$ has finite size and can
therefore only call $\mathcal{O}$ with finitely many input wires; we can thus
fix only finitely many positions of $\mathcal{O}$ when ensuring $C_{k}$ gives
rise to a well-defined query QCMA algorithm for $f_{n}$.

Since we’ve chosen $n$ so that $\mathsf{QCMA}^{r}(f_{n})>2\alpha(k)$, and
since the cost of this $r$-round QCMA protocol is only $2\alpha(k)$, it
follows that this $r$-round QCMA query protocol is either not sound or not
complete: there is an input $x\in\operatorname{Dom}(f_{n})$ on which this
query protocol misbehaves. We will pick this input as our choice for $x^{n}$.
This will ensure that $C_{k}$ either does not satisfy soundness for
$L\cap\\{0,1\\}^{k}$ or does not satisfy completeness, so $M$ is not a valid
$\mathsf{QCMA}^{r}$ protocol for $L$ relative to $\mathcal{O}$. We can then
set $N$ to be the new minimum number such that the oracle $\mathcal{O}$ is
unfixed for all $n\geq N$, and then move on to the next pair $(M,\alpha)$.

This procedure iteratively defines the sequence $x^{n}$. Each element in the
sequence is eventually defined, and they never change once defined. Therefore,
we get a well-defined infinite sequence $\\{x^{n}\\}_{n\in I}$, and we
conclude that the corresponding oracle $\mathcal{O}$ and language $L$ must
satisfy $L\notin\mathsf{QCMA}^{\mathcal{O},R}$. ∎