††thanks: Tom Gur is supported by the UKRI Future Leaders Fellowship
MR/S031545/1.††thanks: SRM is supported by the National Science Foundation
under the QLCI program through grant number OMA-2016245 and the Clarendon
Fund.††thanks: Justin Thaler is supported in part by NSF CAREER award
CCF-1845125, NSF SPX award CCF-1918989, and DARPA under Agreement No.
HR00112020022. Any opinions, findings and conclusions or recommendations
expressed in this material are those of the author and do not necessarily
reflect the views of the United States Government or DARPA.

# Quantum Proofs of Proximity

Marcel Dall’Agnol<EMAIL_ADDRESS>Tom Gur  Department of Computer Science,
University of Warwick, UK<EMAIL_ADDRESS>Subhayan Roy Moulik
Department of Mathematics, UC Berkeley, USA & Department of Computer Science,
University of Oxford, UK<EMAIL_ADDRESS>Justin Thaler  Department of
Computer Science, Georgetown University, USA<EMAIL_ADDRESS>
###### Abstract

We initiate the systematic study of QMA algorithms in the setting of property
testing, to which we refer as _QMA proofs of proximity_ (QMAPs). These are
quantum query algorithms that receive explicit access to a sublinear-size
untrusted proof and are required to accept inputs having a property $\Pi$ and
reject inputs that are $\varepsilon$-far from $\Pi$, while only probing a
minuscule portion of their input.

We investigate the complexity landscape of this model, showing that QMAPs can
be _exponentially_ stronger than both classical proofs of proximity and
quantum testers. To this end, we extend the methodology of Blais, Brody, and
Matulef (Computational Complexity, 2012) to prove quantum property testing
lower bounds via reductions from communication complexity. This also resolves
a question raised in 2013 by Montanaro and de Wolf (cf. Theory of Computing,
2016).

Our algorithmic results include a purpose an algorithmic framework that
enables quantum speedups for testing an expressive class of properties,
namely, those that are succinctly _decomposable_. A consequence of this
framework is a QMA algorithm to verify the Parity of an $n$-bit string with
$O(n^{2/3})$ queries and proof length. We also propose a QMA algorithm for
testing graph bipartitneness, a property that lies outside of this family, for
which there is a quantum speedup.

###### Contents

  1. 1 Introduction
    1. 1.1 Quantum proofs of proximity
    2. 1.2 Our results
      1. 1.2.1 Complexity separations
      2. 1.2.2 Algorithms
    3. 1.3 Technical overview
      1. 1.3.1 Lower bounds
      2. 1.3.2 Algorithmic techniques
    4. 1.4 Open problems
  2. 2 Preliminaries
  3. 3 QMA Proofs of Proximity
    1. 3.1 Definition
  4. 4 Complexity separations
    1. 4.1 Preliminaries
    2. 4.2 MAPs versus quantum testers
    3. 4.3 Quantum testers versus MAPs
  5. 5 A hard class of problems for QMAPs
  6. 6 Quantum speedups for proximity-oblivious MAPs
  7. 7 Decomposable properties
    1. 7.1 Boosting decompositions via amplitude amplification
    2. 7.2 $k$-monotonicity
    3. 7.3 Exact problems
      1. 7.3.1 Parity
      2. 7.3.2 Branching programs
  8. 8 Bipartiteness in bounded-degree graphs
  9. A A QCMAP lower bound for testing unitaries
  10. B Interaction versus quantum proofs

##  1 Introduction

Quantum property testing is a fundamental model of sublinear-time quantum
computation. Its importance stems both from the practical difficulty in
manipulating large quantum states, as well as from the fertile ground that it
provides for complexity theoretic investigations of the power of quantum
mechanics as a computational resource. Accordingly, this model has garnered a
large amount of attention in the last decade (see, e.g., [22, 52, 8, 21, 64,
9, 61, 3, 12, 32, 18], and the survey [60]).

Building on the vast literature of classical property testing (cf. the recent
book [35]), quantum testers are defined as quantum query algorithms that solve
the _approximate_ decision problem of membership in a subset $\Pi$ (of
possibly quantum objects), which is typically referred to as a _property_ ;
that is, the tester must accept if its input is in the property $\Pi$ and
reject if it is _far_ from $\Pi$ with respect to a natural metric.

This paper is concerned with the notion of QMA proofs, the quantum analogue of
NP proofs, in property testing. Namely, we investigate the following question:

_What is the power of QMA proofs for quantum property testing?_

###  1.1 Quantum proofs of proximity

The question of decision versus verification is foundational in theoretical
computer science, and extends far beyond $\mathcal{P}$ vs. $\mathcal{NP}$.
Indeed, the study of _classical_ proof systems in the property testing setting
is well established [29, 13, 72, 53, 37, 14, 45, 15, 46, 47, 41, 69, 71].
These objects are called _proofs of proximity_ , and include, among others,
PCPs of proximity, interactive proofs of proximity, and MA proofs of proximity
(MAPs). We henceforth adopt this standard terminology, noting it is synonymous
with _proof systems in the property testing setting_.

A _Quantum Merlin-Arthur_ (QMA) proof of proximity protocol for a property _of
unitaries_ $\Pi$,111We note that testing unitaries is not the only sensible
definition; see Remark 1 for a discussion. with respect to proximity parameter
$\varepsilon$, is defined as follows. The _verifier_ , a computational device
given oracle access to a unitary $U$, receives a quantum state $\ket{\phi}$
from an all-powerful but untrusted _prover_. Making use of these two
resources, it must decide whether $U\in\Pi$ or $U$ is $\varepsilon$-far from
$\Pi$ with respect to a specific metric.222Note that, unlike in the classical
case, where Hamming distance is with few exceptions the natural choice, there
are many natural metrics on the set of unitary matrices (e.g., those induced
by the operator or Hilbert-Schmidt norms). Such a protocol is said to verify
(or _test_) $\Pi$ if, with high probability, the verifier accepts in the
former case and rejects in the latter (see Section 3 for a formal definition).
We remark that the notion of QMA proofs of proximity is implicit in the
literature as QMA query algorithms for approximate decision problems (e.g.,
the permutation testing problem [2, 73]). In this paper, we initiate the
systematic study of the notion of QMA proofs of proximity (QMAPs), and explore
its power and limitations.

The complexity of a QMAP protocol is measured with respect to the amount of
resources required by the verifier. Namely, we will evaluate the efficiency of
a protocol by its _proof complexity_ $p$ (the number of qubits in the proof
$\ket{\psi}$) and _query complexity_ $q$ (the number of oracle calls made by
the verifier for a worst-case input $U$). In particular, both parameters
should be _sublinear_ in nontrivial protocols.

Before proceeding to state our results, we briefly discuss three applications
that underscore the motivation to study quantum proofs of proximity.

##### Delegated remote quantum computation.

With efficient data structures such as QRAM [33] and reliable communication
channels, one may envision a new paradigm of computing – where the data is
stored in a trusted data centre, and can be accessed (in coherent
superposition) by a remote quantum computer (c.f. [57]). This allows a
$O(n)$-qubit computer to access $2^{n}$ different locations of the data in
single query. This setting motivates the need for protocols for _delegated
remote computation_ , where a remote client interacts with a (powerful) server
in order to perform computation (on remote data) that it could not perform on
its own, but without trusting the server. Current experimental developments
such as [59, 56, 26] further support this possibility [78].

In this setting, suppose a client wants to compute a function $f$ on the data,
$x$. While the client cannot even load the entire database $x$, the server may
compute and send $y=f(x)$ to the client and append a proof of proximity that
asserts $f(x)=y$. This enables the client to check, with sublinear resources,
that $x$ is not far from satisfying $f(x)=y$, i.e., that $x$ is close in, say,
Hamming distance to an input $x^{\prime}$ satisfying $f(x^{\prime})=y$.
Quantum proofs may allow for efficient remote _quantum_ computation. This
extends the study of verifiable quantum computing (c.f. [31]) to the setting
where the input is held in a data centre.

##### Quantum certification.

Suppose a manufacturer produces a device that it claims implements a quantum
circuit with high fidelity. However, we do not have access to the architecture
or authority to crack open the device and examine it. The physical device is
given to us as a black box, into which we may feed a quantum state and receive
another quantum state as output.

If we do not trust the manufacturer and would like to assert that the device
is indeed implementing the claimed functionality, one alternative is to
perform tomography and characterise its input-output behaviour. This needs
extensive resources, however; to characterise an $n$-bit transformation,
$2^{\Omega(n)}$ uses of the device are required [48, 65]. Alternatively, we
could require the manufacturer to provide a QMA proof of proximity that
certifies the operation of the device is at least _close_ to what is expected.

The task of benchmarking and certification of quantum devices has been a
prominent topic of research [28]. In fact, the idea of using tools from
property testing to this end has been suggested in past works [23, 50, 51, 12]
and is closely related to self-testing [76, 70, 75] and the more recent
programme, on quantum algorithmic measurements, that gives a complexity
theoretic perspective on experimental physics and already has applications in
characterisation of quantum many-body systems [6].

##### Complexity class separations in property testing.

A fundamental question in quantum complexity is to determine whether
$\mathcal{QMA}$ (the quantum analog of $\mathcal{NP}$) is strictly more
powerful than $\mathcal{BQP}$ (the quantum analog of $\mathcal{P}$). Quantum
proofs of proximity offer a natural setting to study analogous questions. As
we explain shortly, we show unconditionally that in the property testing
setting, $\mathcal{QMA}$ protocols are exponentially more powerful than both
$\mathcal{BQP}$ and (classical) $\mathcal{MA}$ protocols for certain problems,
and thus that QMA proofs of proximity are “larger than the sum of their parts”
(see Section 1.2.2). We further show that they nevertheless have limited
power, and investigate the complexity landscape surrounding QMAPs (see Section
1.2.1).

######  Remark 1 (Operators vs. states).

The fact that the set of objects subject to testing are _unitaries_ is a
definitional matter of importance. Property testing of quantum objects can be
(roughly) divided into two classes: testing unitaries, as in this work, and
testing _states_. The complexity of quantum testers for the latter is
generally quantified by the number of copies of the state that are necessary
(see, e.g., [60]). Testing (pure) states can be seen as a special case of
testing unitaries: a property $\Pi$ of $n$-qubit states defines a property
$\Lambda$ of $n$-qubit unitaries $U$ such that (say) $U\ket{0^{n}}\in\Pi$ with
the metric on unitaries induced by that on states. (One may also generalise
testing mixed states similarly by considering quantum channels.)

However, if $\Pi$ is a set of states and allowing for _entanglement between
the state being tested and that given as proof_ yields a markedly different
model; indeed, its study may shed light on the _quantum PCP conjecture_ [5].

###  1.2 Our results

Our main results are divided into two parts: Section 1.2.1 charts fundamental
aspects of the complexity landscape surrounding quantum proofs of proximity,
while Section 1.2.2 covers algorithmic results, where we show sufficient
conditions for properties to admit efficient QMAP protocols.

We write $\mathcal{QMAP}(\varepsilon,p,q)$ for the class of
$\varepsilon$-testable properties by a QMA proof of proximity protocol with
proof length $p$ and query complexity $q$ (non-calligraphic acronyms to refer
to algorithms and protocols, while calligraphic letters denote complexity
classes).

####  1.2.1 Complexity separations

Our first collection of results aims to chart the complexity landscape of
quantum proofs of proximity. Recall that $\mathcal{QMAP}(\varepsilon,p,q)$ is
the class of $\varepsilon$-testable properties by a QMAP with proof complexity
$p$ and query complexity $q$. The classes $\mathcal{MAP}$ (MA proofs of
proximity) and $\mathcal{IPP}$ (interactive proofs of proximity) are defined
analogously. $\mathcal{PT}(\varepsilon,q)$ and $\mathcal{QPT}(\varepsilon,q)$
are the properties admitting classical and quantum $\varepsilon$-testers with
query complexity $q$, respectively, and $\mathcal{QCMAP}(\varepsilon,p,q)$ is
the restriction of $\mathcal{QMAP}(\varepsilon,p,q)$ where the proofs are
classical bit strings. Formal definitions of all of these classes can be found
in Section 2 and Section 3.1.

We write complexity classes with the parameters omitted (e.g.,
$\mathcal{QMAP}$) to denote the corresponding class of properties such that
for some proximity parameter $\varepsilon\in(0,1)$ that is a universal
constant, there is a protocol with proof and query complexities bounded by
$\operatorname{polylog}(n)$.

We begin by showing the existence of a property that admits efficient QMAPs,
yet neither quantum property testers nor MAPs can efficiently test it.

######  Theorem 1.

There exists a property $\Pi$ such that, for any small enough constant
$\varepsilon>0$,

$\displaystyle\Pi$ $\displaystyle\in\mathcal{QMAP}(\varepsilon,\log
n,O(1))\text{ and}$ $\displaystyle\Pi$
$\displaystyle\notin\mathcal{QPT}(\varepsilon,o(n^{0.49}))\cup\mathcal{MAP}(\varepsilon,p,q)$

when $p\cdot q=o(n^{1/4})$. In particular,

$\mathcal{QMAP}\not\subseteq\mathcal{QPT}\cup\mathcal{MAP}\;.$

1 is, in fact, implied by a stronger result. We show that, for certain
properties, MAPs are stronger than quantum testers, i.e.
$\mathcal{MAP}\not\subseteq\mathcal{QPT}$ (Theorem 4.3); and, for others,
quantum testers are stronger than MAPs, i.e.
$\mathcal{QPT}\not\subseteq\mathcal{MAP}$ (Theorem 4.4). Combining these
results, we conclude that
$\mathcal{QCMAP}\not\subseteq\mathcal{QPT}\cup\mathcal{MAP}$, i.e., even QMAPs
with classical proofs suffice to obtain an exponential speedup over both MAPs
and quantum testers.

Having shown the aforementioned separation, a natural question poses itself:
are there cases in which a _quantum proof_ cannot be substituted for a
classical one? We observe that a straightforward adaptation of a known result
shows this is indeed the case, albeit _only for subconstant proximity
parameters_ : the $\mathcal{QMA}$ vs. $\mathcal{QCMA}$ oracle separation of
Aaronson and Kuperberg [4] carries over to the property testing setting,
implying $\mathcal{QMAP}(1/\sqrt{n},\log
n,1)\not\subseteq\mathcal{QCMAP}(1/\sqrt{n},p,q)$ if $\sqrt{p}q=o(\sqrt{n})$
(see Appendix A for details).

We then shift to proving _limitations_ on the algorithmic power of QMAPs,
showing that there exist explicit properties that are extremely difficult for
such protocols. First, we observe that known lower bounds on the complexity of
$\mathcal{QMA}$ protocols for the _Permutation Testing_ problem [2, 73] yield
an explicit property that does not have any QMA protocol of polylogarithmic
proof length and query complexity, and in fact establishes that
$\mathcal{IPP}\not\subseteq\mathcal{QMAP}$ (see Appendix B for details). We
thus obtain the complexity landscape shown in Figure 1.

Finally, we present an entire class of properties that cannot be solved by
efficient QMAP protocols. This extends and simplifies one of the main results
of [30], which obtains the same result for classical MAPs.

######  Theorem 2 (Corollary 4, informally stated).

If a non-trivial property $\Pi$ is $k$-wise independent and
$\varepsilon=\Omega(1)$ is sufficiently small, then
$\Pi\notin\mathcal{QMAP}(\varepsilon,p,q)$ when $pq=o(k)$.

${\mathcal{IPP}}$ ${\mathcal{QMAP}}$ ${\mathcal{QCMAP}}$${\mathcal{MAP}}$
${\mathcal{QPT}}$ ${\mathcal{PT}}$ [46][19]1[46]ptTheorem A.1,implicit in
[4]ptTheorem B.2, impliedby [47, 73] Figure 1: Classification of complexity
classes. An arrow from $\mathcal{A}$ to $\mathcal{B}$ is present when there
exists a property requiring $n^{\Omega(1)}$ proof length or query complexity
by algorithms of $\mathcal{A}$ but only $\operatorname{polylog}n$ proof/query
complexity by algorithms of $\mathcal{B}$ (coloured red or grey when with
respect to a proximity parameter $\varepsilon=\Omega(1)$ that is a universal
constant; and violet when $\varepsilon\leq 1/\sqrt{n}$). The grey arrows are
previously known separations.

####  1.2.2 Algorithms

We show two general classes of properties whose structure allows for efficient
QMAP (QMA proof of proximity) protocols. Moreover, these protocols only
require _classical_ proofs (though the verifier is quantum).333Equivalently,
all of the results in this section rely on QCMAP protocols. They are thus
slightly stronger, continuing to hold if we replace $\mathcal{QMA}$ by
$\mathcal{QCMA}$ in the theorem statements. The first class is comprised of
what we call _decomposable properties_ , which generalise the “parametrised
concatenation properties” introduced in [46].

Roughly speaking, a property $\Pi$ is $(k,s)$-decomposable if testing whether
$x\in\Pi$ can be reduced, with the help of a message of length $s$ from the
prover, to that of testing whether $x^{(i)}\in\Lambda^{(i)}$ for $k$ smaller
strings $x^{(i)}$ and properties $\Lambda^{(i)}$ (see Definition 9). Since
there may be several decompositions of the same string, the prover’s message
is said to _specify_ a decomposition, i.e., mappings $x\mapsto x^{(i)}$ and
$\Pi\mapsto\Lambda^{(i)}$.

######  Theorem 3 (Theorem 7.1, informally stated).

If a property $\Pi$ is $(k,s)$-decomposable into strings of length $m$, each
of which is $\varepsilon$-testable by a MAP protocol with proof complexity $p$
and query complexity $q=q(m,\varepsilon)=m^{\alpha}/\varepsilon^{\beta}$, then

$\Pi\in\mathcal{QMAP}(\varepsilon,s+kp,q^{\prime})\;,$

