# Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle

Xingjian Li  Tsinghua University  Qipeng Liu  Simons Institute  Angelos
Pelecanos  UC Berkeley  Takashi Yamakawa  NTT Social Informatics Laboratories

###### Abstract

It is a long-standing open question to construct a classical oracle relative
to which $\BQP/\qpoly\neq\BQP/\poly$ or $\QMA\neq\QCMA$. In this paper, we
construct _classically-accessible classical oracles_ relative to which
$\BQP/\qpoly\neq\BQP/\poly$ and $\QMA\neq\QCMA$. Here, classically-accessible
classical oracles are oracles that can be accessed only classically even for
quantum algorithms. Based on a similar technique, we also show an alternative
proof for the separation of $\QMA$ and $\QCMA$ relative to a distributional
quantumly-accessible classical oracle, which was recently shown by Natarajan
and Nirkhe.

##  1 Introduction

Quantum information is often in possession of richer structures than classical
information, at least intuitively. The first (but often false) thought is that
phases and magnitudes are continuous, and a piece of quantum information may
be able to store exponentially or infinitely more information than classical
ones; which is always not true111As storing and extracting information takes
resources that scale with accuracy.. Since classical and quantum information
present distinct and unique natures, the community studies their differences
under different contexts and directions, including advice-aided quantum
computation [NY04, Aar05, Aar07, AD14, NABT14, HXY19, CLQ19, CGLQ20, GLLZ21,
Liu22], QMA vs QCMA (i.e., quantum NP with either quantum or classical
witness) [AN02, AK07, FK18, NN22], quantum vs classical communication
complexity [Yao93, BCW98, Raz99, AST+03, BYJK04, Gav08] and many others.

One way to understand their differences is by studying one-way communication
complexity: i.e., Alice and Bob want to jointly compute a function with their
private inputs, but only one-time quantum/classical communication from Alice
to Bob is allowed. Among many works, Bar-Yossef, Jayram, and Kerenidis
[BYJK04] showed an exponential separation between quantum and classical one-
way communication complexity, for the so-called hidden matching problem.

The other approach is by looking at QMA vs QCMA. In 2007, Aaronson and
Kuperberg [AK07] showed a black-box separation with respect to a black-box
quantum unitary and left the same separation with respect to a classical
oracle as an open question. More than a decade later, Fefferman and Kimmel
[FK18] proved a second black-box separation using a distributional in-place
oracle, which is a non-standard type of oracles. Recently, Natarajan and
Nirkhe [NN22] moved a step closer to the goal by presenting a black-box
separation with respect to a distributional oracle222In this case, the witness
only depends on the distribution. The oracle is later picked from the
distribution, but independent of the witness.. Therefore, we would like to
further investigate the difference between quantum and classical proofs, i.e.,
the separation between QMA vs QCMA. In this work, we address the question by
demonstrating a separation relative to a _classically accessible classical_
oracle.

######  Definition 1.1 (QMA).

A language $\cal L$ is said to be in QMA if there exists a quantum polynomial-
time machine $\mathcal{V}$ together with a polynomial $p(\cdot)$ such that,

  * •

For all $x\in{\cal L}$, there exists a quantum state $\ket{\psi_{x}}$ of at
most $p(|x|)$ qubits, such that $\mathcal{V}$ accepts on
$\ket{x},\ket{\psi_{x}}$ with a probability at least $2/3$.

  * •

For all $x\not\in{\cal L}$, for all quantum states $\ket{\psi_{x}}$ of at most
$p(|x|)$ qubits, $\mathcal{V}$ accepts on $\ket{x},\ket{\psi_{x}}$ with a
probability at most $1/3$.

One can similarly define the class QCMA except $\ket{\psi_{x}}$ are of
$p(|x|)$ classical bits.

We also aim to understand the difference between quantum and classical
information through advice-aided quantum computation. Classically, a piece of
advice can significantly speed up classical computation, from speeding up
exhaustive search [Hel80] to deciding the unary Halting Problem. In a quantum
world, advice can be either a piece of classical or quantum information. It is
very natural to ask the question: does quantum advice “outperform” classical
advice? Among many questions, one of the most fundamental is to understand the
power of BQP/qpoly and BQP/poly: i.e., the class of languages that can be
decided by bounded-error quantum machines with arbitrary bounded-length
quantum/classical advice and polynomial time.

######  Definition 1.2 (BQP/qpoly).

A language $\cal L$ is said to be in BQP/qpoly if and only if there exists a
quantum polynomial-time machine $\mathcal{A}$ together with a collection of
polynomial-sized quantum states $\\{\ket{z_{n}}\\}_{n\in\mathbb{N}}$ such
that,

  * •

For all $x\in{\cal L}$, $\Pr\left[\mathcal{A}(x,\ket{z_{|x|}})=1\right]\geq
2/3$.

  * •

For all $x\not\in{\cal L}$,
$\Pr\left[\mathcal{A}(x,\ket{z_{|x|}})=0\right]\geq 2/3$.

One can similarly define the class BQP/poly except $\ket{z_{n}}$ are poly-
sized classical strings.

Similar to the case of QMA vs QCMA, Aaronson and Kuperberg [AK07] in the same
paper showed an oracle separation between these two classes, leaving the
separation with respect to a classical oracle as an open question. Recently,
Liu [Liu22] showed the separation for its relational variants (i.e.,
FBQP/qpoly and FBQP/poly) under a special case, where the oracle is never
given to the algorithms333As mentioned in Section 1.3, a concurrent work by
Aaronson, Buhrman, and Kretschmer [ABK23] proves their relational variants
$\mathsf{FBQP}/\qpoly\neq\mathsf{FBQP}/\poly$ _unconditionally_.. Despite all
the efforts, the separation between ${\sf BQP/poly}$ and ${\sf BQP/qpoly}$
relative to a classical oracle remains obscure.

In this work, we proceed with the question by showing a _full separation_
relative to a _classically accessible classical_ oracle. Along the way, we
adapt our techniques and give an alternative proof for the separation between
QMA vs QCMA relative to a _quantumly accessible classical_ distributional
oracle, which was recently established by Natarajan and Nirkhe [NN22].

###  1.1 Our Results

Our first result is a black-box separation between BQP/qpoly vs BQP/poly with
respect to a classically-accessible classical oracle.

_Classically-accessible classical oracles._ A classical oracle $\cal O$ is
said to be classically accessible if a quantum algorithm can only query the
oracle classically; in other words, the only interface of ${\cal O}$ to
quantum algorithms is classical: given an input $x$, it outputs $y={\cal
O}(x)$.

######  Theorem 1.3 (Informal).

There exists a language $\mathcal{L}$ in BQP/qpoly but not in BQP/poly,
relative to a classically accessible classical oracle $\cal O$.

Our work is based on the previous works on quantum advantages with
unstructured oracles, by Yamakawa and Zhandry [YZ22] and recent separation by
Liu [Liu22]. Our work improves [Liu22] in two aspects: first, Liu only proved
the separation of their relational variants, instead of the original decision
classes; second, the separation by Liu does not allow algorithms to have
access to the oracle (either classically, or quantumly), but only the advice
can depend on the oracle.

######  Remark 1.

Although the long-standing open question is to understand the separation
relative to a quantumly accessible classical oracle, our theorem is not weaker
but incomparable. Since classical access is not stronger than quantum access,
it limits both the computational power of quantum machines with quantum and
classical advice: intuitively, classical access makes it easier to prove a
language ${\cal L}$ is not in ${\sf BQP^{\cal O}/poly}$ but harder to prove
${\cal L}\in{\sf BQP^{\cal O}/qpoly}$. A similar observation is applicable to
the theorem concerning the separation between QMA and QCMA.

Our second result is about the separation between QMA and QCMA.

######  Theorem 1.4 (Informal).

There exists a language $\mathcal{L}$ in QMA but not in QCMA, relative to a
classically accessible classical oracle $\cal O$.

Inspired by the techniques used in our Theorem 1.3 and Theorem 1.4, we give an
alternative proof for the result by Natarajan and Nirkhe [NN22]. Note in the
following result, the classical oracle is _quantumly accessible_.

######  Theorem 1.5 (Informal).

There exists a language $\mathcal{L}$ in QMA but not in QCMA, relative to a
distributional quantumly-accessible classical oracle $\cal O$.

A difference between the construction of [NN22] and ours is in the case when
the oracle is fixed to some oracle from the distribution. In [NN22], they can
neither prove nor disprove the separation between QMA and QCMA. However, in
our construction, the separation will disappear if we fix our oracle.

Finally, we observe that the problem considered in [YZ22] gives a new
superpolynomial separation between classical and quantum one-way communication
complexity. Though such a separation has been known since 2004 [BYJK04], the
new separation has two interesting features that Bob’s input length is short
and the classical lower bound holds even if Bob can classically access Alice’s
input as an oracle (see Section 7 for more detail).444As mentioned in Section
1.3, a concurrent work by Aaronson, Buhrman, and Kretschmer [ABK23] observes
that there is a variant of [BYJK04] that satisfies the former (but not
latter).

###  1.2 Overview

#### Quantum Advantages and Separation for a Special Case.

We will introduce the recent work on quantum advantages from unstructured
oracles by Yamakawa and Zhandry [YZ22], as it will be used for both of our
results in this work. They proved that there exists a code
$C\subseteq\Sigma^{n}$ and an oracle-aided function $f_{C}$ such that,
relative to a random oracle from $H:[n]\times\Sigma\to\\{0,1\\}$, the function
$f_{C}^{H}$ is easy to invert on any image with quantum access but inversion
is hard with only classical access. The function is defined as the following:

$\displaystyle
f^{H}_{C}(v_{1},\cdots,v_{n})=\begin{cases}H(1,v_{1})||H(2,v_{2})||\cdots||H(n,v_{n})&\text{
if }(v_{1},\cdots,v_{n})\in C\\\ \bot&\text{ if }(v_{1},\cdots,v_{n})\not\in
C\\\ \end{cases}.$

Intuitively, although the function computes an entry-by-entry hash, the
requirement that $(v_{1},\cdots,v_{n})$ must be a codeword enforces the
hardness of inversion when only classical queries are allowed. More precisely,
the underlying code $C$ satisfies a property called list-recoverability; even
if a classical algorithm learns hash values of a subset $E_{i}\subseteq\Sigma$
for each of $H(i,\cdot)$, only a polynomial number of codewords can be found
in $E_{1}\times E_{2}\times\cdots\times E_{n}$, which does not help invert
random images555When all classical queries are non-adaptive, this is clearly
true: as only polynomially many $f^{H}_{c}$ are known for codewords in $C$.
The idea can be adapted to adaptive queries as well; we do not elaborate on it
here. . On the other hand, they showed a quantum algorithm that uses quantum
queries to invert images.

Liu [Liu22] observed that the inversion quantum algorithm only needs to make
non-adaptive quantum queries that are independent of the image $y$. Therefore,
the algorithm with quantum access can be easily cast into a quantum algorithm
with quantum advice but no queries; on the other hand, he showed that, if an
algorithm has no access to the random oracle, it can not invert even with a
piece of exponentially large classical advice. Since given an image $y$ there
are multiple pre-images of $y$, the above two statements lead to the
separation between FBQP/qpoly and FBQP/poly when an algorithm has no access to
the oracle.

#### Allowing classical queries.

Our first result is to extend the previous separation of FBQP/qpoly and
FBQP/poly by Liu, by allowing quantum algorithms to make online _classical
queries_ to $H$. Since the algorithm with quantum advice makes no queries, it
also works in this setting of classical access. We only need to prove the
hardness with classical advice: i.e., no quantum algorithms can invert with
classical queries and bounded classical advice.

Following the framework by Guo et al. [GLLZ21], when only making classical
queries (say, at most $T$), a piece of $S$ bits of classical advice is
equivalent to the so-called “ordinary advice”: the advice consists of only
$ST$ coordinates, or $ST$ pairs of inputs and outputs. More precisely, the
information the algorithm can learn from $S$ bits of advice and $T$ classical
queries is roughly the same as that from $ST$ bits of ordinary advice and $T$
classical queries. Thus, the first step is to replace classical advice with
ordinary classical advice.

It now remains to show that a quantum algorithm with classical access to $H$
and short ordinary advice can not invert random images. As ordinary advice
only gives information on at most polynomially many pairs of inputs and
outputs, let $E_{i}$ denote the subset of inputs whose hash values under
$H(i,\cdot)$ are in the ordinary advice; since the ordinary advice is of
length polynomial, $|E_{i}|$ is polynomial for each $i\in[n]$. Now let us
assume the algorithm makes non-adaptive queries that are independent of a
challenge. In this case, we can further define $E^{\prime}_{i}$ that consists
of all $x$ inputs whose values $H(i,x)$ are known from these classical
queries. The algorithm in total learns hashes of $H(i,\cdot)$ for the inputs
in $E_{i}\cup E^{\prime}_{i}$. Observing that $|E_{i}\cup E^{\prime}_{i}|$ is
polynomial for each $i$, by the list-recoverability of the underlying code
$C$, the algorithm only learns values of $f^{H}_{C}$ for a polynomial number
of codewords, which almost always never hits a random challenge.

Lastly, we extend the proof to adaptive cases (for more details, please refer
to Section 3).

#### Upgrading to BQP/qpoly v.s. BQP/poly.

Next, we turn the above separation of relational classes into a separation of
BQP/qpoly v.s. BQP/poly. Our idea is to define a language ${\cal L}$ through a
family of random functions for each $n$:
$G_{n}\colon\\{0,1\\}^{n}\to\\{0,1\\}$, i.e., for $x\in\\{0,1\\}^{n}$,
$x\in{\cal L}$ if and only if $G_{n}(x)=1$. We omit the subscript when it is
clear from context in the introduction.

We use an oracle $\cal O$ to hide the evaluation of $G$ on $x$, by requiring
the algorithm to invert the function $f^{H}_{C}$ on image $x$. More precisely,
we define $\mathcal{O}$ as follows:

$\displaystyle\mathcal{O}(\mathbf{v},x)=\begin{cases}G(x)&\text{ if
}f^{H}_{C}(\mathbf{v})=x,\\\ \bot&\text{ otherwise}.\end{cases}$

Then an algorithm only gets oracle access to $\mathcal{O}$, but not $H$ or
$G$.

To see that $\mathcal{L}$ is decidable by a $\BQP/\qpoly$ machine, we can just
take the quantum advice as in [Liu22]. On an input $x$, an algorithm generates
$\mathbf{v}$ such that $f^{H}_{C}(\mathbf{v})=x$ using the quantum advice. We
can then evaluate $G(x)$ by querying $\mathcal{O}$ at $(x,\mathbf{v})$ and
decide if $x\in\cal L$.

On proving that $\mathcal{L}$ cannot be decided by any $\BQP/\poly$ machine,
we leverage the statement proved above: given classical advice, by only
querying a classical oracle $H$, it is hard for an efficient algorithm to
invert $f^{H}_{C}$. The beyond result implies that the algorithm should only
have negligible query weight on $\mathbf{v}$ under the classical oracle
$\mathcal{O}$ such that $f^{H}_{C}(\mathbf{v})=x$; otherwise the algorithm can
be turned into another one that inverts $f^{H}_{C}$.

Therefore, we can reduce the problem to the case where an algorithm has only
access to $G(y)$ for all $y\neq x$, but no access to $G(x)$ for the challenge
$x$; the goal is still to learn $G(x)$. This is exactly the famous Yao’s box
problem [Yao90]: a piece of advice is allowed to depend on the whole oracle
$G$, but then an online algorithm uses the advice to find $G(x)$ for a random
$x$, with no access to $G(x)$. By adapting the ideas in [Yao90, DTT10] and
combining all the previous ideas with a standard diagonalization argument, we
prove the separation ${\sf BQP^{\mathcal{O}}/qpoly}\neq{\sf
BQP^{\mathcal{O}}/poly}$ relative to a classically accessible classical
oracle.

#### Separation between QMA and QCMA relative to a classically accessible
classical oracle.

We first construct a problem that has a short quantum proof for YES instances,
no quantum proof for NO instances, and no classical proof that can distinguish
between YES and NO instances. Given random functions
$H:[n]\times\Sigma\to\\{0,1\\}$ and $G:\\{0,1\\}^{n}\to\\{0,1\\}^{n}$, as well
as a subset $S\subseteq\\{0,1\\}^{n}$ with a size of at least $2/3\cdot
2^{n}$, we create two pairs of oracles:

  * •

For a YES instance, the oracle $G$ and an oracle $\mathcal{O}[G,H,\emptyset]$
are provided. The latter takes an input $t\in\\{0,1\\}^{n}$ and a vector
$\mathbf{v}\in C$ and outputs $1$ if and only if $f^{H}(\mathbf{v})=G(t)$.

  * •

If it is a NO instance, the oracle $G$ and an oracle $\mathcal{O}[G,H,S]$ is
given. The latter takes as input a $t\in\\{0,1\\}^{n}$ and a vector
$\mathbf{v}\in C$, it outputs $1$ if and only if $f^{H}(\mathbf{v})=G(t)$ and
$t\not\in S$.

A quantum algorithm $\mathcal{A}$, with the same advice as in [Liu22],
achieves the following:

  * •

The algorithm $\mathcal{A}$ on oracles $G,\mathcal{O}$ (which will be either
$\mathcal{O}[G,H,\emptyset]$ or $\mathcal{O}[G,H,S]$), uniformly at random
samples $t\in\\{0,1\\}^{n}$. It then uses the quantum advice to compute a
vector $\mathbf{v}$ such that $f^{H}(\mathbf{v})=G(t)$ and outputs
$\mathcal{O}(t,\mathbf{v})$.

  * •

