$\varepsilon$ than the lower bound, is _independent_ of $k$).

In order to apply Theorem 7.1, we must only show that $k$-monotone functions
are decomposable. Define $\Pi_{k,[n]}$ as the set of $k$-monotone Boolean
functions on the line $[n]$.181818We consider the standard representation of a
Boolean function as the bit string obtained by concatenating all function
evaluations, i.e., $f\colon[n]\to\\{0,1\\}$ is represented by
$x\in\\{0,1\\}^{n}$ with $x_{i}=f(i)$. Then,

######  Theorem 7.2.

For any $k\in[n]$, the property $\Pi_{k,[n]}$ is succinctly $k$-decomposable.

###### Proof.

Since a $k$-monotone function $f$ has at most $k-1$ critical points, where it
changes from nondecreasing to nonincreasing or vice-versa, specifying these
points yields a decomposition of $f$ into (1-)monotone subfunctions.

More precisely, a string of length $s\leq(k-1)\log n$ determines a
decomposition of the input $f$ by specifying $\ell\leq k-1$ integers
$1<n_{1}<n_{2}<\cdots<n_{\ell}<n$. Define $n_{0}=1$, $n_{\ell+1}=n$,
$m_{i}\coloneqq n_{i}-n_{i-1}+1$ and the function $f_{i}:[m_{i}]\to\\{0,1\\}$
by $f_{i}(x)=f(x+n_{i-1}-1)$ for all $i\in[\ell+1]$. Then, $f\in\Pi_{k,[n]}$
if and only if:

  1. 1.

for $i\in[\ell+1]$ odd,
$f_{i}\in\Lambda^{(i)}\coloneqq\left\\{g\in\Pi_{1,m_{i}}:g(1)=f_{i}(1)\right\\}$;
and

  2. 2.

for $i\in[\ell+1]$ even,
$f_{i}\in\Lambda^{(i)}\coloneqq\left\\{1-g:g\in\Pi_{1,m_{i}}\text{ and
}g(1)=1-f_{i}(1)\right\\}$.

It is clear that, when $f\in\Pi_{k,[n]}$, there exists a set of $\ell\leq k-1$
distinct integers in $[2,n-1]$ that satisfies both conditions. When $f$ is
$\varepsilon$-far from $\Pi_{k,[n]}$, the sum of absolute distances
$\varepsilon_{i}m_{i}$ from each $f_{i}$ to $\Lambda^{(i)}$ is
$\sum_{i}\varepsilon_{i}m_{i}\geq\varepsilon n$. Therefore,

$\mathbb{E}_{i\leftarrow\mathcal{D}}[\varepsilon_{i}]\geq\varepsilon\cdot\frac{n}{\sum_{i\in[\ell+1]}m_{i}}=\varepsilon\cdot\frac{n}{n+\ell}=\Omega(\varepsilon)\;,$

where $\mathcal{D}$ is the distribution over $[\ell+1]$ that has probability
mass $m_{i}/(\sum_{j\in[\ell+1]}m_{j})$ at point $i$.

Finally, while this ensures $(\ell+1)$-decomposability for some $\ell\leq
k-1$, one may deterministically transform it into a $k$-decomposition (and, in
fact, a $K$-decomposition for any $K\geq\ell$) by, for example, iteratively
finding the largest interval and dividing it at its midpoint $k-\ell-1$ times
(with the requirement that nonincreasing functions in the large interval are
monotone nonincreasing in both subintervals, and likewise for the
nondecreasing case). ∎

Since monotonicity on the line $[m]$ is $\varepsilon$-testable with
$q(m,\varepsilon)=O(1/\varepsilon)$ queries [35, Proposition 1.5], applying
(the second case of) Theorem 7.1 yields Corollary 1: a QCMAP protocol for
$k$-monotonicity with proof complexity $O(k\log n)$ and query complexity
$\tilde{O}(1/\varepsilon)$ exists. (The theorem also gives an upper bound of
$\tilde{O}(\sqrt{n/\varepsilon})$, which is no better:
$\tilde{O}(1/\varepsilon)$ is smaller up to $\varepsilon\approx 1/n$, where
the two bounds match.)

It is worth noting that the standard monotonicity tester on the line is _not_
proximity-oblivious, unlike, e.g., on the Boolean hypercube, where both the
“edge tester” [40] and the state-of-the-art [54] are proximity-oblivious;
thus, one could not directly apply amplitude amplification, and must exploit
decomposability via Theorem 7.1.

Note that the (one-sided) QCMAP for $k$-monotonicity is more efficient than
any one-sided tester, e.g., when $k=\Theta(\log n)$ and
$\varepsilon=\Theta(1/\log^{2}n)$: then the QCMAP’s proof and query
complexities are $\tilde{O}(\log^{2}n)$, whereas one-sided testers must make
$\Omega(\log^{3}n)$ queries. Moreover, our QCMAP outperforms the best known
_two-sided_ tester of [20], which makes $\tilde{O}(1/\varepsilon^{7})$
queries, even with mild dependencies of the proximity parameter $\varepsilon$
on $n$. Indeed, when $\varepsilon=o(1/\log^{1/7}n)$ and $k=O(1)$, the tester’s
query complexity is superlogarithmic while the proof and query complexities of
the QCMAP are logarithmic.

With the transformation from two-sided testers to one-sided MAPs of [46], it
is also possible to compare our one-sided QCMAP against one-sided MAPs. From
the aforementioned two-sided tester, one obtains a MAP with proof complexity
$\operatorname{polylog}n$ and query complexity
$O(\operatorname{polylog}(n/\varepsilon)/\varepsilon^{7})$. Thus, the QCMAP
remains advantageous except when $k$ and $\varepsilon$ are large (e.g.,
$k=\omega(\operatorname{polylog}n)$ and $\varepsilon=\Omega(1)$).

###  7.3 Exact problems

To conclude the discussion of decomposability and its consequences, we shift
focus to a special case: that of testing $n$-bit strings with proximity
parameter $\varepsilon=1/n$. Since, for any $\Pi\subseteq\\{0,1\\}^{n}$ and
$x\in\\{0,1\\}^{n}\setminus\Pi$, the string $x$ is at least $1/n$-far from
$\Pi$, this is the task of _exactly_ deciding membership in $\Pi$.

Observe that for classical MAPs, nontrivial properties require $\Omega(n)$
queries in this case: even if a verifier receives as proof a claim
$x^{\prime}$ that is allegedly equal to its input string, it requires
$O(1/\varepsilon)=\Omega(n)$ queries to check the validity of the claim.
Remarkably, _quantum_ algorithms are able to solve exact decision problems
with sublinear queries (as illustrated by Grover’s algorithm, which makes
$O(\sqrt{n})$ queries). Thus, as we show next, insights arising from
decomposability are applicable to this setting. We begin by showing a
nontrivial QCMA protocol for the parity of a bit string in Section 7.3.1, and
then extend it to _branching programs_ in Section 7.3.2.

####  7.3.1 Parity

Consider the problem of deciding if an $n$-bit string has even parity. This is
clearly maximally hard, requiring $\Omega(n)$ queries even for _interactive
proofs with arbitrary communication_ , which we show next for completeness.

######  Lemma 8.

Any IP verifier that accepts strings of even parity and rejects strings of odd
parity with probability $2/3$ must make at least $n/3$ queries to its input.

###### Proof.

Let $V$ and $P$ be a verifier and an honest prover for an IP for parity, and
assume, towards contradiction, that the query complexity of $V$ is less than
$n/3$.

Fix an arbitrary input $x\in\\{0,1\\}^{n}$ of even parity. Define $S_{x}$ as
the random variable comprising all the coordinates queried by $V$ in an
execution $\langle V^{x},P(x)\rangle$ of the protocol, and let $I\in[n]$ be a
uniform random variable independent from $S_{x}$. Then, since
$\absolutevalue{S_{x}}<n/3$,

$\frac{1}{n}\sum_{i=1}^{n}\mathbb{P}[i\in
S_{x}]=\sum_{i=1}^{n}\mathbb{P}[I=i]\cdot\mathbb{P}[I\in
S_{x}\leavevmode\nobreak\ |\leavevmode\nobreak\ I=i]=\mathbb{P}[I\in
S_{x}]<\frac{1}{3}\;,$

so there exists $i\in[n]$ such that

$\mathbb{P}[V^{x}\text{ queries }i\text{ in the execution }\langle
V^{x},P(x)\rangle]=\mathbb{P}[i\in S_{x}]<\frac{1}{3}\;.$

Now, consider the execution of a protocol on input $y\in\\{0,1\\}^{n}$
obtained by flipping the $i^{\text{th}}$ bit of $x$ (i.e., such that
$y_{j}=x_{j}$ if $j\neq i$ and $y_{i}=1-x_{i}$ otherwise). Let $\tilde{P}$ be
a (malicious) prover that executes on $y$ exactly as $P$ does on $x$; that is,
set $\tilde{P}(y)=P(x)$. We thus have

$\displaystyle\mathbb{P}[\langle V^{y},\tilde{P}(y)\rangle\text{ rejects}]$
$\displaystyle=\mathbb{P}[i\in S_{y}]\cdot\mathbb{P}[\langle
V^{y},\tilde{P}(y)\rangle\text{ rejects}\leavevmode\nobreak\
|\leavevmode\nobreak\ i\in S_{y}]$ $\displaystyle+\mathbb{P}[i\notin
S_{y}]\cdot\mathbb{P}[\langle V^{y},\tilde{P}(y)\rangle\text{
rejects}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\notin S_{y}]\;,$

and, moreover, the following equalities between events hold:

$\displaystyle[i\notin S_{y}]$ $\displaystyle=[i\notin S_{x}]\;,\text{ and
thus}$ $\displaystyle[\langle V^{y},\tilde{P}(y)\rangle\text{
rejects}\leavevmode\nobreak\ |\leavevmode\nobreak\ i\notin S_{y}]$
$\displaystyle=[\langle V^{x},P(x)\rangle\text{ rejects}\leavevmode\nobreak\
|\leavevmode\nobreak\ i\notin S_{x}]\;.$

Therefore,

$\displaystyle\mathbb{P}[\langle V^{y},\tilde{P}(y)\rangle\text{ rejects}]$
$\displaystyle<\frac{1}{3}+\mathbb{P}[i\notin S_{y}]\cdot\mathbb{P}[\langle
V^{y},\tilde{P}(y)\rangle\text{ rejects}\leavevmode\nobreak\
|\leavevmode\nobreak\ i\notin S_{y}]$
$\displaystyle=\frac{1}{3}+\mathbb{P}[\langle V^{x},P(x)\rangle\text{ rejects
and }i\notin S_{x}]$ $\displaystyle\leq\frac{1}{3}+\mathbb{P}[\langle
V^{x},P(x)\rangle\text{ rejects}]\leq\frac{2}{3}\;,$

contradicting the correctness of the protocol. ∎

Rather surprisingly, however, there exists a quantum _non-interactive_
protocol that exploits amplitude amplification and achieves sublinear query
and communication complexities. This is a direct consequence of the following.

######  Proposition 2.