where $q^{\prime}$ is much smaller than $q$ for many parameter values $\alpha$
and $\beta$.

The second class of properties amenable to QMA proofs of proximity are those
admitting _one-sided_ (classical) MAPs which do not receive a proximity
parameter explicitly, but rather reject strings $\varepsilon$-far from the
property with probability that is a function of $\varepsilon$. Such algorithms
are called _proximity-oblivious_ MAPs and readily admit quantum speedups (via
the technique of amplitude amplification; see Section 6).

######  Theorem 4.

If a property $\Pi$ admits a proximity-oblivious MAP protocol with proof
complexity $p$ and query complexity $q$, which always accepts $x\in\Pi$ and
rejects when $x$ is $\varepsilon$-far from $\Pi$ with probability
$\rho(\varepsilon)>0$, then

$\Pi\in\mathcal{QMAP}\left(\varepsilon,p,O\left(\frac{q}{\sqrt{\rho(\varepsilon)}}\right)\right)\;.$

As applications of 3, we show:

######  Corollary 1.

Let $\Pi_{k,[n]}$ denote the set of _$k$ -monotone_ functions
$f\colon[n]\to\\{0,1\\}$, i.e., those which change from nondecreasing to
nonincreasing and vice-versa at most $k-1$ times. For all
$\varepsilon\in(0,1)$,

$\Pi_{k,[n]}\in\mathcal{QMAP}\left(\varepsilon,k\log
n,\tilde{O}\left(\frac{1}{\varepsilon}\right)\right)\;.$

######  Corollary 2 (Corollary 8, informally stated).

For every $k\in[n]$, the property of Eulerian graph orientations of
$K_{2,n-2}$ is $\varepsilon$-testable by a QMAP protocol with proof complexity
$\tilde{O}(k)$ and query complexity
$\tilde{O}\left(\frac{n}{k\sqrt{\varepsilon}}\right)$.

Applying 4, we also show the following:

######  Corollary 3 (Corollaries 6 and 7, informally stated).

For every $k\in[n]$, acceptance by read-once branching programs and membership
in context-free languages are both $\varepsilon$-testable by QMAP protocols
with proof complexity $\tilde{O}(k)$ and query complexity
$O\left(\frac{n}{k\sqrt{\varepsilon}}\right)$.

Corollaries 2 and 3 achieve a dependence on $\varepsilon$ that is
quadratically better as compared to the best known MAPs [46, 41], while
Corollary 1 is more efficient than the best known (classical) testers and MAPs
for a wide range of parameters (see Section 7.2).

Classically, casting _exact decision_ problems in the framework of proofs of
proximity (i.e., testing with respect to proximity parameter
$\varepsilon=1/n$) is completely trivial except for degenerate cases, as most
functions of sublinear query complexity are extremely simple. Rather
surprisingly, this is _not_ the case quantumly, and indeed setting
$\varepsilon=1/n$ in Corollaries 1, 2 and 3 yields sublinear algorithms for
the corresponding exact decision problems. For _layered_ branching programs,
we also prove the following, which improves on the parameters of Corollary 3
and lifts the read-once restriction:

######  Theorem 5.

There exists a QMA protocol for acceptance of $n$-bit strings by layered
branching programs of width $w=w(n)$ and length $\ell=\ell(n)$ with query
complexity $O(\ell^{2/3})$ and proof complexity $O(\ell^{2/3}\log w)$.

For details on decomposability and its implications, see Section 7. Finally,
we prove that QMAP protocols are useful beyond proximity-oblivious and
decomposable properties. The problem of testing bipartiteness of a graph does
not fit either class, yet admits an efficient protocol nonetheless (see
Section 8).

######  Theorem 6 (Theorem 8.1, informally stated).

Bipartiteness for _rapidly-mixing_ $n$-vertex graphs (in the bounded-degree
model) is $\varepsilon$-testable by a QMAP protocol with proof complexity
$\tilde{O}(\sqrt{n})$ and query complexity
$\tilde{O}(n^{1/3}/\varepsilon^{5/6})$.444We remark that this test assumes the
rapidly-mixing promise for both yes- and no-instances.

###  1.3 Technical overview

In this section, we discuss the high-level ideas of the techniques used in the
proofs of the results stated in Section 1.2. Our discussion is divided into
lower bounds and algorithmic techniques.

In Section 1.3.1, we introduce some of the lower bound techniques that we use
in charting the complexity landscape of quantum proofs of proximity. En route,
we extend the framework of Blais, Brody and Matulef [16] to show lower bounds
for _quantum_ property testers. To the best of our knowledge, this is the
first quantum testing lower bound proved via a reduction from quantum
communication complexity, an open question raised by Montanaro and de Wolf
[60, Question 4]. In addition, we show how to prove lower bounds on QMAP
algorithms via an argument about the threshold degree of Boolean functions.

In Section 1.3.2 we show how to construct quantum proofs of proximity for
properties that can be decomposed into sub-problems, and we prove that these
QMAP protocols outperform both quantum testers as well as classical proof of
proximity protocols. Moreover, we give an overview of an efficient QMAP
protocol for a natural property of bounded-degree graphs, _bipartiteness_ ,
which does not fall into the decomposability paradigm.

####  1.3.1 Lower bounds

In this section, we highlight two techniques that we exploit to prove
complexity separations and limitations on QMAPs: (1) proving quantum testing
lower bounds via reductions from quantum communication complexity [16], which
we use to show a separation between MAPs and quantum testers; and (2) proving
QMAP lower bounds by studying the threshold degree of Boolean functions.

##### Quantum testing lower bounds via reductions from communication
complexity.

The methodology of [16] has proven very successful for showing _classical_
property testing lower bounds. However, extending this methodology to the
quantum setting poses an inherent difficulty that we expand upon next.
Following the exposition of [60], we illustrate the methodology and the
difficulty in the quantum setting by considering the problem of testing
whether a function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is $k$-linear, i.e., a
Fourier character of weight $k$.

We can obtain query complexity lower bounds on testers via a reduction from
the randomised _communication complexity_ problem of disjointness, as follows.
Recall that, in the disjointness problem, Alice receives $x\in\\{0,1\\}^{n}$
and Bob receives $y\in\\{0,1\\}^{n}$ (for lower bound purposes, we may assume
without loss of generality that both bit strings are promised to have Hamming
weight $k/2$ for some known $k\in[n]$), and their goal is to decide whether or
not there exists an index $i\in[k]$ such that $x_{i}=y_{i}=1$, while
communicating a minimal number of bits.

Suppose that there exists a property tester for $k$-linearity with query
complexity $q$. We will use this tester to construct a communication
complexity protocol for disjointness (i.e., deciding if, for every $i\in[n]$,
either $x_{i}=0$ or $y_{i}=0$) as follows. First, Alice and Bob use shared
randomness and simulate the tester on the input $f$, interpreted as a function
mapping $\\{0,1\\}^{n}$ to $\\{0,1\\}$ defined as
$f(z)=\bigoplus_{i\in[n]}z_{i}\cdot(x_{i}\oplus y_{i})$. To simulate a query
$f(z)$, Alice computes $A(z)=\bigoplus_{i\in[n]}z_{i}\cdot x_{i}$ and sends it
to Bob, while Bob computes $B(z)=\bigoplus_{i\in[n]}z_{i}\cdot y_{i}$ and
sends it to Alice. Since $f(z)=A(z)\oplus B(z)$, each query to $f$ incurs 2
bits of communication. Moreover, if $x$ and $y$ are disjoint, then $f$ is
$k$-linear; and if they are not disjoint, $f$ is $\ell$-linear for some
$\ell<k$, and is in particular $1/2$-far from every $k$-linear function.
Therefore, the simulated tester indeed solves the communication problem, so
that the $\Omega(k)$ lower bound for the latter implies an $\Omega(k)$ lower
bound for testing $k$-linearity.

An attempt to extend this to _quantum_ testers, however, reveals a severe
bottleneck in the reduction. Note that, classically, the fact that Alice and
Bob can use shared randomness to fix a _deterministic_ tester to simulate is
crucial: at every step, both parties know which query $z$ the tester will make
next _without_ the need to communicate it. The problem is that there is no way
to fix the “quantumness” using shared randomness. Details follow.

While disjointness is still hard in the quantum communication complexity
model, communicating the query (which may be in a superposition) that the
quantum tester requires will incur a _linear_ overhead, rendering the
reduction useless. Namely, to simulate a query to $f$ _in superposition_ , the
parties need to exchange all $n$ qubits at each round: Alice would apply the
unitary (on $n+1$ qubits) $\ket{z}\ket{b}\mapsto\ket{z}\ket{b\oplus A(z)}$,
and send the $(n+1)$-qubit state to Bob, who applies $\ket{z}\ket{b\oplus
A(z)}\mapsto\ket{z}\ket{b\oplus A(z)\oplus B(z)}=\ket{z}\ket{b\oplus f(z)}$
and returns them to Alice. Simulating a single query then requires the
communication of $2n+2$ qubits, rather than the $2$ needed by a classical
tester. Thus, the reduction can only prove a degenerate $\Omega(1)$ testing
lower bound. This is, in fact, not suprising, since $k$-linearity is testable
with $O(1)$ queries by the Bernstein-Vazirani [19] algorithm!

While the discussion above might suggest that communication complexity can
only yield trivial quantum testing lower bounds, we show this is not the case;
indeed, the absence of nontrivial (quantum) applications of the technique thus
far points to a conceptual barrier that is clarified by a coding-theoretic
perspective similar to [36], which reveals that the linear overhead is not
inherent to any quantum reduction. Observe that testing $k$-linearity is a
special case of _testing a subset of a code_ : namely, a $k$-linear function
$f$ where $f(z)=w\cdot z$ corresponds to the _Hadamard encoding_ of the string
$w$ with Hamming weight $k$ (which maps $w\in\\{0,1\\}^{n}$ into the codeword
$C(w)=(w\cdot z:z\in\\{0,1\\}^{n})$ with blocklength $n^{\prime}=2^{n}$). Note
that the aforementioned quantum simulation strategy is efficient, in the sense
that it requires only $O(\log n^{\prime})$ qubits to communicate a
representation of the length-$n^{\prime}$ encoding; the issue is the Hadamard
code’s exponential blocklength $n^{\prime}=2^{n}$, which renders the
simulation’s efficiency moot. As we see next, however, _the same reduction_
yields nontrivial bounds if we choose the code appropriately.

Given a linear code $C\colon\\{0,1\\}^{n}\to\\{0,1\\}^{n^{\prime}}$ with
$n^{\prime}=\operatorname{poly}(n)$, only $\log n^{\prime}=O(\log n)$ qubits
are necessary to represent $C(x)$ and $C(y)$. More precisely, Alice can apply
the $O(\log n)$-qubit unitary $\ket{i}\ket{b}\mapsto\ket{i}\ket{b\oplus
C(x)_{i}}$ and send all $O(\log n)$ qubits to Bob, who applies
$\ket{i}\ket{b}\mapsto\ket{i}\ket{b\oplus C(y)_{i}}$ and returns them. This
composition of unitaries is

$\ket{i}\ket{b}\mapsto\ket{i}\ket{b\oplus C(x)_{i}\oplus
C(y)_{i}}=\ket{i}\ket{b\oplus C(x\oplus y)_{i}}\>,$

simulating a query with _logarithmic_ , rather than linear, overhead.

Therefore, the $\Omega(\sqrt{n})$ quantum communication lower bound for
disjointness [68] implies an $(n^{\prime})^{\Omega(1)}$ lower bound for the
problem of testing a subset of $C$. Indeed, we show that, for a linear code
$C\colon\mathbb{F}^{n}\to\mathbb{F}^{n^{\prime}}$ (over a larger field of odd
characteristic), the property $\left\\{C(z):z\in\\{0,1\\}^{n}\right\\}$, of
_Booleanity_ ,555In fact, we show (and use to prove the separation
$\mathcal{QPT}\not\subseteq\mathcal{MAP}$) a lower bound for _non_
-Booleanity; but the symmetry of the model of communcation complexity implies
the same lower bound holds for Booleanity as well. which may be of interest in
PCP constructions, has a quantum testing lower bound of $\Omega(\sqrt{n}/\log
n)$ via a reduction from disjointness (see Section 4.2 for details). We remark
that since this technique is used to show a separation between quantum testers
and MA proofs of proximity, we use codes that are _locally testable_ and
_relaxed locally decodable_ , which allow for efficient testing by a MAP.
Since there exist such codes with a nearly-linear blocklength [13, 10], the
lower bound we obtain is only slightly worse than a square root.

##### QMAP lower bounds via threshold degree.

We prove lower bounds for QMAPs via the _threshold degree_ of related
functions. A function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ is said to have
threshold degree (at most) $d$ if there exists a degree-$d$ polynomial
$P(X_{1},\ldots,X_{n})$ over $\mathbb{R}$ such that $f(x)=1$ if $P(x)>0$ and
$f(x)=0$ if $P(x)<0$; in other words, the threshold degree of $f$ is the
smallest degree of a polynomial that _sign-represents_ $f$.

As a first step, we show that the inclusion
$\mathcal{QMA}\subseteq\mathcal{PP}$ [58] (in the _polynomial-time_ setting,
implied by the technique known as Marriott-Watrous amplification) carries over
to the property testing setting, implying
$\mathcal{QMAP}\subseteq\mathcal{UPP}$.666$\mathcal{UPP}$ is the query model
version of the class $\mathcal{PP}$ of unbounded-error randomised algorithms,
where in particular the amount of randomness available to the algorithm is
unbounded. Since PP algorithms run in polynomial time, they may access at most
a polynomial number of random bits; this restriction does not hold for
$\mathcal{UPP}$. Next, we show that the query complexity of a UPP algorithm
that computes $f$ is exactly the threshold degree of $f$ (this result is
folklore, but we provide a proof for completeness). Since a property $\Pi$
induces the (partial) function $f_{\Pi}$ such that $f_{\Pi}(x)=1$ when
$x\in\Pi$ and $f_{\Pi}(x)=0$ when $x$ is $\varepsilon$-far from $\Pi$, the
query complexity of a UPP algorithm that “tests” $\Pi$ (i.e., computes
$f_{\Pi}$) is a lower bound on the product $pq$ of the proof and query
complexities of any QMAP protocol for testing $\Pi$. Finally, we show that if
$\Pi$ is _$k$ -wise independent_ (i.e., looks perfectly random on any subset
of $k$ coordinates) and not too large, the threshold degree of $f_{\Pi}$ is at
least $k$, so that $pq=\Omega(k)$ (see Section 5 for details).

In particular, any code with linear dual distance and small enough rate is an
example of a hard property for QMAPs, requiring proof and query complexities
that satisfy $pq=\Omega(n)$ for proximity parameter $\varepsilon=\Omega(1)$.

####  1.3.2 Algorithmic techniques

As a warm-up, consider the _exact decision_ problem of verifying that an
$n$-bit string $x$ has even parity. This is maximally hard for both IP
algorithms and quantum query algorithms, requiring $\Omega(n)$ queries to the
bit string, and thus asymptotically no better than trivially querying every
coordinate. As we will see next, however, QMA algorithms can capitalise on
having a proof _and_ quantum processing power to break the linear barrier.

We rely on the technique of _amplitude amplification_ [17] to obtain such an
algorithm with sublinear proof and query complexities. Loosely speaking,
amplitude amplification takes a (randomised) decision algorithm that always
accepts yes-inputs and rejects no-inputs with probability $\rho$, and produces
an algorithm with rejection probability $2/3$ (for no-inputs) using the former
algorithm only $O(1/\sqrt{\rho})$ times as a subroutine.

We can thus obtain a QMA (query) algorithm for the parity problem as follows.
The proof string specifies the purported parities of each block of an
equipartition of the input $x\in\\{0,1\\}^{n}$ into $p$ blocks of length
$n/p$. The verifier first checks that the proof string has even parity,
rejecting immediately otherwise. Then, the verifier performs amplitude
amplification on the following subroutine: sample $i\in[p]$ uniformly at
random, read the entire block of $n/p$ bits and check that its parity
coincides with that claimed by the proof; if so, accept, and reject otherwise.

Note that the aforementioned subroutine always accepts if $x$ has even parity
and the proof corresponds to the parity of every block. On the other hand, if
a string has odd parity and the proof has even parity, _at least one bit of
the proof_ disagrees with the corresponding block, so that the subroutine
rejects with probability at least $1/p$. Since we need only repeat
$O(\sqrt{p})$ times, each of which queries $n/p$ bits, the query complexity of
our algorithm is $q=O(n/\sqrt{p})$; in particular, if $p=n^{2/3}$ then
$q=O(n^{2/3})$.777Subsequent to discovering the QMA protocol for parity, we
learned that the same result was obtained in unpublished prior work of
Alessandro Cosentino, Robin Kothari, and John Watrous.

This is a special case of a more general phenomenon, which holds for all
_decomposable_ properties (see Section 7.3 for a discussion of how exact
decision follows as a special case). Since amplitude amplification can only be
applied to one-sided algorithms (i.e., those that always accept a valid
input), we restrict our attention to this type of algorithm hereafter.

##### Decomposable properties.

Roughly speaking, a property $\Pi$ is said $(k,s)$-decomposable if a
“specification” of length $s$ efficiently reduces testing $\Pi$ to testing $k$
smaller properties $\Lambda^{(1)},\ldots,\Lambda^{(k)}$. More precisely, $\Pi$
is $(k,s)$-decomposable if,

  1. 1.

there exists some $s$-bit string that specifies a set of $k$ properties
$\Lambda^{(i)}$ as well as $k$ strings $x^{(i)}\in\\{0,1\\}^{m_{i}}$ whose
bits are determined by a small number of bits of $x$; and

  2. 2.