When $\mathcal{O}[G,H,\emptyset]$ is given, by the correctness of the YZ
algorithm, $\mathcal{A}$ will output $1$ with an overwhelming probability.

  * •

When $\mathcal{O}[G,H,S]$ is given, by the definition and the condition
$|S|\geq 2/3\cdot 2^{n}$, $\mathcal{A}$ will output $1$ with a probability at
most $1/3$.

On the other hand, for any quantum algorithm $\mathcal{B}$ with classical
queries and bounded-sized classical proof, it can not distinguish between the
case of having access to $G,\mathcal{O}[G,H,\emptyset]$ or
$G,\mathcal{O}[G,H,S]$. On a high level, the only way to tell the difference
is by finding an input $(t,\mathbf{v})$ such that
$\mathcal{O}[G,H,\emptyset](t,\mathbf{v})\neq\mathcal{O}[G,H,S](t,\mathbf{v})$.
This will require $\mathcal{B}$ to query on an input $(t,\mathbf{v})$ such
that $f^{H}(\mathbf{v})=G(t)$, which is difficult for $\mathcal{B}$ with only
classical advice.

Finally, we mount our new separation result on the diagonalization argument
and construct a language that shows the separation between QMA and QCMA
relative to a classically accessible classical oracle. Please refer to Section
5 for full details.

#### Separation between QMA and QCMA relative to a distributional oracle.

To separate $\QMA$ from $\QCMA$, we would try to separate two distributions of
oracles, namely the YES and NO distributions, defined below: For a random
function $H\colon[n]\times\Sigma\to\\{0,1\\}$,

  * •

If it is a YES instance, an oracle distribution $\\{\mathcal{O}[r]\\}_{r}$
with the index being drawn uniformly at random, such that: $\mathcal{O}[r]$
takes $\mathbf{v}\in\Sigma^{n}$ and evaluates $f^{H}_{C}(\mathbf{v})$, and
outputs 1 iff $f^{H}_{C}(\mathbf{v})=r$;

  * •

If it is a NO instance, the oracle always outputs $0$.

To see that the two distributions can be distinguished using a $\QMA$ machine,
notice that we can take the quantum advice as in [Liu22], and generate
$\mathbf{v}$ such that $f^{H}_{C}(\mathbf{v})=r$. By querying $\mathcal{O}$ at
$\mathbf{v}$, we can distinguish whether the oracle belongs to the YES
distribution or the NO distribution.

To prove the two distributions cannot be distinguished by any $\QCMA$ machine,
we notice that the difference between YES and NO oracles is only on inputs
$\mathbf{v}$ that $f^{H}_{C}(\mathbf{v})=r$. Therefore, we reduce it to the
hardness of finding $\mathbf{v}$ for random $r$ such that
$f^{H}_{C}(\mathbf{v})=r$, even when given classical advice.

In Section 6, we define unary languages $\mathcal{L}_{i}$ and their related
oracle distributions for each $n$. By a standard diagonalization argument, we
can argue that there exists some language $\mathcal{L}$ that is in
$\QMA^{\mathcal{O}}$ but not in $\QCMA^{\mathcal{O}}$.

###  1.3 Concurrent Work

A concurrent work by Aaronson, Buhrman, and Kretschmer [ABK23], among many
results, proves $\mathsf{FBQP}/\poly\neq\mathsf{FBQP}/\qpoly$
_unconditionally_ where $\mathsf{FBQP}/\poly$ and $\mathsf{FBQP}/\qpoly$ are
the relational variants of $\mathsf{BQP}/\poly$ and $\mathsf{BQP}/\qpoly$,
respectively. The key insight behind the result is an observation that a
variant of hidden matching problem [BYJK04] gives an exponential separation
between classical and quantum one-way communication complexity with short
input length for Bob. They essentially prove that any such a separation with
efficient Bob can be used to prove
$\mathsf{FBQP}/\poly\neq\mathsf{FBQP}/\qpoly$. We independently had an
observation that [YZ22] gives such a separation of classical and quantum one-
way communication complexity with short input length for Bob (see Section 7).
By relying on their proof, which is fairly easy in hindsight, it seems
possible to prove $\mathsf{FBQP}/\poly\neq\mathsf{FBQP}/\qpoly$ by using
[YZ22] instead of the hidden matching problem.

A crucial difference between the one-way communication variant of [YZ22] and
the hidden matching problem is that the hardness of the former with classical
communication holds even if Bob can classically query Alice’s input. Due to
this difference, one cannot reprove $\BQP/\poly\neq\BQP/\qpoly$ and
$\QMA\neq\QCMA$ relative to a classically-accessible classical oracle by using
the hidden matching problem instead of [YZ22]. On the other hand, it seems
possible to prove $\QMA\neq\QCMA$ relative to a distributional quantumly-
accessible classical oracle by using (a parallel repetition variant of) their
variant of the hidden matching problem instead of [YZ22].

##  2 Preliminaries

#### Basic notations.

For a set $X$, $|X|$ denotes the cardinality of $X$. We write $x\leftarrow X$
to mean that $x$ is uniformly taken from $X$. For a distribution $\mathcal{D}$
over classical strings, we write $x\leftarrow\mathcal{D}$ to mean that $x$ is
sampled from the distribution $\mathcal{D}$. For sets $X$ and $Y$,
$\mathsf{Func}(X,Y)$ denotes the set of all functions from $X$ to $Y$. For a
positive integer $n$, $[n]$ denotes the set $\\{1,2,...,n\\}$. QPT stands for
“Quantum Polynomial-Time”. We use $\poly$ to mean a polynomial and
$\mathsf{negl}$ to mean a negligible function.

#### Oracle variations.

In the literature on quantum computation, when we say that a quantum algorithm
has oracle access to $f:X\rightarrow Y$, it usually means that it is given
oracle access to an oracle that applies a unitary
$\ket{x}\ket{y}\mapsto\ket{x}\ket{y\oplus f(x)}$. We refer to such a standard
oracle as quantumly-accessible classical oracles. In this paper, we consider
the following two types of non-standard oracles.

The first is classically-accessible classical oracles. A classically-
accessible classical oracle for a classical function $f:X\rightarrow Y$ takes
a _classical string_ $x\in X$ as input and outputs $f(x)$. In other words,
when an algorithm sends $\sum_{x,y}\alpha_{x,y}\ket{x}\ket{y}$ to the oracle,
the oracle first _measures_ the first register and then applies the unitary
$\ket{x}\ket{y}\mapsto\ket{x}\ket{y\oplus f(x)}$. Note that classically-
accessible classical oracles apply non-unitary operations.

The second is distributional quantumly-accessible classical oracles. They are
specified by a distribution $\mathcal{F}$ over classical functions $f$ rather
than by a single function $f$. When we consider an algorithm that is given
oracle access to a distributional quantumly-accessible classical oracle, it
works as follows: At the beginning of an execution of the algorithm, a
function $f$ is chosen according to the distribution $\mathcal{F}$, and then
the algorithm has access to a quantumly-accessible classical oracle that
computes $f$. Note that $f$ is sampled at the beginning and then the same $f$
is used throughout the execution.

#### Complexity classes.

We define the complexity classes which we consider in this paper.
Specifically, we define $\BQP/\qpoly$, $\BQP/\poly$, $\QMA$, and $\QCMA$
relative to classically-accessible classical oracles and $\QMA$ and $\QCMA$
relative to distributional quantumly-accessible classical oracles.

######  Definition 2.1 ($\BQP/\qpoly$ and $\BQP/\poly$ languages relative to
classically-accessible classical oracles.).

Let $\mathcal{O}$ be a classically-accessible classical oracle. A language
$\mathcal{L}\subseteq\\{0,1\\}^{*}$ belongs to $\BQP/\qpoly$ relative to
$\mathcal{O}$ if there is a QPT machine $\mathcal{A}$ and a polynomial-size
family $\\{\ket{z_{n}}\\}_{n\in\mathbb{N}}$ of quantum advice such that for
any $x\in\\{0,1\\}^{*}$,

$\Pr[\mathcal{A}^{\mathcal{O}}(x,\ket{z_{|x|}})=\mathcal{L}(x)]\geq 2/3$

where $\mathcal{L}(x):=1$ if $x\in\mathcal{L}$ and otherwise
$\mathcal{L}(x):=0$.

$\BQP/\poly$ is defined similarly except that the advice is required to be
classical.

######  Definition 2.2 ($\QMA$ and $\QCMA$ languages relative to classically-
accessible classical oracles.).

Let $\mathcal{O}$ be a classically-accessible classical oracle. A language
$\mathcal{L}\subseteq\\{0,1\\}^{*}$ belongs to $\QMA$ relative to
$\mathcal{O}$ if there is a QPT machine $V$ with classical access to its
oracle and a polynomial $p$ such that the following hold:

Completeness

For any $x\in\mathcal{L}$, there is a $p(|x|)$-qubit witness $\ket{w}$ such
that

$\Pr[V^{\mathcal{O}}(x,\ket{w})=1]\geq 2/3.$

Soundness

For any $x\notin\mathcal{L}$ and $p(|x|)$-qubit witness $\ket{w}$,

$\Pr[V^{\mathcal{O}}(x,\ket{w})=1]\leq 1/3.$

$\QCMA$ is defined similarly except that the witness is required to be
classical.

######  Definition 2.3 ($\QMA$ and $\QCMA$ languages relative to
distributional quantumly-accessible classical oracles.).

Let $\mathcal{F}$ be a distributional quantumly-accessible classical oracle,
i.e., it specifies a distribution over classical functions $f$. A language
$\mathcal{L}\subseteq\\{0,1\\}^{*}$ belongs to $\QMA$ relative to
$\mathcal{F}$ if there is a QPT machine $V$ with quantum access to its oracle
and a polynomial $p$ such that the following hold:

Completeness

For any $x\in\mathcal{L}$, there is a $p(|x|)$-qubit witness $\ket{w}$ such
that

$\Pr_{f\leftarrow\mathcal{F}}[V^{f}(x,\ket{w})=1]\geq 2/3.$

Soundness

For any $x\notin\mathcal{L}$ and $p(|x|)$-qubit witness $\ket{w}$,

$\Pr_{f\leftarrow\mathcal{F}}[V^{f}(x,\ket{w})=1]\leq 1/3.$

$\QCMA$ is defined similarly except that the witness is required to be
classical.

######  Remark 2.

Notice that the quantum/classical witness $\ket{w}/w$ can only depend on the
distribution $\mathcal{F}$ rather than a specific oracle $f$.

#### Non-Uniformity in the ROM.

Prior work has developed a number of tools to characterize the power of a non-
uniform adversary in the random oracle model (ROM). Note that we are
considering the ROM where we only allow classical access to random oracles
unlike the quantum ROM [BDF+11]. This is sufficient for our purpose because we
use these tools only for proving $\BQP/\qpoly\neq\BQP/\poly$ and
$\QMA\neq\QCMA$ relative to _classically-accessible_ classical oracles.

Similar to [Liu22], we will be using the presampling technique, introduced by
[Unr07] and further developed by [CDGS18, GLLZ21]. First, we define games in
the ROM.

######  Definition 2.4 (Games in the ROM).

A game $\mathcal{G}$ in the ROM is specified by three classical algorithms
${\sf Samp}^{H},{\sf Query}^{H}$, and ${\sf Verify}^{H}$ where
$H\leftarrow\mathsf{Func}(X,Y)$ for some sets $X,Y$:

  * •

${\sf Samp}^{H}(r)$: it is a deterministic algorithm that takes uniformly
random coins $r\in\mathcal{R}$ as input, and outputs a challenge
$\mathsf{CH}$. 666We note that the randomness $r$ is separate from the
randomness of $H$. $r$ is used to sample the challenge.

  * •

${\sf Query}^{H}(r,\cdot)$: it is a deterministic classical algorithm that
hardcodes the randomness $r$ used to construct the challenge and provides the
adversary’s online queries. 777As an example, for most applications, ${\sf
Query}^{H}(r,\cdot)=H(\cdot)$.

  * •

${\sf Verify}^{H}(r,{\sf ans})$: it is a deterministic algorithm that takes
the same random coins for generating a challenge and an alleged answer ${\sf
ans}$, and outputs $b$ indicating whether the game is won ($b=1$ for winning).

Let $T_{\sf Samp}$ be the number of queries made by ${\sf Samp}$ and $T_{\sf
Verify}$ be the number of queries made by ${\sf Verify}$.

For a fixed $H\in\mathsf{Func}(X,Y)$ and a quantum algorithm $\mathcal{A}$,
the game $\mathcal{G}^{H}_{\mathcal{A}}$ is executed as follows:

  * •

A challenger $\mathcal{C}$ samples $\mathsf{CH}\leftarrow{\sf Samp}^{H}(r)$
using uniformly random coins $r$.

  * •

A (uniform or non-uniform) quantum algorithm $\mathcal{A}$, that has classical
oracle access to ${\sf Query}^{H}(r,\cdot)$, takes $\mathsf{CH}$ as input and
outputs ${\sf ans}$. We call $\mathcal{A}$ an online adversary/algorithm.

  * •

$b\leftarrow{\sf Verify}^{H}(r,{\sf ans})$ is the game’s outcome.

######  Definition 2.5.

We say that a game $\mathcal{G}$ in the ROM has security $\delta(Z,Q):=\delta$
if

$\max_{\mathcal{A}}\Pr_{H}[\mathcal{G}_{\mathcal{A}}^{H}=1]\leq\delta$

where $H\leftarrow\mathsf{Func}(X,Y)$ and $\max$ is taken over all
$\mathcal{A}$ with $Z$-bit classical advice that makes $Q$ classical queries.

The presampling technique relates the probability of success of a non-uniform
algorithm with classical queries to a random oracle with the success
probability of a uniform algorithm in the $P$ bit-fixing game, as defined
below.

######  Definition 2.6 (Games in the $P$-BF-ROM).

A game $\mathcal{G}$ in the $P$-BF-ROM is specified by two classical
algorithms ${\sf Samp}^{H}$ and ${\sf Verify}^{H}$ that work similarly to
those in Definition 2.4.

For a fixed $H\in\mathsf{Func}(X,Y)$ and a pair of algorithms
$(f,\mathcal{A})$, the game $\mathcal{G}^{H}_{f,\mathcal{A}}$ is executed as
follows:

  * •

Offline Stage: Before a game starts, an offline algorithm $f$ (having no
input) generates a list $\mathcal{L}=\\{(x_{i},y_{i})\\}_{i\in[P]}\in(X\times
Y)^{P}$ containing at most $P$ input-output pairs (all $x_{i}$’s are
distinct).

  * •

Online Stage: The game is then executed with $\mathcal{A}$ that knows
$\mathcal{L}$ and has oracle access to $H$ similarly to Definition 2.4. $H$ is
a function drawn at random such that it satisfies $\mathcal{L}$.

######  Definition 2.7.

We say that a game $\mathcal{G}$ in the $P$-BF-ROM has security
$\nu(P,Q):=\nu$ if

$\max_{f,\mathcal{A}}\Pr_{H}[\mathcal{G}_{f,\mathcal{A}}^{H}=1]\leq\nu$

where $H\leftarrow\mathsf{Func}(X,Y)$ and $\max$ is taken over all $f$ that
outputs $P$ input-output pairs and $\mathcal{A}$ that makes $Q$ classical
queries.

######  Theorem 2.8 ([Liu22, Theorem A.1]888Similar theorems with slightly
worse bounds are presented in [CDGS18, Theorem 5 and 6] and [GLLZ21, Theorem
3].).

Let $\mathcal{G}$ be any game with $Q_{\sf Samp},Q_{\sf Verify}$ being the
number of queries made by ${\sf Samp}$ and ${\sf Verify}$. For any classical
advice length $Z$, and number of online queries $Q$:

  1. 1.

For $P=Z(Q+Q_{\sf Samp}+Q_{\sf Verify})$, if $\mathcal{G}$ has security
$\nu(P,Q)$ in the $P$-BF-ROM, then it has security $\delta(Z,Q)\leq
2\cdot\nu(P,Q)$ against non-uniform unbounded-time algorithms with $Z$ bits of
classical advice and $Q$ classical queries.

  2. 2.

For any $P>0$, if $\mathcal{G}$ has security $1/2+\nu(P,Q)$ in the $P$-BF-ROM,
then it has security $\delta(Z,Q)\leq 1/2+\nu(P,Q)+{Z(Q+Q_{\sf Verify}+Q_{\sf
Samp})}/{P}$ against non-uniform unbounded-time algorithms with $Z$ bits of
classical advice and $Q$ classical queries.

We can use the above correspondence to bound the success probability of a non-
uniform quantum algorithm with classical queries to the Yao’s Box game
[Yao90].

######  Lemma 2.9 (Yao’s Box with Classical Queries [Yao90, DTT10]).

Let $G:[N]\to\\{0,1\\}$ be a random function. Let $\mathcal{A}$ be an
unbounded-time algorithm, with $Z$ bits of (classical) advice $z_{G}$ and $Q$
classical queries to $G$. The probability that $\mathcal{A}$ computes $G(x)$
without querying $G$ at random index $x$ is at most

$\Pr_{x}[\mathcal{A}^{G}(z_{G},x)=G(x)]\leq\frac{1}{2}+2\sqrt{\frac{Z(Q+1)}{N}}.$

The above lemma was essentially proved in [DTT10], but we offer here an
alternative proof using the presampling technique of Theorem 2.8.

###### Proof of Lemma 2.9.