For any $k\leq n$, the property
$\Pi\coloneqq\left\\{x\in\\{0,1\\}^{n}:\bigoplus_{j\in[n]}x_{j}=0\right\\}$ is
succinctly $k$-partitionable (with respect to exact decision).

###### Proof.

The set of strings that specify decompositions is
$S=\left\\{y\in\\{0,1\\}^{k}:\bigoplus_{i\in[k]}y_{i}=0\right\\}$, i.e., the
set of $k$-bit strings of even parity. A string $y\in S$ specifies a
decomposition where, for each $i\in[k]$, the $i^{\text{th}}$ subproperty is
$\Lambda^{(i)}=\left\\{x^{(i)}\in\\{0,1\\}^{n/k}:\bigoplus_{j\in[n/k]}x^{(i)}_{j}=y_{i}\right\\}$
and $x\in\\{0,1\\}^{n}$ induces $x^{(i)}$ as the substring of $x$ consisting
of the $i^{\text{th}}$ block of $n/k$ bits, i.e.,
$x^{(i)}=\left(x_{\frac{(i-1)n}{k}+1},x_{\frac{(i-1)n}{k}+2},\ldots,x_{\frac{in}{k}}\right)$.

Note that the condition $x^{(i)}\in\Lambda^{(i)}$ for all $i\in[k]$ uniquely
defines $y\in\\{0,1\\}^{k}$ by
$y_{i}=\bigoplus_{\frac{(i-1)n}{k}<j\leq\frac{in}{k}}x_{j}$. Therefore, if $x$
has even parity, there exists $y\in S$ satisfying the condition, while if
$x\notin\Pi$ the only string that satisfies it is not in $S$. Thus $x$ is
$1/n$-far from $\Pi$ and, _for all $y\in S$_, there exists $i\in[k]$ such that
$x^{(i)}\notin\Lambda^{(i)}$, so that the distances $\varepsilon_{j}$ from
$x^{(j)}$ to $\Lambda^{(j)}$ satisfy
$\frac{1}{k}\sum_{j\in[k]}\varepsilon_{j}\geq\frac{\varepsilon_{i}}{k}\geq\frac{1}{k\cdot\frac{n}{k}}=1/n$.
∎

Applying Theorem 7.1 with $k=n^{2/3}$, we have:

######  Corollary 9.

There exists a QCMA protocol for parity with $O(n^{2/3})$ query and
communication complexities.

####  7.3.2 Branching programs

Recall that Corollary 6 shows membership in the set of strings accepted by
_read-once_ branching programs can be decided with $O(n^{3/4})$ query and
proof complexities; thus, since parity is computed by an ROBP (of width 2), we
obtain a QCMA protocol with the same parameters. Observe, however, that this
is significantly worse than the $O(n^{2/3})$ upper bound of the previous
section, which directly exploits decomposability. This suggests a similar
improvement may be possible for branching programs, which we now show to be
indeed the case for _layered_ branching programs parametrised by their
_length_ $\ell$ and _width_ $w$ (see Section 2 for the definitions).

######  Proposition 3.

Let $B$ be a layered branching program on $n$-bit strings of length
$\ell=\ell(n)$ and width $w=w(n)$. For any $k\leq\ell$, the set
$A_{B}\subseteq\\{0,1\\}^{n}$ of strings accepted by $B$ is $(k,O(k\log
w))$-partitionable (with respect to exact decision).

###### Proof.

Let $V$ be the vertex set of the graph that defines the branching program $B$,
whose layers are $V_{0}=\left\\{v_{0}\right\\}$, $V_{1}$, …, $V_{\ell}$ and
whose set of accepting nodes is $F\subseteq V_{\ell}$. Decompositions are
specified by the set $S=\left\\{(v_{1},\ldots,v_{k}):v_{i}\in
V_{i\ell/k}\text{ and }v_{k}\in F\right\\}$ (whose elements are the $k\log
w$-bit representations of the sequence of vertices). (Note that
$\absolutevalue{V_{i}}\leq w$ implies $\log w$ bits suffice to identify each
vertex in a given layer.) A specification fixes $k$ nodes that partition an
alleged accepting path into paths of length $\ell/k$. Thus, $\Lambda^{(i)}$ is
the set of strings accepted by the branching program that is the subgraph of
$B$ with layers $\left\\{v_{i-1}\right\\}$ and $V_{j}$ for
$\frac{(i-1)\ell}{k}<j\leq\frac{i\ell}{k}$, source node $v_{i-1}$ and
accepting node $v_{i}$. The string $x^{(i)}$ is the $i^{\text{th}}$ block of
$\ell/k$ bits of the input $x$.

If $x\in A_{B}$, there clearly exists an accepting path
$(v_{0},u_{1},\ldots,u_{\ell})$, namely the path determined by the execution
of $B$ on $x$. Therefore,
$y=(u_{\ell/k},u_{2\ell/k},\ldots,u_{(k-1)\ell/k},u_{\ell})\in S$ is a
specification satisfying $x^{(i)}\in\Lambda^{(i)}$ for all $i\in[k]$. If
$x\notin A_{B}$, on the other hand, every specification is such that at least
one sub-path does not match the corresponding sub-path determined by $x$
(since otherwise $x$ would be accepted by $B$), implying
$x^{(i)}\notin\Lambda^{(i)}$ for some $i$. ∎

Applying Theorem 7.1 with $k=\ell^{2/3}$, we obtain 5: width-$w$,
length-$\ell$ branching programs admit QCMAP protocols with proof complexity
$O(\ell^{2/3}\log w)$ and query complexity $O(\ell/\sqrt{k})=O(\ell^{2/3})$.
Note that the $\Omega(n)$ classical complexity lower bound for parity implies
the same bound for width-2 branching programs of length $n$, and that the
complexities of the QCMA protocol are sublinear up to length $o(n^{3/2}/\log
w)$; in particular, this holds for width-$2^{n^{\alpha}}$ branching programs
of length $o(n^{\frac{3}{2}(1-\alpha)})$ for every $\alpha\geq 0$. Thus,
besides lifting the read-once restriction, it improves on Corollary 6 for a
wide range of parameters.

##  8 Bipartiteness in bounded-degree graphs

In the bounded-degree graph model, an algorithm is given query access to the
_adjacency list_ of a graph $G$ whose vertices have their degree bounded by
$d=O(1)$. More precisely, given a vertex $v$ and an index $i\in[d]$, the
oracle corresponds to the mapping $(v,i)\mapsto w$, where $w$ is the
$i^{\text{th}}$ neighbour of $v$ (if it exists) or $w=\bot$ (if $v$ has fewer
than $i$ neighbours). The distance between two graphs is the fraction of pairs
$(v,i)$ whose outputs differ between the adjacency list mappings.

Our goal in this section will be to construct a QMAP protocol for testing
whether a bounded-degree _rapidly-mixing_ graph $G$ (i.e., where the last
vertex in a random walk of sufficiently large length $\ell=O(\log n)$ starting
from any vertex is distributed roughly uniformly), given as an adjacency list
oracle, is bipartite or $\varepsilon$-far from every (rapidly-mixing)
bipartite graph. Note that this differs from the standard testing setting on
graphs by the additional restriction that _both_ yes- and no-inputs be rapidly
mixing: whether $G$ is bipartite or $\varepsilon$-far from bipartite, for any
pair $u,v$ of vertices, the length-$\ell$ random walk starting from $u$ ends
at $v$ with probability between $1/(2n)$ and $2/n$.

Our QMAP protocol for bipartiteness builds on the MAP protocol of [46, Theorem
7.1], modifying it to take full advantage of quantum speedups. In the strategy
laid out in that work, the classical verifier receives as proof a set $S$ of
$k$ vertices that are allegedly on the same side of a bipartition. It
repeatedly samples a uniformly random vertex, takes many lazy random walks of
length $\ell$ and,191919A lazy random walk moves from a vertex $v$ to a
uniform random neighbour with probability $\frac{d_{v}}{2d}$ and otherwise
stays at $v$, where $d_{v}$ is the degree of $v$ and $d=O(1)$ is the graph’s
degree bound. for each of them, records if it stops at a vertex in $S$ as well
as the parity of the number of non-lazy steps (where the walk moves to another
vertex). If two walks starting from the same vertex end in $S$ with different
parities, the verifier has found a witness to the fact that the graph is not
bipartite and rejects.

For any proximity parameter $\varepsilon$ and $k\leq n/2$, the MAP protocol of
[46] requires a proof of length $k\log n$ and makes $O(\varepsilon^{-2}\cdot
n/k)$ queries. By making the verifier quantum (but using the same classical
proof), we obtain improvements in the dependence on both $n/k$ and
$\varepsilon$:

######  Theorem 8.1.

For every $k\leq n/2$, there exists a one-sided QCMAP for deciding whether an
$n$-vertex bounded-degree graph $G$ is bipartite or $\varepsilon$-far from
being bipartite, under the promise that $G$ is rapidly-mixing, with proof
complexity $k\cdot\log n$ and query complexity
$\tilde{O}((n/k)^{2/3}\cdot\varepsilon^{-5/6})$.

Our strategy to obtain a quantum speedup uses the quantum _collision-finding_
algorithm [7, 8] to a suitable modification of the verifier strategy outlined
above.202020We remark that collision-finding here refers to a generalisation
of the _element distinctness_ algorithm to symmetric relations beyond
equality. In particular, it is _not_ a quantum algorithm for the “$r$-to-1
collision problem”, where (many) collisions are promised to exist. We note
that the function $f$ to which we will apply the collision-finding algorithm
is _not_ the adjacency list oracle, but one whose unitary representation can
be obtained by adjacency list queries and classical computation.

######  Theorem 8.2 (Quantum collision-finding [8, Theorem 9]).

Let $f\colon X\to Y$ be a function given via a unitary oracle and $R\subseteq
Y\times Y$ be a symmetric binary relation. There exists a quantum algorithm
that makes $O(\absolutevalue{X}^{2/3}\operatorname{polylog}\absolutevalue{Y})$
queries to $f$, always accepts if $(x,x^{\prime})\notin R$ for every distinct
$x,x^{\prime}\in X$, and rejects with probability $2/3$ if there exist
distinct $x,x^{\prime}\in X$ such that $(x,x^{\prime})\in R$.

Returning to the aforementioned classical MAP, observe that the information of
each set of $t$ random walks of length $\ell$ starting from a fixed vertex can
be represented by a function $f\colon T\to\\{0,1\\}^{2}$, where
$T\subset\\{0,1\\}^{\ell^{\prime}}$ is composed of $t$ strings of length
$\ell^{\prime}=O(\ell)$ (note that each step of the random walk can be
performed with $O(1)$ bits, for a total of $\ell^{\prime}=O(\ell)$ random
coins per walk) and $f(r)$ encodes whether the walk reaches a vertex in $S$ as
well as its parity when its inner randomness corresponds to the string $r$.
Now, applying the collision-finding algorithm to this function for each
sampled vertex already yields a speedup [8]; but it can be improved by
combining this strategy with amplitude amplification (which improves
quadratically the number of samples taken as the starting vertices of the
random walks), as we show next.

###### Proof of Theorem 8.1.