$\varepsilon$-testing $x\in\\{0,1\\}^{n}$ with respect to $\Pi$ reduces to
testing $x^{(i)}$ with respect to $\Lambda^{(i)}$ in the following sense: when
$x\in\Pi$ then $x^{(i)}\in\Lambda^{(i)}$ for all $i\in[k]$, whereas when $x$
is $\varepsilon$-far from $\Pi$, then $x^{(i)}$ is $\varepsilon_{i}$-far from
$\Lambda^{(i)}$ for some $\varepsilon_{i}$ satisfying
$\mathbb{E}_{i}[\varepsilon_{i}]=\Omega(\varepsilon)$, where the expectation
over $i$ means that $i$ is sampled with probability proportional to $m_{i}$.

If the specification is short (i.e., $s=O(k\log n)$), we say $\Pi$ is
_succinctly_ $k$-decomposable (see Section 7 for details). Decomposable
properties generalise the notion of _parametrised $k$-concatenation
properties_ introduced in [46], which corresponds to the special case of a
$(k,0)$-decomposition that is an equipartition of the input string.

Our simplest example of a decomposable problem is that of testing the set of
$k$-monotone functions $f:[n]\to\\{0,1\\}$, i.e., functions that change from
non-decreasing to non-increasing and vice-versa at most $k-1$ times. A natural
decomposition of this property is to specify the set of at most $k-1$
“critical points”, which induce a set of at most $k$ subfunctions $f_{i}$ that
are monotone and overlap with $f_{i-1}$ and $f_{i+1}$ at their endpoints;
then, it suffices to test for (1-)monotonicity of each subfunction. More
precisely, this property is $(k,(k-1)\log n)$-decomposable (thus succinctly
$k$-decomposable), and given the (alleged) critical points
$n_{1}<n_{2}<\cdots<n_{k-1}$, the subproperty $\Lambda^{(i)}$ for odd (resp.
even) $i$ is the set of non-decreasing (resp. non-increasing) functions on
$[m_{i}]$, where $m_{i}=n_{i}-n_{i-1}+1$ (with $n_{0}=1$ and $n_{k}=n$). Note,
moreover, that if $f$ is $\varepsilon$-far from $k$-monotone, then its
absolute distance from all functions specified by the critical points is at
least $\varepsilon n$; thus, denoting by $\varepsilon_{i}$ the distance of
$f_{i}$ to $\Lambda^{(i)}$, we have
$\sum_{i}\varepsilon_{i}m_{i}\geq\varepsilon n$, implying
$\mathbb{E}_{i}[\varepsilon_{i}]=\Omega(\varepsilon)$. We remark that
decomposing other properties (e.g., branching programs, context-free
languages, and Eulerian graph orientations) is much less straightforward and
often allows for breaking the property into any desired number of sub-
properties, which in turn admits proof length versus query complexity
tradeoffs. See Section 7 for details.

Given a $(k,s)$-decomposable property that admits MAPs for the subproperties
$\Lambda^{(i)}$, a natural protocol for $\Pi$ is to sample $i\in[k]$ uniformly
at random and execute the verifier for $\Lambda^{(i)}$. Note that, if these
MAPs have proof complexity $p$ and query complexity $q$, the protocol for
$\Pi$ has proof length $s+kp$. Moreover,
$\mathbb{E}_{i}[\varepsilon_{i}]=\Omega(\varepsilon)$ means that a randomly
chosen $i\in[k]$ is (in expectation) at distance roughly $\varepsilon$ from
$\Lambda^{(i)}$, so it is reasonable to expect that $O(1/\varepsilon)$
classical repetitions of the base protocol would ensure a rejection with high
probability, and that a QMAP protocol can make do with only
$O(1/\sqrt{\varepsilon})$ repetitions using amplitude amplification.

The above outline glosses over the fact that we have no information on _the
distribution of errors_ $(\varepsilon_{1},\dots,\varepsilon_{k})$. For
example, it may be that most $\varepsilon_{i}$ are of the same order of
magnitude (in which case a random $i\in[k]$ is likely to point to a mildly
corrupted $x^{(i)}$), or it may be that a few $\varepsilon_{i}$ are very large
while all other $\varepsilon_{i}$ are small or even zero (in which case
$x^{(i)}$ is unlikely to be corrupted for a random $i\in[k]$, but when it is,
the amount of corruption is large). Fortunately, this issue can be addressed
by the technique of _precision sampling_ [55], incurring a merely logarithmic
overhead. We thus obtain a QMAP protocol for $\varepsilon$-testing $\Pi$ with
proof complexity $s+kp$ and query complexity comparable to $q$ (and often
smaller; see Theorem 7.1 for details).

##### Bipartiteness testing.

Consider the problem of testing whether a bounded-degree graph $G$ (given as
an oracle to its adjacency list) is bipartite or far from any bipartite graph.
(Note that this is not a decomposable property.) There exists a MAP protocol
for a promise variant of this problem, where graphs are _rapidly-mixing_ [46].
We will show that it is possible to combine quantum speedups obtained by
amplitude amplification _and_ by replacing a classical subroutine with a more
efficient quantum analogue.

Let us first consider the (classical) MAP verifier for bipartiteness, which
receives a subset of vertices $S$ of size $k$, allegedly on the same side of a
bipartition, as a proof. To test with respect to proximity parameter
$\varepsilon$, the verifier repeats the following procedure: sample a
uniformly random vertex $v$, take roughly $n/(k\varepsilon)$ short (lazy)
random walks starting from $v$, recording whether the walk ended at a vertex
in $S$ as well as the parity of the walk (i.e., the parity of the number of
non-lazy steps). If two walks start from the same vertex $v$ and end in $S$
with different parities, then reject; otherwise, accept. Setting $m\coloneqq
n/k$, the query complexity of (one iteration of) the verifier is
$m/\varepsilon$ (ignoring constants and polylogarithmic factors).

If the graph is bipartite and the proof $S$ is indeed on the same side of a
bipartition, there cannot exist two paths from the same vertex into $S$ with
different parities (as that would imply a path of odd length with both
endpoints on the same side). Therefore, the verifier always accepts in this
case. If the graph is $\varepsilon$-far from bipartite, however, each
iteration finds evidence to this effect with probability
$\Omega(\varepsilon)$. Thus, the classical verifier samples a new vertex
roughly $1/\varepsilon$ times, for a total query complexity of
$m/\varepsilon^{2}$.

Now, one immediate way to improve this algorithm is to perform amplitude
amplification: the resulting algorithm repeats the procedure
$1/\sqrt{\varepsilon}$ times, improving the query complexity to
$m/\varepsilon^{3/2}$. A second (and less straightforward) strategy is to use
the quantum _collision-finding_ algorithm [7] to reduce the number of random
walks taken from each vertex to $(m/\varepsilon)^{2/3}$, as in [8].888Here and
throughout, we use the term collision-finding to refer to Ambainis’s algorithm
that, for any $f$ with $1$-certificate complexity at most $2$, uses
$\Theta(n^{2/3})$ queries and with constant probability outputs a
$1$-certificate when run on any input $x\in f^{-1}(1)$. This strategy reduces
the required number of queries to $m^{2/3}/\varepsilon^{5/3}$, improving the
dependency on $m$ but achieving a worse one on $\varepsilon$.

Of course, this begs the question: why not apply both optimisations? Indeed,
we show how to tweak the classical MAP verifier in order to do so, and thus
simultaneously obtain the speedups from each of them.999Amplitude
amplification requires that the algorithm be _invertible_ , i.e., be given by
a unitary $A$, as the technique repeatedly applies $A$ and $A^{-1}$. For this
reason, it is often said to apply to quantum algorithms without intermediate
measurements (as these make an algorithm non-invertible), which is not the
case for collision-finding. However, the (standard) _principle of deferred
measurement_ (see, e.g., [62]) allows us to transform any quantum algorithm
$A$ into a reversible $A^{\prime}$ with the same query complexity, and apply
amplitude amplification to the latter.

More precisely, sample a uniformly random vertex $v$ and let $g_{v}$ denote
the mapping $r\mapsto(a,b)\in\\{0,1\\}^{2}$ obtained by executing a random
walk starting from $v$ with $r$ as its inner randomness, where $a=1$ if the
walk stops at a vertex in $S$ and $b$ is the parity of the walk. The
collision-finding algorithm is capable of finding a pair $r_{0},r_{1}$ such
that $g_{v}(r_{i})=(1,i)$ for $i\in\\{0,1\\}$, if such a pair exists. The
query complexity of the collision-finding algorithm is the domain size to a
$2/3$ power, and, since we take $m/\varepsilon$ walks from $v$, the number of
queries is $(m/\varepsilon)^{2/3}$. Although such a collision is not
guaranteed to exist for all starting vertices $v$, it is for a fraction of
roughly $\varepsilon$ of them. By applying amplitude amplification to the
procedure described in this paragraph, we obtain a QMAP protocol for
bipartiteness with proof length $O(k\log n)$ and query complexity
$\tilde{O}((m/\varepsilon)^{2/3}\cdot
1/\sqrt{\varepsilon})=\tilde{O}((n/k)^{2/3}/\varepsilon^{5/6})$ (see Theorem
8.1 for details).

###  1.4 Open problems

This work begins the exploration of quantum proofs of proximity, leaving a
host of uncharted research directions. We wish to highlight a small number of
open problems, which we find to be of particular interest.

In the diagram of complexity class separations of Figure 1, an evident
shortcoming is the absence of $\mathcal{QMAP}\not\subseteq\mathcal{QCMAP}$ in
the natural setting of parameters, i.e., with proximity
$\varepsilon=\Omega(1)$ rather than $\varepsilon=\Theta(1/\sqrt{n})$.

######  Open Question 1.

What is the largest proximity parameter $\varepsilon$ such that

$\mathcal{QMAP}(\varepsilon,\operatorname{polylog}(n),\operatorname{polylog}(n))\not\subseteq\mathcal{QCMAP}(\varepsilon,p,q)$

with some proof and query complexities satisfying $pq=n^{\Omega(1)}$?

Given our focus on quantum MA (i.e., _non-interactive_) proofs of proximity,
it is natural to ask what is achievable by allowing quantum property testers
to interact with quantum provers, as opposed to static proofs.

######  Open Question 2.

What is the power of quantum IP proofs of proximity (QIPPs)?

More specifically, it is known that there exist classical interactive proof of
proximity (IPP) protocols with $\tilde{O}(\sqrt{n})$ proof and query
complexities for large classes of languages [72, 71]. Moreover, these
complexities are optimal (up to polylogarithmic factors) for _classical_
protocols, under reasonable cryptographic assumptions [53]. Could quantum
interactive proofs break the square-root barrier?

######  Open Question 3.

Can QIPPs test logspace-uniform $\mathcal{NC}$ languages with $o(\sqrt{n})$
proof and query complexities?

Finally, while we show a strong lower bound for QMAPs for $k$-wise independent
properties, they do not rule out the existence of sublinear QMAP protocols.
Could a stronger lower bound be shown?

######  Open Question 4.

Do there exist maximally hard properties for QMAPs, requiring $\Omega(n)$
query complexity when the proof complexity is $p=cn$ for some $c=\Omega(1)$?

We note that the question has an easy (negative) answer if we take $c=1$: with
a proof (allegedly) equal to the input string $x$, a QMAP based on Grover
search can test with $O(1/\sqrt{\varepsilon})=O(\sqrt{n})$ queries. Moreover,
[67] provides a (positive) answer for proximity parameter $\varepsilon=1/n$:
there exists a property $\Pi\subset\\{0,1\\}^{n}$ for which deciding whether
$x\in\Pi$ or $x\notin\Pi$ requires proof and query complexities satisfying
$p+q=\Omega(n)$ (indeed, this is true of most bipartitions of
$\\{0,1\\}^{n}$). Then taking $c=\Omega(1)$ small enough implies
$q=\Omega(n)$. Thus, similarly to 1, while we have answers for subconstant
$\varepsilon$, the problem is open when $\varepsilon=\Omega(1)$.

### Organisation

The rest of this paper is organised as follows. In Section 2, we discuss the
preliminaries for the technical sections. QMA proofs of proximity are formally
defined in Section 3, and we prove our complexity class separations in Section
4 (which Appendices A and B complement with separations implied by known
results). Section 5 proves lower bounds for QMAPs and concludes the
complexity-theoretic part of the paper. Proceeding to the algorithmic part, we
show in Section 6 that QMAP protocols enable speedups for proximity-oblivious
MAPs. In Section 7, we define decomposability and prove the bulk of our
algorithmic results, including exact decision problems as a special case.
Finally, in Section 8 we show a QMAP protocol for testing graph bipartiteness.

##  2 Preliminaries

We begin with standard notation. For an integer $\ell\geq 1$, we denote by
$[\ell]$ the set $\\{1,2,\ldots,\ell\\}$. We use $\operatorname{polylog}(n)$
to denote an arbitrary polylogarithmic function, i.e., a polynomial in the
logarithm of $n$. For ease of notation, we also define $N\coloneqq 2^{n}$.

We use $\mathcal{H},\mathcal{K}$ to denote arbitrary finite-dimensional
Hilbert spaces and use indices to differentiate between distinct spaces. The
set of linear operators mapping $\mathcal{H}$ to $\mathcal{K}$ is denoted by
$\mathcal{L}(\mathcal{H},\mathcal{K})$; the shorthand
$\mathcal{L}(\mathcal{H})$ stands for $\mathcal{L}(\mathcal{H},\mathcal{H})$.
The set of positive semidefinite operators on $\mathcal{H}$ having unit trace
is denoted by $\operatorname{pos}(\mathcal{H})$. The set
$T(\mathcal{H},\mathcal{K})$ consists of the linear mappings from
$\mathcal{L}(\mathcal{H})$ to $\mathcal{L}(\mathcal{K})$. We say $T$ is a
completely positive map (CP-Map) if $T\otimes I_{\mathcal{L}(\mathcal{H})}$ is
positive for all $\mathcal{H}$, where $I_{\mathcal{K}}$ denotes the identity
operator on a Hilbert space $\mathcal{K}$ . Furthermore, $T$ is a completely
positive trace preserving map (CPTP map) if $T$ is a trace preserving CP-Map,
i.e., such that $\Tr(T(\rho))=\Tr(\rho)$ for all $\rho$.
$\mathcal{U}(\mathcal{H})$ denotes the set of unitary operators on
$\mathcal{H}$. For a unitary transformation $U\in\mathcal{U}$, its conjugate
transpose is denoted $U^{\dagger}$.

A pure state is a unit vector in the Hilbert space $\mathcal{H}$, and
represented by the Dirac notation, e.g., $\Ket{\psi}$. A mixed state is a
distribution on pure states $\\{p_{k},\Ket{\psi_{k}}\\}$, represented as a
_density matrix_ $\rho=\sum p_{k}\Ket{\psi_{k}}\Bra{\psi_{k}}$. We write
$\dim(\mathcal{H})$ to denote the dimension of the Hilbert space
$\mathcal{H}$. Also, for brevity, we represent $\Ket{0}^{\otimes n}$ as
$\Ket{\mathbf{0}}$, for an arbitrary $n\geq 1$, where $\Ket{0}=[1\ \ 0]^{T}$.

##### Complexity classes.

We use the convention of writing complexity classes in calligraphic capitals
and denoting algorithms or protocols by latin capitals, e.g., $\mathcal{BQP}$
is a complexity class whose problems are solvable by BQP algorithms and
$\mathcal{IP}$ is a complexity class characterised by IP protocols.

##### Quantum query model.

A quantum algorithm $V$ with query access to a bit string $x\in\\{0,1\\}^{n}$
is specified by a sequence of unitary operations $V_{0}\ldots V_{q}$, that do
not depend on the input $x$. A query to $x$ is given by the unitary $U_{x}$ on
$\log n+1$ qubits such that

$U_{x}\Ket{i}\ket{b}=\Ket{i}\ket{b\oplus x_{i}}\;.$

We denote by $V^{U}$ the output of $V$ with oracle access to a unitary $U$.
Similarly, $V^{U}(n)$ denotes the case where $V$ has access to an additional
explicit input $n$.

The final state of an algorithm that makes $q$ queries to the oracle, before
measurement, is given by

$V_{q}(U_{f}\otimes I)V_{q-1}(U_{f}\otimes I)\ldots V_{1}(U_{f}\otimes
I)V_{0}\Ket{\mathbf{0}}\;.$

The overall Hilbert space $\mathcal{H}$ used by the algorithm is split into
three subspaces
$\mathcal{H}_{\text{in}}\otimes\mathcal{H}_{\text{w}}\otimes\mathcal{H}_{\text{out}}$,
and we denote by $\ket{\mathbf{0}}=\ket{0}^{\otimes\log(\dim\mathcal{H})}$ the
initial state of the verifier’s memory. The oracle acts on the space
$\mathcal{H}_{\text{in}}$, the workspace $\mathcal{H}_{\text{w}}$ can have
arbitrary size and $\mathcal{H}_{\text{out}}$ represents the single-qubit
output of the algorithm. The final step of the algorithm is to measure the
$\mathcal{H}_{\text{out}}$ register in the computational basis and return the
outcome.

##### Distance measures.

Unless otherwise stated, we will assume the distance measure $d$ for
_classical_ objects, such as strings of symbols in a finite field
$\mathbb{F}$, as that induced by normalised _Hamming weight_ : for
$x,y\in\mathbb{F}^{n}$, the (normalised) Hamming weight of $x$ is
$\absolutevalue{x}\coloneqq\absolutevalue{\left\\{i\in[n]:x_{i}\neq
0\right\\}}/n$ and the distance between $x$ and $y$ is
$d(x,y)=\absolutevalue{\left\\{i\in[n]:x_{i}\neq y_{i}\right\\}}/n$. We will
often refer to distances between bit strings, which corresponds to the case
where $\mathbb{F}=\mathbb{F}_{2}=\\{0,1\\}$.