We consider the bit-fixing game in the $P$-BF-ROM, where we fix the value of
$G$ at $P$ positions in the offline phase. Since $\mathcal{A}$ is not allowed
to query $G$ at position $x$ even in the $P$-BF-ROM (because it queries $G$
via the original ${\sf Query}^{G}$), the only way for $\mathcal{A}$ to
successfully compute $G(x)$ is if $x$ is included in the set of fixed
positions during the offline phase. This happens with probability
$\frac{P}{N}$ and thus

$\nu(P,T)\leq\frac{P}{N}.$

In this game $Q_{\sf Samp}=0$, since the Sampler outputs a challenge $x\in[N]$
uniformly at random, without the need to perform any queries. The Verifier
only needs to query $G$ at position $x$, thus $Q_{\sf Verify}=1$. The
statement of Item 2 of Theorem 2.8 with $P=\sqrt{Z(Q+1)N}$ implies that the
advantage of a non-uniform algorithm with advice $z_{G}$ and $Q$ queries is at
most

$\delta(Z,Q)\leq\frac{1}{2}+2\sqrt{\frac{Z(Q+1)}{N}}$

. ∎

The series of definitions and lemmas that follow relate the ROM with auxiliary
input to two related kinds of distributions: bit-fixing and dense
distributions. Looking ahead, these are used in the separation between $\QMA$
and $\QCMA$ relative to a classically-accessible oracle in Section 5.

######  Definition 2.10.

For $P\in\mathbb{N}$, we say that a distribution $\mathcal{D}$ supported by
functions $G\colon X\to Y$ is a $P$-bit-fixing distribution if there is a
subset $S\subseteq X$ such that $|S|\leq P$ and

  * •

for all $x\in S$, $G(x)$ takes the same value for all $G$ in the support of
$\mathcal{D}$, and

  * •

for all $x\notin S$, $G(x)$ is uniformly distributed over $Y$ when we sample
$G\leftarrow\mathcal{D}$.

We say that $\mathcal{D}$ is fixed on $x$ if and only if $x\in S$.

In addition, we will consider the following generalization of a $P$-bit-fixing
distribution. A $(P,1-\delta)$-dense distribution is one where the non-fixed
coordinates are close to uniformly distributed. The parameter $1-\delta$
controls how close to uniform they are.

######  Definition 2.11.

A distribution $\mathcal{D}$ supported on functions $G:X\to Y$ is called

  * •

$(1-\delta)$-dense if for every subset $I\subset X$,

$H_{\infty}(G(I))\geq(1-\delta)\cdot|I|\cdot\log|Y|=(1-\delta)\cdot|Y|^{|I|}.$

  * •

$(P,1-\delta)$-dense if it is fixed on at most $P$ coordinates and is
$(1-\delta)$-dense on the rest.

We will further define for each $(P,1-\delta)$-dense distribution
$\mathcal{D}$ its corresponding $P$-bit-fixing distribution to be the unique
bit-fixing distribution with the same fixed coordinates. Formally:

######  Definition 2.12.

Let $\mathcal{D}$ be a $(P,1-\delta)$-dense distribution supported on
functions $G:X\to Y$. Its corresponding $P$-bit-fixing distribution
$\mathcal{D}^{\prime}$ is also supported on functions $G:X\to Y$ and is fixed
on the same coordinates that $\mathcal{D}$ is, and uniform on the rest.

######  Claim 2.13.

[CDGS18, Claim 2] Let $G:X\to Y$ be a random oracle, and let $f$ be an
arbitrary function that maps a random oracle to $S$-bit advice. For an
arbitrary classical advice $z\in\\{0,1\\}^{S}$, let $G_{z}$ be the
distribution of $G$ conditioned on $z=f(G)$. Let
$S_{z}=|X|\log|Y|-H_{\infty}(G_{z})$ be the min-entropy deficiency of $G_{z}$.
For every $\gamma,\delta>0$, $G_{z}$ is $\gamma$-close to a convex combination
of finitely many $(P^{\prime},1-\delta)$-dense sources for

$P^{\prime}=\frac{S_{z}+\log 1/\gamma}{\delta\cdot\log|Y|}.$

In Claim 2.13, the number of fixed entries is related to $S_{z}$, the min-
entropy deficiency of $G_{z}$, which can be exponentially large. The following
claim shows that $S_{z}$ is close to the length $S$ of the classical advice
with high probability.

######  Claim 2.14.

[CDGS18, Claim 4] Let $G:X\to Y$ be a random oracle, and let $f$ be an
arbitrary function that maps a random oracle to some $S$-bit advice.
Additionally, let $S_{z}$ be the min-entropy deficiency of $G_{z}$ as defined
in Claim 2.13. Then the distribution of $S_{z}$ satisfies

$\operatorname*{\mathbb{E}}_{G,z\leftarrow f(G)}[S_{z}]\leq
S\quad\text{and}\quad\Pr_{G,z\leftarrow f(G)}[S_{z}>S+\log
1/\gamma]\leq\gamma.$

Finally, we will use the following claim from [CDGS18], which provides a way
to translate between a $(P,1-\delta)$-dense distribution to a $P$-bit-fixing
one.

######  Claim 2.15.

[CDGS18, Claim 3] Let $\mathcal{D}$ be a $(P,1-\delta)$-dense distribution
supported on functions $G:X\to Y$ and $\mathcal{D}^{\prime}$ be its
corresponding $P$-bit-fixing distribution. Then, for any (adaptive)
distinguisher $\mathcal{B}$ that makes at most $T$ oracle queries,

$\left|\Pr[\mathcal{B}^{\mathcal{D}}=1]-\Pr[\mathcal{B}^{\mathcal{D}^{\prime}}=1]\right|\leq
T\delta\cdot\log|Y|.$

#### One-way to hiding lemma.

We review a lemma called the one-way to hiding lemma originally proven by
Unruh [Unr15]. The following is a variant proven in [AHU19].

######  Lemma 2.16 (One-Way to Hiding Lemma [AHU19, Theorem 3]).

Let $S\subseteq\mathcal{X}$ be random. Let
$G,H\colon\mathcal{X}\to\mathcal{Y}$ be random functions satisfying $\forall
x\not\in S~{}[G(x)=H(x)]$. Let $z$ be a random classical bit string or quantum
state. ($S,G,H,z$ may have an arbitrary joint distribution.) Let $\mathcal{A}$
be an oracle-aided quantum algorithm that makes at most $Q$ quantum queries.
Let $\mathcal{B}$ be an algorithm that on input $z$ chooses $i\leftarrow[q]$,
runs $\mathcal{A}^{H}(z)$, measures $\mathcal{A}$’s $i$-th query, and outputs
the measurement outcome. Then we have

$|\Pr[\mathcal{A}^{G}(z)=1]-\Pr[\mathcal{A}^{H}(z)=1]|\leq
2Q\sqrt{\Pr[\mathcal{B}^{H}(z)\in S]}.$

We remark that we consider quantum access to the oracles in the above lemma
since we use it in the proof of the separation between $\QMA$ and $\QCMA$
relative to a distributional _quantumly-accessible_ oracle in Section 6.

##  3 Quantum vs Classical Advice for [YZ22]

We review the result of [YZ22], which gives an $\NP$-search problem that is
easy for $\BQP$ machines but hard for $\BPP$ machines relative to a random
oracle. Then we show that the problem is easy for $\BQP$ machines with quantum
advice and no online query but hard for unbounded-time machine with
polynomial-size classical advice and polynomially-many classical online
queries relying on an observation of [Liu22].

######  Definition 3.1 ([YZ22]).

Let $C\subseteq\Sigma^{n}$ be a code over an alphabet $\Sigma$ and
$H:[n]\times\Sigma\rightarrow\\{0,1\\}$ be a function. The following function
is called a YZ function with respect to $C$ and $H$:

$\displaystyle f_{C}^{H}:C\rightarrow\\{0,1\\}^{n}$ $\displaystyle
f_{C}^{H}(v_{1},v_{2},...,v_{n})=H(1,v_{1})||H(2,v_{2})||...||H(n,v_{n}).$

######  Remark 3.

When we refer to a code $C\subseteq\Sigma^{n}$, it actually means a family
$\\{C_{n}\\}_{n\in\mathbb{N}}$ of codes $C_{n}\subseteq\Sigma_{n}^{n}$ over an
alphabet $\Sigma_{n}$. We often omit the dependence of $n$ for notational
simplicity.

[YZ22] shows that there is an error correcting code $C$, which satisfies a
property called _list-recoverability_ , such that $f_{C}^{H}$ is easy to
invert with quantum queries to $H$ but hard to invert with classical queries
to $H$ where $H$ is modeled as a random oracle. Liu [Liu22] observed that the
quantum inversion algorithm of [YZ22] does not need to make adaptive queries,
and having a polynomial-size quantum advice on $H$ that is independent of the
target $r$ suffices. In addition, he proved that classical advice does not
suffice for the task if no adaptive query is allowed. Combining the above, we
have the following theorem.

######  Theorem 3.2 ([YZ22, Liu22]).

There is a code $C\subseteq\Sigma^{n}$ satisfying the following:

  1. 1.

(Easiness with Quantum Advice) There is a QPT algorithm $\mathcal{A}$ and a
family of $\poly(n)$-qubit quantum advice $\\{\ket{z_{H}}\\}_{H}$ such that
for any $r\in\\{0,1\\}^{n}$,

$\displaystyle\Pr_{H}[f_{C}^{H}(\mathcal{A}(\ket{z_{H}},r))=r)]\geq
1-\mathsf{negl}(n)$

where $H\leftarrow\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$.

  2. 2.

(Hardness with Classical Advice) For any unbounded-time algorithm
$\mathcal{B}$ and polynomial $s$, there is a negligible function $\mu$ such
that for any family of $s(n)$-bit classical advice $\\{z_{H}\\}_{H}$,

$\displaystyle\Pr_{H,r}[f_{C}^{H}(\mathcal{B}(z_{H},r))=r]\leq\mu(n)$

where $H\leftarrow\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$ and
$r\leftarrow\\{0,1\\}^{n}$.

Moreover, $C$ satisfies $(\zeta,\ell,L)$-list-recoverability, i.e., for any
subset $T_{i}\subseteq\Sigma$ such that $|T_{i}|\leq\ell$ for every $i\in[n]$,

$\displaystyle|\\{(v_{1},...,v_{n})\in C:|\\{i\in[n]:x_{i}\in
T_{i}\\}|\geq(1-\zeta)n\\}|\leq L$

where $\zeta=\Omega(1)$, $\ell=2^{n^{c}}$, and
$L=2^{\tilde{O}(n^{c^{\prime}})}$ for some constants $0<c<c^{\prime}<1$.

We extend Theorem 3.2 to require that the hardness with classical advice holds
even if $\mathcal{A}$ is given a classical access to $H$. This can be seen as
a unification of [YZ22] and [Liu22].

######  Theorem 3.3.

Let $C\subseteq\Sigma^{n}$ be the code in Theorem 3.2, the following holds:

Hardness with Classical Advice and Classical Queries

For any unbounded-time algorithm $\mathcal{B}$ that makes polynomially many
classical queries to $H$ and polynomial $s$, there is a negligible function
$\mu$ such that for any family of $s(n)$-bit classical advice
$\\{z_{H}\\}_{H}$,

$\displaystyle\Pr_{H,r}[f_{C}^{H}(\mathcal{B}^{H}(z_{H},r))=r]\leq\mu(n)$

where $H\leftarrow\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$ and
$r\leftarrow\\{0,1\\}^{n}$.

###### Proof.

The proof is obtained by combining the proofs of [YZ22] and [Liu22]. We give a
full proof for completeness. By Item 1 of Theorem 2.8, we only have to prove
that the winning probability of the following game in the $P$-BF-ROM is
$\mathsf{negl}(n)$ for any $P=\poly(n)$ and an unbounded-time algorithm
$\mathcal{B}$ that makes $Q=\poly(n)$ online classical queries.

Offline Stage

$\mathcal{B}$ chooses list $L=\\{x_{k},y_{k}\\}_{k\in[P]}$ of $P$ input-output
pairs where $x_{k}\in[n]\times\Sigma$ and $y_{k}\in\\{0,1\\}$ for each
$k\in[P]$ and $x_{k}\neq x_{k^{\prime}}$ for all $k\neq k^{\prime}$. Then the
random oracle $H\leftarrow\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$ is
uniformly chosen under the constraint that $H(x_{k})=y_{k}$ for all $i\in[P]$.

Online Stage

$\mathcal{B}$ takes $r\leftarrow\\{0,1\\}^{n}$ as input, makes $Q$ classical
queries to $H$, and outputs
$\mathbf{v}^{*}=(v_{1}^{*},...,v_{n}^{*})\in\Sigma^{n}$.

Decision

$\mathcal{B}$ wins if $\mathbf{v}^{*}\in C$ and $f_{C}^{H}(\mathbf{v}^{*})=r$.

For $i\in[n]$, let $T_{i}:=\\{v_{i}\in\Sigma:x_{k}=(i,v_{i})~{}\text{for
some}~{}k\in[P]\\}$. Let

$\displaystyle\mathsf{Good}:=\\{(v_{1},...,v_{n})\in C:|\\{i\in[n]:x_{i}\in
T_{i}\\}|\geq(1-\zeta)n\\}.$

By the $(\zeta,\ell,L)$-list-recoverability and $|T_{i}|\leq P\leq
2^{n^{c}}\leq\ell$ (for sufficiently large $n$), we have $|\mathsf{Good}|\leq
L$. We consider the following two cases:

#### Case 1: $\mathbf{v}^{*}\in\mathsf{Good}$.

For each element $\mathbf{v}\in\mathsf{Good}$,
$\Pr_{r\leftarrow\\{0,1\\}^{n}}[f_{C}^{H}(\mathbf{v})=r]=2^{-n}$. Thus, by the
union bound, the probability that $\mathcal{B}$ wins is at most
$|\mathsf{Good}|\cdot 2^{-n}=2^{-\Omega(n)}$ by $|\mathsf{Good}|\leq
L=2^{\tilde{O}(n^{c^{\prime}})}$ and $c^{\prime}<1$.

#### Case 2: $\mathbf{v}^{*}\notin\mathsf{Good}$.

The analysis of this case is very similar to the proof of soundness in [YZ22]
and the following proof is partially taken verbatim from theirs. For each
$i\in[n]$ and $j\in[Q]$, let $S_{i}^{j}\subseteq\Sigma$ be the set of elements
$v_{i}$ such that $\mathcal{B}$ ever queried $(i,v_{i})$ by the point when it
has just made the $j$-th query. Let $\hat{S}_{i}^{j}:=S_{i}^{j}\cup T_{i}$ for
each $i\in[n]$ and $j\in\\{0,1,...,Q\\}$. Without loss of generality, we
assume that $v_{i}^{*}\in\hat{S}_{i}^{Q}$ for all $i\in[n]$.999This might
increase $Q$ by at most $n$, but $T$ is still $\poly(n)$ anyway. After the
$j$-th query, we say that a codeword $\mathbf{v}=(v_{1},...,v_{n})\in C$ is
_$K$ -queried_ if there is a subset $I\in[n]$ such that $|I|=K$,
$v_{i}\in\hat{S}_{i}^{j}$ for all $i\in I$, and $v_{i}\notin\hat{S}_{i}^{j}$
for all $i\notin I$. By the assumption that
$\mathbf{v}^{*}\notin\mathsf{Good}$, $\mathbf{v}^{*}$ is $K_{0}$-queried for
some $K_{0}\leq\lceil(1-\zeta)n\rceil$ right after the offline stage. By the
assumption that $v_{i}^{*}\in\hat{S}_{i}^{Q}$ for all $i\in[n]$,
$\mathbf{v}^{*}$ is $n$-queried after the $Q$-th query. Since a $K$-queried
codeword either becomes $(K+1)$-queried or remains $K$-queried by a single
query, $\mathbf{v}^{*}$ must be $K$-queried at some point of the execution of
$\mathcal{B}$ for all $K=K_{0},K_{0}+1,...,n$.

We consider the number of codewords that ever become $K$-queried for
$K=\lceil(1-\zeta)n\rceil$. If $\mathbf{v}=(v_{1},...,v_{n})\in C$ is
$\lceil(1-\zeta)n\rceil$-queried at some point, the number of $i$ such that
$v_{i}\in\hat{S}_{i}^{Q}$ is at least $\lceil(1-\zeta)n\rceil$ since
$\hat{S}_{i}^{j}\subseteq\hat{S}_{i}^{Q}$ for all $i,j$. We have
$|\hat{S}_{i}^{Q}|\leq Q+P=\poly(n)<2^{n^{c}}$ for sufficiently large $n$. On
the other hand, $C$ is $(\zeta,\ell,L)$-list recoverable for $\ell=2^{n^{c}}$
and $L=2^{\tilde{O}(n^{c^{\prime}})}$. Thus, the number of codewords that ever
become $\lceil(1-\zeta)n\rceil$-queried is at most
$L=2^{\tilde{O}(n^{c^{\prime}})}$.

Suppose that we simulate the oracle $H$ for $\mathcal{B}$ via lazy sampling,
that is, instead of uniformly choosing random functions at first, we sample
function values whenever they are specified in the list sent in the offline
stage or queried in the online stage. Suppose that a codeword $\mathbf{v}$
becomes $\lceil(1-\zeta)n\rceil$-queried at some point of the execution of the
experiment. Since the function values on the unqueried $\lfloor\zeta n\rfloor$
positions are not sampled yet, $\mathbf{v}$ can become a valid proof only if
all those values happen to be consistent to $r$, which occurs with probability
$\left(\frac{1}{2}\right)^{\lfloor\zeta n\rfloor}=2^{-\Omega(n)}$ by
$\zeta=\Omega(1)$. Since one of them is the final output $\mathbf{v}^{*}$, by
the union bound, the probability that $\mathbf{v}^{*}$ is a valid proof is at
most $L\cdot\left(\frac{1}{2}\right)^{\lfloor\zeta n\rfloor}=2^{-\Omega(n)}$
by $L=2^{\tilde{O}(n^{c^{\prime}})}$ and $c^{\prime}<1$. ∎