We first consider the classical MAP outlined earlier when it samples a
_single_ starting vertex for a random walk, and apply collision-finding to the
function $f$ whose domain is $T$, a random (multi-)set of sequences of coin
flips. The proof specifies a subset $S\subseteq L$ of size $k$, for some $L$
(allegedly) defining a bipartition $V=L\cup R$ of $G$ with
$\absolutevalue{L}\geq\absolutevalue{R}$. The resulting algorithm (which is
_not_ yet the final QCMAP verifier), is shown in Figure 4.

Input: oracle access to the adjacency list of an $n$-vertex graph $G$, as well
as explicit access to a proximity parameter $\varepsilon>0$ and a proof string
$\pi\in\\{0,1\\}^{k\log n}$ (representing a set $S\subset V(G)$ of size $k$).
1. Sample a uniformly random vertex $v\in V(G)$ and select a multi-set
$T\subset\\{0,1\\}^{\ell^{\prime}}$, where $\ell^{\prime}=O(\ell)$ and
$\ell=O(\log n)$, by sampling
$O\left(\frac{n}{k}\cdot\frac{\log{n}}{\varepsilon}\right)$ bit strings
uniformly and independently. 2. Let $f:T\to\\{0,1\\}^{2}$ be the function
computed by the following subroutine: (2(a)) Let $r\in T$ be the input. Take
the (lazy) random walk of length $\ell$ starting at $v$ using $r$ as the
random bits. Let $a\in\\{0,1\\}$ be the indicator of whether the walk stops at
a vertex in $S$ and $b\in\\{0,1\\}$ be the parity of the walk (i.e., the
number of non-lazy steps). Return $(a,b)$. 3. Execute the algorithm of Theorem
8.2 with respect to $f$ to find $t$ and $t^{\prime}$ such that $f(t)=(a,b)$
and $f(t^{\prime})=(a^{\prime},b^{\prime})$ with $a=a^{\prime}=1$ and $b\neq
b^{\prime}$. Reject if such a pair is found, and accept otherwise.

Figure 4: Quantum algorithm for bipartiteness with low detection probability

First, note that the function $f$ contains a collision with respect to the
relation $R\subset\\{0,1\\}^{4}$ that comprises all pairs of pairs of the type
$((1,b),(1,1-b))$ _if and only if_ there are two random walks of length $\ell$
that start from $v$ end at a vertex in $S$ with different parities.

If $G$ is bipartite with vertex set $L\cup R$ and $S\subseteq L$, every path
with both endpoints in $S$ has even length. But the existence of two paths
from the same vertex into $S$ with different parities implies the existence of
a path of odd length with both endpoints in $S$; therefore, since the function
$f$ does not contain a collision for any starting vertex $v$, the verifier
always accepts when $G$ is bipartite and the proof consists of $k$ elements on
the same side of a bipartition.

If $G$ is $\varepsilon$-far from bipartite, then [46] (building on [38]) show
the following: defining $a$ as the indicator of whether a random walk of
length $\ell=O(\log n)$ starting from vertex $v$ stops at a vertex in $S$, and
$b$ as the parity of this random walk, then an $\Omega(\varepsilon/\log n)$
fraction of vertices in $V(G)$ are such that _both_ $\mathbb{P}[a=1,b=0]$ and
$\mathbb{P}[a=1,b=1]$ are $\Omega(\frac{k\varepsilon}{n\log n})$. Therefore,
with probability $\Omega(\varepsilon/\log n)$, the sampled vertex $v\in V(G)$
satisfies this condition. If such a vertex was sampled, with probability
$\Omega(1)$, in a sufficiently large number $\absolutevalue{T}=O(\frac{n\log
n}{k\varepsilon})$ of random walks starting from it there exists a pair of
length-$\ell$ walks that end in $S$ with different parities. Finally, since
the algorithm of Theorem 8.2 rejects with constant probability if the function
$f$ contains a collision, the algorithm in Figure 4 rejects with probability
$\Omega(\varepsilon/\log n)$.

The quantum collision-finding algorithm computes $O(\absolutevalue{T}^{2/3})$
times the function $f$, each of which simulates a random walk of length
$\ell=O(\log n)$. Each step of the random walk requires $O(1)$ queries to the
graph $G$, so that $O(\log n)$ queries are made per walk. The query complexity
of the algorithm in Figure 4 is therefore

$O\left(\absolutevalue{T}^{2/3}\cdot\ell\right)=\tilde{O}\left(\left(\frac{n}{k\varepsilon}\right)^{2/3}\right).$

Finally, applying amplitude amplification (Theorem 6.1) to this algorithm
(rather, more precisely, to a reversible quantum algorithm that is obtained
from Figure 4 by deferring its measurements; see, e.g., [62]), we obtain a
QCMAP verifier for bipartiteness of bounded-degree graphs with query
complexity

$\tilde{O}\left(\left(\frac{n}{k\varepsilon}\right)^{2/3}\right)\cdot
O\left(\sqrt{\frac{\log
n}{\varepsilon}}\right)=\tilde{O}\left(\left(\frac{n}{k}\right)^{2/3}\cdot\frac{1}{\varepsilon^{5/6}}\right).\qed$

We remark that classically testing bipartiteness in the bounded-degree model
requires $\Omega(\sqrt{n})$ queries _even under the rapidly-mixing promise_ ,
as shown by Goldreich and Ron [39]; therefore, for constant $\varepsilon$, a
QCMAP with proof complexity $\tilde{O}(n^{1/4})$ is enough to overcome the
testing lower bound, while the MAP of [46] requires a proof of length
$\tilde{O}(\sqrt{n})$. Of course, a fairer comparison would be to _quantum_
testers, for which $\tilde{O}(n^{1/3})$ queries suffice [7] but no nontrivial
lower bound is known. The quantum tester is sound without the rapidly-mixing
promise, however, so even though a QCMAP with proof length
$\tilde{O}(\sqrt{n})$ makes fewer queries than the best known quantum tester,
it is not clear how the two algorithms compare.