For unitary matrices $U,V$, unless otherwise stated, we consider the distance
measure to be that induced by the normalised _Hilbert-Schmidt norm_ : the norm
of $U$ is
$\norm{U}\coloneqq\sqrt{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(U)^{2}}$, where
$\sigma_{i}(U)$ is the $i^{\text{th}}$ eigenvalue of $A$ (in some arbitrary
order); and the distance between $U$ and $V$ is $d(U,V)=\norm{U-V}$.

We say two objects $X,Y$ are _$\varepsilon$ -close_ if
$d(X,Y)\leq\varepsilon$, and otherwise they are _$\varepsilon$ -far_. We also
say $X$ is $\varepsilon$-close to a set of objects $\left\\{Y_{i}\right\\}$ if
there exists $i$ such that $d(X,Y_{i})\leq\varepsilon$.

##### Property testing.

An _interactive proof of proximity_ (IPP) for $\Pi$ is a proof system that
solves the approximate decision problem of membership in $\Pi$. The _verifier_
algorithm receives as input a proximity parameter $\varepsilon$ and has oracle
access to $x$. It queries $x$ in at most $q$ coordinates and interacts with an
all-powerful but untrusted prover by exchanging $m$ messages, where the total
number of communicated bits is $c$. The verifier must accept when $x\in\Pi$
and reject when $x$ is $\epsilon$-far from $\Pi$, with bounded probability of
error; the outcome of such an interaction is denoted $\langle
P(x),V^{x}\rangle$. Formally,

######  Definition 1.

An _interactive proof of proximity_ (IPP) for a property $\Pi=\cup_{n}\Pi_{n}$
is an interactive protocol with two parties: a (computationally unbounded)
prover $P$ and a verifier $V$, which is a probabilistic algorithm. The parties
send messages to each other in turns, with the first sent from prover to
verifier, and at the end of the communication, the following two conditions
are satisfied:

  1. 1.

_Completeness:_ For every $\varepsilon>0$, $n\in\mathbb{N}$, and
$x\in\Pi_{n}$, there exists a prover $P$ such that

$\mathbb{P}\left[\langle P(x),V^{x}\rangle(n,\varepsilon)=1\right]\geq 2/3\;,$

where the probability is over the coin tosses of $V$.

  2. 2.

_Soundness:_ For every $\varepsilon>0$, $n\in\mathbb{N}$, $x\in\\{0,1\\}^{n}$
that is $\varepsilon$-far from $\Pi_{n}$ and for every computationally
unbounded (cheating) prover $P^{*}$ it holds that

$\mathbb{P}\left[\langle P^{*}(x),V^{x}\rangle(n,\varepsilon)=1\right]\leq
1/3\;,$

where the probability is over the coin tosses of $V$.

The _query complexity_ $q$ of the protocol is the maximum number of queries
the verifier makes to $x$ in its execution; the _round complexity_ $m$ is the
number of messages exchanged between prover and verifier; and the
_communication complexity_ $c$ is the total number of bits communicated by
these messages.

The set of properties $\Pi$ for which there exists an IPP protocol with
proximity parameter $\varepsilon$ with $m$ messages, communication complexity
$c$ and query complexity $q$ is denoted $\mathcal{IPP}(\varepsilon,c,q,m)$.

When the completeness condition holds with probability 1, i.e., the verifier
always accepts when $x\in\Pi$, we call the protocol _one-sided_. Moreover, if
the verifier does not receive $\varepsilon$ explicitly, but rejects inputs
that are $\varepsilon$-far from $\Pi$ with _detection probability_
$\rho(n,\varepsilon)>0$, the procotol is said to be _proximity-oblivious_.

A _Merlin-Arthur proof of proximity_ (MAP) for $\Pi$ is an IPP where the
entire communication is a single message from the prover to the verifier
(i.e., an IPP with round complexity 1); the class
$\mathcal{MAP}(\varepsilon,p,q)$ is thus defined as
$\mathcal{IPP}(\varepsilon,p,q,1)$. The formal definition of the _quantum_
generalisation of MAPs is given in Section 3.1.

A _property tester_ is an IPP with $r=0$, i.e., where no communication occurs.
In this case, the verifier is called a _tester_ , and we define
$\mathcal{PT}(\varepsilon,q)\coloneqq\mathcal{IPP}(\varepsilon,0,q,0)$.

##### Branching programs.

A branching program on $n$ variables is a directed acyclic graph that has a
unique source vertex $v_{0}$ with in-degree 0 and (possibly) multiple sink
vertices with out-degree 0. Each sink vertex is labeled either with 0 (i.e.,
reject) or 1 (i.e., accept). Each non-sink vertex is labeled by an index
$i\in[n]$ and has exactly 2 outgoing edges, which are labeled by 0 and 1. The
output of the branching program $B$ on input $x\in\\{0,1\\}^{n}$ , denoted
$B(x)$, is the label of the sink vertex reached by taking a walk, starting at
the source vertex $v_{0}$, such that at every vertex labeled by $i\in[n]$, the
step taken is on the edge labeled by $x_{i}$.

A branching program is said to be _read-once_ (or ROBP for short) if, along
every path from source to sink, every index $i\in[n]$ appears at most once.
The size of a branching program $B$ is the number of vertices in its graph.

A branching program is _layered_ if its nodes can be partitioned into $V_{0}$,
$V_{1}$, …, $V_{\ell}$, where $V_{0}$ only contains the source node,
$V_{\ell}$ are the sink nodes and every edge is between $V_{i-1}$ and $V_{i}$
for some $i\in[\ell]$. The _length_ of a layered branching program is its
number of (nontrivial) layers $\ell$, and its _width_ is the maximum size of
its layers, i.e., $\max_{i\in[\ell]}\left\\{\absolutevalue{V_{i}}\right\\}$.

##### Coding theory.

A _code_ $C\colon\mathbb{F}^{k}\to\mathbb{F}^{n}$ (where $\mathbb{F}$ is a
finite field) is an injective mapping from _messages_ of length $k$ to
codewords of _blocklength_ $n$. The _rate_ of the code $C$ is $k/n$ and its
_distance_ is the minimum, over all distinct messages $x,y\in\mathbb{F}^{k}$,
of $d(C(x),C(y))$. We shall sometimes slightly abuse notation and use $C$ to
denote the set of all of its codewords
$\left\\{C(x):x\in\mathbb{F}^{k}\right\\}\subset\mathbb{F}^{n}$. If the
mapping $C$ is linear, we say $C$ is a linear code.

##  3 QMA Proofs of Proximity

This section provides a formal definition of QMAPs.

###  3.1 Definition

A _quantum Merlin-Arthur proof of proximity_ (QMAP) for a property
$\Pi=\bigcup\Pi_{n}$ is a proof system consisting of a quantum algorithm $V$,
called a verifier, that is given as explicit input an integer $n\in\mathbb{N}$
and a proximity parameter $\epsilon>0$. It has oracle access to a unitary
$U\in\mathcal{V}\subseteq\mathcal{U}(2^{n})$ acting on $n$ qubits, which
belongs to a _universe_ $\mathcal{V}$ with an associated distance
measure.101010Note that this definition generalises classical properties,
where
$\mathcal{V}=\left\\{U_{x}:x\in\\{0,1\\}^{n}\right\\}\subset\mathcal{U}(2^{n+1})$,
the unitary $U_{x}$ acts as $U_{x}\ket{i}\ket{b}=\ket{i}\ket{b\oplus x_{i}}$,
and the distance between $U_{x}$ and $U_{y}$ is the Hamming distance between
$x$ and $y$. Furthermore, the verifier receives a $p$-qubit quantum state
$\rho$ explicitly as a purported proof that $U\in\mathcal{V}$.

We allow the oracles in the rest of the work to be quantum oracles, i.e., CP-
Maps. However, using the Stinespring dilation [74, 66], we view them as
unitary operators again, in a larger Hilbert space, and the formalism
generalises readily. This allows us to work with most general transformations
allowable by quantum theory.

The verfier $V$ receives $n$ and $\varepsilon$ as inputs, and outputs a
sequence of unitary operators $V_{0}\ldots V_{q}$ that satisfies the two
following conditions.

  1. 1.

_Completeness._ For every $n\in\mathbb{N}$ and $U\in\Pi_{n}$, there exists a
$p$-qubit quantum state $\ket{\psi}$ such that,111111While the proof can also
be a mixed state, assuming it to be pure is without loss of generality; see
Remark 2. for every proximity parameter $\epsilon>0$,

$\mathbb{P}\left[V^{U}(n,\varepsilon,\ket{\psi})=1\right]\geq 2/3\;.$

Equivalently, _some_ $p$-qubit quantum state $\ket{\psi}$ satisfies

$\norm{(\Ket{1}\Bra{1}\otimes I)W(\ket{\psi}\otimes\Ket{\textbf{0}})}^{2}\geq
2/3\;,$

where $\Ket{\textbf{0}}$ is the initial state of the verifier and $W$ the
unitary obtained by interspersing $q$ calls to the oracle $U$ between the
$V_{i}$; that is, $W=V_{q}(U\otimes I)V_{q-1}\ldots(U\otimes I)V_{0}$.

  2. 2.

_Soundness._ For every $n\in\mathbb{N}$, $\varepsilon>0$ and $p$-qubit quantum
state $\ket{\psi}$, if $U\in\mathcal{U}(2^{n})$ is $\varepsilon$-far from
$\Pi_{n}$, then

$\mathbb{P}\left[V^{U}(n,\varepsilon,\ket{\psi})=1\right]\leq 1/3\;.$

Equivalently, _every_ $p$-qubit quantum state $\ket{\psi}$ satisfies

$\norm{(\Ket{1}\Bra{1}\otimes I)W(\ket{\psi}\otimes\Ket{\textbf{0}})}^{2}\leq
1/3\;,$

where $W=V_{q}(U\otimes I)V_{q-1}\ldots(U\otimes I)V_{0}$.

The query complexity of a QMAP is number of times the verifier calls the
oracle $U$. More precisely, the query complexity is $q=q(n,\varepsilon)$ if,
for every $n\in\mathbb{N}$, $\epsilon>0$ and $U\in\mathcal{U}(2^{n})$, the
verifier makes at most $q$ queries to the input. Its proof complexity is
$p=p(n,\varepsilon)$ if, for every $n\in\mathbb{N}$ and $U\in\Pi_{n}$, there
exists a $2^{p}$-dimensional quantum state $\ket{\psi}$ satisfying both of the
above conditions.

The running time $t_{V}=t_{V}(n,\varepsilon)$ of the verifier is the minimum
depth of the unitaries $V_{0}\ldots V_{q}$, composed of gates from a fixed
constant-qubit gate set. The running time $t_{P}=t_{P}(n,\varepsilon,U)$ of
the prover is similarly the minimum depth of the circuit that prepares the
proof state $\ket{\psi}$.

######  Definition 2 ($\mathcal{QMAP}$ complexity class).

Fix a universe set of unitary operators $\mathcal{V}$ and distance measure
$d:\mathcal{V}\times\mathcal{V}\rightarrow[0,1]$.
$\mathcal{QMAP}(\varepsilon,p,q,t_{V},t_{P})$ is the class of properties
$\Pi\subseteq\mathcal{V}$ that admit a verifier for proximity parameter
$\varepsilon$ with query complexity $q$ and proof complexity $p$ such that the
verifier and prover runtimes are $t_{V}$ and $t_{P}$, respectively.

The complexity class $\mathcal{QCMAP}(\varepsilon,p,q,t_{V},t_{P})$ is defined
as above, with the additional restriction that the proof be _classical_ ,
i.e., that the $p$-qubit quantum state given as proof is a computational basis
state.

$\Qcircuit<EMAIL_ADDRESS>\qw\ghost{V_{0}}\ghost{U}\ghost{V_{1}}\ghost{U}\qw\ghost{V_{q-1}}\ghost{U}\ghost{V_{q}}\qw\\\
\lstick{\ket{\psi}\otimes\ket{\mathbf{0}}}\qw\ghost{V_{1}}\ghost{U}\ghost{V_{0}}\ghost{U}\qw\cdots\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\ghost{V_{q-1}}\ghost{U}\ghost{V_{q}}\qw\\\
\qw\ghost{V_{0}}\ghost{U}\ghost{V_{1}}\ghost{U}\qw\ghost{V_{q-1}}\ghost{U}\ghost{V_{q}}\qw\\\
\\\ \vdots\\\ \\\
\qw\ghost{V_{0}}\qw\ghost{V_{1}}\qw\qw\ghost{V_{q-1}}\qw\ghost{V_{q}}\qw}$

Figure 2: Schematic of a QMAP protocol that receives a proof state
$\Ket{\psi}$ and makes $q$ queries to a unitary $U$.

For ease of notation, since the measures of complexity we will use throughout
are _proof_ and _query_ complexity (but _not_ time complexity), we will often
use $\mathcal{QMAP}(\varepsilon,p,q)$ (and likewise for $\mathcal{QCMAP})$ to
denote the class as above, where $t_{V},t_{P}$ are arbitrary functions.

We also denote the class of properties that are $\varepsilon$-testable by
quantum testers with $q$ queries as $\mathcal{QPT}(\varepsilon,q)$, that is,
$\mathcal{QPT}(\varepsilon,q)\coloneqq\mathcal{QMAP}(\varepsilon,0,q)$.

######  Remark 2 (Proofs are pure states).

Without loss of generality, the quantum state given as the proof is a pure
state on $p$ qubits, i.e., a rank one positive semi-definite matrix. To see
why, note that, if some mixed state $\rho=\sum
p_{i}\Ket{\psi_{i}}\Bra{\psi_{i}}$ causes the verifier to accept with
probability $2/3$, then, by convexity, there exists a state $\Ket{\psi_{k}}$
in that mixture that would also cause the verifier to output $1$ with
probability at least $2/3$. Hence, the proof can be the pure state
$\Ket{\psi_{k}}$. Likewise, if no pure state can make the verifier accept with
probability larger than $1/3$, the same holds for mixed states.

##  4 Complexity separations

Armed with a formal definition of QMAPs, we begin to chart the landscape of
complexity classes to which quantum proofs of proximity belong. In Section
4.1, we provide definitions that will be necessary in the remainder of the
section, mainly pertaining to coding theory.

Our main goal is to prove 1, namely, that QMAPs can exploit quantum resources
and the availability of a proof to gain expressivity that neither can provide
separately. This theorem follows from the _incomparabilty_ between the classes
$\mathcal{MAP}$ and $\mathcal{QPT}$: in Section 4.2, we exhibit a property
$\Pi_{B}$ that is easy to test classically with a short proof, but requires
many queries (without a proof) even for a quantum tester (Theorem 4.3);
moreover, in Section 4.3, we show the existence of a property $\Pi_{F}$ that
is easily testable quantumly but difficult to test classically, even with the
aid of a proof (Theorem 4.4).

The aforementioned results immediately imply the existence of a property,
namely $\Pi_{B}\times\Pi_{F}$, which does not admit efficient MAPs nor quantum
testers, requiring large proof or query complexity, whereas a QMAP with
logarithmic proof and query complexities does exist (indeed, one with a
_classical_ proof).

######  Theorem 4.1 (1, restated).

There exists a property $\Pi\subseteq\\{0,1\\}^{n}$ such that, for any small
enough constant $\varepsilon>0$,

$\Pi\in\mathcal{QCMAP}(\varepsilon,\log n,O(1))$

and

$\Pi\notin\mathcal{QPT}(\varepsilon,o(n^{0.49}))\cup\mathcal{MAP}(\varepsilon,p,q)$

when $p\cdot q=o(n^{1/4})$.

###  4.1 Preliminaries

We first define the necessary notions of local codes that will be used in this
section. We denote throughout a finite field of constant size by $\mathbb{F}$.

######  Definition 3 (Locally Testable Codes (LTCs)).

A code $C\colon\mathbb{F}^{k}\to\mathbb{F}^{n}$ is locally testable, with
respect to proximity parameter $\varepsilon$ and error rate $\sigma$, if there
exists a probabilistic algorithm $T$ that makes $q$ queries to a purported
codeword $w$ such that:

  1. 1.

If $w=C(x)$ for some $x\in\mathbb{F}^{k}$, then
$\mathbb{P}\left[T^{w}=1\right]\geq 1-\sigma$.

  2. 2.

For every $w$ that is $\varepsilon$-far from $C$, we have
$\mathbb{P}\left[T^{w}=0\right]\geq 1-\sigma$.

Note that the algorithm $T$ that an LTC admits is simply an
$\varepsilon$-tester for the property of being a valid codeword of $C$.

######  Definition 4 (Locally Decodable Codes (LDCs)).

A code $C\colon\mathbb{F}^{k}\to\mathbb{F}^{n}$ is locally decodable with
_decoding radius_ $\delta$ and error rate $\sigma$ if there exists a
probabilistic algorithm $D$ that given index $i\in[k]$ makes $q$ queries to a
string $w$ promised to be $\delta$-close to a codeword $C(x)$, and satisfies

$\mathbb{P}[D^{w}(i)=x_{i}]\geq 1-\sigma.$

Since the best known constructions of LDCs have superpolynomial blocklength,
we will make use of a relaxation of this type of code that allows for much
more efficient constructions and suffices for our purposes.

######  Definition 5 (Relaxed LDCs).

A code $C\colon\mathbb{F}^{k}\to\mathbb{F}^{n}$ with relative distance
$\delta_{C}$ is a $q$-local relaxed LDC with success rate $\rho$ and decoding
radius $\delta\in(0,\delta_{C}/2)$ if there exists a randomised algorithm $D$,
known as a _relaxed decoder_ that, on input $i\in[k]$, makes at most $q$
queries to an oracle $w$ and satisfies the following conditions.

  1. 1.

Completeness: For any $i\in[k]$ and $w=C(x)$, where $x\in\mathbb{F}^{k}$,