We have the following corollary. The motivation of showing this corollary is
to ensure that “a large fraction of $H$ works for all $r$” rather than that
“for all $r$, a large fraction of $H$ works”. Looking ahead, this is needed
for proving an oracle separation for $\BQP/\poly$ and $\BQP/\qpoly$ (but not
for $\QMA$ and $\QCMA$).

######  Corollary 3.4.

Let $C$ be the code in Theorem 3.2. Then the following hold:

  1. 1.

(Easiness with Quantum Advice) There is a QPT algorithm $\mathcal{A}$ and a
family of $\poly(n)$-qubit quantum advice
$\\{\ket{z_{\mathcal{H}}}\\}_{\mathcal{H}}$ such that

$\displaystyle\Pr_{\mathcal{H}}[\forall r\in\\{0,1\\}^{n}~{}$
$\displaystyle\Pr[\exists
j\in[n]~{}\text{s.t.}~{}f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{A}(\ket{z_{\mathcal{H}}},r)]\geq
1-\mathsf{negl}(n)]$ $\displaystyle\geq 1-\mathsf{negl}(n)$

where
$\mathcal{H}=(H^{(1)},...,H^{(n)})\leftarrow\left(\mathsf{Func}([n]\times\Sigma,\\{0,1\\})\right)^{n}$.

  2. 2.

(Hardness with Classical Advice and Classical Queries) For any unbounded-time
algorithm $\mathcal{B}$ that makes $\poly(n)$ classical queries to
$\mathcal{H}=(H^{(1)},...,H^{(n)})$ and polynomial $s$, there is a negligible
function $\mu$ such that for any family of $s(n)$-bit classical advice
$\\{z_{\mathcal{H}}\\}_{\mathcal{H}}$,

$\displaystyle\Pr_{\mathcal{H},r}[\exists
j\in[n]~{}\text{s.t.}~{}f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{B}^{\mathcal{H}}(z_{\mathcal{H}},r)]\leq\mu(n)$

where
$\mathcal{H}=(H^{(1)},...,H^{(n)})\leftarrow\left(\mathsf{Func}([n]\times\Sigma,\\{0,1\\})\right)^{n}$
and $r\leftarrow\\{0,1\\}^{n}$.

###### Proof.

For proving Item 1, we can set the advice as
$\ket{z_{\mathcal{H}}}=\ket{z_{H^{(1)}}}\otimes\ket{z_{H^{(2)}}}\otimes\cdots\otimes\ket{z_{H^{(n)}}}$,
and the algorithm just parallel runs the algorithm in Theorem 3.2 for
different $H^{(i)}$. Assume the algorithm in Theorem 3.2 satisfies:

$\displaystyle\Pr_{H}[f_{C}^{H}(\mathcal{A}(\ket{z_{H}},r))=r)]\geq
1-\eta(n),$

for some negligible function $\eta(n)$. For any $r\in\\{0,1\\}^{n}$,

$\displaystyle\Pr_{\mathcal{H}}[\forall
j\in[n],f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})\neq
r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{A}(\ket{z_{\mathcal{H}}},r)]\leq\eta(n)^{n}.$

By an averaging argument, at most $\eta(n)^{n/2}$ fraction of $\mathcal{H}$
will satisfy

$\displaystyle\Pr[\forall j\in[n],f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})\neq
r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{A}(\ket{z_{\mathcal{H}}},r)]\geq\eta(n)^{n/2}$

By applying a union bound over all $r\in\\{0,1\\}^{n}$, we obtain that

$\displaystyle\Pr_{\mathcal{H}}[\exists r\in\\{0,1\\}^{n}\Pr[\forall
j\in[n],f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})\neq
r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{A}(\ket{z_{\mathcal{H}}},r)]\geq\eta(n)]\leq(4\eta(n))^{\frac{n}{2}}$

Applying negation, we obtain the bound above.

For proving Item 2, we will show how an adversary $\mathcal{B}$ that breaks
hardness with classical advice and classical queries, can be used to construct
an adversary $\mathcal{B}^{\prime}$ that breaks hardness with classical advice
and classical queries of Theorem 3.3. To show this, we go through the
following steps:

  1. 1.

For each fixed
$j\in[n],\mathcal{H}_{\bar{j}}=(H^{(1)},\dots,H^{(j-1)},H^{(j+1)},\dots,H^{(n)})$,
we define a pair
$(\mathcal{B}^{\prime}[j,\mathcal{H}_{\bar{j}}],\\{z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}]\\}_{H})$
of an adversary and advice in which $j$ and $\mathcal{H}_{\bar{j}}$ is
hardwired.

  2. 2.

Show that
$(\mathcal{B}^{\prime}[j,\mathcal{H}_{\bar{j}}],\\{z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}]\\}_{H})$
breaks Theorem 3.3 on average over the choice of $j$.

  3. 3.

Fix the “best” $j$ and $\mathcal{H}_{\bar{j}}$ (w.r.t. random $H$) to get a
fixed pair of algorithm and advice that breaks hardness of Theorem 3.3.

Specifically, it works as follows. Suppose there exists some adversary
$\mathcal{B}$ and some polynomial $q(n)$ such that for sufficiently large $n$,

$\displaystyle\Pr_{\mathcal{H},r}[\exists
j\in[n]~{}\text{s.t.}~{}f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=r:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{B}^{\mathcal{H}}(z_{\mathcal{H}},r)]\geq
q(n)$

For each $j$ and $\mathcal{H}_{\bar{j}}$, we define
$(\mathcal{B}^{\prime}[j,\mathcal{H}_{\bar{j}}],\\{z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}]\\}_{H})$
as follows:

$z^{\prime}_{H}{[}j,\mathcal{H}_{\bar{j}}{]}$:

Given $\mathcal{H}_{\bar{j}}$, set

$\mathcal{H}=(H^{(1)},\dots,H^{(j-1)},H,H^{(j+1)},\dots,H^{(n)}).$

Set $z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}]$ to the advice of $\mathcal{B}$
for $\mathcal{H}$, i.e.
$z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}]:=z_{\mathcal{H}}$.

${\mathcal{B}^{\prime}[j,\mathcal{H}_{\bar{j}}]}^{H}(z^{\prime}_{H}{[}j,\mathcal{H}_{\bar{j}}{]},r)$:

It runs $\mathcal{B}^{\mathcal{H}}(z^{\prime}_{H}[j,\mathcal{H}_{\bar{j}}],r)$
where $\mathcal{B}^{\prime}$ hardwired $\mathcal{H}_{\bar{j}}$ into its
algorithm. It simulates the oracle $\mathcal{H}$ for $\mathcal{B}$ by querying
its own oracle $H$ as $H^{(j)}$ and simulates other $H^{(i)}(i\neq j)$ by
querying the hardwired $\mathcal{H}_{\bar{j}}$.

By the above argument, we have

$\displaystyle\Pr_{H,r,j,\mathcal{H}_{\bar{j}}}[f_{C}^{H}(\mathcal{B}^{\prime}[j,\mathcal{H}_{\bar{j}}]^{H}(z_{H}^{\prime}[j,\mathcal{H}_{\bar{j}}],r))=r]$
$\displaystyle=\Pr_{\mathcal{H},r,j}[f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{B}^{\mathcal{H}}(z_{\mathcal{H}},r)]$
$\displaystyle\geq\frac{q(n)}{n}.$

Thus, by taking $j=j^{*}$ and $\mathcal{H}_{\bar{j^{*}}}^{*}$ that makes the
above probability the largest for random $\mathcal{H}$,
$(\mathcal{B}^{\prime},\\{z^{\prime}_{H}\\}_{H}):=(\mathcal{B}^{\prime}[j^{*},\mathcal{H}_{\bar{j^{*}}}^{*}],\\{z^{\prime}_{H}[j^{*},\mathcal{H}_{\bar{j^{*}}}^{*}]\\}_{H})$
breaks hardness of Theorem 3.3. ∎

##  4 $\BQP/\poly$ vs $\BQP/\qpoly$ under Classically-Accessible Oracle

In this section, we demonstrate a $\BQP/\qpoly$ and $\BQP/\poly$ separation
relative to a classically-accessible classical oracle.

The main technical lemma needed for proving the separation is the following.

######  Lemma 4.1.

There is a family of distributions $\\{\mathcal{D}_{n}\\}_{n\in\mathbb{N}}$,
where $\mathcal{D}_{n}$ is supported on tuples $(G,\mathcal{O})$ of functions
$G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and
$\mathcal{O}:\\{0,1\\}^{p(n)}\rightarrow\\{0,1\\}^{q(n)}$ for some polynomials
$p$ and $q$, satisfying the following:

  1. 1.

(Easiness with Quantum Advice.) There is a QPT algorithm $\mathcal{A}$ with
classical access to $\mathcal{O}$ and a family of $\poly(n)$-qubit quantum
advice $\\{\ket{z_{\mathcal{O}}}\\}_{\mathcal{O}}$ such that

$\displaystyle\Pr_{(G,\mathcal{O})\leftarrow\mathcal{D}_{n}}[\forall
x\in\\{0,1\\}^{n}~{}\Pr[\mathcal{A}^{\mathcal{O}}(\ket{z_{\mathcal{O}}},x)=G(x)]\geq
1-\mathsf{negl}(n)]\geq 1-\mathsf{negl}(n).$

  2. 2.

(Hardness with Classical Advice.) For any unbounded-time algorithm
$\mathcal{B}$ that makes $\poly(n)$ classical queries to $\mathcal{O}$ and a
family of $\poly(n)$-bit classical advice
$\\{z_{\mathcal{O}}\\}_{\mathcal{O}}$,

$\displaystyle\Pr_{\begin{subarray}{c}(G,\mathcal{O})\leftarrow\mathcal{D}_{n}\\\
x\leftarrow\\{0,1\\}^{n}\end{subarray}}[\mathcal{B}^{\mathcal{O}}(z_{\mathcal{O}},x)=G(x)]\leq\frac{3}{5}$

for all sufficiently large $n$.

For proving Lemma 4.1, we prepare the following lemma.

######  Lemma 4.2.

Let $G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ be a uniformly random function. For
an unbounded-time algorithm $\mathcal{A}$ that makes $\poly(n)$ classical
queries to $G$ and a family of $\poly(n)$-bit classical advice
$\\{z_{G}\\}_{G}$, suppose that the following holds:

$\displaystyle\Pr_{G,x\leftarrow\\{0,1\\}^{n}}[\mathcal{A}^{G}(z_{G},x)=G(x)]>\frac{3}{5}.$

Then the probability that $x$ is contained in the query list is at least
$\frac{1}{20}$ for $\frac{1}{30}$ fraction of $x\in\\{0,1\\}^{n}$ for
sufficiently large $n$.

###### Proof.

For each $x\in\\{0,1\\}^{n}$, we define $G_{x}$ as the random function $G$
with its input on $x$ removed, i.e. $G_{x}(x^{\prime})=G(x^{\prime})$ for
$x^{\prime}\neq x$ and $G_{x}(x)=0$. Since $\mathcal{A}$ only makes classical
queries to $G$, the only way for it to distinguish $G$ from $G_{x}$ is to
query the oracle at $x$. Denote by $\delta_{x}$ the probability that $x$ is in
the query list of $\mathcal{A}^{G_{x}}$, where the probability is over the
randomness of $\mathcal{A}$ and $G_{x}$. We obtain that,

$\displaystyle|\Pr_{G}[\mathcal{A}^{G}(z_{G},x)=G(x)]-\Pr_{G}[\mathcal{A}^{G_{x}}(z_{G},x)=G(x)]|\leq\delta_{x}.$

Now we consider the case when we uniform randomly choose
$x\leftarrow\\{0,1\\}^{n}$, and require $\mathcal{A}^{G_{x}}(z_{G},x)$ to
output $G(x)$. This is exactly Yao’s box problem, where the adversary is
required to output $G(x)$ without querying $x$. By Lemma 2.9, we have the
following bound for Yao’s box with classical queries and classical advice:

$\displaystyle\Pr_{G,x}[\mathcal{A}^{G_{x}}(z_{G},x)=G(x)]\leq\frac{1}{2}+2\sqrt{\frac{|z_{G}|(Q+1)}{2^{n}}}=\frac{1}{2}+\mathsf{negl}(n)$

where we assume that $\mathcal{A}$ makes $Q$ queries. Thus we have that

$\displaystyle\Pr_{G,x}[\mathcal{A}^{G}(z_{G},x)=G(x)]-\Pr_{G,x}[\mathcal{A}^{G_{x}}(z_{G},x)=G(x)]\geq\frac{1}{10}-\mathsf{negl}(n),$

Therefore, we have

$\displaystyle\operatorname*{\mathbb{E}}_{x}[\delta_{x}]\geq\operatorname*{\mathbb{E}}_{x}\left[\left|\Pr_{G}[\mathcal{A}^{G}(z_{G},x)=G(x)]-\Pr_{G}[\mathcal{A}^{G_{x}}(z_{G},x)=G(x)]\right|\right]\geq\frac{1}{10}-\mathsf{negl}(n)$

We now show that $\delta_{x}$ is at least $\frac{1}{20}$ with probability
$\frac{1}{30}$ for sufficiently large $n$.

$\Pr_{x}\left[\delta_{x}\geq\frac{1}{20}\right]+\left(1-\Pr_{x}\left[\delta_{x}\geq\frac{1}{20}\right]\right)\cdot\frac{1}{20}\geq\mathbb{E}_{x}[\delta_{x}]\geq\frac{1}{10}-\mathsf{negl}(n)$
$\implies\Pr_{x}\left[\delta_{x}\geq\frac{1}{20}\right]\geq\frac{1}{20}-\mathsf{negl}(n)$

Thus for sufficiently large $n$, for a
$\frac{1}{20}-\mathsf{negl}(n)\geq\frac{1}{30}$ fraction of
$x\in\\{0,1\\}^{n}$, $\mathcal{A}$ will query $x$ with probability at least
$\frac{1}{20}$. ∎

Then we prove Lemma 4.1.

###### Proof of Lemma 4.1.

We define $\mathcal{D}_{n}$ to be the distribution that samples $G$ and
$\mathcal{O}$ as follows:

$\mathcal{D}_{n}$:

Let $C\subseteq\Sigma^{n}$ be the code in Corollary 3.4. It samples random
functions $G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}$ and $H^{(j)}:\\{0,1\\}^{\log
n}\times\Sigma\rightarrow\\{0,1\\}$ for $j\in[n]$ and defines $\mathcal{O}$ as
follows: $\mathcal{O}$ takes $x\in\\{0,1\\}^{n}$ and
$(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\in C^{n}$ as input, and outputs
$G(x)$ if there is $j\in[n]$ such that $f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x$
and outputs $\bot$ otherwise.101010Note that $x$ here plays the role of $r$ in
Corollary 3.4. For simplicity we will denote by
$\mathcal{H}=(H^{(1)},\dots,H^{(n)})$.

First, we show the easiness with quantum advice (Item 1). Let
$(\mathcal{A}^{\prime},\\{\ket{z^{\prime}_{\mathcal{H}}}\\}_{\mathcal{H}})$ be
the tuple of an algorithm and family of quantum advice in Item 1 of Corollary
3.4. We construct $(\mathcal{A},\\{\ket{z_{\mathcal{O}}}\\}_{\mathcal{O}})$
that satisfies Item 1 of Lemma 4.1.

In fact, we allow the advice $\ket{z_{\mathcal{O}}}$ to be a mixed state and
write it by $\rho_{\mathcal{O}}$. Note that this does not weaken the statement
since any mixed state can be considered as a distribution over pure states and
thus there must exist a pure state advice $\ket{z_{\mathcal{O}}}$ that is at
least as good as $\rho_{\mathcal{O}}$. The algorithm $\mathcal{A}$ and quantum
advice $\rho_{\mathcal{O}}$ is described as follows:

$\rho_{\mathcal{O}}$:

We describe a randomized procedure to set $\rho_{\mathcal{O}}$ given an oracle
$\mathcal{O}$. This should be understood as setting $\rho_{\mathcal{O}}$ to be
the mixed state corresponding to the output of the procedure. Sample
$(G,\mathcal{H})$ from the conditional distribution of $\mathcal{D}_{n}$
conditioned on the given $\mathcal{O}$. Note that then the joint distribution
of $(G,\mathcal{H},\mathcal{O})$ is identical to the real one. Then
$\rho_{\mathcal{O}}$ is set to be $\rho_{\mathcal{H}}$.

$\mathcal{A}^{\mathcal{O}}(\rho_{\mathcal{O}},x)$:

It runs $\mathbf{v}\leftarrow\mathcal{A}^{\prime}(\rho_{\mathcal{O}},x)$,
queries $(x,\mathbf{v})$ to $\mathcal{O}$, and outputs whatever $\mathcal{O}$
returns.

Then Item 1 of Corollary 3.4 implies

$\displaystyle\Pr_{(G,\mathcal{O})\leftarrow\mathcal{D}_{n}}[\forall
x\in\\{0,1\\}^{n}~{}\Pr[\mathcal{A}^{\mathcal{O}}(\rho_{\mathcal{O}},x)=G(x)]\geq
1-\mathsf{negl}(n)]\geq 1-\mathsf{negl}(n).$

Thus, Item 1 of Lemma 4.1 holds.

Next, we show the hardness with classical advice (Item 2). Suppose that there
is $(\mathcal{B},\\{z_{\mathcal{O}}\\}_{\mathcal{O}})$ that breaks it. Then we
have

$\displaystyle\Pr_{\begin{subarray}{c}(G,\mathcal{O})\leftarrow\mathcal{D}_{n}\\\
x\leftarrow\\{0,1\\}^{n}\end{subarray}}[\mathcal{B}^{\mathcal{O}}(z_{\mathcal{O}},x)=G(x)]>\frac{3}{5}$

for infinitely many $n\in\mathbb{N}$. Recall that $\mathcal{O}$ returns $G(x)$
only if the query $(x,(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)}))$ satisfies
$f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x$ for some $j\in[n]$. Thus, by a direct
reduction to Lemma 4.2, for a $\frac{1}{30}$ fraction of $x\in\\{0,1\\}^{n}$,
the query list of $\mathcal{B}$ to a randomly chosen $\mathcal{O}$ according
to $\mathcal{D}_{n}$ will contain a query of the form
$(x,(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)}))$ such that there is $j\in[n]$
such that $f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x$ with probability at least
$\frac{1}{20}$.