## References

  * Aaronson [2010] Scott Aaronson.  BQP and the polynomial hierarchy.  In Leonard J. Schulman, editor, _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ , pages 141–150. ACM, 2010.  doi: 10.1145/1806689.1806711.
  * Aaronson [2012] Scott Aaronson.  Impossibility of succinct quantum proofs for collision-freeness.  _Quantum Inf. Comput._ , 12(1-2):21–28, 2012\.  doi: 10.26421/QIC12.1-2-3.
  * Aaronson and Ambainis [2018] Scott Aaronson and Andris Ambainis.  Forrelation: A problem that optimally separates quantum from classical computing.  _SIAM J. Comput._ , 47(3):982–1038, 2018.  doi: 10.1137/15M1050902.
  * Aaronson and Kuperberg [2007] Scott Aaronson and Greg Kuperberg.  Quantum versus classical proofs and advice.  In _22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 13-16 June 2007, San Diego, California, USA_ , pages 115–128. IEEE Computer Society, 2007.  doi: 10.1109/CCC.2007.27.
  * Aharonov et al. [2013] Dorit Aharonov, Itai Arad, and Thomas Vidick.  Guest column: the quantum PCP conjecture.  _SIGACT News_ , 44(2):47–79, 2013.  doi: 10.1145/2491533.2491549.
  * Aharonov et al. [2022] Dorit Aharonov, Jordan Cotler, and Xiao-Liang Qi.  Quantum algorithmic measurement.  _Nature Communications_ , 13(1):1–9, 2022.  doi: 10.1038/s41467-021-27922-0.
  * Ambainis [2007] Andris Ambainis.  Quantum walk algorithm for element distinctness.  _SIAM J. Comput._ , 37(1):210–239, 2007.  doi: 10.1137/S0097539705447311.
  * Ambainis et al. [2011] Andris Ambainis, Andrew M. Childs, and Yi-Kai Liu.  Quantum property testing for bounded-degree graphs.  In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings_ , volume 6845 of _Lecture Notes in Computer Science_ , pages 365–376. Springer, 2011.  doi: 10.1007/978-3-642-22935-0\\_31.
  * Ambainis et al. [2016] Andris Ambainis, Aleksandrs Belovs, Oded Regev, and Ronald de Wolf.  Efficient quantum algorithms for (gapped) group testing and junta testing.  In Robert Krauthgamer, editor, _Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016_ , pages 903–922. SIAM, 2016.  doi: 10.1137/1.9781611974331.ch65.
  * Asadi and Shinkar [2021] Vahid R. Asadi and Igor Shinkar.  Relaxed locally correctable codes with improved parameters.  In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, _48th International Colloquium on Automata, Languages, and Programming, ICALP 2021, July 12-16, 2021, Glasgow, Scotland (Virtual Conference)_ , volume 198 of _LIPIcs_ , pages 18:1–18:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi: 10.4230/LIPIcs.ICALP.2021.18.
  * Aspnes et al. [1991] James Aspnes, Richard Beigel, Merrick L. Furst, and Steven Rudich.  The expressive power of voting polynomials.  In Cris Koutsougeras and Jeffrey Scott Vitter, editors, _Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, May 5-8, 1991, New Orleans, Louisiana, USA_ , pages 402–409. ACM, 1991.  doi: 10.1145/103418.103461.
  * Badescu et al. [2019] Costin Badescu, Ryan O’Donnell, and John Wright.  Quantum state certification.  In Moses Charikar and Edith Cohen, editors, _Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019_ , pages 503–514. ACM, 2019.  doi: 10.1145/3313276.3316344.
  * Ben-Sasson et al. [2006] Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil P. Vadhan.  Robust PCPs of proximity, shorter PCPs, and applications to coding.  _SIAM J. Comput._ , 36(4):889–974, 2006.  doi: 10.1137/S0097539705446810.
  * Ben-Sasson et al. [2017] Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Michael Riabzev, and Nicholas Spooner.  Interactive oracle proofs with constant rate and query complexity.  In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, _44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland_ , volume 80 of _LIPIcs_ , pages 40:1–40:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi: 10.4230/LIPIcs.ICALP.2017.40.
  * Berman et al. [2018] Itay Berman, Ron D. Rothblum, and Vinod Vaikuntanathan.  Zero-knowledge proofs of proximity.  In Anna R. Karlin, editor, _9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA_ , volume 94 of _LIPIcs_ , pages 19:1–19:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.  doi: 10.4230/LIPIcs.ITCS.2018.19.
  * Blais et al. [2012] Eric Blais, Joshua Brody, and Kevin Matulef.  Property testing lower bounds via communication complexity.  _Comput. Complex._ , 21(2):311–358, 2012.  doi: 10.1007/s00037-012-0040-x.
  * Brassard et al. [2002] Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.  Quantum amplitude amplification and estimation.  _Contemporary Mathematics_ , 305:53–74, 2002.  doi: 10.1090/conm/305/05215.
  * Bubeck et al. [2020] Sébastien Bubeck, Sitan Chen, and Jerry Li.  Entanglement is necessary for optimal quantum property testing.  In Sandy Irani, editor, _61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020_ , pages 692–703. IEEE, 2020.  doi: 10.1109/FOCS46700.2020.00070.
  * Buhrman et al. [2008] Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig.  Quantum property testing.  _SIAM J. Comput._ , 37(5):1387–1400, 2008.  doi: 10.1137/S0097539704442416.
  * Canonne et al. [2019] Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, and Karl Wimmer.  Testing $k$-monotonicity: The rise and fall of boolean functions.  _Theory Comput._ , 15:1–55, 2019.  doi: 10.4086/toc.2019.v015a001.
  * Chakraborty and Maitra [2013] Kaushik Chakraborty and Subhamoy Maitra.  Improved quantum test for linearity of a boolean function.  _CoRR_ , abs/1306.6195, 2013.  doi: 10.48550/arXiv.1306.6195.
  * Chakraborty et al. [2010] Sourav Chakraborty, Eldar Fischer, Arie Matsliah, and Ronald de Wolf.  New results on quantum property testing.  In Kamal Lodaya and Meena Mahajan, editors, _IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India_ , volume 8 of _LIPIcs_ , pages 145–156. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010.  doi: 10.4230/LIPIcs.FSTTCS.2010.145.
  * Chefles [2000] Anthony Chefles.  Quantum state discrimination.  _Contemporary Physics_ , 41(6):401–424, 2000\.  doi: 10.1080/00107510010002599.
  * Chen [2016] Lijie Chen.  A note on oracle separations for BQP.  _CoRR_ , abs/1605.00619, 2016.  doi: 10.48550/arXiv.1605.00619.
  * Chiesa et al. [2020] Alessandro Chiesa, Tom Gur, and Igor Shinkar.  Relaxed locally correctable codes with nearly-linear block length and constant query complexity.  In _Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020_ , pages 1395–1411, 2020.  doi: 10.1137/1.9781611975994.84.
  * Daiss et al. [2021] Severin Daiss, Stefan Langenfeld, Stephan Welte, Emanuele Distante, Philip Thomas, Lukas Hartung, Olivier Morin, and Gerhard Rempe.  A quantum-logic gate between distant quantum-network modules.  _Science_ , 371(6529):614–617, 2021.  doi: 10.1126/science.abe3150.
  * Dall’Agnol et al. [2021] Marcel Dall’Agnol, Tom Gur, and Oded Lachish.  A structural theorem for local algorithms with applications to coding, testing, and privacy.  In Dániel Marx, editor, _Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021_ , pages 1651–1665. SIAM, 2021.  doi: 10.1137/1.9781611976465.100.
  * Eisert et al. [2020] Jens Eisert, Dominik Hangleiter, Nathan Walk, Ingo Roth, Damian Markham, Rhea Parekh, Ulysse Chabaud, and Elham Kashefi.  Quantum certification and benchmarking.  _Nature Reviews Physics_ , pages 1–9, 2020.  doi: 10.1038/s42254-020-0186-4.
  * Ergün et al. [2004] Funda Ergün, Ravi Kumar, and Ronitt Rubinfeld.  Fast approximate probabilistically checkable proofs.  _Inf. Comput._ , 189(2):135–159, 2004.  doi: 10.1016/j.ic.2003.09.005.
  * Fischer et al. [2014] Eldar Fischer, Yonatan Goldhirsh, and Oded Lachish.  Partial tests, universal tests and decomposability.  In Moni Naor, editor, _Innovations in Theoretical Computer Science, ITCS’14, Princeton, NJ, USA, January 12-14, 2014_ , pages 483–500. ACM, 2014.  doi: 10.1145/2554797.2554841.
  * Gheorghiu et al. [2019] Alexandru Gheorghiu, Theodoros Kapourniotis, and Elham Kashefi.  Verification of quantum computation: An overview of existing approaches.  _Theory Comput Syst_ , 63(4):715–808, 2019.  doi: 10.1007/s00224-018-9872-3.
  * Gilyén and Li [2020] András Gilyén and Tongyang Li.  Distributional property testing in a quantum world.  In Thomas Vidick, editor, _11th Innovations in Theoretical Computer Science Conference, ITCS 2020, January 12-14, 2020, Seattle, Washington, USA_ , volume 151 of _LIPIcs_ , pages 25:1–25:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.  doi: 10.4230/LIPIcs.ITCS.2020.25.
  * Giovannetti et al. [2008] Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone.  Quantum random access memory.  _Phys. Rev. Lett._ , 100:160501, Apr 2008.  doi: 10.1103/PhysRevLett.100.160501.
  * Goldreich [2014] Oded Goldreich.  On multiple input problems in property testing.  In Klaus Jansen, José D. P. Rolim, Nikhil R. Devanur, and Cristopher Moore, editors, _Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain_ , volume 28 of _LIPIcs_ , pages 704–720. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.  doi: 10.4230/LIPIcs.APPROX-RANDOM.2014.704.
  * Goldreich [2017] Oded Goldreich.  _Introduction to Property Testing_.  Cambridge University Press, 2017.  ISBN 978-1-107-19405-2.  doi: 10.1017/9781108135252.
  * Goldreich [2020] Oded Goldreich.  On the communication complexity methodology for proving lower bounds on the query complexity of property testing.  In _Computational Complexity and Property Testing - On the Interplay Between Randomness and Computation_ , volume 12050 of _Lecture Notes in Computer Science_ , pages 87–118. Springer, 2020.  doi: 10.1007/978-3-030-43662-9\\_7.
  * Goldreich and Gur [2021] Oded Goldreich and Tom Gur.  Universal locally verifiable codes and 3-round interactive proofs of proximity for CSP.  _Theor. Comput. Sci._ , 878-879:83–101, 2021.  doi: 10.1016/j.tcs.2021.05.030.
  * Goldreich and Ron [1999] Oded Goldreich and Dana Ron.  A sublinear bipartiteness tester for bounded degree graphs.  _Comb._ , 19(3):335–373, 1999.  doi: 10.1007/s004930050060.
  * Goldreich and Ron [2002] Oded Goldreich and Dana Ron.  Property testing in bounded degree graphs.  _Algorithmica_ , 32(2):302–343, 2002.  doi: 10.1007/s00453-001-0078-7.
  * Goldreich et al. [2000] Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, and Alex Samorodnitsky.  Testing monotonicity.  _Comb._ , 20(3):301–337, 2000.  doi: 10.1007/s004930070011.
  * Goldreich et al. [2018] Oded Goldreich, Tom Gur, and Ron D. Rothblum.  Proofs of proximity for context-free languages and read-once branching programs.  _Inf. Comput._ , 261:175–201, 2018.  doi: 10.1016/j.ic.2018.02.003.
  * Goldreich et al. [2019] Oded Goldreich, Tom Gur, and Ilan Komargodski.  Strong locally testable codes with relaxed local decoders.  _ACM Trans. Comput. Theory_ , 11(3):17:1–17:38, 2019.  doi: 10.1145/3319907.
  * Göös and Maystre [2021] Mika Göös and Gilbert Maystre.  A majority lemma for randomised query complexity.  In Valentine Kabanets, editor, _36th Computational Complexity Conference, CCC 2021, July 20-23, 2021, Toronto, Ontario, Canada (Virtual Conference)_ , volume 200 of _LIPIcs_ , pages 18:1–18:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.  doi: 10.4230/LIPIcs.CCC.2021.18.
  * Gur and Lachish [2021] Tom Gur and Oded Lachish.  On the power of relaxed local decoding algorithms.  _SIAM J. Comput._ , 50(2):788–813, 2021.  doi: 10.1137/19M1307834.
  * Gur and Rothblum [2017] Tom Gur and Ron D. Rothblum.  A hierarchy theorem for interactive proofs of proximity.  In Christos H. Papadimitriou, editor, _8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA_ , volume 67 of _LIPIcs_ , pages 39:1–39:43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.  doi: 10.4230/LIPIcs.ITCS.2017.39.
  * Gur and Rothblum [2018] Tom Gur and Ron D. Rothblum.  Non-interactive proofs of proximity.  _Comput. Complex._ , 27(1):99–207, 2018.  doi: 10.1007/s00037-016-0136-9.
  * Gur et al. [2021] Tom Gur, Yang P. Liu, and Ron D. Rothblum.  An exponential separation between MA and AM proofs of proximity.  _Comput. Complex._ , 30(2):12, 2021.  doi: 10.1007/s00037-021-00212-3.
  * Haah et al. [2017] Jeongwan Haah, Aram W. Harrow, Zhengfeng Ji, Xiaodi Wu, and Nengkun Yu.  Sample-optimal tomography of quantum states.  _IEEE Trans. Inf. Theory_ , 63(9):5628–5641, 2017.  doi: 10.1109/TIT.2017.2719044.
  * Han et al. [1997] Yenjo Han, Lane A. Hemaspaandra, and Thomas Thierauf.  Threshold computation and cryptographic security.  _SIAM J. Comput._ , 26(1):59–78, 1997.  doi: 10.1137/S0097539792240467.
  * Harrow and Montanaro [2013] Aram W. Harrow and Ashley Montanaro.  Testing product states, quantum Merlin-Arthur games and tensor optimization.  _J. ACM_ , 60(1):3:1–3:43, 2013.  doi: 10.1145/2432622.2432625.
  * Harrow et al. [2017] Aram W. Harrow, Cedric Yen-Yu Lin, and Ashley Montanaro.  Sequential measurements, disturbance and property testing.  In Philip N. Klein, editor, _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19_ , pages 1598–1611. SIAM, 2017.  doi: 10.1137/1.9781611974782.105.
  * Hillery and Andersson [2011] Mark Hillery and Erika Andersson.  Quantum tests for the linearity and permutation invariance of boolean functions.  _Phys. Rev. A_ , 84:062329, Dec 2011.  doi: 10.1103/PhysRevA.84.062329.
  * Kalai and Rothblum [2015] Yael Tauman Kalai and Ron D. Rothblum.  Arguments of proximity - [extended abstract].  In Rosario Gennaro and Matthew Robshaw, editors, _Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II_ , volume 9216 of _Lecture Notes in Computer Science_ , pages 422–442. Springer, 2015.  doi: 10.1007/978-3-662-48000-7\\_21.
  * Khot et al. [2018] Subhash Khot, Dor Minzer, and Muli Safra.  On monotonicity testing and boolean isoperimetric-type theorems.  _SIAM J. Comput._ , 47(6):2238–2276, 2018.  doi: 10.1137/16M1065872.
  * Levin [1987] Leonid A. Levin.  One-way functions and pseudorandom generators.  _Comb._ , 7(4):357–363, 1987.  doi: 10.1007/BF02579323.
  * Levine et al. [2019] Harry Levine, Alexander Keesling, Giulia Semeghini, Ahmed Omran, Tout T. Wang, Sepehr Ebadi, Hannes Bernien, Markus Greiner, Vladan Vuletić, Hannes Pichler, and Mikhail D. Lukin.  Parallel implementation of high-fidelity multiqubit gates with neutral atoms.  _Phys. Rev. Lett._ , 123:170503, Oct 2019.  doi: 10.1103/PhysRevLett.123.170503.
  * Liu et al. [2022] Junyu Liu, Connor T. Hann, and Liang Jiang.  Quantum data center: Theories and applications.  _CoRR_ , abs/2207.14336, 2022.  doi: 10.48550/arXiv.2207.14336.
  * Marriott and Watrous [2005] Chris Marriott and John Watrous.  Quantum Arthur-Merlin games.  _Comput. Complex._ , 14(2):122–152, 2005.  doi: 10.1007/s00037-005-0194-x.
  * Monroe et al. [2014] C. Monroe, R. Raussendorf, A. Ruthven, K. R. Brown, P. Maunz, L.-M. Duan, and J. Kim.  Large-scale modular quantum-computer architecture with atomic memory and photonic interconnects.  _Phys. Rev. A_ , 89:022317, Feb 2014.  doi: 10.1103/PhysRevA.89.022317.
  * Montanaro and de Wolf [2016] Ashley Montanaro and Ronald de Wolf.  A survey of quantum property testing.  _Theory Comput._ , 7:1–81, 2016.  doi: 10.4086/toc.gs.2016.007.
  * Natarajan and Vidick [2017] Anand Natarajan and Thomas Vidick.  A quantum linearity test for robustly verifying entanglement.  In Hamed Hatami, Pierre McKenzie, and Valerie King, editors, _Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017_ , pages 1003–1015. ACM, 2017.  doi: 10.1145/3055399.3055468.
  * Nielsen and Chuang [2016] Michael A. Nielsen and Isaac L. Chuang.  _Quantum Computation and Quantum Information (10th Anniversary edition)_.  Cambridge University Press, 2016.  ISBN 978-1-10-700217-3.  doi: 10.1017/CBO9780511976667.
  * O’Donnell and Servedio [2003] Ryan O’Donnell and Rocco A. Servedio.  New degree bounds for polynomial threshold functions.  In Lawrence L. Larmore and Michel X. Goemans, editors, _Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA_ , pages 325–334. ACM, 2003.  doi: 10.1145/780542.780592.
  * O’Donnell and Wright [2015] Ryan O’Donnell and John Wright.  Quantum spectrum testing.  In Rocco A. Servedio and Ronitt Rubinfeld, editors, _Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015_ , pages 529–538. ACM, 2015.  doi: 10.1145/2746539.2746582.
  * O’Donnell and Wright [2016] Ryan O’Donnell and John Wright.  Efficient quantum tomography.  In Daniel Wichs and Yishay Mansour, editors, _Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016_ , pages 899–912. ACM, 2016.  doi: 10.1145/2897518.2897544.
  * Paulsen [2003] Vern Paulsen.  _Completely Bounded Maps and Operator Algebras_.  Cambridge University Press, 2003.  doi: 10.1017/CBO9780511546631.
  * Raz and Shpilka [2004] Ran Raz and Amir Shpilka.  On the power of quantum proofs.  In _19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA_ , pages 260–274. IEEE Computer Society, 2004.  doi: 10.1109/CCC.2004.1313849.
  * Razborov [2003] A A Razborov.  Quantum communication complexity of symmetric predicates.  _Izvestiya: Mathematics_ , 67(1):145–159, Feb 2003.  ISSN 1468-4810.  doi: 10.1070/im2003v067n01abeh000422.
  * Reingold et al. [2021] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum.  Constant-round interactive proofs for delegating computation.  _SIAM J. Comput._ , 50(3), 2021.  doi: 10.1137/16M1096773.
  * Renou et al. [2018] Marc Olivier Renou, Jędrzej Kaniewski, and Nicolas Brunner.  Self-testing entangled measurements in quantum networks.  _Phys. Rev. Lett._ , 121:250507, Dec 2018.  doi: 10.1103/PhysRevLett.121.250507.
  * Rothblum and Rothblum [2020] Guy N. Rothblum and Ron D. Rothblum.  Batch verification and proofs of proximity with polylog overhead.  In Rafael Pass and Krzysztof Pietrzak, editors, _Theory of Cryptography - 18th International Conference, TCC 2020, Durham, NC, USA, November 16-19, 2020, Proceedings, Part II_ , volume 12551 of _Lecture Notes in Computer Science_ , pages 108–138. Springer, 2020.  doi: 10.1007/978-3-030-64378-2\\_5.
  * Rothblum et al. [2013] Guy N. Rothblum, Salil P. Vadhan, and Avi Wigderson.  Interactive proofs of proximity: delegating computation in sublinear time.  In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, _Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013_ , pages 793–802. ACM, 2013.  doi: 10.1145/2488608.2488709.
  * Sherstov and Thaler [2019] Alexander A. Sherstov and Justin Thaler.  Vanishing-error approximate degree and QMA complexity.  _CoRR_ , abs/1909.07498, 2019.  doi: 10.48550/arXiv.1909.07498.
  * Stinespring [1955] W. Forrest Stinespring.  Positive functions on C*-algebras.  _Proceedings of the American Mathematical Society_ , 6(2):211–216, 1955.  doi: 10.2307/2032342.
  * Šupić and Bowles [2020] Ivan Šupić and Joseph Bowles.  Self-testing of quantum systems: a review.  _Quantum_ , 4:337, 2020.  doi: 10.22331/q-2020-09-30-337.
  * Tavakoli et al. [2018] Armin Tavakoli, Jędrzej Kaniewski, Tamás Vértesi, Denis Rosset, and Nicolas Brunner.  Self-testing quantum states and measurements in the prepare-and-measure scenario.  _Phys. Rev. A_ , 98:062307, Dec 2018.  doi: 10.1103/PhysRevA.98.062307.
  * Watrous [2009] John Watrous.  Quantum computational complexity.  In Robert A. Meyers, editor, _Encyclopedia of Complexity and Systems Science_ , pages 7174–7201. Springer, 2009.  doi: 10.1007/978-0-387-30440-3\\_428.
  * Wehner et al. [2018] Stephanie Wehner, David Elkouss, and Ronald Hanson.  Quantum internet: A vision for the road ahead.  _Science_ , 362(6412):eaam9288, 2018.  doi: 10.1126/science.aam9288.