$\mathbb{P}[D^{w}(i)=x_{i}]\geq 2/3.$

  2. 2.

Relaxed Decoding: For any $i\in[k]$ and any $w\in\mathbb{F}^{n}$ that is
$\delta$-close to a (unique) codeword $C(x)$,

$\mathbb{P}[D^{w}(i)\in\\{x_{i},\bot\\}]\geq 2/3.$

  3. 3.

Success Rate: There exists a constant $\rho>0$ such that, for any
$w\in\mathbb{F}^{n}$ that is $\delta$-close to a codeword $C(x)$, there exists
a set $I_{w}\subseteq[k]$ of size at least $\rho k$ such that for every $i\in
I_{w}$,

$\mathbb{P}[D^{w}(i)=x_{i}]\geq 2/3\enspace.$

As shown by [13, 42, 25, 10], there exist linear codes of only slightly
superlinear blocklength that are both locally testable _and_ relaxed locally
decodable:121212We note that while LTCs and RLDCs are usually defined with
respect to _binary_ alphabets, they can be constructed over larger fields as
well as fields of odd characteristic. The constructions essentially rely on
two components: a base (linear) code and a PCP of proximity, both of which
readily extend to larger alphabets.

######  Theorem 4.2.

For any constant $\gamma>0$, there exist linear codes over $\mathbb{F}$ with
blocklength $n=k^{1+\gamma}$ that are relaxed locally decodable with $O(1)$
queries with respect to decoding radius $\delta=\Omega(1)$. Moreover, given
any constant proximity parameter $\varepsilon\in(0,\delta]$, the code is also
locally testable with $O(1)$ queries.

Moreover, the tester and local decoder for these codes are one-sided (i.e.,
always accept when given a valid codeword as input), and the blocklength
cannot be improved to linear [44, 27].

##### Communication complexity.

In the model of quantum communcation complexity, two parties with unbounded
computational power aim to compute a joint predicate by communicating the
smallest number of qubits with each other. Alice knows $x\in\\{0,1\\}^{k}$,
Bob knows $y\in\\{0,1\\}^{k}$ and both hold a function
$f:\\{0,1\\}^{2k}\to\\{0,1\\}$, and, by communicating qubits with each other,
they must compute $f(x,y)$ with bounded probability of error. The
_communication complexity_ of $f$ is the worst-case number qubits that need to
be communicated in order to compute $f(x,y)$ over all $x,y$, minimised over
all communication protocols.

We will make use of the well-known communication complexity problem of
_disjointness_.

######  Definition 6.

Let $x,y\in\\{0,1\\}^{k}$ and $S,T\subseteq[k]$ be sets whose indicator
vectors are $x$ and $y$, respectively; i.e.,
$S=\left\\{i\in[k]:x_{i}=1\right\\}$ and $T=\left\\{i\in[k]:y_{i}=1\right\\}$.
Then $\mathsf{DISJ}_{k}(x,y)=1$ if and only if $S$ and $T$ are disjoint, that
is,