Also note that classical access to $\mathcal{O}$ can be simulated by classical
access to $G$ and $\mathcal{H}=(H^{(1)},\dots,H^{(n)})$. Thus, the above
directly gives an algorithm that violates the hardness with classical advice
and classical access to $\mathcal{H}$ (Item 2 of Corollary 3.4). To show this,
we go through the following steps:

  1. 1.

For each fixed $G$, we define a pair
$(\mathcal{B}^{\prime}[G],\\{z^{\prime}_{\mathcal{H}}[G]\\}_{\mathcal{H}})$ of
an adversary and advice in which $G$ is hardwired.

  2. 2.

Show that
$(\mathcal{B}^{\prime}[G],\\{z^{\prime}_{\mathcal{H}}[G]\\}_{\mathcal{H}})$
breaks Item 2 of Corollary 3.4 on average over the choice of $G$.

  3. 3.

Fix the “best” $G$ (w.r.t. random $\mathcal{H}$) to get a fixed pair of
algorithm and advice that breaks Item 2 of Corollary 3.4.

Specifically, it works as follows. For each $G$, we define
$(\mathcal{B}^{\prime}[G],\\{z^{\prime}_{\mathcal{H}}[G]\\}_{\mathcal{H}})$ as
follows:

$z^{\prime}_{\mathcal{H}}{[}G{]}$:

Construct $\mathcal{O}$ from $(G,\mathcal{H})$. Set
$z^{\prime}_{\mathcal{H}}[G]:=z_{\mathcal{O}}$.

${\mathcal{B}^{\prime}[G]}^{\mathcal{H}}(z^{\prime}_{\mathcal{H}}{[}G{]},x)$:

It runs $\mathcal{B}^{\mathcal{O}}(z^{\prime}_{\mathcal{H}}[G],x)$ where
$\mathcal{B}^{\prime}$ simulates the oracle $\mathcal{O}$ for $\mathcal{B}$ by
using its own oracle $\mathcal{H}$ and the hardwired oracle $G$ and outputs a
uniformly chosen query by $\mathcal{B}$.

By the above argument, we have

$\displaystyle\Pr_{G,\mathcal{H},x}[\exists
j\in[n]~{}\text{s.t.}~{}f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x:(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\leftarrow\mathcal{B}^{\prime}[G]^{\mathcal{H}}(z^{\prime}_{\mathcal{H}}[G],x)]\geq\frac{1}{600Q}$

where $Q$ is the number of queries by $\mathcal{B}$. Thus, by taking $G=G^{*}$
that makes the above probability the largest,
$(\mathcal{B}^{\prime},\\{z^{\prime}_{\mathcal{H}}\\}_{\mathcal{H}}):=(\mathcal{B}^{\prime}[G^{*}],\\{z^{\prime}_{\mathcal{H}}[G^{*}]\\}_{\mathcal{H}})$
breaks Item 2 of Corollary 3.4.111111At first glance, this argument seems to
allow $\mathcal{B}^{\prime}$ to be a non-uniform machine that takes $G$ as
advice. However, this is not needed since $\mathcal{B}^{\prime}$ can find the
best $G$ by itself by using its unbounded-time computational power.  ∎

Given Lemma 4.1, it is straightforward to prove a separation between
$\BQP/\qpoly$ and $\BQP/\poly$ relative to a classically-accessible classical
oracle by the standard diagonalization argument.

######  Theorem 4.3.

There is a classically-accessible classical oracle $\mathcal{O}$ relative to
which $\BQP/\poly\neq\BQP/\qpoly$.

###### Proof.

Suppose that we generate $(G,\mathcal{O})\leftarrow\mathcal{D}_{n}$ and define
a language $\mathcal{L}:=\bigsqcup_{n\in\mathbb{N}}G_{n}^{-1}(1)$ and an
oracle $\mathcal{O}$ that returns $\mathcal{O}_{|x|}(x)$ on a query
$x\in\\{0,1\\}^{*}$. We claim that $\mathcal{L}\in\BQP^{\mathcal{O}}/\qpoly$
and $\mathcal{L}\notin\BQP^{\mathcal{O}}/\poly$ with probability $1$.

To see $\mathcal{L}\in\BQP^{\mathcal{O}}/\qpoly$ with probability $1$, Item 1
of Lemma 4.1 implies that there is a $\BQP$ machine $\mathcal{A}$ with
polynomial-size quantum advice that decides $\mathcal{L}$ on all $x$ of length
$n$ with probability at least $1-\frac{1}{n^{2}}$ for all sufficiently large
$n$. Since $\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\pi^{2}/6$ is finite, the
Borel–Cantelli lemma implies that the probability that $\mathcal{A}$ fails on
infinitely many $n$ is $0$. In other words, the probability that there is $N$
such that $\mathcal{A}$ succeeds in deciding $\mathcal{L}$ on all $x$ such
that $|x|\geq N$ is $1$. By augmenting $\mathcal{A}$ to decide $\mathcal{L}$
by brute-force when the instance has length smaller than $N$, we can conclude
that there is a $\BQP$ machine with polynomial-size quantum advice that
decides $\mathcal{L}$ on all $x\in\\{0,1\\}^{*}$ with probability $1$ over the
random choice of $(G,\mathcal{O})$ for $n\in\mathbb{N}$.

Next, we prove $\mathcal{L}\notin\BQP^{\mathcal{O}}/\poly$ with probability
$1$. For a $\BQP$ machine $\mathcal{B}$ that takes $\ell(n)$-bit classical
advice for a polynomial $\ell$, we define $S_{\mathcal{B}}(n)$ to be the event
over the choice of $(G,\mathcal{O})$ that there is a $\ell(n)$-bit classical
advice $z_{\mathcal{O}}$ such that

$\Pr[\forall
x\in\\{0,1\\}^{n}~{}\mathcal{B}^{\mathcal{O}}(z_{\mathcal{O}},x)=G(x)]\geq\frac{2}{3}.$

Item 2 of Lemma 4.1 implies that there is an integer $N$ such that for any
$\BQP$ machine $\mathcal{B}$ with classical access to $\mathcal{O}$, we have
$\Pr_{G,\mathcal{O}}[S_{\mathcal{B}}(n)]\leq c$ for all $n\geq N$ where
$c:=9/10$. We now show that

$\Pr_{G,\mathcal{O}}[S_{\mathcal{B}}(1)\land S_{\mathcal{B}}(2)\land\dots]=0$

  * •

We will consider a sequence of input lengths $n_{1},n_{2},\dots$ defined by
$n_{1}:=N$ and $n_{i}:=T(n_{i-1})+1$, where $T(n)$ is the running time of
$\mathcal{B}$ on input of length $n$. This means that when $\mathcal{B}$’s
input length is $n_{i-1}$, it cannot touch the oracle on input length $\geq
n_{i}$. This guarantees that $\Pr[S_{\mathcal{B}}(n_{i})\mid
S_{\mathcal{B}}(n_{j})]=\Pr[S_{\mathcal{B}}(n_{i})]$ for all $i>j$.

  * •

We can now show that the probability that $\mathcal{B}$ succeeds on all inputs
is equal to $0$ over the choices of $G,\mathcal{O}$.

$\displaystyle\Pr[S_{\mathcal{B}}(1)\land S_{\mathcal{B}}(2)\land\dots]$
$\displaystyle\leq\Pr\left[\bigwedge_{i}S_{\mathcal{B}}(n_{i})\right]$
$\displaystyle=\Pr[S_{\mathcal{B}}(n_{1})]\cdot\Pr[S_{\mathcal{B}}(n_{2})\mid
S_{\mathcal{B}}(n_{1})]\cdot\dots$ $\displaystyle\leq c\cdot c\cdot\dots$
$\displaystyle=0$

Since there are countably many QPT machines,

$\Pr_{G,\mathcal{O}}[\exists\mathcal{B}~{}S_{\mathcal{B}}(1)\land
S_{\mathcal{B}}(2)\land\dots]=0.$

This means that $\mathcal{L}\not\in\BQP^{\mathcal{O}}/\poly$ with probability
$1$ over the choice of $(G,\mathcal{O})$. ∎

#### Stronger separations.

We can easily extend our proof to show
$\BQP/\qpoly\cap\NP\cap\coNP\not\subseteq\BQP/\poly$ relative to a
classically-accessible classical oracle. This can be seen by observing that
for any $x\in\\{0,1\\}^{n}$, we can use
$(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)})\in C^{n}$ such that
$f_{C}^{H^{(j)}}(\mathbf{v}^{(j)})=x$ for some $j\in[n]$ as a witness that
certifies $G(x)$. This means that the language $\mathcal{L}$ in the proof of
Theorem 4.3 is in $\NP\cap\coNP$. Moreover, we can further strengthen the
separation to show $\mathsf{YQP}\cap\NP\cap\coNP\not\subseteq\BQP/\poly$
relative to a classically-accessible classical oracle. Here, $\mathsf{YQP}$ is
the class of problems that can be decided by a $\BQP$ machine with _untrusted_
quantum advice, which was introduced in [Aar07] followed by a minor
definitional modification in [AD14]. This can be seen by observing that the
$\BQP/\qpoly$ algorithm for deciding the language $\mathcal{L}$ works even if
the advice is untrusted because its guess of $G(x)$ is correct whenever the
oracle $\mathcal{O}$ does not return $\bot$ on
$(x,(\mathbf{v}^{(1)},...,\mathbf{v}^{(n)}))$ where $\mathbf{v}^{(j)}$ are
candidate solutions to the YZ problem w.r.t. $H^{(j)}$ and $x$ generated by
using the given (potentially ill-formed) quantum advice.

##  5 $\QMA$ vs $\QCMA$ under Classically-Accessible Oracle

In this section, we demonstrate a $\QMA$ and $\QCMA$ separation relative to a
classically-accessible classical oracle.

#### Notation.

Let $C$ be the code in Theorem 3.2. (Remark that $C$ and $\Sigma$ are actually
indexed by $n$, but we omit it for notational simplicity. See Remark 3.) For
$n\in\mathbb{N}$, functions $G:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ and
$H:[n]\times\Sigma\rightarrow\\{0,1\\}$, and a subset
$S\subseteq\\{0,1\\}^{n}$, we define the following oracle:

$\mathcal{O}_{n}{[}G,H,S{]}$:

It takes $t\in\\{0,1\\}^{n}$ and $\mathbf{v}\in C$ as input and outputs $1$ if
$f_{C}^{H}(\mathbf{v})=G(t)$ and $t\notin S$ and otherwise outputs $0$.

The following is the key technical lemma for the separation between $\QMA$ and
$\QCMA$ relative to a classically-accessible oracle.

######  Lemma 5.1.

The following hold:

  1. 1.

(Distinguishability with Quantum Witness) There is a QPT algorithm
$\mathcal{A}$ that makes polynomially many classical queries and a polynomial
$\ell$ such that the following hold:

    1. (a)

There is an $\ell(n)$-qubit state $\ket{w}$ such that

$\Pr_{G,H}[\mathcal{A}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},\ket{w})=1]\geq
1-\mathsf{negl}(n)$

where $G\leftarrow\mathsf{Func}(\\{0,1\\}^{n},\\{0,1\\}^{n})$ and
$H\leftarrow\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$.

    2. (b)

For any $G$, $H$, $S\subseteq\\{0,1\\}^{n}$, and $\ell(n)$-qubit state
$\ket{w}$,

$\Pr[\mathcal{A}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},\ket{w})=1]\leq
1-\frac{|S|}{2^{n}}$

for all $n\in\mathbb{N}$.

  2. 2.

(Indistinguishability with Classical Witness) For any unbounded-time algorithm
$\mathcal{B}$ that makes polynomially many classical queries and polynomial
$s$, there is a negligible function $\mu$ such that for any family of
$s(n)$-bit classical witness $\\{w_{G,H}\\}_{G,H}$, there is a family
$\\{S_{G,H}\\}_{G,H}$ with $|S_{G,H}|\geq 2^{n}\cdot 2/3$ and

$\left|\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w_{G,H})=1]-\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S_{G,H}]}(1^{n},w_{G,H})=1]\right|\leq\mu(n).$

###### Proof.

We start with the distinguishability with quantum witness.

Distinguishability with quantum witness. We use the quantum advice of Theorem
3.2 as a witness. The algorithm $\mathcal{A}$ proceeds as follows: Sample a
random $t\in\\{0,1\\}^{n}$ and compute $r=G(t)$. Note that $r$ is also
uniformly random over $\\{0,1\\}^{n}$. Since we can generate $\mathbf{v}\in C$
such that $H(\mathbf{v})=r$ using the algorithm in Theorem 3.2 with
probability $1-\mathsf{negl}(n)$ over random $H,r$, $\mathcal{A}$ queries
$\mathcal{O}_{n}[G,H,S]$ with the generated $(t,\mathbf{v})$, and output the
query result. If $S=\emptyset$, the oracle should return 1 with probability
$1-\mathsf{negl}(n)$, else returns $0$ if the random $t\in S$, which happens
with probability $\frac{|S|}{2^{n}}$.

Indistinguishability with classical witness. In the following proof, unless
specified otherwise, we assume $G,H$ are uniformly sampled when using the
notation $\Pr_{G,H}[X]$.

The advantage for an unbounded-time algorithm $\mathcal{B}$ with classical
oracle queries to distinguish $(G,\mathcal{O}_{n}[G,H,\emptyset])$ from
$(G,\mathcal{O}_{n}[G,H,S_{G,H}])$ is at most the probability the queries of
$\mathcal{B}$ include an input $(t,\mathbf{v})$ on which the two oracles
differ. These inputs are precisely the ones that satisfy $t\in S_{G,H}$ and
$f_{C}^{H}(\mathbf{v})=G(t)$. Thus we define $\tilde{\mathcal{B}}$ to be the
adversary that is given oracle access to $(G,\mathcal{O}_{n}[G,H,\emptyset])$,
the same input as $\mathcal{B}$, and the set $S_{G,H}$ and outputs the first
query $(t,\mathbf{v})$ of $\mathcal{B}$ on which the two oracles differ, i.e.
$t\in S_{G,H}$ and $f_{C}^{H}(\mathbf{v})=G(t)$. (If there is no such query,
$\tilde{\mathcal{B}}$ aborts.) Then we have the following inequality:

$\displaystyle\left|\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w_{G,H})=1]-\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S_{G,H}]}(1^{n},w_{G,H})=1]\right|$
$\displaystyle\leq\Pr_{G,H}\left[t\in S_{G,H}\land
f_{C}^{H}(\mathbf{v})=G(t):(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w_{G,H},S_{G,H})\right]$

Note that one can simulate the oracle $(G,\mathcal{O}_{n}[G,H,\emptyset])$
using only access to $(G,H)$. Thus it suffices to prove the following:

######  Claim 5.2.

For any unbounded-time $\tilde{\mathcal{B}}$ that makes polynomially many
classical queries and polynomial $s$, there is a negligible function $\mu$
such that for any family of $s(n)$-bit classical advice $\\{w_{G,H}\\}_{G,H}$,
there is a family $\\{S_{G,H}\\}_{G,H}$ of subsets of $\\{0,1\\}^{n}$ such
that $|S_{G,H}|\geq 2^{n}\cdot 2/3$ and

$\Pr_{G,H}[t\in S_{G,H}\land
f_{C}^{H}(\mathbf{v})=G(t):(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G,H}(1^{n},w_{G,H},S_{G,H})]\leq\mu(n).$

We prove Claim 5.2 by reducing it to a similar statement with
$(P^{\prime},1-\delta)$-dense distributions by using Claim 2.13.121212We
cannot simply apply Theorem 2.8 here because the probability considered in
Claim 5.2 is not captured by security of a game in the ROM as defined in
Definition 2.5.

Let $Q$ be the number of queries by $\tilde{\mathcal{B}}$. Applying Claim 2.13
and Claim 2.14, for all $\gamma,\delta>0$, there is a family
$\\{\mathcal{D}_{G,H}\\}_{G,H}$ of convex combinations of finitely many
$(P^{\prime},1-\delta)$-dense distributions $\mathcal{D}_{G,H}$ such that for
any family $\\{S_{G,H}\\}_{G,H}$ of subsets of $\\{0,1\\}^{n}$,