##  Appendix A A QCMAP lower bound for testing unitaries

The known $\mathcal{QMA}$ versus $\mathcal{QCMA}$ (oracle) separation of
Aaronson and Kuperberg [4] is naturally cast as a testing problem, and thus
yields a corresponding separation between $\mathcal{QMAP}$ and
$\mathcal{QCMAP}$. More precisely, we consider the following property of
unitaries:

$\Pi_{AK}=\left\\{U\in\mathbb{C}^{n\times
n}:\begin{array}[]{ll}UU^{\dagger}=U^{\dagger}U=I\text{ and
}\exists\ket{\psi}\text{ such that }U\ket{\psi}=-\ket{\psi}\\\ \text{and
}U\ket{\varphi}=\ket{\varphi}\text{ when
}\bra{\varphi}\ket{\psi}=0\end{array}\right\\}\;,$

where the distance measure is the one induced by the (normalised) Hilbert-
Schmidt norm:
$d(U,V)=\sqrt{\frac{1}{n}\cdot\Tr\big((U-V)^{\dagger}(U-V)\big{missing})}$.
Note that, for every $U\in\Pi_{AK}$,

$d(U,I)=\sqrt{\frac{1}{n}\sum_{i=1}^{n}\sigma_{i}(U-I)^{2}}=\frac{2}{\sqrt{n}},$

where $I$ is the $n\times n$ identity matrix and $\sigma_{i}(A)$ is the
$i^{\text{th}}$ eigenvalue of $A$ in (say) nonincreasing order. Then
$d(\Pi_{AK},I)=2/\sqrt{n}$, so that distinguishing between a unitary in
$\Pi_{AK}$ and $I$ reduces to testing $\Pi_{AK}$ with proximity parameter
$\varepsilon\leq 2/\sqrt{n}$. Formally,

######  Theorem A.1.

For any proximity parameter $\varepsilon\leq 2/\sqrt{n}$, we have
$\Pi_{AK}\in\mathcal{QMAP}(\varepsilon,\log n,1)$ and
$\Pi_{AK}\notin\mathcal{QCMAP}(\varepsilon,p,q)$ when $\sqrt{p}\cdot
q=o(\sqrt{n})$.

###### Proof.

Without loss of generality, we assume query access to a _controlled_ unitary
$U\in\Pi_{AK}$ or to the identity unitary. Note that, since the identity is
$\varepsilon$-far from $\Pi_{AK}$, distinguishing between $U\in\Pi_{AK}$ and
$I$ is at least as hard as testing $\Pi_{AK}$.

A $\mathcal{QMAP}$ algorithm with logarithmic proof length and query
complexity 1 is as follows: given a $\log n$-qubit quantum state $\ket{\psi}$
as proof, apply the unitary to $\ket{\psi}$, accepting if and only if a phase
flip is detected (by measuring and inspecting the outcome of the control
qubit). Clearly, the eigenstate with eigenvalue $-1$ is a proof that causes
the algorithm to accept with certainty if $U\in\Pi_{AK}$, while no quantum
state is accepted if $U=I$ (also with certainty).

The lower bound is immediate from the one proven in [4], which can be
rephrased as follows: any QCMA algorithm that receives a proof of length $p$
and makes $q=o(\sqrt{n/p})$ oracle queries to $U\in\Pi_{AK}$ or the identity
operator either accepts $I$ or rejects some element of $\Pi_{AK}$ with
probability at least $1/2$. ∎

######  Remark 6.

In the usual encoding of an oracle for an $n$-bit string $x$ as a unitary
$\ket{i}\ket{b}\mapsto\ket{i}\ket{b\oplus x_{i}}$, a Hamming distance of
$\Theta(1)$ translates into $\Theta(1)$ distance in the Hilbert-Schmidt
metric. Therefore, Theorem A.1 falls short of proving
$\mathcal{QMAP}\not\subseteq\mathcal{QCMAP}$ (where the omitted proof and
query complexities are polylogarithmic, and the proximity parameter is
constant).

##  Appendix B Interaction versus quantum proofs

In this section we compare the power of classical interactive proofs of
proximity (IPPs) and non-interactive quantum proofs of proximity (QMAPs), and
show that the rather well studied problem of _permutation testing_ admits an
efficient IPP but no efficient QMAP. In fact, for permutation testing, even an
Arthur-Merlin Proof of Proximity is sufficient, as shown in [47]. Informally,
an Arthur-Merlin Proof of Proximity (AMP) is a proof system with one round of
communication where the verifier sends the first message.

Let $\Pi_{P}$ be the property (of _functions_ $f:[n]\to[n]$) defined as

$\Pi_{P}=\left\\{f:f\text{ is a bijection}\right\\}\;,$

i.e., $\Pi_{P}$ is the set of all permutations. We note that in an oracle
query to $f$, an algorithm sends $x\in[n]$ and receives (the $\log n$-bit
string) $f(x)$; accordingly, a quantum query maps ($2\log n$-qubit states via)
$\ket{x}\ket{y}\mapsto\ket{x}\ket{y+f(x)}$. Moreover, distance is measured in
terms of the fraction of inputs where functions disagree (rather than with
respect to their representations as bit strings), i.e., $f$ and $g$ are
$\varepsilon$-far when $\absolutevalue{\left\\{x\in[n]:f(x)\neq
g(x)\right\\}}/n\geq\varepsilon$.

The separation follows immediately from the two following theorems.

######  Theorem B.1 ([47, Lemma 4.2]).

For every with $\varepsilon>0$, There exists an AMP for $\varepsilon$-testing
$\Pi_{P}$ with query complexity $O(1/\varepsilon)$ and communication
complexity $O(\log n/\varepsilon)$, that communicates two messages: the first
is sent from verifier to prover and the second from prover to verifier.
Therefore,