$\mathsf{DISJ}_{k}(x,y)=\left\\{\begin{array}[]{ll}1&\text{ if }S\cap
T=\varnothing\\\
0&otherwise\end{array}\right.=\left\\{\begin{array}[]{ll}1&\text{ if
}x_{i}=0\text{ or }y_{i}=0\text{ for all }i\in[k],\\\
0&otherwise.\end{array}\right.$

This problem is known to be hard for quantum communication protocols,
requiring $\Omega(\sqrt{k})$ qubits of communication, as shown in [68].

###  4.2 MAPs versus quantum testers

We now set out to prove Theorem 4.3, which shows a property $\Pi_{B}$ that is
efficiently testable with a short classical proof (Lemma 1) but for which a
quantum tester must make a large number of queries (Lemma 2).

The property in question is defined as follows. First, consider a linear code
$C:\mathbb{F}^{k}\rightarrow\mathbb{F}^{n}$ with $n=k^{1.001}$, over a field
$\mathbb{F}$ of odd characteristic and size $O(1)$, that is both _relaxed
locally decodable_ with $O(1)$ queries and decoding radius $\delta=\Omega(1)$;
as well as _locally testable_ with $O(1)$ queries for any constant proximity
parameter $\varepsilon\in(0,\delta]$ (recall that Theorem 4.2 shows that codes
with these parameters exist).

The property $\Pi_{B}$ comprises the encoding of _non-Boolean_ messages, that
is:

$\Pi_{B}=\left\\{C(z):z\in\mathbb{F}^{k}\setminus\\{0,1\\}^{k}\right\\}\;.$

We first show that the property $\Pi_{B}$ is efficiently testable via a MAP
protocol with a short proof.

######  Lemma 1.

For any constant $\varepsilon\in(0,\delta]$,
$\Pi_{B}\in\mathcal{MAP}(\varepsilon,\log n,O(1))$.

###### Proof.

The verifier will follow the following strategy to test $\Pi_{B}$: first, test
whether the input is $\varepsilon$-close to the code $C$ (which can be
accomplished with $O(1)$ queries due to the local testability of $C$). If the
tester rejects, then not only is the input far from $\Pi_{B}$, but from all of
$C$, in which case it rejects.

Except with small probability, if the tester accepts the input is
$\delta$-close to $C$, so we may locally decode any coordinate of the message
(also with $O(1)$ queries); using the proof string to determine this location,
the verifier then checks if the symbol at that coordinate is Boolean-valued.

This strategy is laid out in Algorithm 1.

1

Input: explicit access to a proximity parameter $\varepsilon>0$ and a proof
string $\pi\in\\{0,1\\}^{\log n}$, as well as oracle access to
$x\in\mathbb{F}^{n}$.

2

3Test if the input $w$ is a valid codeword with proximity parameter
$\varepsilon$. Reject if the test rejects.

4Interpret the proof as an index $i\in[k]$, locally decode $z_{i}$ and accept
if $z_{i}\in\mathbb{F}\setminus\\{0,1\\}$. Otherwise, reject.

Algorithm 1 MAP verifier for $\Pi_{B}$

Note that the proof complexity is $\log n$ by definition, and, since both
local testing and local decoding have query complexity $O(1)$, the verifier
makes $O(1)$ queries in total (note that querying an element of $\mathbb{F}$
requires $O(1)$ _bit_ queries, so the complexities of the tester and decoder
are still constant in terms of bit queries). Moreover, if $w\in\Pi_{B}$, then
$w=C(z)$ for some $z\in\mathbb{F}^{k}\setminus\\{0,1\\}^{k}$, and local
testing succeeds with probability 1; and when the prover specifies a
coordinate $i$ such that $z_{i}\notin\\{0,1\\}$, local decoding also succeeds
with probability 1, so completeness follows.

Now, if $w$ is $\varepsilon$-far from $\Pi_{B}$, then either (1) the input $w$
is $\varepsilon$-far from _any_ codeword of the code $C$; or (2) $w$ is
$\varepsilon$-close to some $C(z)$ such that $z\in\\{0,1\\}^{k}$.

In the first case, local testing (and thus the verifier) will reject with
probability $2/3$. In the second case, the testing step may not trigger a
rejection, but the local decoder then outputs, regardless of the proof
$i\in[k]$, either $\bot$ or $z_{i}\in\\{0,1\\}$ with probability $2/3$, any of
which cause the verifier to reject. ∎

The next lemma shows that, unlike MAPs, quantum testers cannot test $\Pi_{B}$
efficiently.

######  Lemma 2.

Any quantum tester for the property $\Pi_{B}$ with constant proximity
parameter $\varepsilon\in[0,\delta)$ must have query complexity
$\Omega(n^{0.49})$.

###### Proof.

Recall that in the disjointness problem, Alice is given as input
$x\in\\{0,1\\}^{k}$, Bob is given $y\in\\{0,1\\}^{k}$ and they must compute
$\mathsf{DISJ}_{k}(x,y)$; and that $\Pi_{B}$ is the encoding of non-Boolean
strings of length $k=n^{\frac{1}{1.001}}$ by the code $C$.

To show that any quantum tester needs $\Omega(n^{0.49})$ queries to
$\varepsilon$-test $\Pi_{B}$, we give a reduction showing that a tester with
query complexity $q$ can be used to compute $\mathsf{DISJ}_{k}$ by
communicating $O(q\log n)$ qubits. Since the quantum communication complexity
of $\mathsf{DISJ}_{k}$ is
$\Omega(\sqrt{k})=\Omega(n^{\frac{1}{2}\cdot\frac{1}{1.001}})=\Omega(n^{0.499})$,
the query complexity of the quantum tester follows.

First, Alice and Bob use $C$ to encode $x$ and $y$, respectively. Now Alice
holds $C(x)\in\mathbb{F}^{n}$ and Bob holds $C(y)\in\mathbb{F}^{n}$. Note
that, defining $z\coloneqq x+y\in\mathbb{F}^{k}$, we have
$\mathsf{DISJ}(x,y)=0\iff z\notin\\{0,1\\}^{k}\iff C(z)\in\Pi_{B}$ (recall
that the characteristic of $\mathbb{F}$ is larger than $2$, so that if
$x_{i}=y_{i}=1$, we have $z_{i}=2\notin\\{0,1\\}$). Now, Alice and Bob
respectively set up the unitaries $U_{A}$ and $U_{B}$ shown below, where the
first register holds $\log n$ qubits and the second holds $O(1)$ qubits
(enough to specify a single element of $\mathbb{F}$).

$\displaystyle\forall i\in[n],\alpha\in\mathbb{F},\quad$ $\displaystyle
U_{A}\ket{i}\ket{\alpha}=\ket{i}\ket{\alpha+C(x)_{i}}$ $\displaystyle
U_{B}\ket{i}\ket{\alpha}=\ket{i}\ket{\alpha+C(y)_{i}}\;.$

Alice then simulates the quantum tester and only communicates with Bob in
order to make a query to the oracle; if the tester accepts, Alice outputs 0,
and she outputs 1 otherwise.

More precisely, whenever the tester calls the oracle $U$, which acts as
$U\ket{i}\ket{\alpha}=\ket{i}\ket{\alpha+C(z)_{i}}$ on a $(\log n+O(1))$-bit
quantum state $\rho$, Alice first applies $U_{A}$ to $\rho$, then sends all
qubits to Bob; Bob then applies $U_{B}$ on the qubits it receives and returns
them to Alice. This communicates a total of $O(\log n)$ qubits and implements
the same transformation as querying $U$, since $U_{B}\cdot
U_{A}\ket{i}\ket{j}=\ket{i}\ket{j+C(x)_{i}+C(y)_{i}}=\ket{i}\ket{j+C(x+y)_{i}}$
by the linearity of the code $C$ and the fact that $z=x+y$.

Each query made by the tester entails $O(\log n)$ qubits of communication, so
that after $q$ queries, Alice and Bob exchange $O(q\cdot\log n)$ qubits in
total. The tester accepts with probability at least $2/3$ when
$C(z)\in\Pi_{B}\iff\mathsf{DISJ}(x,y)=0$, in which case Alice outputs 0. If
$\mathsf{DISJ}(x,y)=1$, we have that $C(z)$ is $\delta$-far from $\Pi_{B}$
(since the relative distance of $C$ is $\delta$). Since
$\varepsilon\leq\delta$, the $\varepsilon$-tester rejects with probability
$2/3$ and Alice outputs 1 in this case.

Thus, Alice is able to compute $\mathsf{DISJ}_{k}$ with $O(q\cdot\log n)$
qubits of communication. Since the quantum communication complexity of
$\mathsf{DISJ}_{k}$ is $\Omega(\sqrt{k})$ [68], we conclude that the tester
must make $\Omega(\sqrt{k}/\log n)=\Omega(n^{0.499}/\log n)=\Omega(n^{0.49})$
queries. ∎

######  Remark 3.

Although we reduce $\mathsf{DISJ}$ to testing _non_ -Booleanity, a symmetric
argument shows the same lower bound for the (arguably more natural) property
of _Booleanity_ $\left\\{C(z):z\in\\{0,1\\}^{k}\right\\}$. Often, one key step
in PCP constructions is to check that an encoding corresponds to a logical
assignment, i.e., that it is the encoding of a Boolean message. Therefore,
bounds on Booleanity may have consequences for PCPs.

We conclude this section with the separation immediately implied by Lemma 1
and Lemma 2.

######  Theorem 4.3.

For every constant $\varepsilon\in(0,\delta]$, the property $\Pi_{B}$ belongs
to $\mathcal{MAP}(\varepsilon,\log n,O(1))$ but does not belong to
$\mathcal{QPT}(\varepsilon,o(n^{0.49}))$. Therefore,

$\mathcal{MAP}(\varepsilon,\log
n,O(1))\not\subseteq\mathcal{QPT}(\varepsilon,o(n^{0.49}))\;.$

###  4.3 Quantum testers versus MAPs

In this section, we will show the existence of a property that is easily
testable with a quantum tester, but for which a classical tester – even with
additional access to a proof – must make a number of queries that depends
strongly on the length of the input. More formally, we will show in Theorem
4.4 the existence of a property of $n$-bit strings in
$\mathcal{QPT}(\varepsilon,O(1/\varepsilon))$ that is not in
$\mathcal{MAP}(\varepsilon,p,q)$ when $p\cdot q=o(n^{1/4})$ and $\varepsilon$
is a small enough constant.

The property in question is derived from Forrelation, a problem that strongly
separates classical and quantum algorithms in the query model; in fact, the
work that proved such a separation already shows that it carries over to the
property testing setting [3], which we will extend to the setting of MAPs.
Formally, we have

######  Lemma 3 ([3]).

Define the property $\Pi_{F}$ as

$\Pi_{F}=\left\\{(f,g):\Phi_{f,g}\leq 1/100\right\\},$

where $(f,g)$ are $n/2$-bit strings corresponding to pairs of $\log(n/2)$-bit
Boolean functions and
$\Phi_{f,g}=(n/2)^{-3/2}\sum_{x,y\in\\{0,1\\}^{\log(n/2)}}f(x)(-1)^{x\cdot
y}g(y)$.

Then, for any $\varepsilon>0$ sufficiently small,

$\Pi_{F}\in\mathcal{QPT}(\varepsilon,O(1/\varepsilon))\text{ and
}\Pi_{F}\notin\mathcal{PT}(\varepsilon,o(\sqrt{n}/\log n)).$

Therefore, the property $\Pi_{F}$ is easy for quantum testers and hard for
their classical counterparts. This section is thus devoted to showing that
testing $\Pi_{F}$ is hard not only for property testers, but for MAPs as well:
we will prove that a MAP for $\Pi_{F}$ requires proof length $p$ and query
complexity $q$ satisfying $pq=\Omega(n^{1/4})$. We first introduce relevant
definitions and theorems, then describe the steps of the proof.

Recall that $\mathcal{MA}$ is the class of languages that are decidable _in
polynomial time_ with a (polynomial-size) proof string, the analogue of which
is $\mathcal{MAP}$ in the property-testing setting. By [49], $\mathcal{MA}$ is
contained in the class $\mathcal{BPP}_{\text{path}}$ of languages decidable
(with high probability) by a randomised Turing machine whose computational
paths are all equally likely.131313In $\mathcal{BPP}$, the probability of
following a computational path is a function of its length (which coincides
with the number of random coins flipped by the algorithm).
$\mathcal{BPP}_{\text{path}}$ differs from $\mathcal{BPP}$ by lifting this
restriction. Query lower bounds for Forrelation (i.e., deciding whether
$\absolutevalue{\Phi_{f,g}}\leq 1/100$ or $\Phi_{f,g}>3/5$ for a pair $(f,g)$
of Boolean functions) against the latter are known:

######  Proposition 1 ([1, 24]).

Any $BPP_{\text{path}}$ algorithm for Forrelation must make $\Omega(n^{1/4})$
queries to its input.

We are now ready to describe the three steps taken in proving hardness of
$\Pi_{F}$ for $\mathcal{MAP}$: we (1) show that transforming an MA algorithm
with proof complexity $p$ and query complexity $q$ into a $BPP_{\text{path}}$
one [49] yields an algorithm with query complexity $O(pq)$; (2) show how a MAP
for $\Pi_{F}$ implies an $\mathcal{MA}$ algorithm with the same parameters
_for Forrelation_ ; and (3) conclude that $pq=o(n^{1/4})$ implies a
$\mathcal{BPP}_{\text{path}}$ upper bound of $O(pq)=o(n^{1/4})$ for the query
complexity of Forrelation, which contradicts Proposition 1.

The original proof of $\mathcal{MA}\subseteq\mathcal{BPP}_{\text{path}}$
([49], Theorem 3.7) takes an MA algorithm with proof complexity $p$ and
constant success probability, repeats the execution $O(p)$ times, amplifying
the success probability to $1-O(2^{-p})$, and then defines a
$\text{BPP}_{\text{path}}$ machine as follows. The machine (non-
deterministically) guesses a proof string and simulates the MA algorithm with
it, spawning “dummy” execution paths if the MA algorithm accepts. Inspecting
this transformation in the query model, we obtain a quadratic overhead: if the
MA algorithm has query complexity $q$ and proof complexity $p$, the
$\text{BPP}_{\text{path}}$ machine thus obtained has query complexity $O(pq)$
(the $O(p)$ repetitions of the MA algorithm increase its query complexity
multiplicatively by this amount, while the dummy paths make no queries).

The second step is formalised by the following lemma.

######  Lemma 4.

A MAP protocol for $\Pi_{F}$ with sufficiently small proximity parameter
$\varepsilon>0$ implies an $\mathcal{MA}$ algorithm for Forrelation with the
same query and proof complexities as the MAP protocol.

###### Proof.

We define an MA protocol _for Forrelation_ (as a gap problem) the natural way:
the proofs and queries correspond to the proofs and queries of the MAP, and
the MA verifier accepts if and only if the MAP rejects.

To show correctness of this protocol, we follow the reduction of [3].
Specifically, [3, Lemma 40] shows that any $(f^{\prime},g^{\prime})$ such that
$f^{\prime}$ is $\varepsilon$-close to $f$ and $g^{\prime}$ is
$\varepsilon$-close to $g$ satisfies $\absolutevalue{\langle
f^{\prime},Hg^{\prime}\rangle-\langle
f,Hg\rangle}=O(\sqrt{\varepsilon}\log(1/\varepsilon))$. By choosing a suitably
small $\varepsilon$, the right-hand side is at most (say) $1/100$. Thus any
$(f,g)$ such that $\langle f,Hg\rangle>3/5$ is $\varepsilon$-far from $\Pi$,
and it follows that the MAP protocol will accept (with high probability) pairs
$(f,g)$ such that $\absolutevalue{\langle f,Hg\rangle}\leq 1/100$ and will
reject if $\langle f,Hg\rangle>3/5$. Therefore, the MA protocol is able to
distinguish between the two cases. ∎

A simple argument now proves the separation.

######  Theorem 4.4.

Let $\varepsilon>0$ be a small enough constant. There exists a property
$\Pi_{F}$ such that $\Pi_{F}\in\mathcal{QPT}(\varepsilon,O(1/\varepsilon))$
and $\Pi_{F}\notin\mathcal{MAP}(\varepsilon,p,q)$ for any $p,q$ such that
$p\cdot q=o(n^{1/4})$.

###### Proof.

Suppose, towards contradiction, that there existed a MAP for $\Pi_{F}$ with
any proximity parameter $\varepsilon$, as well as proof complexity $p$ and
query complexity $q$ satisfying $p\cdot q=o(n^{1/4})$.

By Lemma 4, there exists an MA protocol for Forrelation with the same query
and proof complexities, which can then be transformed into a
$BPP_{\text{path}}$ algorithm with query complexity $O(p\cdot q)=o(n^{1/4})$
for the same problem. But this contradicts the $\Omega(n^{1/4})$ lower bound
of Proposition 1. ∎

We are finally ready to prove the main separation, by exhibiting a property
$\Pi$ in $\mathcal{QCMAP}$ which is in neither $\mathcal{MAP}$ nor
$\mathcal{QPT}$.

###### Proof of Theorem 4.1.

Recall that our goal is to show that the property $\Pi=\Pi_{B}\times\Pi_{F}$
that is efficiently $\varepsilon$-testable by a QCMAP, but not by a quantum
tester (without a proof) nor classicaly with a proof, for some small enough
$\varepsilon=\Omega(1)$. To this end, we invoke Theorem 4.3 and Theorem 4.4
and give the following verifier strategy explicitly. Note that, while the
strings in $\Pi_{B}$ are over an alphabet $\mathbb{F}$ larger than
$\\{0,1\\}$, since $\absolutevalue{\mathbb{F}}=O(1)$ each symbol can be
represented by $O(1)$ bits (and the proof indicates the first bit in such a
block).

1

Input: explicit access to a proximity parameter
$\varepsilon^{\prime}=2\varepsilon>0$ and a proof $i\in[n/2]$, as well as
oracle access to a string $z\in\\{0,1\\}^{n}$

2

3Interpret the input as a concatenation of $n/2$-bit strings $x$ and $y$. Use
the algorithm of Lemma 1 to verify, with $O(1)$ queries and the proof $i$,
whether $x\in\Pi_{B}$ with proximity
$\varepsilon\coloneqq\varepsilon^{\prime}/2$.

4Use the quantum tester of Lemma 3 to test, with $O(1)$ queries, if
$y\in\Pi_{F}$ with proximity $\varepsilon$.

5If both of the previous tests accepted, then accept; otherwise, reject.

Algorithm 2 QCMAP verifier for $\Pi_{B}\times\Pi_{F}$

Completeness follows immediately from Lemma 1 and Lemma 3, since the verifier
for $\Pi_{B}$ accepts with certainty and the and tester for $\Pi_{F}$ accepts
with probability $2/3$ when $x\in\Pi_{B}$ and $y\in\Pi_{F}$. If, on the other
hand, $(x,y)$ is $\varepsilon$-far from $\Pi_{B}\times\Pi_{F}$, then either
$x$ is $\varepsilon$-far from $\Pi_{B}$ or $y$ is $\varepsilon$-far from
$\Pi_{F}$, and either the verifier for $\Pi_{B}$ or the tester for $\Pi_{F}$
will reject (with probability $2/3$). Thus, the QCMAP verifier for $\Pi$
(executed with respect to proximity parameter
$\varepsilon^{\prime}=2\varepsilon$) implies
$\Pi\in\mathcal{QCMAP}(\varepsilon,\log n,O(1))$.

All that remains is to show $\Pi=\Pi_{B}\times\Pi_{F}$ does not admit an
efficient quantum tester nor a MAP. Assume, towards contradiction, that either
$\Pi\in\mathcal{QPT}(\varepsilon,o(n^{0.49}))$ or
$\Pi\in\mathcal{MAP}(\varepsilon,p,q)$ when $p\cdot q=o(n^{1/4})$. In the
first case, applying the tester for $\Pi$ to $\Pi_{B}\times\left\\{y\right\\}$
for some fixed $y\in\Pi_{F}$ shows that
$\Pi_{B}\in\mathcal{QPT}(\varepsilon,o(n^{0.49}))$, a contradiction with Lemma
2. In the second case, applying the MAP protocol for $\Pi$ to
$\left\\{x\right\\}\times\Pi_{F}$, for some fixed $x\in\Pi_{B}$, shows that
$\Pi_{F}\in\mathcal{MAP}(\varepsilon,p,q)$, a contradiction with Theorem 4.4.
∎

##  5 A hard class of problems for QMAPs

When introducing a new complexity class in the landscape of known classes, it
is important not only to exhibit problems it can solve, but also problems it
cannot. We set out to show a natural limitation on QMAPs in this section, by
answering (negatively) the following question: if a property “looks random” on
any subset of $q$ coordinates, can a quantum proof be of any help to a
verifier with query complexity $q$? Intuitively, the answer should be no: if
querying $q$ coordinates provides no information as to whether or not an input
satisfies a property, then any proof (quantum or otherwise) should not be able
to offer more information in conjunction with the queries than it does on its
own.

We formalise this intuition in Theorem 5.2, which states the following: if a
property $\Pi\subset\\{0,1\\}^{n}$ is $k$-wise independent and sparse (i.e.,
its size $|\Pi|$ is sufficiently small compared to the set of all $2^{n}$ bit
strings), then $k$ is a lower bound on the number of queries made by any
randomised query algorithm that accepts all inputs in $\Pi$ with probability
strictly greater than $1/2$, and rejects with probability strictly greater
than $1/2$ when run on any input that is far from $\Pi$. In other words, the
$\mathcal{UPP}$ query complexity of testing $\Pi$ is at least $k$ (recall that
$\mathcal{UPP}$ is the query model version of $\mathcal{PP}$, which captures
randomized computation with small bias). Note that _some_ assumption on the
sparsity of $\Pi$ is necessary for any non-trivial lower bound to hold, if
only to rule out, e.g., the trivially testable property $\Pi=\\{0,1\\}^{n}$.

Combining Theorem 5.2 with the well-known inclusion
$\mathcal{QMA}\subseteq\mathcal{PP}$ [58] allows us to conclude the following:
for any $k$-wise independent and sufficiently sparse property $\Pi$, the
product of proof and query complexities of a QMAP for verifying membership in
$\Pi$ with constant proximity parameter $\varepsilon$ is $\Omega(k)$ (see
Corollary 4).

The proof of Theorem 5.2 works as follows. Our analysis shows that the
sparsity of $\Pi$ ensures there exists a subset
$\Pi^{\prime}\subset\\{0,1\\}^{n}$ that is far from $\Pi$ such that
$\Pi^{\prime}$ is _also_ $k$-wise independent (see Lemma 5). This means that
any query algorithm making fewer than $k$ queries cannot distinguish a random
input in $\Pi$ from a random input in $\Pi^{\prime}$, as both sets “look
random” when inspecting only $k$ bits of a randomly chosen input from the set.
Yet since $\Pi^{\prime}$ is far from $\Pi$, any testing procedure for $\Pi$
must distinguish $\Pi$ from $\Pi^{\prime}$. Hence, any tester for $\Pi$ must
make $k$ queries (even if it only outputs the correct answer on inputs in
$\Pi$ and $\Pi^{\prime}$ with probability strictly greater than $1/2$).

##### Technical Details.

We begin recalling the definition of $k$-wise independence.

######  Definition 7.

A set of strings $S\subseteq\\{0,1\\}^{n}$ is called $k$-wise independent if,
for any fixed set of indices $I\subset[n]$ of size $k$, the string $x_{|I}$ is
uniformly random when $x$ is sampled uniformly from $S$. Equivalently, for
every $y\in\\{0,1\\}^{k}$,

$\absolutevalue{\left\\{x\in
S:x_{|I}=y\right\\}}=\frac{\absolutevalue{S}}{2^{k}}.$

We next show that, given any small enough set $S$ of strings, there exists a
$\Omega(n)$-wise independent set that is $\varepsilon$-far from $S$. In the
following lemma, $H$ denotes the binary entropy function
$H(\alpha)=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha)$ (whose restriction to
$[0,1/2]$ is bijective).

######  Lemma 5.

Let $\varepsilon\in(0,H^{-1}(1/5))$ and $S\subseteq\\{0,1\\}^{n}$ be such that
$\absolutevalue{S}<2^{(1/4-H(\varepsilon))n}$. Then there exists a linear code
$C$ that is $\varepsilon$-far from $S$ with dual distance $\Omega(n)$;
equivalently, $C$ is $\Omega(n)$-wise independent.

###### Proof.

Let $C\colon\\{0,1\\}^{3n/4}\to\\{0,1\\}^{n}$ be a random linear code (where
each entry of its generator matrix is a Bernoulli($1/2$) random variable).
Then, for every $x\in\\{0,1\\}^{3n/4}$, the codeword $C(x)$ is uniformly
random in $\\{0,1\\}^{n}$ (but _not_ independent of other codewords). Denoting
by $N_{\varepsilon}(S)$ the $\varepsilon$-neighbourhood of $S$ (i.e., the set
of bit strings at distance at most $\varepsilon$ from $S$), we have:

$\displaystyle\mathbb{P}[C\cap N_{\varepsilon}(S)\neq\varnothing]$
$\displaystyle\leq\sum_{x\in\\{0,1\\}^{3n/4}}\mathbb{P}[C(x)\in
N_{\varepsilon}(S)]=2^{3n/4}\cdot\frac{\absolutevalue{N_{\varepsilon}(S)}}{2^{n}}$
$\displaystyle\leq\frac{\absolutevalue{S}\cdot
2^{H(\varepsilon)n}}{2^{n/4}}=o(1),$

and, by the probabilistic method, there exists a code $C\subset\\{0,1\\}^{n}$
of size $2^{3n/4}$ that is $\varepsilon$-far from $S$. Moreover, the dual code
$C^{\perp}\colon\\{0,1\\}^{n/4}\to\\{0,1\\}^{n}$ is a linear code whose
distance meets the Gilbert-Varshamov bound with high probability; that is, the
distance of this dual code is $\Omega(n)$ with probability $1-o(1)$, proving
the claim. ∎

The previous lemma, when applied to a “random-looking” set $S$ (i.e., a
$k$-wise independent $S$, for $k=o(n)$), will ensure that $S$ and the code $C$
are hard to distinguish. To make this precise, we first recall the definition
of the _threshold degree_ of a (partial) function.

######  Definition 8.

Let $\mathcal{X}\subseteq\\{1,-1\\}^{n}$ and let $f:\mathcal{X}\to\\{1,-1\\}$
be any function defined on domain
$\mathcal{X}\subseteq\\{1,-1\\}^{n}$.141414For notational convenience, we
consider Boolean functions with codomain $\\{1,-1\\}$, noting that this is
equivalent to the usual codomain $\\{0,1\\}$ by mapping $0\to 1$, $1\to-1$,
and $\oplus$ to multiplication. The threshold degree of $f$, denoted
$\mathsf{thrdeg}(f)$, is the minimal degree of an $n$-variate polynomial $p$
that sign-represents $f$, i.e., such that $f(x)=\mathsf{sgn}(p(x))$ for all
$x\in\mathcal{X}$.151515Here, $\mathsf{sgn}(t)$ is defined to equal $1$ if
$t>0$, $-1$ if $t<0$, and $0$ if $t=0$. Note that no constraints are placed on
the behaviour of $p(x)$ at inputs in $\\{1,-1\\}^{n}\setminus\mathcal{X}$.

The threshold degree is a measure of complexity of Boolean functions (in
particular), so that we expect functions with high threshold degree to also
have high query complexity. This intuition is validated by the following
folklore result: the minimal query complexity of a UPP algorithm that computes
$f$ is exactly equal to its threshold degree. We provide a proof of this fact
for completeness, as, to the best of our knowledge, it is not explicitly
proven in the literature.

We write $f\in\mathcal{UPP}(q)$ when there exists a UPP algorithm with query
complexity $q$ that computes $f$, and denote by $q(f)$ the integer such that
$f\in\mathcal{UPP}(q(f))$ but $f\notin\mathcal{UPP}(q(f)-1)$.

######  Lemma 6.

For any $\mathcal{X}\subseteq\\{1,-1\\}^{n}$ and
$f\colon\mathcal{X}\to\\{1,-1\\}$, it holds that $\mathsf{thrdeg}(f)=q(f)$.

###### Proof.

We prove both inequalities, starting with $q(f)\leq\mathsf{thrdeg}(f)\coloneqq
d$.

Let $P(X_{1},\ldots,X_{n})=\sum_{S\subset[n],\absolutevalue{S}\leq
d}\alpha_{S}\prod_{i\in S}X_{i}$ be a polynomial of degree $d$ that sign-
represents $f$, i.e., such that $f(x)=\textsf{sgn}(P(x))$ for all
$x\in\mathcal{X}$. Consider the algorithm $A$ that queries the set of
coordinates $S$ with probability
$\absolutevalue{\alpha_{S}}/\sum_{\absolutevalue{T}\leq
d}\absolutevalue{\alpha_{T}}$ and outputs
$\mathsf{sgn}(\alpha_{S})\cdot\prod_{i\in S}x_{i}$ (note that its query
complexity is $d$). Fix $x\in\mathcal{X}$ and suppose, without loss of
generality, that $f(x)=1$. We thus have

$\mathbb{E}[A^{x}]=\frac{1}{\sum_{\absolutevalue{T}\leq
d}\absolutevalue{\alpha_{T}}}\sum_{\absolutevalue{S}\leq
d}\absolutevalue{\alpha_{S}}\cdot\mathsf{sgn}(\alpha_{S})\cdot\prod_{i\in
S}x_{i}=\frac{P(x)}{\sum_{\absolutevalue{T}\leq
d}\absolutevalue{\alpha_{T}}}>0,$

and, since $A^{x}$ only outputs 1 or $-1$, we have
$\mathbb{P}[A^{x}=-1]+\mathbb{P}[A^{x}=1]=1$ and thus
$\mathbb{P}[A^{x}=1]>1/2$. It follows that $A$ is a UPP algorithm for $f$ with
query complexity $d$ and thus $q(f)\leq\mathsf{thrdeg}(f)$.

To prove the reverse inequality, consider a UPP algorithm $A$ that computes
$f$ with query complexity $q\coloneqq q(f)$, given by a distribution over
decision trees of depth at most $q$. To see that the function computed by each
decision tree $T$ can be sign-represented by a polynomial of degree at most
$q$ (which is a standard fact), we follow the exposition on _leaf indicators_
in [43]. Denote by $L$ the set of leaves of $T$, and identify each $\ell\in L$
with its indicator function $\ell\colon\\{1,-1\\}^{n}\to\\{0,1\\}$ such that
$\ell(x)=1$ if and only if $\ell$ is the unique leaf reached on input $x$ in
$T$.

Then, if $c_{\ell}\in\\{1,-1\\}$ is the output of the decision tree when an
execution ends at the leaf $\ell$, the output of $T$ on input $x$ is
$\sum_{\ell\in L}c_{\ell}\cdot\ell(x)$. Thus, showing $\ell(\cdot)$ can be
represented by a polynomial of degree at most $q$ implies the same degree
bound for the computation of $T$. Fix $\ell\in L$, let
$(i_{1},\ldots,i_{d})\in[n]^{q}$ be the coordinates queried by the root-to-
leaf path that ends at $\ell$, and let the sequence of bits
$(b^{\ell}_{1},\ldots,b^{\ell}_{d})\in\\{1,-1\\}^{q}$ correspond to the
queried values that cause this path to be followed. Then,

$\ell(x_{1},\ldots,x_{n})=\prod_{j=1}^{q}\frac{x_{i_{j}}+b_{j}}{2b_{j}},$

so $\ell(\cdot)$ can be represented by the degree-$q$ polynomial
$P(X_{1},\ldots,X_{n})=2^{-q}\prod_{j=1}^{q}(X_{i_{j}}+b_{j})/b_{j}$. Thus,
the output of $A^{x}$ _when it selects this tree_ is the degree-$q$ polynomial
$\sum_{\ell\in L}c_{\ell}\cdot\ell(x)$, and $\mathbb{E}[A^{x}]$ is a convex
combination of such sums (which also has degree $q$). Since
$f(x)=\mathsf{sgn}(\mathbb{E}[A^{x}])$ for all $x\in\mathcal{X}$, we conclude
that $\mathsf{thrdeg}(f)\leq q(f)$ and the claim follows. ∎

The final ingredient to show the lower bound is the next theorem, a special
case of the “Theorem of the Alternative” [63, 11].

######  Theorem 5.1.

Let $\mathcal{X}\subseteq\\{1,-1\\}^{n}$ and let
$f\colon\mathcal{X}\to\\{1,-1\\}$ be any partial Boolean function defined over
domain $\mathcal{X}$. If there exists a distribution $\mathcal{D}$ on
$\mathcal{X}$ such that $\mathbb{E}_{x\leftarrow\mathcal{D}}[f(x)\cdot
m(x)]=0$ for every monomial $m$ of degree less than $k$, then the threshold
degree of $f$ is at least $k$.

We are now ready to prove the main result of this section.

######  Theorem 5.2.

Let $\Pi\subseteq\\{1,-1\\}^{n}$ be a $k$-wise independent property such that
$\absolutevalue{\Pi}<2^{(1/4-H(\varepsilon))n}$ with $k=o(n)$. Then
$f\notin\mathcal{UPP}(k-1)$, where $f$ is the partial function such that
$f(x)=-1$ when $x\in\Pi$, $f(x)=1$ when $x$ is $\varepsilon$-far from $\Pi$,
and $f$ is undefined otherwise.

###### Proof.

First, apply Lemma 5 to obtain a $k$-wise independent code
$C\subseteq\\{0,1\\}^{n}$ that is $\varepsilon$-far from $\Pi$. Let
$\mathcal{D}$ be the distribution obtained by drawing a uniform random element
of $\Pi$ with probability $1/2$ and drawing a uniform random element of $C$
with probability $1/2$. Then for every monomial $m$ of degree less than $k$,

$\displaystyle\mathbb{E}_{x\leftarrow\mathcal{D}}[f(x)m(x)]$
$\displaystyle=\frac{\mathbb{E}_{x\leftarrow\Pi}[f(x)m(x)]+\mathbb{E}_{x\leftarrow
C}[f(x)m(x)]}{2}$
$\displaystyle=\frac{\mathbb{E}_{x\leftarrow\Pi}[m(x)]-\mathbb{E}_{x\leftarrow
C}[m(x)]}{2}=0.$

The final equality above holds by virtue of the $k$-wise independence of both
$\Pi$ and $C$. Let $\mathcal{X}$ be the union of inputs in $\Pi$ and inputs
that are $\varepsilon$-far from $\Pi$. Define the partial function $f$ over
domain $\mathcal{X}$ via:

$f(x)=\left\\{\begin{array}[]{cl}-1&\text{, if }x\in\Pi\\\ 1&\text{, if
}x\in\mathcal{X}\setminus\Pi.\end{array}\right.$

By Theorem 5.1, the distribution $\mathcal{D}$ constructed above witnesses the
fact that $\mathsf{thrdeg}(f)\geq k$. Since the $\mathcal{UPP}$ query
complexity of $f$ is $\mathsf{thrdeg}(f)$ by Lemma 6, the claim follows. ∎

We conclude the section with a corollary that follows from the inclusion
$\mathcal{QMA}\subseteq\mathcal{PP}$. The proof of this inclusion (in the
polynomial-time setting) proceeds in two steps: (1) reducing the error rate of
a QMA algorithm to roughly $2^{-p}$, where $p$ is the length of the proof
given to the verifier, by repeating the algorithm $O(p)$ times; and (2)
running the verifier with the proof fixed to be the maximally mixed state.
This exhibits a gap of roughly $2^{-p}$ between the acceptance probabilities
of yes- and no-inputs, which suffices to place the problem in $\mathcal{PP}$
[58, 77]. The same transformation, carried out _in the query model_ , implies
that any sufficiently small $\Pi\in\mathcal{QMAP}(\varepsilon,p,q)$ can be
“$\varepsilon$-tested” by a UPP algorithm with query complexity $O(pq)$; that
is, any function $f$ as in the statement of Theorem 5.2 is such that
$f\in\mathcal{UPP}(O(pq))$. Therefore,

######  Corollary 4.

For any sufficiently constant small $\varepsilon>0$ and $k$-wise independent
property $\Pi\subseteq\\{0,1\\}^{n}$ such that $\absolutevalue{\Pi}<2^{n/5}$,
we have $\Pi\notin\mathcal{QMAP}(\varepsilon,p,q)$ unless $pq=\Omega(k)$.

##  6 Quantum speedups for proximity-oblivious MAPs

We now shift gears and move to our _algorithmic_ results. We recall in this
section the technique of quantum _amplitude amplification_ , and prove its
consequences for the classes of algorithms we consider in this work. Roughly
speaking, given an algorithm that finds, with probability $\gamma$, a preimage
of 1 of a Boolean function, amplitude amplification allows us to repeat it
$O(1/\sqrt{\gamma})$ times in order to find such a preimage with high
probability (as opposed to $O(1/\gamma)$ repetitions classically). Formally,
we have:

######  Theorem 6.1 ([17]).

Let $v\colon S\to\\{0,1\\}$ be a Boolean function (from an arbitrary set $S$)
and let $A$ be a quantum algorithm that makes no intermediate measurements
(i.e., is a unitary transformation), such that measuring the state
$A\ket{\mathbf{0}}$ yields as outcome $s\in v^{-1}(1)$ with probability
$\gamma>0$. Then there exists a quantum algorithm $B$ that uses
$O(1/\sqrt{\gamma})$ applications of the unitaries $A$ and $A^{-1}$, such that
measuring $B\ket{\mathbf{0}}$ yields as outcome $s\in v^{-1}(1)$ with
probability $2/3$.

We note that the theorem applies to classical randomised algorithms as a
special case. An immediate corollary for _promise problems_ in the query model
(which is the setting for property testers, MAPs and variations thereof) is
the following.161616While we could state amplitude amplification for testers
directly, a subtle issue would arise: MAPs are equivalent to a collection of
_partial_ testers, which are not “vanilla” testers but are still promise
problems.

######  Corollary 5 (Amplitude amplification for promise problems in the query
model).

Let $Y,N\subseteq\\{0,1\\}^{n}$ with $Y\cap N=\varnothing$ define a promise
problem on $n$-bit strings whose yes- and no-inputs are $Y$ and $N$,
respectively. Let $A$ be a randomised algorithm with oracle access to a string
$x\in\\{0,1\\}^{n}$ that makes $q$ queries, always accepts when $x\in Y$ and
rejects with probability at least $\gamma$ when $x\in N$. Then, there exists a
quantum algorithm $B$ that makes $O(q/\sqrt{\gamma})$ queries to the unitary
$U_{x}\ket{i}\ket{b}=\ket{i}\ket{b\oplus x_{i}}$, always accepts when $x\in Y$
and rejects with probability $2/3$ when $x\in N$.

This follows from the observation that each $x\in Y\cup N$ induces a function
$f_{x}\colon\\{0,1\\}^{r}\to\\{0,1\\}$ where $r$ is the number of random bits
used by $A$. If $A^{x}$ accepts when the outcome of its random coin flips is
$s$, we define $f_{x}(s)=0$, and if $A^{x}$ rejects when its random string is
$s$, then $f_{x}(s)=1$. We then apply Theorem 6.1 to the algorithm $A^{x}$,
for each fixed $x\in Y\cup N$ (or, more precisely, to the modified algorithm
that computes $f_{x}$ written as a reversible circuit and thus implements a
query to $x$ as $(i,b)\mapsto(i,b\oplus x_{i})$), obtaining $B^{U_{x}}$
(recall that $U_{x}$ is the unitary mapping
$\ket{i}\ket{b}\mapsto\ket{i}\ket{b\oplus x_{i}}$). Measuring
$B^{U_{x}}\ket{\mathbf{0}}$, using the outcome as the random string for an
execution of $A^{x}$ and outputting accordingly yields the claimed algorithm.

Note that Corollary 5 directly applies to _one-sided proximity-oblivious_
testers, which are testers that always accept $n$-bit strings in the property
and reject strings that are $\varepsilon$-far from it with _detection
probability_ $\rho(\varepsilon,n)$. We now prove the following observation,
which shows that the same speedup can be obtained for MAPs; more precisely,
properties that admit one-sided proximity-oblivious MAPs allow for more
efficient verification by a quantum algorithm using the same proof string.

######  Theorem 6.2.

Let $\Pi$ be a property admitting a one-sided proximity-oblivious MAP
protocol, which receives a proof of length $p=p(n)$, makes $q=q(n)$ queries
and rejects strings $\varepsilon$-far from $\Pi$ with probability at least
$\rho=\rho(\varepsilon,n)$. Then, for any $\varepsilon\in(0,1)$,

$\Pi\in\mathcal{QCMAP}\left(\varepsilon,p,\frac{q}{\sqrt{\rho}}\right)\;.$

###### Proof.

Observe that the MAP verifier $V$ can be equivalently described as a
collection of probabilistic algorithms
$\left\\{V_{\pi}:\pi\in\\{0,1\\}^{p}\right\\}$ indexed by all proof strings
$\pi$. By definition, for every $x\in\Pi$ there exists $\pi\in\\{0,1\\}^{p}$
such that $V^{x}_{\pi}$ always accepts; and, for every $x$ that is
$\varepsilon$-far from $\Pi$, every proof string $\pi$ is such that
$V^{x}_{\pi}$ rejects with probability at least $\rho$. Therefore, $V_{\pi}$
solves the promise problem whose yes-inputs comprise the subset of $\Pi$ for
which $\pi$ is a valid proof, and whose no-inputs are the strings
$\varepsilon$-far from $\Pi$.

Let $W_{\pi}$ be the algorithm obtained from $V_{\pi}$ by Corollary 5. Then
$W^{x}_{\pi}$ accepts (with probability 1) when $x\in\Pi$ and $\pi$ is a valid
proof for $x$, and $W^{x}_{\pi}$ rejects (with probability $2/3$) when $x$ is
$\varepsilon$-far from $\Pi$ and $\pi$ is any proof string; in other words,
the algorithm $W$ that executes $W_{\pi}$ when it receives $\pi$ as a proof
string is a QCMAP verifier for $\Pi$. Moreover, since the proof string is
reused and $W$ makes $O(q/\sqrt{\rho})$ queries, the proof and query
complexities are as stated. ∎

We conclude with two applications of Theorem 6.2: to _read-once branching
programs_ (ROBPs) and _context-free languages_ (CFLs), which are shown to
admit proximity-oblivious MAPs in [41] (see Remark 4 for details on these
results).

######  Theorem 6.3 ([41], Lemma 3.1).

For every read-once branching program on $n$ variables of size $s=s(n)$, let
$A_{B}\coloneqq\left\\{x\in\\{0,1\\}^{n}:B(x)=1\right\\}$ be the set of
strings accepted by $B$. Then, for every $k\leq n$, the property $\Pi_{B}$
admits a one-sided proximity-oblivious MAP with communication complexity
$O(k\log s)$, query complexity $n/k$ and detection probability
$\rho(\varepsilon,n)=\varepsilon$.

######  Theorem 6.4 ([41], Lemma 4.5).

For every $k\leq n$, every context-free language $L$ admits a one-sided
proximity-oblivious MAP with communication complexity $O(k\log n)$, query
complexity $n/k$ and detection probability $\rho(\varepsilon,n)=\varepsilon$.

Therefore, applying Theorem 6.2 to Theorems 6.3 and 6.4, we obtain:

######  Corollary 6.

For every read-once branching program $B$ on $n$ variables of size $s=s(n)$,
denote by $A_{B}\coloneqq\left\\{x\in\\{0,1\\}^{n}:B(x)=1\right\\}$ the set of
strings accepted by $B$. Then

$A_{B}\in\mathcal{QCMAP}\left(\varepsilon,O(k\log
s),O\left(\frac{n}{k\sqrt{\varepsilon}}\right)\right)\quad\text{for every
}k\leq n\text{ and }\varepsilon\in(0,1).$

######  Corollary 7.

For every context-free language $L$,

$L\in\mathcal{QCMAP}\left(\varepsilon,O(k\log
n),O\left(\frac{n}{k\sqrt{\varepsilon}}\right)\right)\quad\text{for every
}k\leq n\text{ and }\varepsilon\in(0,1).$

Interestingly, these corollaries make explicit a phenomenon in quantum proofs
of proximity that does not hold for their classical counterparts: it is
possible to test with proximity $\varepsilon=1/n$, i.e., solve the _exact
decision_ problem of acceptance by an ROBP and membership in a context-free
language, with sublinear proof and query complexity. In particular, taking
$k=n^{3/4}$, both complexities are $O(n^{3/4})$. Nonetheless, for the case of
branching programs, we will show in Section 7.3 how to lift the read-once
restriction and improve on the parameters by directly exploiting
_decomposability_.

######  Remark 4.

We note that a context-free language $L$ is defined in terms of an alphabet of
_terminals_ (which is generally larger than $\\{0,1\\}$) as well as an
alphabet of variables. However, if both alphabets have constant size, we may
represent symbols as bit strings with a constant overhead per query; thus
Corollary 7 holds for languages over large (constant-size) alphabets.

Moreover, the results of [41] corresponding to Corollaries 6 and 7 are in fact
stronger: both apply more generally to IPPs, and thus to MAPs as a special
case (see [41, Section 3.2] for details). In addition, the detection
probability of the MAP for ROBPs is $\varepsilon n/n^{\prime}$ if the
branching program has an accepting path of length $n^{\prime}\leq n$; and the
MAP for context-free languages works for _partial derivation languages_ , a
generalisation of CFLs whose strings may include variable symbols as well as
terminals.

##  7 Decomposable properties

In this section, we show how quantum speedups can be applied to proof of
proximity protocols for properties that can be broken up into sub-problems in
a distance-preserving manner. Roughly speaking, a property $\Pi$ of $n$-bit
strings is _$(k,s)$ -decomposable_ if, using $s$ bits of information (which we
call a _specification_), $\Pi$ can be mapped to $k$ properties
$\left\\{\Lambda^{(i)}\right\\}$ and the input string $x$ can be mapped to a
set of $k$ strings $\left\\{x^{(i)}\right\\}$ satisfying the following
conditions: (1) when $x\in\Pi$, there exists a specification such that
$x^{(i)}\in\Lambda^{(i)}$ for all $i\in[k]$; and (2) when $x$ is
$\varepsilon$-far from $\Pi$, then, for some specification, $x^{(i)}$ is
roughly $\varepsilon$-far from $\Lambda^{(i)}$ for an average $i\in[k]$.

######  Definition 9 (Decomposable property).

Let $\Pi=\bigcup\Pi_{n}$ be a property of bit strings. For $k=k(n)$, $s=s(n)$,
$m_{1}=m_{1}(n),\ldots,m_{k}=m_{k}(n)$, we say $\Pi$ is _$(k,s)$
-decomposable_ if there exists a mapping from $S\subseteq\\{0,1\\}^{s}$ to
(possibly distinct) subproperties
$\Lambda^{(1)}\subset\\{0,1\\}^{m_{1}},\ldots,\Lambda^{(k)}\subset\\{0,1\\}^{m_{k}}$
such that every $x\in\\{0,1\\}^{n}$ uniquely determines
$x^{(i)}\in\\{0,1\\}^{m_{i}}$ satisfying:171717We remark that the mappings
$\Pi\mapsto(\Lambda^{(1)},\Lambda^{(2)},\ldots,\Lambda^{(k)})$ and
$x\mapsto(x^{(1)},x^{(2)},\ldots,x^{(k)})$ are functions of the specification
$y\in S$ of the decomposition. Although the notation $x^{(i),y}$ and
$\Lambda^{(i),y}$ is formally more accurate, the dependency on $y$ will be
clear from context and we omit it for ease of notation.

  1. 1.

If $x\in\Pi$, then there exists $y\in S$ such that $x^{(i)}\in\Lambda^{(i)}$
for all $i\in[k]$; and

  2. 2.

If $x$ is $\varepsilon$-far from $\Pi$, then, for all $y\in S$ and $i\in[k]$,
the string $x^{(i)}$ is $\varepsilon_{i}$-far from $\Lambda^{(i)}$ and
$\mathbb{E}_{i\leftarrow\mathcal{D}}[\varepsilon_{i}]=\Omega(\varepsilon)$,
where $\mathcal{D}$ is the distribution over $[k]$ with probability mass
$m_{i}/(\sum_{j\in[k]}m_{j})$ on $i$.

If $s=O(k\log n)$ we say $\Pi$ is _succinclty_ $k$-decomposable. If the
strings $x^{(i)}$ form a partition of $x$, we say $\Pi$ is
$(k,s)$-_partitionable_.

Note that $k$-decompositions specified by $O(k)$ coordinates of the input
string are succinct. All of our applications are to succincly decomposable
properties, and often the $\left\\{x^{(i)}\right\\}$ form an equipartition of
$x$ (so each bit of $x^{(i)}$ depends on a single bit of $x$) and
$\mathcal{D}$ is thus the uniform distribution. However, note that if a
decomposition is significantly asymmetric, then $\mathcal{D}$ preserves
(average) distance while uniform sampling may deteriorate it to
$o(\varepsilon)$ (e.g., if $m_{i}=o(m_{1})$ when $i>1$ and $x^{(1)}$
concentrates all of the corruption).

While the second condition of Definition 9 requires the expectation lower
bound to hold for arbitrary $\varepsilon$, the definition is still meaningful
when it holds only for restricted values of $\varepsilon$. Indeed, we will
make use of it for _exact decision_ problems in Section 7.3, where the only
proximity parameter we consider is $\varepsilon=1/n$; we call such properties
decomposable (or partitionable) with respect to exact decision.

As we will see in the next sections, decomposable properties enable the
construction of efficient proof of proximity protocols and generalise the
notion of “parametrised concatenation properties” introduced by [46].

###  7.1 Boosting decompositions via amplitude amplification

As the next theorem shows, decomposable properties allow for quantum speedups
regardless of whether they admit proximity-oblivious MAPs.

######  Theorem 7.1.

Let $\Pi$ be a property that is $(k,s)$-decomposable into properties of
$m_{i}$-bit strings, and set $m=\max_{i\in[k]}\left\\{m_{i}\right\\}$. Suppose
each bit of $x^{(i)}$ can be determined by reading $b$ bits of the input
string, and each $\Lambda^{(i)}$ admits a one-sided MAP with proximity
parameter $\varepsilon$, query complexity
$q=q(m,\varepsilon)=m^{\alpha}/\varepsilon^{\beta}$ and proof complexity
$p=p(m,\varepsilon)$. Then

$\Pi\in\mathcal{QCMAP}(\varepsilon,s+kp,q^{\prime})\;,$

with

$q^{\prime}=\begin{cases}\tilde{O}\left(b\cdot
m^{\alpha}\cdot\varepsilon^{-\max\left(\frac{1}{2},\beta\right)}\right)&\text{if
}\alpha>0\text{ and }\beta\geq 0\\\
\tilde{O}\left(b\cdot\min\left\\{m^{1-\frac{1}{2\beta}}/\sqrt{\varepsilon},\leavevmode\nobreak\
m^{1-\frac{1}{\beta}}/\varepsilon\right\\}\right)&\text{if }\alpha=0\text{ and
}\beta\geq 1,\end{cases}$

where $\tilde{O}$ hides polylogarithmic factors in $1/\varepsilon$ (but not
$m$). Moreover, for _exact decision_ (i.e., testing with proximity
$\varepsilon=1/n$), a proof of length $s$ and $O(bm\sqrt{k})$ queries suffice.

Before proceeding to the proof, we note that if the MAP protocols for the
subproperties are proximity-oblivious, the query complexity can be improved
(see Remark 5). Let us also summarise the proof strategy of [46], which we
build upon and generalise.

Consider the special case where a property $\Pi$ is _$k$ -partitionable_ and
the strings $x^{(i)}$ are simply the substrings of $x$ of length $m=n/k$
which, concatenated, form $x$. Suppose, moreover, that the subproperties
$\Lambda^{(i)}$ admit _testers_ with query complexity
$q=m^{\alpha}/\varepsilon^{\beta}$ and that $\Pi$ is the union of
$\Lambda^{(1)}\times\Lambda^{(2)}\times\cdots\Lambda^{(k)}$ (over all strings
in $S$). Note that while, in general, a specification must show how to obtain
$\Lambda^{(i)}$ from $\Pi$ _and_ how to obtain $x^{(i)}$ from $x$, for an
equipartition the latter is implicit.

A natural candidate for a (classical) MAP protocol for $\Pi$ is to guess an
index $i\in[k]$ and run the tester for $\Lambda^{(i)}$ on $x^{(i)}$. If
$x\in\Pi$, then $x^{(i)}\in\Lambda^{(i)}$ for $i\in[k]$ and the tester always
accepts; while if $x$ is $\varepsilon$-far from $\Pi$, then $x^{(i)}$ is
$\varepsilon_{i}$-far from $\Lambda^{(i)}$ for some $\varepsilon_{i}$
satisfying $\frac{1}{k}\sum_{i}\varepsilon_{i}\geq\varepsilon$, _regardless of
the specification_ (recall that $x$ is $\varepsilon$-far from $\bigcup_{y\in
S}\Lambda^{(1)}\times\Lambda^{(2)}\times\cdots\Lambda^{(k)}$).

We now proceed to the proof of the general case, where the decomposition need
not be a partition, and it suffices for the subproperties to admit a MAP
(rather than a tester). Moreover, we show that quantum algorithms enable a
speedup via amplitude amplification (but this requires the MAPs to be _one-
sided_ , unlike in the classical case).

###### Proof.

Recall that we have a property $\Pi$ that is $(k,s)$-decomposable by a
collection of strings $S\subseteq\\{0,1\\}^{s}$, where each $y\in S$
determines $k$ properties $\Lambda^{(i)}\subseteq\\{0,1\\}^{m_{i}}$ and a
decomposition of $x$ into $k$ strings $x^{(i)}\in\\{0,1\\}^{m_{i}}$. Moreover,
each $\Lambda^{(i)}$ admits a MAP with proof complexity $p$ and query
complexity $m^{\alpha}/\varepsilon^{\beta}$. The verifier for $\Pi$ executes
the steps shown in Figure 3.

We note that a more naive strategy would succeed, albeit with a worse
dependence on $\varepsilon$: choosing $i\in[k]$ with probability proportional
to $m_{i}$ yields a string $x^{(i)}$ which is $\varepsilon/2$-far from
$\Lambda^{(i)}$ with probability at least $\varepsilon/2$, so that one could
execute the MAP verifier for $\Lambda^{(i)}$ with proximity parameter
$\varepsilon/2$ (and use amplitude amplification to achieve constant soundness
by repeating this $O(1/\sqrt{\varepsilon})$ times). However, the technique of
_precision sampling_ [55] overcomes the issue of not knowing the distances
$\varepsilon_{i}$ between $x^{(i)}$ and $\Lambda^{(i)}$ more economically:
trying every proximity parameter $2^{j}$ with $j\in[O(\log 1/\varepsilon)]$,
in the spirit of binary search, incurs a merely logarithmic overhead.

Input: explicit access to a proximity parameter $\varepsilon>0$ and a proof
string $\pi\in\\{0,1\\}^{s+kp}$, and oracle access to a string
$x\in\\{0,1\\}^{n}$. 1. Interpret the proof as a concatenation of a string
$y\in\\{0,1\\}^{s}$ with $k$ strings $\pi_{1},\ldots,\pi_{k}\in\\{0,1\\}^{p}$.
If $y\notin S$, i.e., $y$ does not specify a decomposition, then reject. 2.
For every $j\in[\lceil\log 1/\varepsilon\rceil+1]$, let $M_{j}$ be the
algorithm obtained from Corollary 5 by performing $O\left(\sqrt{\frac{\log
1/\varepsilon}{2^{j}\varepsilon}}\right)$ rounds of amplitude amplification to
the following subroutine: (2(a)) Sample $i\in[k]$ with probability
$m_{i}/\sum_{j\in[k]}m_{j}$ and run the MAP verifier for $\Lambda^{(i)}$ on
input $x^{(i)}$, with proximity parameter $2^{-j}$, using $\pi_{i}$ as the
proof string. Reject if the MAP for $\Lambda^{(i)}$ rejects. 3. Execute
$M_{j}$ for every $j\in[O(\log 1/\varepsilon)]$. If any of them rejects, then
reject; otherwise, accept.

Figure 3: QCMAP verifier for a $(k,s)$-decomposable property $\Pi$

Completeness follows immediately: if $x\in\Pi$, then there exists a string
$y\in S$ such that $x$ determines $x^{(i)}\in\Lambda^{(i)}$ for all $i\in[k]$.
Since the properties $\Lambda^{(i)}$ admit one-sided MAP protocols with proof
complexity $p$, the procedure in Item 22(a) always accepts when given the
proof string $\pi=(y,\pi_{1},\ldots,\pi_{k})$, where $\pi_{i}$ is a valid
proof for $x^{(i)}$. Therefore, the verifier always accepts as well.

Now, suppose $x$ is $\varepsilon$-far from $\Pi$ and the proof string
$\pi=(y,\pi_{1},\ldots,\pi_{n})$ is such that $y\in S$ (since otherwise the
verifier rejects immediately). Then, since $\Pi$ is decomposable, $x^{(i)}$ is
$\varepsilon_{i}$-far from $\Lambda^{(i)}$ and
$\mathbb{E}_{i\leftarrow\mathcal{D}}[\varepsilon_{i}]=\Omega(\varepsilon)$,
where $\Lambda^{(i)}$ are the subproperties defined by $y$ and $\mathcal{D}$
is the distribution over $[k]$ that samples $i$ with probability proportional
to $m_{i}$.

To show soundness, we will make use of the following (precision sampling)
lemma.

######  Lemma 7 ([34, Fact A.1]).

There exists
$j\in\left[\left\lceil\log\frac{1}{\varepsilon}\right\rceil+1\right]$ such
that

$\mathbb{P}_{i\leftarrow\mathcal{D}}[\varepsilon_{i}\geq
2^{-j}]=\Omega\left(\frac{2^{j}\varepsilon}{\log 1/\varepsilon}\right)\;.$

If the procedure in Item 22(a) samples $i\in[k]$ such that
$\varepsilon_{i}\geq 2^{-j}$, then it rejects with probability $2/3$ (since
the MAP has soundness $2/3$). With $j$ as ensured by Lemma 7, the probability
it samples such an $i\in[k]$ is $\Omega\left(\frac{2^{j}\varepsilon}{\log
1/\varepsilon}\right)$, so that the probability it rejects is
$\frac{2}{3}\cdot\Omega\left(\frac{2^{j}\varepsilon}{\log
1/\varepsilon}\right)=\Omega\left(\frac{2^{j}\varepsilon}{\log
1/\varepsilon}\right)$; therefore, the algorithm $M_{j}$ obtained from
Corollary 5 by $O\left(\sqrt{\frac{\log
1/\varepsilon}{2^{j}\varepsilon}}\right)$ rounds of amplitude amplification
rejects, causing the verifier to also reject, with probability $2/3$.

We now prove the stated upper bounds on the query complexity. For every $j$,
each execution of the MAP verifier for $\Lambda^{(i)}$ makes $q(m,2^{-j})$
queries to $x^{(i)}$, which translate into $b\cdot q(m,2^{-j})$ queries to $x$
(since each query to $x^{(i)}$ can be emulated with $b$ queries to $x$). The
total query complexity is therefore

$\sum_{j\in[\lceil\log{1/\varepsilon}\rceil+1]}\sqrt{\frac{\log
1/\varepsilon}{2^{j}\varepsilon}}\cdot b\cdot
q\left(m,2^{-j}\right)=\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log{1/\varepsilon}\rceil+1]}\frac{q\left(m,2^{-j}\right)}{2^{j/2}}\right)\;.$