$\displaystyle\begin{split}&\Big{|}\Pr_{G,H}[t\in S_{G,H}\land
f_{C}^{H}(\mathbf{v})=G(t):(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G,H}(1^{n},w_{G,H},S_{G,H})]\\\
&-\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H}\end{subarray}}[t\in
S_{G^{\prime},H^{\prime}}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t):(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S_{G^{\prime},H^{\prime}})]\Big{|}\quad\leq
2\gamma,\end{split}$ (1)

where $P^{\prime}=\frac{s+2\log 1/\gamma}{\delta\cdot n}$. Here we used Claim
2.13 which states that $\mathcal{D}_{G,H}$ is $\gamma$-close to $G,H$ for
$P^{\prime}=\frac{s_{G,H}+\log 1/\gamma}{\delta\cdot n}$, with $s_{G,H}$ being
the min-entropy deficiency of $G,H$ conditioned on $w_{G,H}$. Then we use
Claim 2.14 and “truncate” $s_{G,H}$ to a maximum of $s+\log 1/\gamma$ by only
increasing the distance between the two distributions by an additional
$\gamma$ additive factor.

Let us now construct a subset $S_{G^{\prime},H^{\prime}}$ that satisfies the
statement of our claim. We will begin by finding a randomized construction of
such a subset $S^{*}$ that will depend on all $(G,H,G^{\prime},H^{\prime})$,
and we will derandomize it to $S_{G^{\prime},H^{\prime}}$. For each $(G,H)$,
since $\mathcal{D}_{G,H}$ is a convex combination of
$(P^{\prime},1-\delta)$-dense distributions, it can be written as

$\mathcal{D}_{G,H}=\sum_{i}p_{G,H,i}\mathcal{D}_{G,H,i}$

where $0<p_{G,H,i}\leq 1$, $\sum_{i}p_{G,H,i}=1$ and each
$\mathcal{D}_{G,H,i}$ is a $(P^{\prime},1-\delta)$-dense distribution. Let
$\mathcal{I}_{G,H}$ be a distribution that samples $i$ with probability
$p_{G,H,i}$.

#### Randomized $S^{*}$.

The randomized subset $S^{*}$ is defined using Algorithm 1.

Procedure 1 Sampling $G^{\prime},H^{\prime},S^{*}$ from
$\mathcal{D}^{1}_{G,H}$

1: Sample $i$ according to $\mathcal{I}_{G,H}$.

2: Sample $G^{\prime},H^{\prime}$ from $\mathcal{D}_{G,H,i}$.

3: Define $S^{*}:=\\{\text{set of indices not fixed
by}~{}\mathcal{D}_{G,H,i}\\}$.

We proceed with proving Claim 5.2 with this randomized $S^{*}$. We will use
the notation $(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1}_{G,H}$ to
mean that we sample $(G^{\prime},H^{\prime},S^{*})$ according to Algorithm 1.
Since each $\mathcal{D}_{G,H,i}$ is a $(P^{\prime},1-\delta)$-dense
distribution, we have that $|S^{*}|\geq 2^{n}-P^{\prime}$ always.

Define $\mathcal{D}^{1,*}_{G,H}$ to be the distribution that samples
$(G^{\prime},H^{\prime})$ by first sampling
$(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1}_{G,H}$ and then
replacing $G^{\prime}(t)$ on all $t\in S^{*}$ by resampling according to the
$(1-\delta)$-dense distribution indicated by $\mathcal{D}_{G,H,i}$. By
definition, since we replace the non-fixed values of $G^{\prime}$ with a new
sample from the same $(1-\delta)$-dense distribution, the two distributions of
$G^{\prime}(t)$ for
$(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1}_{G,H}$ and
$(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}$ are the same.
Thus, we have

$\displaystyle\begin{split}&\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1}_{G,H}\end{subarray}}\left[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})\right]\\\
&=~{}\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}\left[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})\right].\end{split}$
(2)

Now we prove that

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})]\leq\mathsf{negl}(n).$
(3)

Note that

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})]$
$\displaystyle=\sum_{i\in[Q_{G^{\prime}}]}\left(\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}\left[t=t_{i}\land
t\in S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})\right]\right)$
$\displaystyle+\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}[t\notin\\{t_{1},...,t_{Q_{G^{\prime}}}\\}\land
t\in S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})].$

where $Q_{G^{\prime}}$ is the number of queries to $G^{\prime}$ and $t_{i}$ is
the $i$-th query to $G^{\prime}$. For each $i$, we will set the parameters
$\gamma=2^{-n}$ and $\delta=2^{-n^{c^{\prime\prime}}}$ (for a sufficiently
small constant $c^{\prime\prime}$ that will be specified below) to bound the
first term as follows:

$\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}\left[t=t_{i}\land
t\in S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})\right]\leq\mathsf{negl}(n).$

This is because of the following argument: We can decompose the above
probability as a weighted sum of probabilities over the
$(P^{\prime},1-\delta)$-dense distributions $\mathcal{D}_{G,H,i}$. Then, from
Claim 2.15, we can replace each $\mathcal{D}_{G,H,i}$ with its corresponding
$P^{\prime}$-bit-fixing distribution $\mathcal{D}^{\prime}_{G,H,i}$, while
only incurring an error of at most $Q\delta\cdot n$. Recall that $Q=\poly(n)$
is the number of queries that $\tilde{\mathcal{B}}$ makes to the oracle, and
we have upper-bounded $\log|Y|$ by $n$, since $G^{\prime}$ maps inputs to
$\\{0,1\\}^{n}$. Setting $\delta=2^{n^{-c^{\prime\prime}}}$ for a sufficiently
small $c^{\prime\prime}$ 131313In particular, we want $c^{\prime\prime}$ to be
smaller than the constant $c$ that appears in the list-recoverability of the
code in Theorem 3.2 so we can apply the same proof as Theorem 3.3 to show the
hardness of YZ with $P^{\prime}$-bit-fixing oracles., gives that by
substituting the corresponding bit-fixing distributions the advantage of the
adversary only increases negligibly.

Now it suffices to show the hardness of the YZ problem when
$G^{\prime},H^{\prime}$ are drawn from a $P^{\prime}$-bit-fixing distribution.
Recall that $P^{\prime}=\frac{s+2\log 1/\gamma}{\delta\cdot n}$, and thus
$P^{\prime}=\Theta\left(2^{n^{c^{\prime\prime}}}\poly(n)\right)$ for our
choice of parameters. The hardness of the YZ problem under $P^{\prime}$-bit-
fixing oracles can be shown by repeating exactly the same proof as that of
Theorem 3.3 noting that $G^{\prime}(t_{i})$ is uniformly random for
$\tilde{\mathcal{B}}$ before querying it when $t\in S^{*}$ and thus we can
embed a fresh problem instance $r\leftarrow\\{0,1\\}^{n}$ into
$G^{\prime}(t_{i})$. For the same proof to go through, we also need the fact
that
$P^{\prime}=\Theta\left(2^{n^{c^{\prime\prime}}}\poly(n)\right)<2^{n^{c}}$,
where $c<1$ is the positive constant such that the code $C$ satisfies
$(\zeta,2^{n^{c}},L)$-list-recoverability.

The second term

$\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{1,*}_{G,H}\end{subarray}}[t\notin\\{t_{1},...,t_{Q_{G^{\prime}}}\\}\land
t\in S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})]$

is bounded by $2^{-n}+\mathsf{negl}(n)$. We again use Claim 2.15 with the same
choice of parameters $(\gamma,\delta)$ to replace $(G^{\prime},H^{\prime})$
with their bit-fixing counterparts, while incurring negligible error. Now
$G^{\prime}(t)$ is uniformly random for $\tilde{\mathcal{B}}$ (since it was
never queried) and the probability that $f_{C}^{H^{\prime}}(\mathbf{v})$ is
equal to a uniformly random value is $2^{-n}$. Combining the above and
$Q_{G^{\prime}}=\poly(n)$, we get Equation 3.

#### Derandomizing $S^{*}$.

Our goal is to show that there exists a family of subsets
$\\{S_{G,H}\\}_{G,H}$ such that the statement holds. To do this, we will take
our randomized construction of $S^{*}$ and derandomize it to obtain a fixed
subset $S_{G^{\prime},H}$ for any $G^{\prime},H^{\prime}$. To this end, we
begin with sampling $G^{\prime},H^{\prime},S^{*}$ according to
$\mathcal{D}^{2}_{G,H}$, whose description is given in Algorithm 2.

Procedure 2 Sampling $G^{\prime},H^{\prime},S^{*}$ from
$\mathcal{D}^{2}_{G,H}$

1: Sample $i$ according to $\mathcal{I}_{G,H}$.

2: Sample $G^{\prime},H^{\prime}$ from $\mathcal{D}_{G,H,i}$.

3: ($\star$) Sample $i^{\prime}$ from the conditional distribution of $i$
conditioned on $(G,H,G^{\prime},H^{\prime})$. Formally, sample $i^{\prime}$
with probability
$\frac{p_{G,H,i^{\prime}}\cdot\Pr[(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H,i^{\prime}}]}{\sum_{i}p_{G,H,i}\cdot\Pr[(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H,i}]}$

4: ($\star$) Define $S^{*}:=\\{\text{set of indices not fixed
by}~{}\mathcal{D}_{G,H,i^{\prime}}\\}$.

Note that the distribution of $(G^{\prime},H^{\prime})$ from steps 1 and 2 is
$\mathcal{D}_{G,H}$. We will also denote with
$\mathcal{S}_{G,H,G^{\prime},H^{\prime}}$ the distribution of $S^{*}$ from
steps 3 and 4 conditioned on $(G,H,G^{\prime},H^{\prime})$. It is not hard to
see that the resulting distributions $\mathcal{D}^{1}_{G,H}$ and
$\mathcal{D}^{2}_{G,H}$ are equal, and thus Equation 3 gives:

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime},S^{*})\leftarrow\mathcal{D}^{2}_{G,H}\end{subarray}}[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})]\leq\mathsf{negl}(n).$

Writing $\mathcal{D}^{2}_{G,H}$ in terms of $\mathcal{D}_{G,H}$ and
$\mathcal{S}_{G,H,G^{\prime},H^{\prime}}$ gives:

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H}\\\
S^{*}\leftarrow\mathcal{S}_{G,H,G^{\prime},H^{\prime}}\end{subarray}}[t\in
S^{*}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S^{*})]\leq\mathsf{negl}(n).$
(4)

What we now have is that for a set $S^{*}$ sampled according to the
distribution $\mathcal{S}_{G,H,G^{\prime},H^{\prime}}$, the value of the LHS
is negligible. Thus, there must exist some fixed subset
$S_{G,H,G^{\prime},H^{\prime}}$ for every $(G,H,G^{\prime},H^{\prime})$ such
that

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H}\end{subarray}}[t\in
S_{G,H,G^{\prime},H^{\prime}}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S_{G,H,G^{\prime},H^{\prime}})]\leq\mathsf{negl}(n).$
(5)

Additionally, the above probability never uses the original $G,H$ oracles.
Hence we can apply a trivial averaging argument to conclude that there must
exist some fixed $S_{G^{\prime},H^{\prime}}$ that only depends on
$G^{\prime},H^{\prime}$ such that

$\displaystyle\Pr_{\begin{subarray}{c}G,H\\\
(G^{\prime},H^{\prime})\leftarrow\mathcal{D}_{G,H}\end{subarray}}[t\in
S_{G^{\prime},H^{\prime}}\land
f_{C}^{H^{\prime}}(\mathbf{v})=G^{\prime}(t)\colon(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G^{\prime},H^{\prime}}(1^{n},w_{G^{\prime},H^{\prime}},S_{G^{\prime},H^{\prime}})]\leq\mathsf{negl}(n).$
(6)

Now we combine Equations 1 and 6 where we set
$\delta=2^{-n^{c^{\prime\prime}}}$, $s=\poly(n)$, $Q=\poly(n)$, and
$\gamma=2^{-n}$, which implies that
$P^{\prime}=\Theta(2^{n^{c^{\prime\prime}}}\poly(n))$, and we conclude that

$\Pr_{G,H}[t\in S_{G,H}\land
f_{C}^{H}(\mathbf{v})=G(t):(t,\mathbf{v})\leftarrow\tilde{\mathcal{B}}^{G,H}(1^{n},w_{G,H},S_{G,H})]\leq\mathsf{negl}(n).$

Finally, recall that $|S_{G,H}|\geq 2^{n}-P^{\prime}\geq 2^{n}\cdot 2/3$ and
thus our condition on the sizes of the subsets is also satisfied. This
completes the proof of Claim 5.2, which in turn completes the proof of Lemma
5.1.

∎

Next, we give a corollary of Lemma 5.1, which is useful for showing the
separation between $\QMA$ and $\QCMA$ relative to a classically-accessible
oracle.

######  Corollary 5.3.

Let $\mathcal{A}$ and $\ell$ be as in Lemma 5.1. For any unbounded-time
algorithm $\mathcal{B}$ that makes polynomially many classical queries and
polynomial $s$, there is an integer $N_{\mathcal{B},s}$ such that either of
the following holds for all $n\geq N_{\mathcal{B},s}$:

  1. 1.

There are $G\in\mathsf{Func}(\\{0,1\\}^{n},\\{0,1\\}^{n})$ and
$H\in\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$ such that

    1. (a)

There is an $\ell(n)$-qubit state $\ket{w}$ such that
$\Pr[\mathcal{A}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},\ket{w})=1]\geq
2/3$.

    2. (b)

$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w)=1]<2/3$ for any
$w\in\\{0,1\\}^{s(n)}$.

  2. 2.

There are $G\in\mathsf{Func}(\\{0,1\\}^{n},\\{0,1\\}^{n})$,
$H\in\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$, and $S\subseteq\\{0,1\\}^{n}$
such that

    1. (a)

$\Pr[\mathcal{A}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},\ket{w})=1]\leq 1/3$ for any
$\ell(n)$-qubit state $\ket{w}$.

    2. (b)

There is $w\in\\{0,1\\}^{s(n)}$ such that
$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},w)=1]>1/3$.

###### Proof.

By Item 1a of Lemma 5.1 and a standard averaging argument, for
$1-\mathsf{negl}(n)$-fraction of $(G,H)$, there is an $\ell(n)$-qubit state
$\ket{w}$ such that

$\Pr[\mathcal{A}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},\ket{w})=1]\geq\frac{2}{3}$

for sufficiently large $n$. Let $\mathsf{Good}_{n}$ be the set of all such
$(G,H)$. Suppose that there is $(G,H)\in\mathsf{Good}_{n}$ such that
$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w)=1]<2/3$ for any
$w\in\\{0,1\\}^{s(n)}$. Then it implies that Item 1 of Corollary 5.3 is
satisfied. Thus, it suffices to prove that Item 2 of Corollary 5.3 is
satisfied assuming that for all $(G,H)\in\mathsf{Good}_{n}$, there is
$w\in\\{0,1\\}^{s(n)}$ such that
$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w)=1]\geq 2/3$. We
prove it below.

Since $\mathsf{Good}_{n}$ consists of $1-\mathsf{negl}(n)$-fraction of
$(G,H)$, a similar inequality to Item 2 of Lemma 5.1 holds even if we sample
$(G,H)$ from $\mathsf{Good}_{n}$, i.e., there is a negligible function
$\mu^{\prime}$ such that for any family of $s(n)$-bit classical advice
$\\{w_{G,H}\\}_{G,H}$, there is a subset $S\subseteq\\{0,1\\}^{n}$ such that
$|S|\geq 2^{n}\cdot 2/3$ and

$\left|\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w_{G,H})=1]-\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},w_{G,H})=1]\right|\leq\mu^{\prime}(n)$

where $(G,H)\leftarrow\mathsf{Good}_{n}$. In particular, there is
$(G,H)\in\mathsf{Good}_{n}$ such that for any $s(n)$-bit classical advice $w$,
there is a subset $S\subseteq\\{0,1\\}^{n}$ such that $|S|\geq 2^{n}\cdot 2/3$
and

$\left|\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w)=1]-\Pr_{G,H}[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},w)=1]\right|<\frac{1}{3}$

for sufficiently large $n$. We fix such $(G,H)$. Since
$(G,H)\in\mathsf{Good}_{n}$, by our assumption, there is
$w\in\\{0,1\\}^{s(n)}$ such that
$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,\emptyset]}(1^{n},w)=1]\geq 2/3$.
Combined with the above inequality, there are $w\in\\{0,1\\}^{s(n)}$ and a
subset $S\subseteq\\{0,1\\}^{n}$ such that $|S|\geq 2^{n}\cdot 2/3$ and
$\Pr[\mathcal{B}^{G,\mathcal{O}_{n}[G,H,S]}(1^{n},w)=1]>1/3$. This means that
Item 2b of Corollary 5.3 is satisfied. Moreover, since $|S|\geq 2^{n}\cdot
2/3$, Item 1b implies Item 2a of Corollary 5.3. Thus, Item 2 of Corollary 5.3
is satisfied. This completes the proof of Corollary 5.3. ∎

Given Corollary 5.3, it is straightforward to prove the separation of $\QMA$
and $\QCMA$ relative to a classically-accessible oracle using the standard
diagonalization argument.

######  Theorem 5.4.

There is a classically-accessible classical oracle relative to which
$\QMA\neq\QCMA$.

###### Proof of Theorem 5.4.