$\Pi_{P}\in\mathcal{AMP}(\varepsilon,O(\log
n/\varepsilon),O(1/\varepsilon),2)\;.$

Since
$\mathcal{AMP}(\varepsilon,c,q,r)\subseteq\mathcal{IPP}(\varepsilon,c,q,r+1)$
(by initiating the protocol with a “dummy” message by the prover), the
following corollary is immediate.

######  Corollary 10.

$\Pi_{P}\in\mathcal{IPP}(\varepsilon,O(\log
n/\varepsilon),O(1/\varepsilon),3)$.

Having established that $\Pi_{P}$ admits an efficient IPP, we must now show it
is _not_ efficiently testable by a QMAP:

######  Lemma 9 ([73, Theorem 1.2]).

Any QMAP protocol for testing $\Pi_{P}$ with respect to proximity parameter
$\varepsilon=\Omega(1)$, using a proof of length $p$ and making $q$ queries,
satisfies $p\cdot q^{3}=\Omega(n)$; i.e.,

$\Pi_{P}\notin\mathcal{QMAP}(\varepsilon,p,q)\text{ when }p\cdot
q^{3}=o(n)\;.$

Note that this implies that either $p$ or $q$ must be $\Omega(n^{1/4})$ in any
QMAP protocol for $\Pi_{P}$. Finally, Theorem B.1 and Lemma 9 together imply
the main result of this section.

######  Theorem B.2.

Let $\Pi_{P}\subset\left\\{f:[n]\to[n]\right\\}$ be the set of bijective
functions from $[n]$ to $[n]$, with the distance between functions $f$ and $g$
defined as $\absolutevalue{\left\\{x\in[n]:f(x)\neq g(x)\right\\}}/n$. Then,
for any $\varepsilon=\Omega(1)$,

$\displaystyle\Pi_{P}$ $\displaystyle\in\mathcal{IPP}(\varepsilon,O(\log
n),O(1),3)\text{ and}$ $\displaystyle\Pi_{P}$
$\displaystyle\notin\mathcal{QMAP}(\varepsilon,p,q)\text{ when }p\cdot
q^{3}=o(n)\;.$

In particular,

$\mathcal{IPP}(\varepsilon,O(\log
n),O(1),3)\not\subseteq\mathcal{QMAP}(\varepsilon,o(n^{1/4}),o(n^{1/4}))\;.$


# Augmenting NER Datasets with LLMs: Towards Automated and Refined Annotation

Yuji Naraki
LegalOn Technologies
Tokyo, Japan
<EMAIL_ADDRESS>
&Ryosuke Yamaki∗
Ritsumeikan University / ProPlace Inc
Shiga / Tokyo, Japan
<EMAIL_ADDRESS>
Yoshikazu Ikeda
Osaka University / ProPlace Inc
Osaka / Tokyo, Japan
<EMAIL_ADDRESS>&Takafumi Horie
Ritsumeikan University
Shiga, Japan
<EMAIL_ADDRESS>
Hiroki Naganuma
Mila, Université de Montréal / ProPlace Inc.
Montreal, Canada / Tokyo, Japan
<EMAIL_ADDRESS>equal contributions

###### Abstract

In the field of Natural Language Processing (NLP), Named Entity Recognition
(NER) is recognized as a critical technology, employed across a wide array of
applications. Traditional methodologies for annotating datasets for NER models
are challenged by high costs and variations in dataset quality. This research
introduces a novel hybrid annotation approach that synergizes human effort
with the capabilities of Large Language Models (LLMs). This approach not only
aims to ameliorate the noise inherent in manual annotations, such as
omissions, thereby enhancing the performance of NER models, but also achieves
this in a cost-effective manner. Additionally, by employing a label mixing
strategy, it addresses the issue of class imbalance encountered in LLM-based
annotations. Through an analysis across multiple datasets, this method has
been consistently shown to provide superior performance compared to
traditional annotation methods, even under constrained budget conditions. This
study illuminates the potential of leveraging LLMs to improve dataset quality,
introduces a novel technique to mitigate class imbalances, and demonstrates
the feasibility of achieving high-performance NER in a cost-effective way.

##  1 Introduction

In the field of Natural Language Processing (NLP), Named Entity Recognition
(NER) is a critical task that involves identifying and classifying named
entities in a given text into predefined categories, including persons,
organizations, locations, temporal expressions, quantities, monetary values,
and percentages (Mohit, 2014). NER is integral to a wide range of
applications, from basic information retrieval and content classification to
more complex tasks like question answering and machine translation (Guo et
al., 2009; Aliod et al., 2006; Babych & Hartley, 2003). The enhancement of NER
model performance not only directly contributes to the improvement of broad
NLP applications but also plays a crucial role in enhancing our understanding
and engagement with text-based data (Cheng & Erk, 2019; Etzioni et al., 2005).

In recent years, NER methods leveraging the in-context learning capabilities
of Large Language Models (LLMs) have been proposed, demonstrating high
performance close to that of models specialized in NER by carefully selecting
the examples provided to the LLMs (Wang et al., 2023). This indicates the
effectiveness of utilizing LLMs’ advanced text comprehension abilities for NER
tasks. On the other hand, inference with LLMs requires significant
computational resources and involves lengthy latency before obtaining
inference results, making them unsuitable for applications requiring the rapid
processing of huge amounts of text data. Therefore, we believe it is crucial
to develop approaches that leverage the language understanding capabilities of
LLMs while requiring fewer computational resources and achieving faster NER
task processing. Consequently, we focus on improving the quality of datasets
used for training NER models with the aid of LLMs, aiming to enhance the
performance of smaller, faster, dedicated NER models.

The performance and effectiveness of NER models rely heavily on the quality of
annotations in the datasets used during their training (Mitkov et al., 2000).
Currently, the majority of datasets employed for training NER models are
annotated manually by humans. This manual annotation process is fraught with
several challenges, such as inconsistent quality of annotations, the presence
of missed and incorrect annotations, significant time and financial costs, and
the need for ethical considerations when dealing with text data that may
contain offensive content, among others (Katiyar & Cardie, 2018; Fort et al.,
2011).

In this study, we propose a novel approach to address these issues,
particularly the problems of missed annotations and the time and financial
costs associated with manual annotation, intending to enhance the quality of
datasets and thereby strengthen the performance and effectiveness of NER
models. Our proposed method leverages LLMs to supplement the missed
annotations in datasets that have been manually annotated (where the presence
of missed annotations is assumed) as shown in Figure 1. By utilizing a hybrid
approach that combines manual annotations with annotations generated by large
LLMs, we aim to recover from the noise introduced by missed annotations in the
dataset, thereby enhancing the quality of the datasets used for training NER
models at a low cost and in an automated manner.

Figure 1: LLM-based annotation and label mixing.

In our proposed method, a detailed analysis of the annotations by LLMs
revealed that a single expression could be assigned multiple named entity
labels. Also, an imbalance in the data volume per label exists, which in turn
causes performance disparities among labels in the NER model. This is
particularly critical in the “Miscellaneous” category, where such inequalities
are most pronounced. To address these issues, we implemented a label mixing
technique for the multiple assigned named entity labels, thereby ensuring the
robustness of the NER model by mixing these labels.

In the experiments, the CoNLL03 (Tjong Kim Sang & De Meulder, 2003) and
WikiGold (Balasuriya et al., 2009) datasets were enhanced using our proposed
hybrid annotation method combining manual human efforts and LLMs, and the
improved datasets were then used to train a BERT-based (Devlin et al., 2019)
NER specialized model. The experimental results demonstrated that our proposed
approach could achieve high performance in training NER models with datasets
containing noise such as missed annotations, despite requiring minimal
financial cost.

The contributions of this study can be summarized in three main points:

  * •

We propose a hybrid annotation method combining manual human efforts and LLMs
for NER datasets, automatically recovering from noise such as missed
annotations contained within the datasets (Figure 2).

  * •

By incurring only a minimal financial cost, we enhance the performance of NER-
specialized models (Table 1).

  * •

In response to the issue of imbalance among named entity labels arising from
LLM-based annotations, we propose a label mixing technique, ensuring the
robustness of the NER model (Figure 4).

##  2 Related Works

###  2.1 Reliability of NER datasets

The reliability of datasets used in NER tasks has been scrutinized. Studies,
such as the one presented in Han et al. (2023a), highlight the inherent errors
in these datasets. These inaccuracies range from mislabeled entities to
inconsistent categorization, impacting the overall performance and reliability
of NER systems (Mishra et al., 2020; Mitkov et al., 2000).

###  2.2 LLMs for NER tasks

Wang et al. (2023) attempted to utilize GPT, a large-scale language model
(LLM) (Brown et al., 2020; Ouyang et al., 2022), for annotation tasks and
validated its effectiveness. Additionally, they tested the output format and
improved annotation accuracy using few-shot learning. LLMs’ advantages for NER
tasks are high consistency and efficiency. Conventional methods trained with
manual annotation tend to vary due to annotator subjectivity and fatigue. In
addition, the annotation cost for LLMs is much cheaper than that of human
annotators. The disadvantage of their work is that the computational cost of
inference is very high each time. While their approach directly solves the NER
task, which differs, our approach includes augmenting and creating the NER
dataset from scratch.

###  2.3 Challenges and Remedies in Automatic Annotation

There are several challenges in automatic annotation. First, Ghosh et al.
(2023) proposes ACLM (Attention-map aware keyword selection for Conditional
Language Model fine-tuning), an attention map-based data expansion method to
address the problem of data imbalance. It should be noted, however, that this
method does not take advantage of LLMs. Next, Shen et al. (2023b) proposes
using multiple prompt templates to address the problem of multiple label
assignments to the same entity. Furthermore, DiffusionNER in Shen et al.
(2023a) and Zhang et al. (2022) address the issues of noise and generative
bias by utilizing causality-based methods. To address these issues, we propose
a hybrid approach that combines manual annotation with automatic LLMs
annotation.

Other related studies in NER that must be mentioned are Li et al. (2020) for a
comprehensive review of NER deep learning methods, Liu et al. (2021) addresses
noise from external knowledge bases, and Wang et al. (2022) propose MINER
(Mutual Information based Named Entity Recognition) for out-of-vocabulary
support.

While the above diverse approaches address the NER challenge, this study
proposes a unique methodology that focuses on improving the reliability of the
dataset itself and leads to better accuracy for NER tasks.

##  3 Methods

LLM-based Annotation

In linguistic data automation using LLM, the GPT-NER methodology, as
delineated in Wang et al. (2023), emerges as a paradigmatic example. This
method profoundly influences our study, harnessing LLMs to facilitate
automated annotation. Central to the GPT-NER strategy is the LLM’s capability
to discern and earmark specific entities within the text, encapsulating these
segments with distinct character strings, specifically “@@” and “##”. For
illustrative purposes, given an input such as “I live in Tokyo”, wherein the
objective is to pinpoint LOC (location) entities, the LLM’s output would be “I
live in @@Tokyo##”. This delineation effectively signifies the accurate
detection of “Tokyo” as a location entity, with the “@@” and “##” serving as
the entity’s boundaries.