If $q(m,\varepsilon)=m^{\alpha}/\varepsilon^{\beta}$ with $\alpha>0$ and
$\beta\geq 0$, then

$\displaystyle\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log{1/\varepsilon}\rceil+1]}\frac{q\left(m,2^{-j}\right)}{2^{j/2}}\right)$
$\displaystyle=\tilde{O}\left(\frac{bm^{\alpha}}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}2^{j\left(\beta-\frac{1}{2}\right)}\right)$
$\displaystyle=\tilde{O}\left(bm^{\alpha}\varepsilon^{-\max(1/2,\beta)}\right)\;.$

If $\alpha=0$ and $\beta>0$, we use the bound $q(m,2^{-j})\leq m$ for all
$\varepsilon$ (from the trivial tester that queries the entire input) to
obtain two upper bounds for the query complexity: the first is

$\displaystyle\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}\frac{q\left(m,2^{-j}\right)}{2^{j/2}}\right)$
$\displaystyle=\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}\min\left\\{\frac{m}{2^{j/2}},2^{j\left(\beta-\frac{1}{2}\right)}\right\\}\right)$
$\displaystyle=\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}m^{1-\frac{1}{2\beta}}\right)$
$\displaystyle=\tilde{O}\left(\frac{bm^{1-\frac{1}{2\beta}}}{\sqrt{\varepsilon}}\right)\;.$