We enumerate all tuples $(\mathcal{B}_{1},s_{1}),(\mathcal{B}_{2},s_{2}),...$
where $\mathcal{B}_{j}$ is a QPT machine that makes polynomially many
classical queries and $s_{j}$ is a polynomial for $j\in\mathbb{N}$. Let
$T_{j}$ be a polynomial such that $\mathcal{B}_{j}$ runs in time $T_{j}(n)$
when it takes $1^{n}$ and $y\in\\{0,1\\}^{s_{j}(n)}$ as input. For a sequence
$\mathcal{O}=(\mathcal{O}_{1},\mathcal{O}_{2},...)$ of oracles
$\mathcal{O}_{n}:\\{0,1\\}^{n}\times C_{n}\rightarrow\\{0,1\\}$,
$n^{*}\in\mathbb{N}$, $G:\\{0,1\\}^{n^{*}}\rightarrow\\{0,1\\}^{n^{*}}$,
$H:[n^{*}]\times\Sigma^{n^{*}}\rightarrow\\{0,1\\}$, and
$S\subseteq\\{0,1\\}^{n^{*}}$, let $\tilde{\mathcal{O}}[G,H,S]$ be the same as
$\mathcal{O}$ except that the $n^{*}$-th oracle is replaced with
$\mathcal{O}_{n^{*}}[G,H,S]$. That is, we define
$\tilde{\mathcal{O}}[G,H,S]:=(\tilde{\mathcal{O}}_{1}[G,H,S],\tilde{\mathcal{O}}_{2}[G,H,S],...)$
where $\tilde{\mathcal{O}}_{n^{*}}[G,H,S]:=\mathcal{O}_{n^{*}}[G,H,S]$ and
$\tilde{\mathcal{O}}_{n}[G,H,S]:=\mathcal{O}_{n}$ for all $n\neq n^{*}$. We
define sequences of oracles $G^{(0)},G^{(1)},...$ and
$\mathcal{O}^{(0)},\mathcal{O}^{(1)},...$ and a sequence of bits
$\mathsf{flag}_{1},\mathsf{flag}_{2},...$ by the following procedure, where
for each $i$, $G^{(i)}$ and $\mathcal{O}^{(i)}$ themselves are also sequences
of oracles $G^{(i)}_{1},G^{(i)}_{2},...$ and
$\mathcal{O}^{(i)}_{1},\mathcal{O}^{(i)}_{2},...$, respectively, such that
$G^{(i)}_{n}:\\{0,1\\}^{n}\rightarrow\\{0,1\\}^{n}$ and
$\mathcal{O}^{(i)}_{n}:\\{0,1\\}^{n}\times C\rightarrow\\{0,1\\}$.

  1. 1.

Take $(G_{1}^{(0)},G_{2}^{(0)},...)$ and $(H_{1}^{(0)},H_{2}^{(0)},...)$ in
such a way that there is a $\ell(n)$-qubit state $\ket{w}$ such that

$\Pr[\mathcal{A}^{G_{n},\mathcal{O}_{n}[G_{n}^{(0)},H_{n}^{(0)},\emptyset]}(1^{n},\ket{w})=1]\geq
2/3$

for all $n\in\mathbb{N}$ where $\mathcal{A}$ and $\ell$ are as in Item 1 of
Lemma 5.1. Note that such $(G_{1}^{(0)},G_{2}^{(0)},...)$ and
$(H_{1}^{(0)},H_{2}^{(0)},...)$ exist by Item 1 of Lemma 5.1. Let
$\mathcal{O}^{(0)}:=(\mathcal{O}^{(0)}_{1},\mathcal{O}^{(0)}_{2},...)$ where
$\mathcal{O}^{(0)}_{n}:=\mathcal{O}_{n}[G_{n}^{(0)},H_{n}^{(0)},\emptyset]$
for $n\in\mathbb{N}$. Set $n_{0}:=1$ and $\mathsf{flag}_{n}:=1$ for all
$n\in\mathbb{N}$.

  2. 2.

For $i=1,2,...,$

    1. (a)

Let $n_{i}:=\max\\{T_{i-1}(n_{i-1})+1,N_{\mathcal{B}_{i},s_{i}}\\}$ where
$N_{\mathcal{B}_{i},s_{i}}$ is as in Corollary 5.3 where we define
$T_{0}(n_{0}):=1$ for convenience.

    2. (b)

Do either of the following:

      1. i.

If there are $G_{n_{i}}^{(i)}$ and $H_{n_{i}}^{(i)}$ such that

         * •

there is an $\ell(n_{i})$-qubit state $\ket{w}$ such that
$\Pr[\mathcal{A}^{G^{(i)},\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)},H_{n_{i}}^{(i)},\emptyset]}(1^{n_{i}},\ket{w})=1]\geq
2/3$, and

         * •

$\Pr[\mathcal{B}_{i}^{G^{(i)},\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)}H_{n_{i}}^{(i)},\emptyset]}(1^{n_{i}},w)=1]<2/3$
for any $w\in\\{0,1\\}^{s_{i}(n_{i})}$,

where $G_{n}^{(i)}:=G_{n}^{(i-1)}$ for all $n\neq n_{i}$ (which define
$G^{(i)}:=(G_{1}^{(i)},G_{2}^{(i)},...)$), then set
$\mathcal{O}^{(i)}:=\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)},H_{n_{i}}^{(i)},\emptyset]$.

      2. ii.

Otherwise, by Corollary 5.3, there are $G_{n_{i}}^{(i)}$, $H_{n_{i}}^{(i)}$,
and $S_{n_{i}}^{(i)}$ such that

         * •

$\Pr[\mathcal{A}^{G^{(i)},\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)},H_{n_{i}}^{(i)},S_{n_{i}}^{(i)}]}(1^{n_{i}},\ket{w})=1]\leq
1/3$ for any $\ell(n_{i})$-qubit state $\ket{w}$.

         * •

There is $w\in\\{0,1\\}^{s_{i}(n_{i})}$ such that
$\Pr[\mathcal{B}_{i}^{G^{(i)},\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)},H_{n_{i}}^{(i)},S_{n_{i}}^{(i)}]}(1^{n_{i}},w)=1]>1/3$.

where $G_{n}^{(i)}:=G_{n}^{(i-1)}$ for all $n\neq n_{i}$ (which define
$G^{(i)}:=(G_{1}^{(i)},G_{2}^{(i)},...)$). Set
$\mathcal{O}^{(i)}:=\tilde{\mathcal{O}}^{(i-1)}[G_{n_{i}}^{(i)},H_{n_{i}}^{(i)},S_{n_{i}}^{(i)}]$
and overwrite $\mathsf{flag}_{n_{i}}:=0$.

Let $G$ and $\mathcal{O}$ be oracles that are consistent to $G^{(i)}$ and
$\mathcal{O}^{(i)}$, respectively, on all $n\in[n_{i+1}-1]$ for all
$i\in\\{0\\}\cup\mathbb{N}$. (That is, for any $i\in\\{0\\}\cup\mathbb{N}$,
$n\in[n_{i+1}-1]$, $t\in\\{0,1\\}^{n}$, and $\mathbf{v}\in C$,
$G(t)=G_{n}^{(i)}(t)$ and
$\mathcal{O}(t,\mathbf{v})=\mathcal{O}_{n}^{(i)}(t,\mathbf{v})$.) They are
well-defined since we have $G_{n}^{(i+1)}=G_{n}^{(i)}$ and
$\mathcal{O}_{n}^{(i+1)}=\mathcal{O}_{n}^{(i)}$ for all $n\leq n_{i+1}-1$ by
the definitions of $G^{(i)}$ and $\mathcal{O}^{(i)}$. Let $\mathcal{L}$ be a
unary language defined as $\mathcal{L}:=\\{1^{n}:\mathsf{flag}_{n}=1\\}$. Then
by the definitions of $G$ and $\mathcal{O}$, $\mathcal{A}$ is a valid $\QMA$
verification algorithm for $\mathcal{L}$ i.e.,
$\mathcal{L}\in\QMA^{G,\mathcal{O}}$.141414Strictly speaking, $\mathcal{A}$
may not work as a $\QMA$ verifier for small $n$ on which
$\Pr[\mathcal{A}^{G_{n},\mathcal{O}_{n}[G_{n}^{(0)},H_{n}^{(0)},\emptyset]}(1^{n},\ket{w})=1]\geq
2/3$ does not hold. However, since there are only finitely many such $n$, we
can augment $\mathcal{A}$ to work on all $n\in\mathbb{N}$ by hardwiring the
correct outputs on all such $n$. Moreover, for any QPT machine
$\mathcal{B}_{i}$ with classical witness length $s_{i}$, it fails to be a
valid $\QCMA$ verification algorithm for $\mathcal{L}$ on input length
$n_{i}$. Thus, we have $\mathcal{L}\notin\QCMA^{G,\mathcal{O}}$. This
completes the proof of Theorem 5.4. ∎

##  6 $\QMA$ vs $\QCMA$ under Distributional Oracle

In this section, we demonstrate a $\QMA$ and $\QCMA$ separation relative to a
distributional quantumly-accessible classical oracle.

######  Lemma 6.1.

There exists a family of oracles
$\\{\mathcal{O}_{n}^{b}[H,r]\\}_{n\in\mathbb{N},b\in\\{0,1\\},H\in\mathcal{H}_{n},r\in\\{0,1\\}^{n},}$
and a distribution $\mathcal{D}_{n}$ over $\mathcal{H}_{n}\times\\{0,1\\}^{n}$
such that the following hold:

  1. 1.

(Distinguishability with Quantum Witness.) There exists QPT algorithm
$\mathcal{A}$ and $\poly(n)$-qubit quantum witness $\\{\ket{z_{H}}\\}_{H}$
such that

$\displaystyle\Pr_{\begin{subarray}{c}(H,r)\leftarrow\mathcal{D}_{n}\\\
b\leftarrow\\{0,1\\}\end{subarray}}[\mathcal{A}^{\mathcal{O}_{n}^{b}[H,r]}(\ket{z_{H}},r)=b]\geq
1-\mathsf{negl}(n).$

  2. 2.

(Indistinguishability with Classical Witness.) For any QPT algorithm
$\mathcal{B}$ and any polynomial $s$, there is a negligible function $\mu$
such that for any $s(n)$-bit classical witness $\\{z_{H}\\}_{H}$

$\displaystyle\left|\Pr_{\begin{subarray}{c}(H,r)\leftarrow\mathcal{D}_{n}\\\
b\leftarrow\\{0,1\\}\end{subarray}}[\mathcal{B}^{\mathcal{O}_{n}^{b}[H,r]}(z_{H},r)=b]-\frac{1}{2}\right|\leq\mu(n).$

###### Proof.

Let $C\subseteq\Sigma^{n}$ be the code in Theorem 3.2. Let
$\mathcal{H}_{n}:=\mathsf{Func}([n]\times\Sigma,\\{0,1\\})$. For a function
$H_{n}:[n]\times\Sigma\rightarrow\\{0,1\\}$ and $r_{n}\in\\{0,1\\}^{n}$, let
$\mathcal{O}_{n}^{b}[H,r]$ be an oracle that works as follows: if $b=1$,
$\mathcal{O}_{n}^{1}[H,r]$ takes $\mathbf{v}\in\Sigma^{n}$ as input and
outputs $1$ if $f_{C}^{H}(\mathbf{v})=r_{n}$ and outputs $0$ otherwise; if
$b=0$, $\mathcal{O}_{n}^{0}[H,r]$ always returns $0$ for all inputs
$\mathbf{v}\in\Sigma^{n}$. Note that $\mathcal{O}_{n}^{0}[H,r]$ does not
depend on $(H,r)$ at all, but we use this notation for convenience.

#### Distinguishability with quantum witness.

We use the quantum advice of Theorem 3.2 as a witness. Since we can generate a
$\mathbf{v}\in C$ such that $H(\mathbf{v})=r$ using the algorithm in Theorem
3.2 with probability $1-\mathsf{negl}(n)$ over random $H,r$, we query
$\mathcal{O}_{n}^{b}[H,r]$ with the generated $\mathbf{v}$, and outputs the
query result. If $b=1$, the oracle should return 1 with probability
$1-\mathsf{negl}(n)$, else it will always return $0$.

#### Indistinguishability with classical witness.

By the one-way to hiding lemma (Lemma 2.16), the probability that an
unbounded-time algorithm $\mathcal{B}$ can distinguish
$\mathcal{O}_{n}^{1}[H,r]$ from $\mathcal{O}_{n}^{0}[H,r]$ is related to the
probability that measuring a random query of $\mathcal{B}$ collapses to an
input on which the two oracles differ. The inputs $\mathbf{v}$ for which
$\mathcal{O}_{n}^{1}[H,r]$ and $\mathcal{O}_{n}^{0}[H,r]$ differ are precisely
the ones that satisfy $f_{C}^{H}(\mathbf{v})=r$. Thus if we define
$\mathcal{M}$ to be the adversary that outputs the measurement of a random
query of $\mathcal{B}$ we have

$\displaystyle\left|\Pr_{H,r}[\mathcal{B}^{\mathcal{O}_{n}^{1}[H,r]}(z_{H},r)=1]-\Pr_{H,r}[\mathcal{B}^{\mathcal{O}_{n}^{0}[H,r]}(z_{H},r)=1]\right|$
$\displaystyle\leq
2q\sqrt{\Pr\left[f_{C}^{H}(\mathbf{v})=r\mid\mathbf{v}\leftarrow\mathcal{M}^{\mathcal{O}_{n}^{0}[H,r]}(z_{H},r)\right]}$

where $q$ is the number of $\mathcal{B}$’s queries.

Since $\mathcal{O}_{n}^{0}[H,r]$ is an oracle with all-zeros, $\mathcal{M}$
can simulate it without access to $H$. Thus from Item 1 of Theorem 3.2, the
RHS is $\mathsf{negl}(n)$. This implies that for any unbounded-time algorithm
$\mathcal{B}$ that makes $\poly(n)$ quantum queries and a family of
$\poly(n)$-bit classical witness $\\{z_{H}\\}_{H}$,

$\displaystyle\left|\Pr_{H,r}[\mathcal{B}^{\mathcal{O}_{n}^{1}[H,r]}(z_{H},r)=1]-\Pr_{H,r}[\mathcal{B}^{\mathcal{O}_{n}^{0}[H,r]}(z_{H},r)=1]\right|\leq\mathsf{negl}(n).$

Equivalently, we have

$\displaystyle\left|\Pr_{H,r,b\leftarrow\\{0,1\\}}[\mathcal{B}^{\mathcal{O}_{n}^{b}[H,r]}(z_{H},r)=b]-\frac{1}{2}\right|\leq\mathsf{negl}(n).$

∎

We now use the standard diagonalization argument to translate the
indistinguishability result of Lemma 6.1 to a $\QMA$ and $\QCMA$ separation
with respect to a distributional quantumly-accessible classical oracle
$\mathcal{O}$.

######  Theorem 6.2.

There is a distributional quantumly-accessible classical oracle $\mathcal{O}$
relative to which $\QMA\neq\QCMA$.

###### Proof.

Let $\mathcal{L}$ be a unary language chosen uniformly at random, that is for
each $n$, we choose $b_{n}\leftarrow\\{0,1\\}$ independently and put $1^{n}$
into $\mathcal{L}$ if and only if $b_{n}=1$. The oracle
$\mathcal{O}=\\{\mathcal{O}_{n}\\}_{n\in\mathbb{N}}$ is chosen as follows
where we abuse the notation to write $r_{n}$ to mean an oracle that takes a
null string as input and outputs $r_{n}$:

  * •

If $1^{n}\in\mathcal{L}$ (i.e., $b_{n}=1$), then
$\mathcal{O}_{n}:=(\mathcal{O}^{1}_{n}[H_{n},r_{n}],r_{n})$ where
$(H_{n},r_{n})\leftarrow\mathcal{D}_{n}$.

  * •

If $1^{n}\not\in\mathcal{L}$ (i.e., $b_{n}=0$), then
$\mathcal{O}_{n}:=(\mathcal{O}^{0}_{n}[H_{n},r_{n}],r_{n})$ where
$(H_{n},r_{n})\leftarrow\mathcal{D}_{n}$.

We start with proving that $\mathcal{L}\in\QMA^{\mathcal{O}}$ with probability
1 over the choice of $\\{(b_{n},H_{n},r_{n})\\}_{n}$. The verifier $V$ works
as follows: It first queries $\mathcal{O}$ at point $0^{n}$, obtains the
random string $r_{n}$, then calls the algorithm in Lemma 6.1. Since for each
$n$, if $b_{n}=1$, the algorithm
$\mathcal{A}^{\mathcal{O}_{n}^{1}[H_{n},r_{n}]}(\ket{z_{H_{n}}},r_{n})$ will
return 1 with probability $1-\mathsf{negl}(n)$, and if $b_{n}=0$, the
$\mathcal{A}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(\ket{z},r_{n})$ will always
return 0 for all witness $\ket{z}$. Thus for each $n$ the verifier will fail
with probability $\mathsf{negl}(n)$. By applying the Borel-Cantelli lemma and
following the same arguments as in Theorem 4.3, we can prove that
$\mathcal{L}\in\QMA^{\mathcal{O}}$. Note that our final oracle distribution
$\mathcal{F}$ will fix $H_{n}$ for each $n$, thus here we allow the witness
$\ket{z_{H_{n}}}$ to depend on $H_{n}$.

Next, we prove $\mathcal{L}\not\in\QCMA^{\mathcal{O}}$ with probability $1$
over the choice of $\\{(b_{n},H_{n},r_{n})\\}_{n}$. Fix a QPT machine $V$ that
takes $\ell(n)$-bit classical witness for some polynomial $\ell$ and let
$S_{V}(n)$ be the event that $V^{\mathcal{O}}$ succeeds on $1^{n}$, that is
either

  * •