Additionally, this approach empowers the LLM to apprehend both the intrinsic
properties of entities and their interplay with the input-output schema,
achieved through the integration of few-shot examples. In alignment with this
methodology, we have formulated the ensuing prompt structure. [l]Instructions
for the Large Language Model You are an excellent linguist.

Identify [target entity type] entities in given text.

If the text contains no [target entity type] entities, replicate the input
text without any changes.

Strictly adhere to the definition provided below.

Definition of [target entity type]:

[definition target entity type]

[Example $1$ Input]

[Example $1$ Output]

[Example $2$ Input]

[Example $2$ Output]

$\cdots$

[Example $K$ Input]

[Example $K$ Output]

Within this structured prompt design, the [target entity type] slot
accommodates various entity types, including but not limited to PER, ORG, LOC,
and MISC. Concurrently, the [definition target entity type] slot is allocated
for the explicit definition of these enumerated entity types. Moreover, the
[Example $K$ Input] and [Example $K$ Output] slots are respectively reserved
for the input text and its corresponding output text, collectively functioning
as few-shot examples.

As this prompt dictates, the entity recognition process is methodically
applied to each target entity type within the text targeted for annotation. In
scenarios where this strategy involves multiple iterations of annotation for
each type of entity, a single word may be assigned multiple different entity
types. To resolve instances of such overlapping entities, the simplest method
we adopt is to select one entity from those multiple assignments randomly.

The criterion for selecting few-shot examples is inspired by the GPT-NER
approach, entailing the selection of examples from validation data. This
selection is predicated on the cosine similarity between token embeddings
present in the input text.

Hybrid: LLM-Based and Manual Annotation

To enhance the quality of the NER dataset, we created Hybrid annotations by
merging annotations from LLMs with those generated manually. This merging
process involved carefully analyzing the annotations from both sources,
ensuring consistency and accuracy. The merged data combines all entity labels
from the manual data and those from LLM annotation that do not overlap the
same position as those from the manual data. Since the entity labels of the
manual data are expected to be of higher quality than the ones from LLM
annotation, they are merged in preference to the ones from LLM annotation. The
merged dataset offers a more robust and diverse set of annotations, mitigating
biases and errors that might exist in either of the individual sources.

Figure 2: Comparison of model performance when using noised and datasets
annotated by Hybrid approach.

Label Mixing in LLM-Based Annotation

Addressing the issue, as mentioned earlier, of multiple labels being assigned
to a single word, we extended the Mixup (Zhang et al., 2018) technique,
traditionally used in image processing, to NER tasks. Mixup is a data
augmentation method that improves model performance and robustness by mixing
two inputs and outputs. Our approach involves blending two different entity
labels for a single token to create new annotations. This method is formally
represented as follows:

$y_{\text{mix}}=\lambda\times y_{i}+(1-\lambda)\times y_{j}$

Where $y_{i}$ and $y_{j}$ are two labels annotated NER tags, and
$\lambda\in[0,1]$ is a parameter determining the mixing ratio. Following the
mixup technique (Zhang et al., 2018), $\lambda$ is drawn from the beta
distribution ($\alpha=\beta=0.2$). Compared to randomly selecting one label
from multiple labels assigned to a single word, this technique contributes to
a more nuanced understanding of tokens that could belong to multiple entity
types, enhancing the dataset’s richness and classification flexibility.

##  4 Experiments

Budget | #Manual | #LLM | F1 Score
---|---|---|---
$38 | 87 | 0 | 0.02
70 | 702 | 0.81
35 | 2106 | 0.84
0 | 3510 | 0.85
$152 | 351 | 0 | 0.63
280 | 2808 | 0.85
140 | 8424 | 0.87
0 | 14041 | 0.86
$608 | 1404 | 0 | 0.86
1263 | 5616 | 0.87
1123 | 11232 | 0.87
Table 1: Comparison between different data count balances from manual and LLM-
based data under the fixed budgets.

###  4.1 Setup

In our research, we conducted experiments using two distinct datasets.
Firstly, we employed the CoNLL03 dataset (Tjong Kim Sang & De Meulder, 2003),
recognized as a standard benchmark in the field of NER. Additionally,
acknowledging recent advancements in this field models that have led to a
saturation in performance improvements on the CoNLL03 dataset, we also
included the WikiGold dataset (Balasuriya et al., 2009). The WikiGold dataset
was specifically chosen due to its higher level of challenge and the
observation that performance levels achieved on it have not yet paralleled
those on the CoNLL03 dataset. This was split into training, validation, and
test sets in a 7:1:2 ratio for the experiments.

For the automated annotation process, we leveraged ChatGPT
(gpt-3.5-turbo-0613) API111https://chat.openai.com as LLM, and we set the
number of few-shot examples at 32.

Finally, to validate the effectiveness of our annotation approach, we fine-
tuned a sequence classification model based on a pre-trained BERT (Devlin et
al., 2019), utilizing the datasets annotated through this methodology. The
evaluation of the NER task is in line with Tjong Kim Sang & De Meulder (2003),
and we present weighted average F1 scores in this paper.

A detailed description of the hardware and software configurations is also
provided in Appendix appendix A to ensure reproducibility.

###  4.2 Results

Noise Recovery with LLM-based Annotations:

We assessed the capability of LLM-based annotations to recover from noisy
data. Han et al. (2023b) pointed out some annotation errors, such as missing
annotations or label switching, in the CoNLL03 dataset (Tjong Kim Sang & De
Meulder, 2003). We prepared noised data that reproduces this problem by
removing annotations for some entity annotations. We show that it can be
improved by combining LLM-based annotation in the previously described manner.
We experimented with 20%, 40%, 60%, 80% entity annotations removed. By
comparing the noised datasets to those enhanced through our proposed combining
methodology, we established a baseline for improvement. Figure 2 presents a
comparative analysis of these datasets, highlighting the efficiency of our
approach to noise reduction. It was shown that even when noise is severe, it
can be significantly improved by combining LLM-based annotations.

Figure 3: Number of annotations for each entity type in the manual, noised,
and LLM-based datasets.

Comparison Under the Same Budget:

We evaluated our approach under identical budget constraints by drawing
parallels with the study of Ding et al. (2023). Our experiments were conducted
on three different budgets. We created composite datasets including different
numbers of samples from manual and LLM-based annotations. The middle budget
($152) is the cost of LLM-based annotation of all training data of the CoNLL03
dataset, and the costs of a quarter and a quadruple of it are assumed for
small ($38) and large ($608) budgets, respectively. The relationship between
the balance of the number of data in each budget and performance is shown in
Table 1.

When the budget is small ($38), training is not possible with only manual data
due to the small amount of data. Table 1 shows that it is thought that
performance can be improved by using LLM-based annotations to increase the
training data. For the middle budget ($152), the model’s performance was
reduced using only the manual data; using just 2,808 LLM-based annotations
showed a significant improvement. In addition, the performance of the Hybrid
annotations was higher than that of LLM-based alone, suggesting that the use
of both annotations contributes to the performance. For the large budget
($608), the performance is sufficient with 1,404 manual data, but a slight
performance improvement was confirmed by reducing the manual data and using
LLM-based as well. The results show that the composite datasets can increase
the number of data at a low cost and improve the performance of downstream
tasks under all budgets.

Addressing the Imbalanced Class Issue:

Figure 3 shows that there is a difference in the number of annotations for
each entity type. This imbalance issue is even greater with annotation by LLM.
Also, the performance difference of LLM-based annotation per entity type is
large compared to manual annotation. To tackle the class imbalance issue, we
motivated the use of our proposal, label mixing. We present the comparison
between LLM-based annotation and label mixing in Figure 4. Label mixing
reduced the performance difference between entity types. Therefore, we believe
that soft labeling of LLM-based annotations according to possible entities
rather than one-hot hard labels will prevent model training in a biased
manner.

Figure 4: Improvement of each entity type and micro average with label mixing. | CoNLL03 | WikiGold
---|---|---
| ORG | LOC | MISC | ORG | LOC | MISC
PER | 72 | 37 | 15 | 13 | 5 | 1
ORG | - | 180 | 59 | - | 44 | 41
LOC | - | - | 158 | - | - | 5
Table 2: The number of entities overlapping among classes in the CoNLL03 and
WikiGold dataset.

In addition to the analysis above, we further explore the impact of LLM-based
annotations and label mixing on the CoNLL03 and WikiGold datasets,
particularly focusing on the number of entities that overlap between two
classes. Table 2 presents a detailed quantification of these overlapping
entities between different entity types when annotated by LLM. The fact that
the entities overlapping between classes constitute only 521 cases (2.65%) of
the CoNLL03 dataset and 109 cases (6.80%) of the WikiGold dataset, and yet the
application of label mixing to these specific data points results in a
performance improvement across the dataset, is a suggestive observation. This
observation implies that the strategic application of label mixing to even a
small subset of data can improve the performance balance between entity types.
Moreover, the fact that the number of entities overlapping between classes
such as LOC and MISC with ORG is comparatively higher than other combinations,
while there is less overlap between PER and MISC, indicates a potential
challenge in the discriminatory capability of LLM-based annotations for the
former combinations. These observations support the effectiveness of label
mixing as a technique to buffer these shortcomings, suggesting that it serves
as a valuable strategy for improving the robustness and performance of NER
models.

##  5 Discussion and Conclusion

Our study extends the use of LLMs beyond annotation tasks. We identified and
addressed new NER annotation challenges, proposing novel solutions. Our
integration of LLM-based annotations with manual annotation, especially in
datasets with noise or limited samples, significantly enhances downstream task
performance. This method leverages LLMs’ evolving strengths (Zhao et al.,
2023; Min et al., 2023) and introduces label mixing to address biases and
imbalances from LLM-based annotations. Our work illuminates LLMs’ role in
enhancing NER, underscoring the need for ongoing adaptation and improvement in
annotation methodologies.

##  6 Ethical Considerations

In our research, we focus not on generating text, but on the automation of
annotations. This approach places concerns about creating potentially harmful
sentences outside our scope of study. However, while our primary objective is
to annotate entities with labels, it is essential to consider the implications
of certain annotations, such as the toxicity of entities, especially when
these annotations pertain to specific demographic groups.

This risk stems from biases inherent in the LLMs used for annotation,
necessitating continuous monitoring.

##  7 Limitations

Finally, we would like to mention the limitations of our work. As the first
limitation, we have only validated our proposed methods with relatively small
datasets, CoNLL03 and Wikigold, thus requiring validation with larger NER
datasets, such as OntoNotes 5.0 (Weischedel et al., 2013).

Another limitation is that when using the ChatGPT (gpt-35-turbo-0613) API,
some regions and organizations are not generated due to their alignment. It is
conceivable that this kind of alignment-based distribution bias could affect
NER task performance.

The final limitation involves the LLM-based annotation method for NER tasks,
which requires computational costs proportional to the number of entity types.
Thus, algorithms independent of entity type count are needed.