The second upper bound matches that obtained by the classical MAP, and is
tighter when $m^{\frac{1}{2\beta}}\geq 1/\sqrt{\varepsilon}$. Since
$2^{j/2}\leq 4/\sqrt{\varepsilon}$ for all $j$ in the sum above, we have
$\sqrt{\varepsilon}=O(2^{-j/2})$; therefore,

$\displaystyle\tilde{O}\left(\frac{b}{\sqrt{\varepsilon}}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}\frac{q\left(m,2^{-j}\right)}{2^{j/2}}\right)$
$\displaystyle=\tilde{O}\left(\frac{b}{\varepsilon}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}\frac{\sqrt{\varepsilon}}{2^{j/2}}\cdot
q\left(m,2^{-j}\right)\right)$
$\displaystyle=\tilde{O}\left(\frac{b}{\varepsilon}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}\min\left\\{\frac{m}{2^{j}},2^{j(\beta-1)}\right\\}\right)$
$\displaystyle=\tilde{O}\left(\frac{b}{\varepsilon}\sum_{j\in[\lceil\log(1/\varepsilon)\rceil+1]}m^{1-\frac{1}{\beta}}\right)$
$\displaystyle=\tilde{O}\left(\frac{bm^{1-\frac{1}{\beta}}}{\varepsilon}\right)\;.$

Finally, observe that, for testing with $\varepsilon=1/n$ (i.e., deciding
exactly), one may take the MAPs for $\Lambda^{(i)}$ to be the trivial testers
(with query complexity $m$ and no proof). Moreover, it is unnecessary to
iterate over $j$ and apply Lemma 7; sampling $i\in[k]$ uniformly and running
the trivial tester requires $bm$ queries to $x$ and leads to a rejection with
probability at least $1/k$, since $\frac{1}{k}\sum_{i\in[k]}\varepsilon_{i}>0$
implies $x^{(i)}\notin\Lambda^{(i)}$ for at least one $i\in[k]$. Therefore,
applying $O(\sqrt{k})$ rounds of amplitude amplification to this procedure
ensures rejection of an $x$ that is $\varepsilon$-far from $\Pi$ with constant
probability and yields query complexity $O(bm\sqrt{k})$. ∎

######  Remark 5 (Additional speedup for proximity-oblivious MAPs).

If the MAP verifiers for the subproperties $\Lambda^{(i)}$ are proximity-
oblivious, it is possible to improve on the query complexity of Theorem 7.1
significantly. More precisely, suppose each $\Lambda^{(i)}$ admits a
proximity-oblivious MAP with query complexity $O(1)$ and detection probability
$\rho(\varepsilon,m)=\varepsilon^{\beta}/m^{\alpha}$. Then, if an input is
$\varepsilon$-far from $\Pi$, for some $j\in[O(\log 1/\varepsilon)]$ (as
ensured by Lemma 7), the procedure of Item 22(a) samples $i\in[k]$ such that
$x^{(i)}$ is $\varepsilon_{i}$-far from $\Lambda^{(i)}$ with
$\varepsilon_{i}=\tilde{\Omega}(2^{j}\varepsilon)$.

The procedure thus rejects with probability
$\tilde{\Omega}(2^{j}\varepsilon)\cdot\rho(2^{-j},m)=\tilde{\Omega}(2^{j(1-\beta)}\varepsilon/m^{\alpha})$
in this case. By applying
$\tilde{O}(m^{\alpha/2}/\sqrt{2^{-j(\beta-1)}\varepsilon})$ rounds of
amplitude amplification for each $j$ (instead of
$\tilde{O}(1/\sqrt{2^{j}\varepsilon})$ performed for MAPs that are not
proximity-oblivious), and, since $2^{-j}=\Omega(\varepsilon)$, the total query
complexity becomes $\tilde{O}(b\sqrt{m^{\alpha}/\varepsilon^{\beta}})$.

We finish this section with a corollary of Theorem 7.1 in the _graph
orientation model_. A directed graph is called _Eulerian_ if the in-degree of
each of its vertices is equal to its out-degree. An orientation is a mapping
from the edges to $\\{0,1\\}$, representing whether each edge is oriented from
$i$ to $j$ or from $j$ to $i$, and the distance between two orientations is
the fraction of edges whose orientation must be changed to transform one into
the other. Let $\Pi_{E}$ be the property consisting of all Eulerian
orientations of the complete bipartite graph $K_{2,n-2}$, i.e., the graph with
vertex set $[n]$ and edge set $\left\\{\left\\{i,j\right\\}:i\leq 2,j\geq
3\right\\}$.

A MAP protocol for $\Pi_{E}$ parametrised by an integer $k$ is constructed in
[46]; its proof and query complexities are $O(k\cdot\log{n})$ and
$\tilde{O}(n/(\varepsilon k))$, respectively. That protocol is obtained by
applying their (classical) version of Theorem 7.1 using the trivial tester for
each of the subproperties. Using the same proof (and thus the same
decomposition), and recalling that the trivial tester makes
$q(m,\varepsilon)=m$ queries for a sub-property of length $m$, we obtain

######  Corollary 8.

The property $\Pi_{E}$ has a one-sided QCMAP, with respect to proximity
parameter $\varepsilon$, that uses a proof of length $O(k\cdot\log{n})$ and
has query complexity $\tilde{O}\left(\frac{n}{k\sqrt{\varepsilon}}\right)$.

Note that the query complexity of the classical MAP becomes linear with
$\varepsilon=\Omega(1/k)$, whereas the QCMAP is able to decide _exactly_ (i.e.
test with $\varepsilon=1/n$) with query complexity $O(n^{3/2}/k)$ (which is
still sublinear whenever $k=\omega(\sqrt{n})$). In particular, with
$k=n^{3/4}$, both query and communication complexities are
$\tilde{O}(n^{3/4})$; see the Section 7.3 for further discussion and
applications of Theorem 7.1 to exact decision problems.

###  7.2 $k$-monotonicity

In this section, we show that a generalisation of monotonicity of Boolean
functions over the line $[n]$ is efficiently testable by QCMAP protocols. A
function $f:[n]\to\\{0,1\\}$ is _$k$ -monotone_ if any sequence of integers
$1\leq x_{1}<x_{2}\ldots<x_{\ell}\leq n$ such that $f(x_{1})=1$ and
$f(x_{i})\neq f(x_{i+1})$ for all $i<\ell$ has length $\ell\leq k$. This
problem was studied in [20], where one-sided $\varepsilon$-testers for
$k$-monotonicity on the line are shown to require $\Omega(k/\varepsilon)$
queries, while two-sided testers can achieve query complexity
$\tilde{O}(1/\varepsilon^{7})$ (which, although a far worse dependence on