$1^{n}\in\mathcal{L}$ and there exists classical witness
$w_{\mathcal{O}}\in\\{0,1\\}^{\ell(n)}$ such that $V^{\mathcal{O}}$ accepts
$(1^{n},w_{\mathcal{O}})$ with probability at least $\frac{2}{3}$, or

  * •

$1^{n}\not\in\mathcal{L}$ and $V^{\mathcal{O}}$ accepts $(1^{n},w)$ with
probability at most $\frac{1}{3}$ for all $w\in\\{0,1\\}^{\ell(n)}$.

To be precise,

$\displaystyle S_{V}(n)=[$ $\displaystyle\exists
w\in\\{0,1\\}^{\ell(n)}:\Pr[V^{\mathcal{O}^{b_{n}=1}}(1^{n},w)=1]\geq 2/3]$
$\displaystyle\vee[\forall
w\in\\{0,1\\}^{\ell(n)}:\Pr[V^{\mathcal{O}^{b_{n}=0}}(1^{n},w)=1]\leq 1/3]$

We first show that for any QPT algorithm $V^{\mathcal{O}}$, there is a
distinguishing algorithm $\mathcal{B}^{\mathcal{O}_{n}^{b_{n}}[H_{n},r_{n}]}$
in Lemma 6.1 that has the same accept probability as $V^{\mathcal{O}}$ for all
given $(H_{1},H_{2},\dots)$.
$\mathcal{B}^{\mathcal{O}_{n}^{b_{n}}[H_{n},r_{n}]}$ takes the witness
$z_{\mathcal{O}}$, and it hardcodes all other $H_{i},b_{i}(i\neq n)$ in its
program, and it simulates the behaviour of $V^{\mathcal{O}}$ by randomly
choosing $r_{i}$ for $i\neq n$, and calculates $O_{i}^{b_{i}}[H_{i},r_{i}]$
for $i\neq n$ oracle queries, and when querying $n$, it queries its own
oracle. In the end, $\mathcal{B}$ sets its output to be the same as $V$. It
can be seen that

$\displaystyle\Pr_{H_{n},r_{n}}\left[\mathcal{B}^{\mathcal{O}_{n}^{b_{n}}[H_{n},r_{n}]}(w_{\mathcal{O}},r_{n})=1\right]=\Pr_{\\{r_{i}\\}_{i},H_{n}}\left[V^{\mathcal{O}}(1^{n},w_{\mathcal{O}})=1\mid\\{H_{i},b_{i}\\}_{i\neq
n}\right].$

Notice that on the left-hand side we can view $w_{\mathcal{O}}$ as a witness
$z_{H_{n}}$ as in Lemma 6.1.

Now we prove that there exists universal constant $c<1$ such that for any QPT
verification algorithm $V$, there exist infinitely many $n$ such that

$\Pr_{\\{(b_{n},H_{n},r_{n})\\}_{n}}[S_{V}(n)]<c.$

By our observation above, if we can prove that for all unbounded quantum
algorithms $\mathcal{B}$, the following inequality holds:

$\displaystyle\Pr_{H_{n},r_{n},b_{n}}[[E_{1}\wedge b_{n}=1]\vee[E_{2}\wedge
b_{n}=0]]<c,$

where

$\displaystyle E_{1}=\exists
w\in\\{0,1\\}^{\ell(n)}:\Pr[\mathcal{B}^{\mathcal{O}_{n}^{1}[H_{n},r_{n}]}(w,r_{n})=1]\geq
2/3,$ $\displaystyle E_{2}=\forall
w\in\\{0,1\\}^{\ell(n)}:\Pr[\mathcal{B}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(w,r_{n})=1]\leq
1/3,$

then $\Pr[S_{V}(n)]$ is also bounded by an averaging argument. We can see that

$\displaystyle\Pr[[E_{1}\wedge b_{n}=1]\vee[E_{2}\wedge
b_{n}=0]]=\frac{1}{2}(\Pr[E_{1}]+\Pr[E_{2}]).$

It can be seen that

$\displaystyle\Pr[E_{1}]=\Pr[E_{1}\wedge\neg E_{2}]+\Pr[E_{1}\wedge E_{2}].$

We prove $\Pr[E_{1}\wedge E_{2}]\leq\frac{4}{5}(1+2\mu(n))$ as follows. By
Item 2 of Lemma 6.1, for all polynomial sized $w_{H_{n}}$,

$\displaystyle\Pr_{H_{n},r_{n}}[\mathcal{B}^{\mathcal{O}_{n}^{1}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]-\Pr_{H_{n},r_{n}}[\mathcal{B}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]\leq
2\mu(n).$

By a standard averaging argument,151515Concretely, add $1$ to both sides,
apply Markov’s inequality, and then subtract $1$ from both sides. Then we see
that for at most $\frac{4}{5}(1+2\mu(n))$ fraction of $(H_{n},r_{n})$, we have
$\Pr[\mathcal{B}^{\mathcal{O}_{n}^{1}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]-\Pr[\mathcal{B}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]\geq
1/4$.  we can conclude that for at least $1-\frac{4}{5}(1+2\mu(n))$ fraction
of $(H_{n},r_{n})$,

$\Pr[\mathcal{B}^{\mathcal{O}_{n}^{1}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]-\Pr[\mathcal{B}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]<1/4,$

implying that if $E_{1}$ occurs, $E_{2}$ does not occur, i.e., there exists
$w_{H_{n}}\in\\{0,1\\}^{\ell(n)}$ such that

$\displaystyle\Pr[\mathcal{B}^{\mathcal{O}_{n}^{0}[H_{n},r_{n}]}(w_{H_{n}},r_{n})=1]>\frac{2}{3}-\frac{1}{4}>\frac{1}{3}.$

Thus we have that $\Pr[E_{1}\wedge E_{2}]\leq\frac{4}{5}(1+2\mu(n))$, giving
us

$\displaystyle\frac{1}{2}(\Pr[E_{1}]+$
$\displaystyle\Pr[E_{2}])\leq\frac{1}{2}(\Pr[E_{1}\wedge\neg
E_{2}]+\frac{4}{5}(1+2\mu(n))+\Pr[E_{2}])$
$\displaystyle\leq\frac{1}{2}(\Pr[\neg
E_{2}]+\frac{5}{6}+\Pr[E_{2}])=\frac{11}{12}.$

Thus, we can set $c:=11/12$.

We now show that

$\Pr_{\\{H_{n},r_{n},b_{n}\\}_{n}}[\exists V\;S_{V}(1)\land
S_{V}(2)\land\dots]=0.$

Consider a sequence of input lengths $n_{1},n_{2},\dots$, such that the
indistinguishability condition of Lemma 6.1 holds for $n_{i}$ and $n_{i}\geq
T(n_{i-1})+1$, where $T(n)$ is the running time of $V$ on input of length $n$.
This means that when $V$’s input length is $n_{i-1}$, it cannot touch the
oracle on input length $\geq n_{i}$. This guarantees that
$\Pr[S_{V}(n_{i})\mid S_{V}(n_{j})]=\Pr[S_{V}(n_{i})]$ for all $i>j$.

We can now show that the probability that $V$ succeeds on all inputs is equal
to $0$ over the choices of $H_{n},r_{n},b_{n}$.

$\displaystyle\Pr[S_{V}(1)\land S_{V}(2)\land\dots]$
$\displaystyle\leq\Pr\left[\bigwedge_{i}S_{V}(n_{i})\right]$
$\displaystyle=\Pr[S_{V}(n_{1})]\cdot\Pr[S_{V}(n_{2})\mid
S_{V}(n_{1})]\cdot\dots$ $\displaystyle\leq c\cdot c\cdot\dots$
$\displaystyle=0$

Since there are countably many $\QCMA$ machines, we have that

$\Pr_{\\{H_{n},r_{n},b_{n}\\}_{n}}[\exists V\;S_{V}(1)\land
S_{V}(2)\land\dots]=0.$

Thus $\mathcal{L}\not\in\QCMA^{\mathcal{O}}$ with probability $1$ over the
choice of $\\{H_{n},r_{n},b_{n}\\}_{n}$.

We conclude that by fixing $H_{n},b_{n}$ for each $n$, we can obtain a
language $\mathcal{L}$ in $\QMA^{\mathcal{O}}$ but not in
$\QCMA^{\mathcal{O}}$, where $\mathcal{O}$ is now a distribution over
$\\{r_{n}\\}_{n}$.

∎

##  7 One-Way Communication Complexity

We observe that the results of [YZ22, Liu22] (Theorem 3.2) can be seen as a
separation of classical and quantum one-way communication complexity. Consider
the following protocol between Alice and Bob where we use the notations
defined in Section 3.

Alice’s input:

A truth table of a function $H:[n]\times\Sigma\rightarrow\\{0,1\\}$.

Bob’s input:

A string $r=(r_{1},...,r_{n})\in\\{0,1\\}^{n}$.

One-way communication:

Alice sends a classical or quantum message $m$ to Bob.

Bob’s output:

Bob outputs $\mathbf{v}=(\mathbf{v}_{1},...,\mathbf{v}_{n})\in C$. We say that
Bob wins if $H_{i}(\mathbf{v}_{i})=r_{i}$ for all $i\in[n]$.

Quantum (resp. classical) one-way communication complexity is defined to be
the minimum length of the quantum (resp. classical) message $m$ that enables
Bob to win with high probability (say, $2/3$). Theorem 3.2 directly means that
quantum one-way communication complexity is $\poly(n)$ but classical one-way
communication complexity is super-polynomial in $n$ (one can see that it is
actually subexponential in $n$ from its proof).161616Strictly speaking, Item 1
of Theorem 3.2 only ensures the existence of a quantum communication protocol
with $\poly(n)$-qubit communication that works on average over random $H$. In
the standard definition of one-way communication complexity, we require a
protocol to work for all inputs. For ensuring that, we have to rely on the
perfectly correct version of [YZ22] that can be found at the end of [YZ22,
Section 4].  This gives a new super-polynomial separation between classical
and quantum one-way communication complexity. Such a separation is already
known back in 2004 by Bar-Yossef, Jayram, and Kerenidis [BYJK04] where they
showed it based on a problem called the hidden matching problem. However, our
protocol has the following two interesting features compared to theirs.

First, Bob’s input length is exponentially smaller than Alice’s input length.
Why is that interesting? To give the context, we review the following theorem
shown by Aaronson [Aar07].

######  Theorem 7.1.

For any (possibly partial) boolean function
$f:\\{0,1\\}^{N}\times\\{0,1\\}^{M}\rightarrow\\{0,1\\}$,
$\mathcal{R}^{1}(f)=O(M\mathcal{Q}^{1}(f))$.

Here, $\mathcal{Q}^{1}$ and $\mathcal{R}^{1}$ mean the quantum and classical
randomized bounded-error one-way communication complexity, respectively. This
theorem means that we cannot have a large quantum-classical separation for
boolean functions if Bob’s input length is small. We circumvent this barrier
by considering _relations_ rather than functions.171717Interestingly, a
similar observation was made by a concurrent work [ABK23] where they show a
variant of the hidden matching problem with short Bob’s input length. This is
reminiscent of [YZ22] that overcomes the barrier of Aaronson-Ambainis
conjecture [AA14] by considering search problems rather than decision
problems.

Second, by Theorem 3.3, one can see that the hardness with classical
communication remains to hold even if we allow Bob to classically query
Alice’s input. On the other hand, the hidden matching problem becomes
completely easy if we allow such classical queries. This property is the key
to show $\BQP/\poly\neq\BQP/\qpoly$ and $\QMA\neq\QCMA$ relative to
classically-accessible classical oracles.

##  8 Acknowledgements

The authors would like to thank Shalev Ben-David and Srijita Kundu for
pointing out an issue with a proof in a prior version of this paper.

## References

  * [AA14] Scott Aaronson and Andris Ambainis.  The need for structure in quantum speedups.  Theory Comput., 10:133–166, 2014.
  * [Aar05] Scott Aaronson.  Limitations of quantum advice and one-way communication.  Theory Comput., 1(1):1–28, 2005.
  * [Aar07] Scott Aaronson.  The learnability of quantum states.  Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 463(2088):3089–3114, sep 2007.
  * [ABK23] Scott Aaronson, Harry Buhrman, and William Kretschmer.  A qubit, a coin, and an advice string walk into a relational problem, 2023\.
  * [AD14] Scott Aaronson and Andrew Drucker.  A full characterization of quantum advice.  SIAM J. Comput., 43(3):1131–1183, 2014.
  * [AHU19] Andris Ambainis, Mike Hamburg, and Dominique Unruh.  Quantum security proofs using semi-classical oracles.  In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 269–295. Springer, Heidelberg, August 2019.
  * [AK07] Scott Aaronson and Greg Kuperberg.  Quantum versus classical proofs and advice.  In Twenty-Second Annual IEEE Conference on Computational Complexity (CCC’07), pages 115–128. IEEE, 2007.
  * [AN02] Dorit Aharonov and Tomer Naveh.  Quantum np - a survey.  arXiv, 2002.
  * [AST+03] Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, and Avi Wigderson.  The quantum communication complexity of sampling.  SIAM J. Comput., 32(6):1570–1585, 2003.
  * [BCW98] Harry Buhrman, Richard Cleve, and Avi Wigderson.  Quantum vs. classical communication and computation.  In Jeffrey Scott Vitter, editor, Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23-26, 1998, pages 63–68. ACM, 1998.
  * [BDF+11] Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, and Mark Zhandry.  Random oracles in a quantum world.  In Dong Hoon Lee and Xiaoyun Wang, editors, ASIACRYPT 2011, volume 7073 of LNCS, pages 41–69. Springer, Heidelberg, December 2011\.
  * [BYJK04] Ziv Bar-Yossef, T. S. Jayram, and Iordanis Kerenidis.  Exponential separation of quantum and classical one-way communication complexity.  In László Babai, editor, 36th ACM STOC, pages 128–137. ACM Press, June 2004.
  * [CDGS18] Sandro Coretti, Yevgeniy Dodis, Siyao Guo, and John P. Steinberger.  Random oracles and non-uniformity.  In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 227–258. Springer, Heidelberg, April / May 2018.
  * [CGLQ20] Kai-Min Chung, Siyao Guo, Qipeng Liu, and Luowen Qian.  Tight quantum time-space tradeoffs for function inversion.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 673–684. IEEE, 2020.
  * [CLQ19] Kai-Min Chung, Tai-Ning Liao, and Luowen Qian.  Lower bounds for function inversion with quantum advice.  arXiv preprint arXiv:1911.09176, 2019.
  * [DTT10] Anindya De, Luca Trevisan, and Madhur Tulsiani.  Time space tradeoffs for attacks against one-way functions and PRGs.  In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 649–665. Springer, Heidelberg, August 2010.
  * [FK18] Bill Fefferman and Shelby Kimmel.  Quantum vs. classical proofs and subset verification.  In Igor Potapov, Paul G. Spirakis, and James Worrell, editors, 43rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2018, August 27-31, 2018, Liverpool, UK, volume 117 of LIPIcs, pages 22:1–22:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [Gav08] Dmitry Gavinsky.  Classical interaction cannot replace a quantum message.  In Proceedings of the fortieth annual ACM symposium on Theory of computing, pages 95–102, 2008.
  * [GLLZ21] Siyao Guo, Qian Li, Qipeng Liu, and Jiapeng Zhang.  Unifying presampling via concentration bounds.  In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 177–208. Springer, Heidelberg, November 2021\.
  * [Hel80] Martin Hellman.  A cryptanalytic time-memory trade-off.  IEEE transactions on Information Theory, 26(4):401–406, 1980.
  * [HXY19] Minki Hhan, Keita Xagawa, and Takashi Yamakawa.  Quantum random oracle model with auxiliary input.  In Advances in Cryptology–ASIACRYPT 2019: 25th International Conference on the Theory and Application of Cryptology and Information Security, Kobe, Japan, December 8–12, 2019, Proceedings, Part I, pages 584–614. Springer, 2019.
  * [Liu22] Qipeng Liu.  Non-uniformity and quantum advice in the quantum random oracle model.  arXiv, 2022.
  * [NABT14] Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, and Luca Trevisan.  Quantum lower bound for inverting a permutation with advice.  arXiv preprint arXiv:1408.3193, 2014.
  * [NN22] Anand Natarajan and Chinmay Nirkhe.  A classical oracle separation between qma and qcma.  arXiv, 2022.
  * [NY04] Harumichi Nishimura and Tomoyuki Yamakami.  Polynomial time quantum computation with advice.  Inf. Process. Lett., 90(4):195–204, 2004.
  * [Raz99] Ran Raz.  Exponential separation of quantum and classical communication complexity.  In 31st ACM STOC, pages 358–367. ACM Press, May 1999.
  * [Unr07] Dominique Unruh.  Random oracles and auxiliary input.  In Alfred Menezes, editor, CRYPTO 2007, volume 4622 of LNCS, pages 205–223. Springer, Heidelberg, August 2007.
  * [Unr15] Dominique Unruh.  Revocable quantum timed-release encryption.  J. ACM, 62(6):49:1–49:76, 2015.
  * [Yao90] Andrew Chi-Chih Yao.  Coherent functions and program checkers (extended abstract).  In 22nd ACM STOC, pages 84–94. ACM Press, May 1990.
  * [Yao93] Andrew Chi-Chih Yao.  Quantum circuit complexity.  In 34th FOCS, pages 352–361. IEEE Computer Society Press, November 1993.
  * [YZ22] Takashi Yamakawa and Mark Zhandry.  Verifiable quantum advantage without structure.  FOCS 2022: 63rd IEEE Symposium on Foundations of Computer Science, 2022\.