## References

  * Aliod et al. (2006) Diego Mollá Aliod, Menno van Zaanen, and Daniel Smith.  Named entity recognition for question answering.  In _Australasian Language Technology Association Workshop_ , 2006.  URL https://api.semanticscholar.org/CorpusID:14715684.
  * Babych & Hartley (2003) Bogdan Babych and Anthony F. Hartley.  Improving machine translation quality with automatic named entity recognition.  _Proceedings of the 7th International EAMT workshop on MT and other Language Technology Tools, Improving MT through other Language Technology Tools Resources and Tools for Building MT - EAMT ’03_ , 2003.  URL https://api.semanticscholar.org/CorpusID:6516117.
  * Balasuriya et al. (2009) Dominic Balasuriya, Nicky Ringland, Joel Nothman, Tara Murphy, and James R. Curran.  Named entity recognition in Wikipedia.  In _Proceedings of the 2009 Workshop on The People’s Web Meets NLP: Collaboratively Constructed Semantic Resources (People’s Web)_ , pp. 10–18, Suntec, Singapore, August 2009. Association for Computational Linguistics.  URL https://aclanthology.org/W09-3302.
  * Brown et al. (2020) Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei.  Language models are few-shot learners, 2020.
  * Cheng & Erk (2019) Pengxiang Cheng and Katrin Erk.  Attending to entities for better text understanding.  _ArXiv_ , abs/1911.04361, 2019.  URL https://api.semanticscholar.org/CorpusID:207852851.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pp. 4171–4186, Minneapolis, Minnesota, June 2019. Association for Computational Linguistics.  doi: 10.18653/v1/N19-1423.  URL https://aclanthology.org/N19-1423.
  * Ding et al. (2023) Bosheng Ding, Chengwei Qin, Linlin Liu, Yew Ken Chia, Boyang Li, Shafiq Joty, and Lidong Bing.  Is GPT-3 a good data annotator?  In _Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 11173–11195, Toronto, Canada, July 2023. Association for Computational Linguistics.  doi: 10.18653/v1/2023.acl-long.626.  URL https://aclanthology.org/2023.acl-long.626.
  * Etzioni et al. (2005) Oren Etzioni, Michael J. Cafarella, Doug Downey, Ana-Maria Popescu, Tal Shaked, Stephen Soderland, Daniel S. Weld, and Alexander Yates.  Unsupervised named-entity extraction from the web: An experimental study.  _Artif. Intell._ , 165:91–134, 2005.  URL https://api.semanticscholar.org/CorpusID:7162988.
  * Fort et al. (2011) Karën Fort, Gilles Adda, and Kevin Bretonnel Cohen.  Amazon mechanical turk: Gold mine or coal mine?  _Computational Linguistics_ , pp. 413–420, 2011.
  * Ghosh et al. (2023) Sreyan Ghosh, Utkarsh Tyagi, Manan Suri, Sonal Kumar, S Ramaneswaran, and Dinesh Manocha.  Aclm: A selective-denoising based generative data augmentation approach for low-resource complex ner.  _arXiv preprint arXiv:2306.00928_ , 2023.
  * Guo et al. (2009) Jiafeng Guo, Gu Xu, Xueqi Cheng, and Hang Li.  Named entity recognition in query.  In _Proceedings of the 32nd International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’09, pp. 267–274, New York, NY, USA, 2009. Association for Computing Machinery.  ISBN 9781605584836.  doi: 10.1145/1571941.1571989.  URL https://doi.org/10.1145/1571941.1571989.
  * Han et al. (2023a) Ridong Han, Tao Peng, Chaohao Yang, Benyou Wang, Lu Liu, and Xiang Wan.  Is information extraction solved by chatgpt? an analysis of performance, evaluation criteria, robustness and errors.  _ArXiv_ , abs/2305.14450, 2023a.  URL https://api.semanticscholar.org/CorpusID:258865200.
  * Han et al. (2023b) Ridong Han, Tao Peng, Chaohao Yang, Benyou Wang, Lu Liu, and Xiang Wan.  Is information extraction solved by chatgpt? an analysis of performance, evaluation criteria, robustness and errors, 2023b.
  * Katiyar & Cardie (2018) Arzoo Katiyar and Claire Cardie.  Nested named entity recognition revisited.  In _North American Chapter of the Association for Computational Linguistics_ , 2018.  URL https://api.semanticscholar.org/CorpusID:44170949.
  * Li et al. (2020) Jing Li, Aixin Sun, Jianglei Han, and Chenliang Li.  A survey on deep learning for named entity recognition.  _IEEE transactions on knowledge and data engineering_ , 34(1):50–70, 2020.
  * Liu et al. (2021) Kun Liu, Yao Fu, Chuanqi Tan, Mosha Chen, Ningyu Zhang, Songfang Huang, and Sheng Gao.  Noisy-labeled ner with confidence estimation.  _arXiv preprint arXiv:2104.04318_ , 2021.
  * Min et al. (2023) Bonan Min, Hayley Ross, Elior Sulem, Amir Pouran Ben Veyseh, Thien Huu Nguyen, Oscar Sainz, Eneko Agirre, Ilana Heintz, and Dan Roth.  Recent advances in natural language processing via large pre-trained language models: A survey.  _ACM Computing Surveys_ , 56(2):1–40, 2023.
  * Mishra et al. (2020) Shubhanshu Mishra, Sijun He, and Luca Belli.  Assessing demographic bias in named entity recognition.  _arXiv preprint arXiv:2008.03415_ , 2020.
  * Mitkov et al. (2000) Ruslan Mitkov, Constantin Orasan, and Richard J. Evans.  The importance of annotated corpora for nlp: the cases of anaphora resolution and clause splitting.  2000\.  URL https://api.semanticscholar.org/CorpusID:14801671.
  * Mohit (2014) Behrang Mohit.  Named entity recognition.  In _Natural language processing of semitic languages_ , pp. 221–245. Springer, 2014.
  * Ouyang et al. (2022) Long Ouyang, Jeff Wu, Xu Jiang, Diogo Almeida, Carroll L. Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, John Schulman, Jacob Hilton, Fraser Kelton, Luke Miller, Maddie Simens, Amanda Askell, Peter Welinder, Paul Christiano, Jan Leike, and Ryan Lowe.  Training language models to follow instructions with human feedback, 2022.
  * Shen et al. (2023a) Yongliang Shen, Kaitao Song, Xu Tan, Dongsheng Li, Weiming Lu, and Yueting Zhuang.  Diffusionner: Boundary diffusion for named entity recognition.  _arXiv preprint arXiv:2305.13298_ , 2023a.
  * Shen et al. (2023b) Yongliang Shen, Zeqi Tan, Shuhui Wu, Wenqi Zhang, Rongsheng Zhang, Yadong Xi, Weiming Lu, and Yueting Zhuang.  Promptner: Prompt locating and typing for named entity recognition.  _arXiv preprint arXiv:2305.17104_ , 2023b.
  * Tjong Kim Sang & De Meulder (2003) Erik F. Tjong Kim Sang and Fien De Meulder.  Introduction to the CoNLL-2003 shared task: Language-independent named entity recognition.  In _Proceedings of the Seventh Conference on Natural Language Learning at HLT-NAACL 2003_ , pp. 142–147, 2003.  URL https://aclanthology.org/W03-0419.
  * Wang et al. (2023) Shuhe Wang, Xiaofei Sun, Xiaoya Li, Rongbin Ouyang, Fei Wu, Tianwei Zhang, Jiwei Li, and Guoyin Wang.  Gpt-ner: Named entity recognition via large language models.  _ArXiv_ , abs/2304.10428, 2023.  URL https://api.semanticscholar.org/CorpusID:258236561.
  * Wang et al. (2022) Xiao Wang, Shihan Dou, Limao Xiong, Yicheng Zou, Qi Zhang, Tao Gui, Liang Qiao, Zhanzhan Cheng, and Xuanjing Huang.  Miner: Improving out-of-vocabulary named entity recognition from an information theoretic perspective.  _arXiv preprint arXiv:2204.04391_ , 2022.
  * Weischedel et al. (2013) Ralph Weischedel, Martha Palmer, Mitchell Marcus, Eduard Hovy, Sameer Pradhan, Lance Ramshaw, Nianwen Xue, Ann Taylor, Jeff Kaufman, Michelle Franchini, Mohammed El-Bachouti, Robert Belvin, and Ann Houston.  OntoNotes Release 5.0, 2013.  URL https://hdl.handle.net/11272.1/AB2/MKJJ2R.
  * Zhang et al. (2018) Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz.  mixup: Beyond empirical risk minimization.  In _International Conference on Learning Representations_ , 2018.  URL https://openreview.net/forum?id=r1Ddp1-Rb.
  * Zhang et al. (2022) Shuai Zhang, Yongliang Shen, Zeqi Tan, Yiquan Wu, and Weiming Lu.  De-bias for generative extraction in unified ner task.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pp. 808–818, 2022.
  * Zhao et al. (2023) Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, et al.  A survey of large language models.  _arXiv preprint arXiv:2303.18223_ , 2023.

## Appendix

##  Appendix A Details of Experiment Setup

Hardware Configurations:

In our experiments, we used virtual machines on Google Cloud. The detailed
machine specifications are as follows:

  * •

Machine type: n1 standard 4

  * •

Memory: 15 GB

  * •

virtual CPU: Intel Broadwell x 4

  * •

GPU: NVIDIA T4 x 1

BERT Configurations:

The configurations of BERT used for the performance evaluation are as follows:

  * •

Pre-trained model: bert-model-unbased 222https://huggingface.co/bert-base-
uncased

  * •

Learning rate: $1e-05$

  * •

Upper limit for norm of gradients: $10$

  * •

Batch size: $64$ for training, $32$ for inference

  * •

Max length of token: $128$

Each training was terminated when the F1 score on the validation set remained
unchanged for three consecutive epochs.

In NER, labels must be assigned at the word level, but BERT’s tokenizer often
splits a single word into multiple tokens. Therefore, in this study, when a
word is split into multiple tokens, when a word is split into multiple tokens,
the model adopts the label for the first token as the label for the entire
word.

##  Appendix B Datasets

CoNLL03 (Tjong Kim Sang & De Meulder, 2003):

The CoNLL-2003 dataset is designed to recognize four types of named entities,
including person names, place names, organization names, and other
miscellaneous entities. The data file consists of four columns: word, part-of-
speech tag, syntactic chunk tag, and named entity tag, with each item
separated by a space. The named entity and syntactic chunk tags use the I-TYPE
format 333This tag means ”Inside” and is assigned to words that are within an
entity of a specific type (TYPE). That is, this tag is used when a word is
part of a specific entity and indicates the type of that entity. For example,
”I-PER” indicates that the word is part of a person’s name (Person)., and the
B-TYPE 444The B in B-TYPE means ”Beginning” and is the tag given to the first
word of the second entity when directly followed by an entity of the same
type. This tag is used to indicate that a new entity is beginning and to
distinguish it from the previous entity. For example, ”B-PER” means that the
new person’s name begins with this word. tag is introduced to indicate the
start of a new phrase.

WikiGold (Balasuriya et al., 2009):

The Wikigold dataset is a manually annotated corpus for named entity
recognition consisting of a small sample of Wikipedia articles. Words are
labeled for each of the four named entity classes (LOC, MISC, ORG, and PER) of
CONLL-03 described above.