meets distribution testing
Yupan Liu[Email<EMAIL_ADDRESS>School of Computer Science and Engineering, The Hebrew University of Jerusalem

$\StoqMA$ captures the computational hardness of approximating the ground energy of local Hamiltonians that do not suffer the so-called sign problem.
We provide a novel connection between $\StoqMA$ and the distribution testing via reversible circuits.
First, we prove that easy-witness $\StoqMA$ (viz. $\eStoqMA$, a sub-class of $\StoqMA$) is contained in $\MA$.
Easy witness is a generalization of a subset state such that the associated set's membership can be efficiently verifiable, and all non-zero coordinates are not necessarily uniform.
Second, by showing distinguishing reversible circuits with random ancillary bits is $\StoqMA$-complete (as a comparison, distinguishing quantum circuits is $\QMA$-complete [27]), we construct soundness error reduction of $\StoqMA$.
This new $\StoqMA$-complete problem further signifies that $\StoqMA$ with perfect completeness ($\StoqMA_1$) is contained in $\eStoqMA$, which leads us to an alternating proof for $\StoqMA_1 \subseteq \MA$ previously proved in [6, 13].
Additionally, we show that both variants of $\StoqMA$ that without any random ancillary bit and with perfect soundness are contained in $\NP$.
Our results make a step towards collapsing the hierarchy $\MA \subseteq \StoqMA \subseteq \SBP$ [6], in which all classes are contained in $\AM$ and collapse to $\NP$ under derandomization assumptions.

§ INTRODUCTION

This tale originates from Arthur-Merlin protocols, such as complexity classes $\MA$ and $\AM$, introduced by Babai [5].
$\MA$ is a randomized generalization of the complexity class $\sf NP$, namely the verifier could take advantage of the randomness.
$\AM$ is additionally allowing two-message interaction.
Surprisingly, two-message Arthur-Merlin protocols are as powerful as such protocols with a constant-message interaction, whereas it is a long-standing open problem whether $\MA=\AM$.
It is evident that ${\sf NP} \subseteq {\MA} \subseteq {\AM}$.
Moreover, under well-believed derandomization assumptions [32, 34], these classes collapse all the way to $\sf NP$.
Despite limited progress on proving $\MA=\AM$, is there any intermediate class between $\MA$ and $\AM$?

$\StoqMA$ is a natural class between $\MA$ and $\AM$, initially introduced by Bravyi, Bessen, Terhal [6].
$\StoqMA$ captures the computational hardness of the stoquastic local Hamiltonian problems.
The local Hamiltonian problem, defined by Kitaev [29], is substantially approximating the minimum eigenvalue (a.k.a. ground energy) of a sparse exponential-size matrix (a.k.a. local Hamiltonian) within inverse-polynomial accuracy.
Stoquastic Hamiltonians [8] are a family of Hamiltonians that do not suffer the sign problem, namely all off-diagonal entries in the Hamiltonian are non-positive.
$\StoqMA$ also plays a crucial role in the Hamiltonian complexity – $\StoqMA$-complete is a level in the complexity classification of $2$-local Hamiltonian problems on qubits [16, 11], along with $\PTIME$, $\NP$-complete, and $\QMA$-complete.

Inspiring by the Monte-Carlo simulation in physics, Bravyi and Terhal [6, 13] propose a $\MA$ protocol for the stoquastic frustration-free local Hamiltonian problem, which further signifies $\StoqMA$ with perfect completeness ($\StoqMA_1$) is contained in $\MA$.
A uniformly-restricted variant[It is the projection uniform stoquastic local Hamiltonian problem, namely each local term in Hamiltonian is exactly a projection. See Definition 2.10 in [2]. ] of this problem, which is also referred to as $\SetCSP$ [1][Namely, a modified constraint satisfaction problem where both constraints and satisfied assignments are a subset. ], essentially captures the $\MA$-hardness.

To characterize $\StoqMA$ through the distribution testing lens, we begin with an informal definition of $\StoqMA$ and leave the details in <Ref>.
For a language $\calL$ in $\StoqMA$, there exists a verifier $V_x$ that takes $x \in \calL$ as an input, where the verifier's computation is given by a classical reversible circuit, viewed as a quantum circuit.
Besides a non-negative state[A witness here could be any quantum state, but the optimal witness is a nonnegative state, see <Ref>. ] in the verifier's input as a witness, to utilize the randomness, ancillary qubits in the verifier's input consist of not only state $\ket{0}$ but also $\ket{+} := (\ket{0}+\ket{1})/\sqrt{2}$.
After applying the circuit, the designated output qubit is measured in the Hadamard basis[It is worthwhile to mention that we can analogously define $\MA$ [8] (see <Ref>), namely replacing the measurement on the output qubit by the computational basis. ].
A problem is in $\StoqMA(a,b)$ for some $a>b \geq 1/2$, if for yes instances, there is a witness making the verifier accept with probability at least $a$; whereas for no instances, all witness make the verifier accepts with probability at most $b$.
The gap between $a$ and $b$ is at least an inverse polynomial since error reduction for $\StoqMA$ is unknown.

The optimality of non-negative witness suggests a novel connection to the distribution testing.
Let $\ket{0}\ket{D_0}+\ket{1}\ket{D_1}$ be the state before the final measurement, where $\ket{D_k}=\sum_{i\in\binset^{n-1}} \sqrt{D_k(i)} \ket{i}$ for $k=0,1$ and $n$ is the number of qubits utilized by the verifier.
A straightforward calculation indicates that the acceptance probability of a $\StoqMA$ verifier is linearly dependent to the squared Hellinger distance $d^2_H(D_0,D_1)$ between $D_0$ and $D_1$, which indeed connects to the distribution testing!
Consequently, to prove $\StoqMA \subseteq \MA$, it suffices to approximate $d^2_H(D_0,D_1)$ within an inverse-polynomial accuracy using merely polynomially many samples[Each sample is actually the measurement outcome on an independent copy of the verifier, see <Ref>. ].

§.§ Main results

$\StoqMA$ with an easy witness ($\eStoqMA$).

With this connection to the distribution testing, it is essential to take advantage of the efficient query access of a non-negative witness where a witness satisfied this condition is so-called an easy witness.
For such a sub-class of $\StoqMA$, viz. $\eStoqMA$, such that there exists an easy witness for any yes instances, we are then able to show an $\MA$ containment by utilizing both query and sample accesses to the witness.
Informally, an easy witness is a generalization of a subset state such that the associated state's membership is efficiently verifiable, and all non-zero coordinates are needlessly uniform.
It is evident that a classical witness is also an easy witness, but the opposite is not necessarily true (See <Ref>).
Now let us state our first main theorem:

$\eStoqMA = \MA$.

It is worthwhile to mention that easy witness also relates to $\SBP$ (Small Bounded-error Probability) [10].
In particular, Goldwasser and Sipser [23] propose the celebrated Set Lower Bound protocol – it is an $\AM$ protocol for the problem of approximately counting the cardinality of such an efficient verifiable set.
Recently, Watson [43] and Volkovich [41] separately point out such a problem is essentially $\SBP$-complete.

Even though $\eStoqMA$ seems only a sub-class of $\StoqMA$, we could provide a simplified alternating proof for $\StoqMA_1 \subseteq \MA$ [6, 13].
Namely, employing the local verifiability of $\SetCSP$ [1], it is evident to show that $\eStoqMA$ contains $\StoqMA$ with perfect completeness, which infers $\StoqMA_1 \subseteq \MA$ by <Ref>.
However, it remains open whether all $\StoqMA$ verifier has an easy witness, whereas an analogous statement is false for classical witnesses (see <Ref>).

Reversible Circuit Distinguishability is $\StoqMA$-complete.
It is well-known that distinguishing quantum circuits (a.k.a. the Non-Identity Check problem), namely given two efficient quantum circuits and decide whether there exists a pure state that distinguishes one from the other, is $\QMA$-complete [27].
Moreover, if we restrict these circuits to be reversible (with the same number of ancillary bits), then this variant is $\NP$-complete [26].
What happens if we also allow randomized ancillary bits, viewed as quantum circuits with ancillary qubits which is initially state $\ket{+}$? It seems reasonable to believe this variant is $\MA$-complete; however, it is actually $\StoqMA$-complete, as stated in <Ref>:

Distinguishing reversible circuits with ancillary random bits within an inverse-polynomial accuracy is $\StoqMA$-complete.

In fact, <Ref> is a consequence of the distribution testing explanation of a $\StoqMA$ verifier's maximum acceptance probability.
We can view <Ref> as new strong evidence of $\StoqMA=\MA$.
It further straightforwardly infers a simplified proof of [26]:

Distinguishing reversible circuits without ancillary random bits is $\NP$-complete.

Apart from the role of the randomness, <Ref> is analogous for $\StoqMA$ regarding the well-known derandomization property [19] of Arthur-Merlin systems with perfect soundness:

$\StoqMA$ with perfect soundness is contained in $\NP$.

Notably, the $\NP$-containment in <Ref> holds even for $\StoqMA(a,b)$ verifiers with an arbitrarily small gap $a-b$.
It is fairly surprising since $\StoqMA(a,b)$ with an exponentially small gap at least contains $\NP^{\PP}$ [33], but such a phenomenon does not appear here.

Soundness error reduction of $\StoqMA$.
Error reduction is a rudimentary property of many complexity classes, such as $\PTIME$, $\BPP$, $\MA$, $\QMA$, etc. .
It is peculiar that such property of $\StoqMA$ is wide-open, even though this class has been proposed since 2006 [6].
An obstacle follows from the limitation of performing a single-qubit Hadamard basis final measurement, so we cannot take the majority vote of outcomes from the verifier's parallel repetition directly.

Utilizing the gadget in the proof of <Ref>, we have derived soundness error reduction of $\StoqMA$, which means we could take the conjunction of verifier's parallel repetition's outcomes:

For any polynomial $r=\poly(n)$,

\[\StoqMA\left(\frac{1}{2}+\frac{a}{2},\frac{1}{2}+\frac{b}{2}\right) \subseteq \StoqMA\left(\frac{1}{2}+\frac{a^r}{2},\frac{1}{2}+\frac{b^r}{2}\right).\]

§.§ Proof overview

$\eStoqMA \subseteq \MA$ from distribution testing.
As mentioned before, the maximum acceptance probability of a $\StoqMA$ verifier is substantially approximating the Hellinger distance $d_H^2(D_0,D_1)$ between (sub-)distributions $D_0,D_1$ associated with the state $\ket{0}\ket{D_0}+\ket{1}\ket{D_1}$ before the final measurement.
It seems plausible to prove $\StoqMA\subseteq\MA$ by taking samples and post-processing.
However, the known sample complexity lower bound (See <Ref>) indicates that (almost) exponentially many samples are necessary.
Fortunately, we could circumvent this barrier for showing $\eStoqMA \subseteq \MA$, since an easy witness guarantees efficient query access to $D_0,D_1$.
In particular, employing both sample and query oracle accesses to $D_0,D_1$, such approximation of the squared Hellinger distance $d_H^2(D_0,D_1)$ needs merely polynomially many samples!
This advantage first noticed by Rubinfeld and Servedio [36], and then almost fully characterized by Canonne and Rubinfeld [17]. We leave the details in <Ref>.
Recently, this technique also has algorithmic applications: it is used in quantum-inspired classical algorithms for machine learning [39, 15].

The main idea is writing the acceptance probability $\Pacc$ of a $\StoqMA$ verifier's easy witness as an expectation over $D_1$ (or $D_0$) of some random variable regarding coordinates in $D_0,D_1$.
By a standard concentration bound, it is desirable to approximate $\Pacc$ with a polynomially small additive error utilizing only polynomially many sample and query oracle accesses. The details of the implementation of these oracles can be found in <Ref>.
Equipped with this idea, we indeed obtain an $\MA$-containment of $\eStoqMA$.

Distinguishing reversible circuits by mimicking the SWAP test.

We begin with the SWAP test for distinguishing two quantum states [7], since it could be thought as a $\StoqMA$ verification circuit with the maximum acceptance probability $1$.
The SWAP test thus inspires a procedure to distinguish two reversible circuits $C_0,C_1$ using a non-negative witness: starting with a $\ket{+}$ ancillary qubit as a control qubit, first run the controlled-$C_0$, then apply an $X$ gate on the control qubit, then run the controlled-$C_1$; finally, measure the control qubit on the Hadamard basis.

Recall that a single-qubit Hadamard-basis measurement is linearly dependent to the squared Hellinger distance $d_H^2(D_0,D_1)$, where $D_i (i=0,1)$ is a coefficient vector associated with the given non-negative witness for all indices starting at $i$.
In our procedure, $D_0$ corresponds to the state that applying a reversible circuit $C_0$ on given witness $\ket{w}$ and ancillary qubits, and so does $D_1$, which infers the $\StoqMA$ containment.
The $\StoqMA$-hardness proof is straightforward: replacing $C_0$ and $C_1$ by identity and $V_x^{\dagger} X_1 V_x$, respectively, where $V_x$ is the given $\StoqMA$ verification circuit.

We then provide the intuition that $\StoqMA$ with perfect soundness is in $\NP$.
By an analogous idea in [19], we could find two matched pairs $(s,r)$ and $(s',r')$ as a classical witness, where $s,s'$ are indices of non-zero coordinates in the given witness, and $r,r'$ are random binary strings.
Specifically, for yes instances, there exist two such pairs such that the resulting strings $C_0(s,r)$ [Namely, a reversible circuit takes $(s,r)$ as an input, and permute it to the other binary string as the output. ] and $C_1(s',r')$ are identical; whereas it is evident that no matched pairs exist for no instances.

A conjunction of $\StoqMA$ verifiers' parallel repetition's outcomes.
Even though we cannot perform a majority vote of parallel repetitions of a $\StoqMA$ verifier, we still could take a conjunction of repetitive $\StoqMA$ verifiers' outcomes (a.k.a. AND-type repetition procedure).
Given a $\StoqMA$ verification circuit $V_x$, we result in a new $\StoqMA$ verifier by separately substituting an identity and $V_x^{\dagger} X_1 V_x$ for $C_0$, $C_1$.
Notice the acceptance probability of a $\StoqMA$ verifier's non-negative witness is linearly dependent to an inner product of two distributions, we could take advantage of this new $\StoqMA$ verifier by running many copies of these reversible circuits parallelly with the same target qubit.
For yes instancesm it follows that an inner product of two tensor products of distributions is equal to the product of inner products of these distributions.

However, it seems problematic for no instances, since a dishonest prover probably wants to cheat with an entangled witness instead of a tensor product among each repetitive verifiers.
We resolve this issue by an observation used in the $\QMA$ error reduction [31]: the maximum acceptance probability of a verifier $V_x$ is the same as the maximum eigenvalue of a projection $V_x^{\dagger} \Pi_1 V_x$ where $\Pi_1$ is the final measurement on the designated output qubit.
Eventually, an entangled witness will not help a dishonest prover.
This is because the maximum eigenvalue of the tensor product of the projection $V_x^{\dagger} \Pi_1 V_x$ is also the product of the maximum eigenvalue of this projection, which further leads us to soundness error reduction of $\StoqMA$ as <Ref>.

§.§ Discussion and open problems

Towards $\SBP = \MA$.
As stated before, it is known $\MA \subseteq \StoqMA \subseteq \SBP \subseteq \AM$ [6, 10].
Note a subset state associated with an efficient membership-verifiable set is an easy witness.
Could we utilize this connection and deduce a proof of $\SBP \subseteq \eStoqMA$?

Owing to the wide uses of the Set Lower Bound protocol [23], such a solution would be a remarkable result with many complexity-theoretic applications.
Unfortunately, even a $\QMA$ containment for this kind of approximate counting problem is unknown.
Despite such smart usage of the Grover algorithm implies an $O(\sqrt{2^n/|S|})$-query algorithm [12, 4, 40], we are not aware of utilizing a quantum witness.
Furthermore, an oracle separation between $\SBP$ and $\QMA$ [3] suggests that such a proof of $\SBP \subseteq \QMA$ is supposed to be in a non-black-box approach, which signifies a better understanding beyond a query oracle is required.

Besides $\SBP$ vs. $\MA$, it remains open whether $\StoqMA=\MA$.
It is natural to ask whether each $\StoqMA$ verifier has an easy witness.
However, we even do not know how to prove $\StoqMA(1-a,1-1/\poly(n))$ has an easy witness, where $a$ is negligible (i.e., an inverse super-polynomial).
In [2], they prove $\StoqMA(1-a,1-1/\poly(n)) \subseteq \MA$ by applying the probabilistic method on a random walk, whereas the existence of an easy witness seems to require a stronger structure[The candidate here is the set $S$ of all good strings (see <Ref>) of the given $\SetCSP$ instance, which is unnecessary the optimal witness. It is thus unclear whether the frustration of $S$ remains negligible. ].

Towards error reduction of $\StoqMA$.
Error reduction of $\StoqMA$ is an open problem since Bravyi, Bessen, and Terhal define this class in 2006 [6].
We first state this conjecture formally:

For any $a,b$ such that $1/2 \leq b < a \leq 1$ and $a-b \geq 1/\poly(n)$, the following holds for any polynomial $l(n)$:

\[\StoqMA(a,b) \subseteq \StoqMA\left(1-2^{-l(n)},\frac{1}{2}+2^{-l(n)}\right).\]

As [2] shows that $\StoqMA$ with a negligible completeness error is contained in $\MA$, (completeness) error reduction of $\StoqMA$ plays a crucial role in proving $\StoqMA=\MA$.
Instead of performing the majority vote among parallelly running verifiers, another commonplace approach is first reducing errors of completeness and soundness separately, then utilizing these two procedures alternatively with well-chosen parameters.
For instance, the renowned polarization lemma of $\SZK$ [37, 9], and the space-efficient error reduction of $\QMA$ [20].
Since <Ref> already states soundness error reduction of $\StoqMA$, is it possible to also construct a completeness error reduction?
Namely, a procedure that builds a new $\StoqMA(1/2+a'/2,1/2+b'/2)$ verifier from the given $\StoqMA(1/2+a/2,1/2+b/2)$ verifier such that $a'$ is super-polynomially close to $1$.
It seems to require new ideas since a direct analogue of the XOR lemma in the polarization lemma of $\SZK$, such as Lemma 4.11 in [9], does not work.

$\StoqMA$ with an exponentially small gap.
Fefferman and Lin prove [21] that $\sf PreciseQMA$ is as powerful as $\PSPACE$, where $\sf PreciseQMA$ is a variant of $\QMA(a,b)$ with an exponentially small gap $a-b$.
Moreover, we know that both $\sf PreciseQCMA$ and $\sf PreciseMA$ are equal to $\NP^{\PP}$ [33], where $\sf PreciseQCMA$ is a precise variant of $\QMA$ with a classical witness of the verifier.
It is evident that $\sf PreciseStoqMA$ is between $\NP^{\PP}$ and $\PSPACE$, also a variant of this class is exactly $\NP^{\PP}$ if we restrict the optimal witness to be classical.
Does $\sf PreciseStoqMA$ an intermediate class between $\NP^{\PP}$ and $\PSPACE$, or even strong enough to capture the full $\PSPACE$ power?

$\QMA$ with perfect soundness.
As we proved in <Ref>, $\StoqMA$ with perfect soundness is in $\NP$ where the promise gap could be arbitrarily small.
What about $\QMA$ with perfect soundness?
It is shown that this class is equivalent to $\NQP$ [30], which is also equivalent to $\mathsf{coC_{=}P}$.
Moreover, the exact variant of the Non-Identity Check is $\NQP$-complete [38].
Could we provide any new characterization of $\NQP$?

§.§ Paper organization

<Ref> introduces useful terminologies and notations.
<Ref> proves that easy-witness $\StoqMA$ is contained in $\MA$, which indicates a simplified proof of $\StoqMA_1 \subseteq \MA$, together with remarks on the limitations of classical-witness $\StoqMA$.
<Ref> presents a new $\StoqMA$-complete problem named reversible circuit distinguishability, and the complexity of this problem's exact variant, which infers $\StoqMA$ with perfect soundness is in $\NP$.
Employed with this new $\StoqMA$-complete problem, <Ref> provides error reduction of $\StoqMA$ regarding soundness error.

§ PRELIMINARIES

§.§ Quantum computing

We here review the terminologies and notations of quantum computation used in this paper. We further refer to textbooks [35, 31] for a detailed introduction.

An $n$-qubit quantum state is a unit vector in the Hilbert space $\qubits{n}$, where $\otimes$ is the tensor product. The computational basis for this Hilbert space is $\{ \ket{i}: i \in \binset^n \}$, also the Hadamard basis is $\{  \ket{i}: i \in \{+,-\}^n\}$ where $\ket{+}=(\ket{0}+\ket{1})/\sqrt{2}$ and $\ket{-}=(\ket{0}-\ket{1})/\sqrt{2}$.
For a quantum state $\ket{\psi}$, we denote $\bra{\psi}$ as its conjugate transpose.
The inner product between two vectors $\ket{\psi}$ and $\ket{\phi}$ is referred to as $\innerprod{\psi}{\phi}$ and their outer product as $\ketbra{\psi}{\phi}$.
For any vector $\ket{\psi} \in \qubits{n}$, its $l_2$-norm is defined as $\norm{\ket{\psi}}_2 :=  \left(\sum_{i \in \binset^n} |\innerprod{\psi}{i}|^2\right)^{1/2}$.

We then introduce some notations which is less commonplace and more particular for this paper:
the support of $\ket{\psi}$,  $supp(\ket{\psi}) := \{i \in \{0,1\}^n : \innerprod{\psi}{i} \ne 0\}$, is the set strings with non-zero amplitude.
A quantum state $\ket{\psi}$ is non-negative of $\innerprod{i}{\psi} \geq 0$ for all $i \in \{0,1\}^n$.
For any $S \subseteq \{0,1\}^n$, we refer the state $\ket{S} := \frac{1}{\sqrt{|S|}} \sum_{i \in S} \ket{i}$ to as  the subset state corresponding to the set $S$ [42].

§.§ Complexity classes

A (promise) problem $\calL = (\calL_{\rm yes}, \calL_{\rm no})$ consists of two non-overlapping subsets $\calL_{\rm yes}, \calL_{\rm no} \subseteq \{0,1\}^{*}$.
We now define the complexity classes that are considered in this paper using the language of reversible circuits.
We begin with a definition of $\MA$.

A promise problem $\calL = (\calL_{\rm yes}, \calL_{\rm no}) \in$ $\MA$ if there exists an $\MA$ verifier such that for any input $x \in \calL$, an associated uniformly generated verification circuit $V_x$ using only classical reversible gates (i.e. Toffoli, CNOT, X) on $n:=n_w+n_0+n_+$ qubits and a computational-basis measurement on the output qubit, where $n_w$ is the number of qubits for a witness, and $n_0~(\text{or }n_+)$ is the number of $\ket{0}~(\text{or }\ket{+})$ ancillary qubits, such that

Completeness.  If $x\in \calL_{\rm yes}$, then there exists an $n$-qubit non-negative state witness $\ket{w}$ such that $\Pr{V_x \text{ accepts } \ket{w}} \geq 2/3$.

Soundness.  If $x \in \calL_{\rm no}$, we have $\Pr{V_x \text{ accepts } \ket{w}} \leq 1/3$ for any $n$-qubit witness $\ket{w}$.

We refer the equivalence between <Ref> and the standard definition of $\MA$ to as <Ref>, which is firstly observed by [8].

The standard definition of $\MA$ only allows classical witnesses, viz. binary strings.
To show it is equivalent to <Ref>, it suffices to prove the optimal witness for yes instances is classical.
Notice that $\Pr{V_x \text{ accepts } \ket{w}} = \bra{\psi_{\rm in}} V_x^{\dagger} \Pi_{\rm out} V_x \ket{\psi_{\rm in}}$ where $\ket{\psi_{\rm in}}:=\ket{w}\otimes \ket{0}^{\otimes n_0} \otimes \ket{+}^{\otimes n_+}$ and $\Pi_{\rm out} = \ketbra{0}{0}_1\otimes I_{\rm else}$.
Since $V_x^{\dagger} \Pi_{\rm out} V_x$ is a diagonal matrix, the optimal witness of $V_x$ is clearly classical.

Analogously, we could define $\NP$ using classical reversible gates by setting $n_+=0$ in <Ref>.
Now we proceed with the definition of $\StoqMA$. Namely replacing the measurement on the output qubit by a Hadamard basis, this generalization leads to the complexity class $\StoqMA$:

A promise problem $\calL = (\calL_{\rm yes}, \calL_{\rm no}) \in$ $\StoqMA$ if there is a $\StoqMA$ verifier such that for any input $x \in \calL$, a uniformly generated verification circuit $V_x$ using Toffoli, CNOT, X gates on $n:=n_w+n_0+n_+$ qubits and a Hadamard-basis measurement on the output qubit, where $n_w$ is the number of qubits for a witness, and $n_0$ $(\text{or}~n_+)$ is the number of $\ket{0}$ $(\text{or}~\ket{+})$ ancillary qubits, such that for efficiently computable functions $a(n)$ and $b(n)$:

Completeness.  If $x\in \calL_{\rm yes}$, then there exists an $n$-qubit non-negative state witness $\ket{w}$ such that $\Pr{V_x \text{ accepts } \ket{w}} \geq a(n)$.

Soundness.  If $x \in \calL_{\rm no}$, we have $\Pr{V_x \text{ accepts } \ket{w}} \leq b(n)$ for any $n$-qubit witness $\ket{w}$.

Moreover, $a(n)$ and $b(n)$ satisfy $1/2 \leq b(n) < a(n) \leq 1$ and $a(n)-b(n) \geq 1/\poly(n)$.

Error reduction of $\StoqMA$ remains open since this class defined in 2006 [6] since this class does not permit amplification of gap between thresholds $a, b$ based on majority voting.
Hence, the completeness-soundness gap is at least an inverse polynomial. We leave the remarks regarding non-negativity of witnesses and parameters to <Ref>:

Owing to the Perron-Frobenius theorem (see Theorem 8.4.4 in [24]), a straightforward corollary is that $\psi$ maximizing the acceptance probability has non-negative amplitudes in the computational basis, namely it suffices to consider only non-negative witness for yes instances.
Additionally, it is clear-cut that the acceptance probability for any non-negative witness $\ket{\psi}$, regardless of the optimality, is at least $1/2$ by a direct calculation.

§.§ Distribution testing

Distribution testing is generally about telling whether one probability distribution is close to the other.
We further recommend a comprehensive survey [14] for a detailed introduction.

We begin with the squared Hellinger distance $d^2_H(D_0,D_1)$ between two (sub-)distributions $D_0,D_1$, where $d^2_H(D_0,D_1):=\frac{1}{2} \| \ket{D_0}-\ket{D_1}\|_2^2$ and $\ket{D_k} = \sum_{i} \sqrt{D_k(i)}\ket{i}$ for any $k=0,1$.
This distance is comparable with the total variation distance (see Proposition 1 in [18]).
We then introduce a specific model used for this paper, namely the dual access model:

Let $D$ be a fixed distribution over $[2^n]$. A dual oracle for $D$ is a pair of oracles $(\Sample{D},\Query{D})$:

* Sample access: $\Sample{D}$ returns an element $i\in[2^n]$ with probability $D(i)$. And it is independent of all previous calls to any oracle.

* Query access: $\Query{D}$ takes an input a query element $j\in[2^n]$, and returns the probability weight $D(j)$ that the distribution $D$ puts on $j$.

We then explain how to implement these oracles here in <Ref>:

The sample access oracle in <Ref> could be implemented by running an independent copy of the circuit that generates the state $\ket{0}\ket{D_0}+\ket{1}\ket{D_1}$, and measuring all qubits on the computational basis. Meanwhile, the query access oracle is substantially an efficient evaluation algorithm corresponding to the (sub-)distributions $D_0,D_1$.

In [17], Cannonne and Rubinfeld show that approximating the total variation distance between two distributions within an additive error $\epsilon$ requires only $\Theta(1/\epsilon^2)$ oracle accesses (see Theorems 6 and 7 in [17]).
However, suppose we allow to utilize only sample accesses. In that case, such a task requires $\Omega(N/\log N)$ samples even within constant accuracy (see Theorem 9 in [18]), where $N$ is the dimension of distributions.

§ $\STOQMA$ WITH EASY WITNESSES

In this section, we will prove $\StoqMA$ with easy witnesses, viz. $\eStoqMA$, is contained in $\MA$.
Easy witness is named in the flavor of the seminal easy witness lemma [25], which means that an $n$-qubit non-negative state witness of a $\StoqMA$ verifier has a succinct representation.
In particular, there exists an efficient algorithm to output the coordinate of the given index.
It is a straightforward generalization of subset states where the membership of the corresponding subset is efficiently verifiable.
We here define $\eStoqMA$ formally:

A promise problem $\calL=(\calL_{\rm yes},\calL_{\rm no}) \in \eStoqMA$ if there is a $\StoqMA$ verifier such that for any input $x \in \calL$, a uniformly generated verification circuit $V_x$ using only Toffoli, CNOT, X gates on $n:=n_w+n_0+n_+$ qubits and a Hadamard-basis measurement on the output qubit, where $n_w$ is the number of qubits for a witness, and $n_0~(\text{or } n_+)$ is the number of $\ket{0}~(\text{or } \ket{+})$ ancillary qubits, such that for efficiently computable functions $a(n)$ and $b(n)$:

Completeness. There exists an $n$-qubit non-negative witness $\ket{w}:=\sum_{i\in\binset^n} \sqrt{D_w(i)} \ket{i}$ such that $\Pr{V_x \text{ accepts } \ket{w}} \geq a(n)$, and there is an efficient algorithm $\Query{w}$ that outputs the coordinate $D_w(i)$ of the given index $i \in \binset^n$ in the distribution $D_w$.

Soundness. For any $n$-qubit witness $\ket{w}$, $\Pr{V_x \text{ accepts }\ket{w}} \leq b(n)$.

Moreover, $a(n)$ and $b(n)$ satisfy $1/2 \leq b(n) < \alpha(n) \leq 1$ and $a(n) - b(n) \geq 1/\poly(n)$.

Distribution testing techniques inspire an $\MA$ containment of $\eStoqMA$, as <Ref>.
Precisely, employed with the dual access model defined by Cannonne and Rubinfeld [17], we obtain an empirical estimation with an inverse-polynomial accuracy of an $\eStoqMA$ verifier's acceptance probability, where both sample complexity and time complexity are efficient.

For any $1/2 \leq b < a \leq 1$ and $a-b\geq 1/\poly(n)$,

\[\eStoqMA(a,b) \subseteq \MA\left(\tfrac{9}{16},\tfrac{7}{16}\right).\]

In [6, 13], Bravyi, Bessen, and Terhal proved $\StoqMA_1 \subseteq \MA$, utilizing a relatively complicated random walk based argument.
By taking advantage of $\eStoqMA$, we here provide a simpler proof by plugging <Ref> into <Ref>:

$\StoqMA_1 \subseteq \eStoqMA$.

The proof of <Ref> straightforwardly follows from the definition of $\SetCSP$ (see <Ref>), namely any $\SetCSP_{0,1/\poly}$ instance obviously has an easy witness, and it is indeed optimal.
We leave the technical details regarding $\SetCSP$ in <Ref>.

How strong is the $\eStoqMA$?
<Ref> suggests $\eStoqMA$ seems more powerful than $\cStoqMA$:

A classical witness is clearly also an easy witness, but the opposite is not necessarily true.
Even though Merlin could send the algorithm $\Query{D_w}$ as a classical witness to Arthur, Arthur merely can prepare $\ket{w}$ by a post-selection, which means $\cStoqMA$ does not trivially contain $\eStoqMA$.

Furthermore, the proof of $\StoqMA(a,b)$ with classical witnesses is in $\MA$ [22] could preserve completeness and soundness parameters. By inspection, it is clear-cut that this proof even holds when the gap $a-b$ is arbitrarily small, whereas the proof of <Ref> works only for inverse-polynomial accuracy.
Further remarks of classical witness' limitations can be found in <Ref>.

§.§ $\eStoqMA\subseteq \MA$: the power of distribution testing

To derive an $\MA$ containment of $\eStoqMA$, it suffices to distinguish two non-negative states within an inverse-polynomial accuracy regarding the inner product (i.e., squared Hellinger distance).
Utilizing both sample accesses and query accesses, we could approximate an acceptance probability of an $\eStoqMA$ verifier within an additive error $\epsilon$, and the number of required sample and query accesses are both $\Theta(1/\epsilon^2)$.
Our construction tightly follows Theorem 6 in [17].

In the dual access model, there is a randomized algorithm $\calT$ which takes an input $x$, $1/2 \leq b(|x|) < a(|x|) \leq 1$, as well as access to $(\Sample{D},\Query{D})$, where the quantum state before the measurement is $\ket{\psi} = \sum_{i\in[2^n]} \sqrt{D(i)} \ket{i}$. After making $O\left(1/(a-b)^2\right)$ calls to the oracles, $\calT$ outputs either accept or reject such that:

* If $\frac{1}{2}\|\ket{D_0}+\ket{D_1}\|_2^2 \geq a$, $\calT$ outputs accept with probability at least $9/16$;

* If $\frac{1}{2}\|\ket{D_0}+\ket{D_1}\|_2^2 \leq b$, $\calT$ outputs accept with probability at most $7/16$,

where $D_a~(a\in\binset)$ is a sub-distribution such that $\forall i \in \binset^{n-1}, D_a(i):=D(a||i)$.

To construct this algorithm $\calT$, we begin with estimating the quantity $\norm{\ket{D_0}+\ket{D_1}}_2^2/2\norm{D_1}_1$ up to some additive error $\epsilon := (a-b)/8$.
We first observe that

\begin{equation}
\label{eq:statistics-approx-PaccX}
\frac{\norm{\ket{D_0}+\ket{D_1}}_2^2}{2\norm{D_1}_1}
= \frac{1}{2} \sum_{i \in \binset^{n-1}} \left(1+\tfrac{\sqrt{D_0(i)}}{\sqrt{D_1(i)}}\right)^2 \frac{D_1(i)}{\|D_1\|_1}\\
= \mathop{\mathbb{E}}_{i \sim D_1/\norm{D_1}_1} \left[ \frac{1}{2} \left( 1+\tfrac{\sqrt{D_0(i)}}{\sqrt{D_1(i)}} \right)^2 \right].
\end{equation}

Since the inner product is symmetric, it also implies
$\frac{\norm{\ket{D_0}+\ket{D_1}}_2^2}{2\norm{D_0}_1} = \mathop{\mathbb{E}}_{i \sim D_0/\norm{D_0}_1} \left[ \frac{1}{2} \left( 1+\frac{\sqrt{D_1(i)}}{\sqrt{D_0(i)}} \right) \right]$.
Notice if $D_1(i)=0$ for some $i$, the corresponding point will never be sampled.
$\calT$ only require to achieve an empirical estimate of this expected value, which suffices to utilize $m=O\left(1/(a-b)^2\right)$ samples $s_i$ from $D_1$, querying $D_0(s_i)$ and $D_1(s_i)$, and computing $X_i = \frac{1}{2}\left( 1+\frac{\sqrt{D_0(s_i)}}{\sqrt{D_1(s_i)}} \right)^2 \|D_1\|_1$.

Now we proceed with the explicit construction of $\calT$, as <Ref>.

IfElseIfElseIfThenElse IfElseendif
$\Sample{D}$ and $\Query{D}$ oracle accesses; parameters $\frac{1}{2} \leq b < a \leq 1$.
Set $m,m' := \Theta(1/\epsilon^2)$, where $\epsilon := (a-b)/8$
Draw samples $o_1,\cdots,o_{m'}$ from $D_{\rm out}:= \text{marginal distribution of the designated output qubit}$
Compute $\hat{Z} := \frac{1}{m'} \sum_{i=1}^{m'} Z_i$, where $Z_i := o_{i}$
Draw samples $s_1,\cdots,s_{m}$ from $D$
$i = 1,\cdots,m$
$\hat{Z} \geq \frac{1}{2}$with $\Query{D}$, get $X_i := \frac{1}{2} \left(1+\tfrac{\sqrt{D_0(s_i)}}{\sqrt{D_1(s_i)}}\right)^2$
*with $\Query{D}$, get $X_i := \frac{1}{2} \left(1+\tfrac{\sqrt{D_1(s_i)}}{\sqrt{D_0(s_i)}}\right)^2$

Compute $\hat{X} := \frac{1}{m} \sum_{i=1}^m X_i$
$\hat{Z} \geq \frac{1}{2}$  and  $\hat{X}\hat{Z} \geq \frac{1}{2}(a+b)$output ACCEPT
$\hat{Z} < \frac{1}{2}$  and  $\hat{X}(1-\hat{Z}) \geq \frac{1}{2}(a+b)$output ACCEPT
output REJECT
$O(1/(a-b)^2)$-additive approximation tester $\calT$ of $\frac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2$

Analysis.  Define random variables $Z_i$ as in <Ref>.
We obviously have $\E[Z_i] = \|D_1\|_1 \in [0,1]$. Since all $Z_i$s' are independent, a Chernoff bound ensures

\begin{equation}
\label{eq:eStoqMA-in-MA-RV1}
\Pr{\left|\hat{Z} - \|D_1\|_1\right| \leq \epsilon} \geq 1-2e^{-2m'/\epsilon^2},
\end{equation}

which is at least $3/4$ by an appropriate choice of $m'$.

Note drawing samples from $p_0$ implicitly by post-selecting the output qubit to be $0$.
However, due to the inner product's symmetry and $\norm{D_0}_1+\norm{D_1}_1=1$, there must exist $i \in \binset$ such that $\norm{D_i}_1 \geq 1/2$. Hence, the required sample complexity will be enlarged merely by a factor of $2$.

Let us also define random variables $X_i$ as in <Ref>. W.L.O.G. assume that $\norm{D_1}_1 \geq 1/2 \geq \norm{D_0}_1$.
By <Ref>, we obtain
$\E_{i \sim D_1/\norm{D_1}_1} [X_i] = \norm{\ket{D_0}+\ket{D_1}}_2^2/2\norm{D_1}_1$.
Because the $X_i$'s are independent and takes value in $[1/2,1]$, by Chernoff bound,

\begin{equation}
\label{eq:eStoqMA-in-MA-RV2}
\Pr{\left|\hat{X}-\frac{\norm{\ket{D_0}+\ket{D_1}}_2^2}{2\|D_1\|_1}\right| \leq \epsilon} \geq 1- 2e^{-2m/\epsilon^2}.
\end{equation}

Therefore, by our choice of $m$, $\hat{X}$ is an $\epsilon$-additive approximation of $\norm{\ket{D_0}+\ket{D_1}}_2^2/2\norm{D_1}_1$ with probability at least $3/4$.
Note that $X_i, Z_i$ are independent, we obtain $\E\left[\hat{X} \hat{Z}\right] = \frac{1}{2} \norm{\ket{D_0}+\ket{D_1}}_2^2$.
Hence, notice $1/2 \leq \|D_1\|_1 \leq 1$ and $1/2 \leq \frac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2 \leq 1$, by combining Equations (<ref>) and (<ref>), we obtain with probability $9/16$:

\[
\begin{aligned}
\hat{X}\hat{Z} &\leq \left( \tfrac{\norm{\ket{D_0}+\ket{D_1}}_2^2}{2\|D_1\|_1} + \epsilon \right)\left( \|D_1\|_1+\epsilon \right)
\leq \tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2 +\epsilon^2+\epsilon+2\epsilon \leq \tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2+4\epsilon; \\
\hat{X}\hat{Z} &\geq \left( \tfrac{\norm{\ket{D_0}+\ket{D_1}}_2^2}{2\|D_1\|_1} - \epsilon \right)\left( \|D_1\|_1-\epsilon \right)
\geq \tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2+\epsilon^2-\epsilon-2\epsilon \geq \tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2-4\epsilon.
\end{aligned}
\]

It implies that
$\Pr{\left|\hat{X}\hat{Z} - \tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2\right| \leq 4\epsilon} \geq 9/16$.
We thereby conclude that

* If $\tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2 \geq a$, then $\hat{X}\hat{Z} \geq a-4\epsilon$ and $\calT$ outputs ACCEPT w.p. at least $9/16$.

* If $\tfrac{1}{2}\norm{\ket{D_0}+\ket{D_1}}_2^2 \leq b$, then $\hat{X}\hat{Z} \leq b+4\epsilon$ and $\calT$ outputs ACCEPT w.p. at most $7/16$.

Furthermore, the algorithm $\calT$ makes $m'+2m$ calls for $\Sample{D}$ and $m$ calls for $\Query{D}$ .

It is worthwhile to mention that this construction in the proof of <Ref> is optimal regarding the sample complexity, as Theorem 7 in [17].

Finally, we complete the proof of <Ref> by <Ref>.

Given an $\eStoqMA(a,b)$ verifier $V_x$, we here construct a $\MA$ verifier $V'_x$ that follows from <Ref> in <Ref>:

* For each call to the sample oracle $\Sample{D_w}$, we run the $\eStoqMA$ verifier $V_x$ (without measuring the output qubit) with the witness $w$, and draw samples by performing measurements:

* For samples $s_i~(1 \leq i \leq m)$ from distribution $D$, measure all qubits utilized by the verification circuit in the computational basis;

* For samples $o_j~(1 \leq j \leq m')$ from distribution $D_{\rm out}$, measure the designated output qubit in the computational basis.

* For each call to the query oracle $\Query{D_w}$ with index $i$, find the corresponding index $i'$ at the beginning by performing the permutation associated with $V_x^{\dagger}$ on $i$, and then evaluate the value $D_w(i')$ by the given algorithm associated with this easy witness.

* Compute an empirical estimation of $\frac{1}{2} \norm{\ket{D_0}+\ket{D_1}}_2^2$ as <Ref>, and then decide whether $V_x$ accepts $w$.

The circuit size of $V'_x$ is a polynomial of $|x|$ since both sample and query complexity are efficient.
We thus conclude that the new $\MA$ verifier $V'_x$ is efficient, and only requires $O\left(1/(a-b)^2\right)$ copies of the witness $w$, which finishes the completeness case.

For the soundness case, the acceptance probability $\Pacc$ of the $\eStoqMA$ verifier $V_x$ for all witnesses is obviously upper-bounded by $b$, regardless of whether witnesses are easy or not. Furthermore, entangled witnesses are useless since we draw samples by performing measurements separately. Hence, the maximum acceptance probability of the new $\MA$ verifier $V'_x$ is also at most $b$.

§.§ $\StoqMA$ with perfect completeness is in $\eStoqMA$

Now we complete proof of <Ref>.
The terminologies of $\SetCSP$ can be found in <Ref>.

By <Ref>, we know that $\SetCSP_{0,1/\poly}$ is $\StoqMA_1$-complete, so it suffices to show that $\SetCSP_{0,1/\poly}$ is contained in $\eStoqMA_1$.

By <Ref>, given a $\SetCSP_{0,b}$ instance $C$, we can construct a $\StoqMA\left(1,1-b/2\right)$ verifier.
The corresponding subset $S \subseteq \binset^n$, where $S$ satisfies all set-constraints of $C$, is an optimal witness.
It is left to show that this subset states is an easy witness.

We here achieve the proof by inspection.
Let $S$ be the set of all good strings of $C$, then $\setunsat(C,S)=0$. Notice that $x\in S$ is a good string of $C$ iff $x$ is a good string of all set-constraints $C_i (1\leq i \leq m)$. So the membership of $S$ can be decided efficiently, namely the subset state $\ket{S}$ is an easy witness.

Together with <Ref>, we conclude a straightforward corollary by <Ref>.

$\StoqMA_1 \subseteq \MA$.

§.§ Limitations of classical-witness $\StoqMA$

We will first present the proof of $\cStoqMA \subseteq \MA$ that preserves both completeness and soundness parameters, and then briefly discuss the limitations of $\StoqMA$ with classical witnesses.

A parameter-preserving proof of $\cStoqMA \subseteq \MA$.
We illustrate the intuition by a simple observation: for any $s\in\binset^n$ and any reversible circuit $U$, we have $\bra{s} U^{\dagger} \ketbra{+}{+}_1 U \ket{s} = \tfrac{1}{2} + \tfrac{1}{2} \bra{s} U^{\dagger} X_1 U \ket{s}$ since $\ketbra{+}{+}=\frac{1}{2} (X+I)$.
It is time to proceed with the actual proof.

For any $1/2 \leq b < a \leq 1$ and $a-b\geq 1/\poly(n)$,
\[\cStoqMA(a,b) \subseteq \MA(2a-1,2b-1).\]

Given a $\cStoqMA$ verifier $V_x$ on $n=n'+n_0+n_w$ qubits where $n'$ is the number of qubits of a witness, we construct a new $\MA$ verifier $\tilde{V}_x$ on $n=n'+n_0+n_w$ qubits: first run the verification circuit $V_x$ (without measuring the output qubit), then apply an $X$ gate on the output qubit, after that run the verification circuit's inverse $V_x^{\dagger}$, finally measure the first $n'+n_0$ qubits in the computational basis; $\tilde{V}_x$ accepts iff the first $n'$ bits of the measurement outcome is exactly $s_1\cdots s_{n'}$ and the remained bits are all zero.

We then calculate the acceptance probability of a classical witness $\ket{s}$ of a $\cStoqMA$ verifier $V_x$, where $w=w_1\cdots w_{n'} \in \binset^{n'}$. Notice $\ketbra{+}{+}=\frac{1}{2} \left( I+X \right)$, we obtain

\begin{equation}
\label[equation]{eq:cStoqMA-in-MA-LHS}
\begin{aligned}
\Pr{V_x \text{ accepts } s} &= \| \ketbra{+}{+}_1 V_x \ket{s}\ket{0^{n_0}}\ket{+}^{\otimes n_+} \|_2^2\\
&=\tfrac{1}{2} + \tfrac{1}{2} \bra{s}\bra{0^{n_0}}\bra{+}^{\otimes n_+} V_x^{\dagger} \left( X\otimes I_{n-1} \right) V_x \ket{s}\ket{0^{n_0}}\ket{+}^{\otimes n_+}.
\end{aligned}
\end{equation}

By a straightforward calculation, the acceptance probability of a classical witness $\ket{s}$ of $\tilde{V}_x$ is

\begin{equation}
\label[equation]{eq:cStoqMA-in-MA-RHS}
\Pr{\tilde{V}_x \text{ accepts } s} = \innerprod{R}{R} \text{ where } \ket{R}:=\left( \bra{s}\bra{0^{n_0}} \otimes I_{n_+} \right) V_x^{\dagger} \left( X\otimes I_{n-1} \right) V_x \ket{s}\ket{0^{n_0}}\ket{+}^{\otimes n_+}.
\end{equation}

It is evident that $\ket{R}$ is a subset state and ${\rm supp}(\ket{R}) \subseteq \binset^{n_+}$.
Together with Equations (<ref>) and (<ref>), we have completed the proof by noticing

\[ \Pr{V_x \text{ accepts } s} = \frac{1}{2}+\frac{1}{2} \bra{+}^{\otimes n_+}\ket{R}
= \frac{1}{2}+\frac{1}{2} \innerprod{R}{R}
= \frac{1}{2}+\frac{1}{2} \Pr{\tilde{V}_x \text{ accepts } s}. \]

Could we extend <Ref> from a classical witness to a probabilistic witness $\sum_{s_i} \sqrt{D(i)} \ket{s_i}$ with a polynomial-size support[Such witnesses are clearly easy witnesses, but not all easy witnesses have polynomial-bounded size support. ]?
Notice that the crucial equality $\bra{+}^{\otimes n_+}\ket{R} = \innerprod{R}{R}$ utilized in <Ref> does not hold anymore, we need an efficient evaluation algorithm calculating $D(i)$ given an index $i$.
Moreover, we have to calculate each coordinate's contribution on the acceptance probability separately, so the accumulated additive error is still supposed to be inverse-polynomial, which indicates the support size of this probabilistic witness is negligible for some polynomial.

In addition, the proof of <Ref> immediately infers the precise variant of $\StoqMA$ with classical witnesses, where the completeness-soundness gap is exponentially small, is equal to $\mathsf{PreciseMA}$.
However, the proof of <Ref> no longer works for precise scenarios, indicating that $\StoqMA$ with classical witness seems not interesting.

Classical witness is not optimal for any $\StoqMA$ verifier.
By combining $\StoqMA_1\subseteq \MA_1$ and the gadget in the proof of <Ref>, we could construct a $\StoqMA_1$ verifier such that a classical witness is optimal.
However, it does not mean that a classical witness is optimal for any $\StoqMA_1$ verifier.
In fact, <Ref> below provides a simple counterexample.

A classical witness is not optimal for any $\StoqMA_1$ verifier.

Consider a $\StoqMA_1$ verifier $V_x$ that uses only identity gates, then

* For all classical witness $s_i\in\binset^{n_w}$, $\Pr{V_x \text{ accepts } s_i}=\frac{1}{2}$ since $\innerprod{R_0}{R_1}=0$ where the resulting state before the measurement is $\ket{0}\otimes \ket{R_0} + \ket{1}\otimes \ket{R_1}$.

* For any classical witness $s_i,s_j\in\binset^{n_w}$ such that $s_i$ and $s_j$ are identical except for the first bit, one can construct a witness $\ket{s}=\frac{1}{\sqrt{2}}\ket{s_i}+\frac{1}{\sqrt{2}}\ket{s_j}$, $\Pr{V_x \text{ accepts } s}=1$ since $\innerprod{R_0}{R_1}=1$.

We thus conclude that classical witness is not optimal for this $\StoqMA_1$ verifier.

However, this impossibility result is unknown for an easy witness of any $\StoqMA$ verifier yet.

§ COMPLEXITY OF REVERSIBLE CIRCUIT DISTINGUISHABILITY

This section will concentrate on the complexity classification of distinguishing reversible circuits, namely given two efficient reversible circuits, and decide whether there is a non-negative state that tells one from the other.
With randomized ancillary bits, this problem is $\StoqMA$-complete, as <Ref>.
However, this problem's exact variant, namely assuming these two reversible circuits are equal for no instances (viz. $\StoqMA$ with perfect soundness), is $\NP$-complete (see <Ref>).
Moreover, <Ref> also implies that distinguishing reversible circuits without any randomized ancillary bit is $\NP$-complete, which signifies a simplified proof of [26].

§.§ Reversible circuit distinguishability is $\StoqMA$-complete

We begin with the formal definition of the Reversible Circuit Distinguishability problem.

Given a classical description of two reversible circuits $C_0,C_1$ (using Toffoli, CNOT, X gates) on $n:=n_w+n_0+n_+$ qubits, where $n_w$ is the number of qubits of a non-negative state witness $\ket{w}$, $n_0$ is the number of $\ket{0}$ ancillary qubits, and $n_+$ is the number of $\ket{+}$ ancillary qubits. Let the resulting state before measuring the designated output qubit be $\ket{R_i}:=C_i \ket{w}\ket{0}^{\otimes n_0}\ket{+}^{\otimes n_+}$, $i\in\binset$.
Promise that $C_0$ and $C_1$ are either far enough or close enough, decide whether

* Yes ($\alpha$-far): there exists a non-negative witness $\ket{w}$ such that $\frac{1}{2} \|\ket{R_0}-\ket{R_1}\|_2^2 \geq \alpha$;

* No ($\beta$-close): for any non-negative witness $\ket{w}$,  then $\frac{1}{2} \|\ket{R_0}-\ket{R_1}\|_2^2 \leq \beta$;

where $\beta - \alpha \geq 1/\poly(n)$.

It is worthwhile to mention that the distance between reversible circuits in <Ref> is the squared Hellinger distance $d_H^2(D_0,D_1) = \frac{1}{2} \|\ket{R_0}-\ket{R_1}\|_2^2$  where $\ket{R_i} = \sum_{j\in\binset^n} \sqrt{D_i(j)}\ket{j}$ and $D_0, D_1$ are probability distribution over $\binset^{n}$.

Now we will prove that Reversible Circuit Distinguishability (RCD) is $\StoqMA$-complete, and the proof of <Ref> preserves parameters:

For any $\beta - \alpha \geq 1/\poly(n)$, $(\alpha,\beta)$-Reversible Circuit Distinguishability is $\StoqMA\left(1-\alpha/2,1-\beta/2 \right)$-complete.

We will first show $(\alpha,\beta)$-Reversible Circuit Distinguishability is $\StoqMA\left(1-\alpha/2,1-\beta/2 \right)$-hard.
Consider a $\StoqMA$ verifier $V_x$ as <Ref>, let $C_0:=V_x X_1 V_x^{\dagger}$ where the $X$ gate in the middle acts on the output qubit, and let $C_1$ be identity. Then for any non-negative witness $\ket{w}$, we obtain:

\begin{equation}
\label{eq:RCD-is-StoqMA-hard}
\begin{aligned}
\Pr{V_x \text{ accepts } \ket{w}} &= \bra{w}\bra{0}^{\otimes n_0}\bra{+}^{\otimes n_+} \left(V_x^{\dagger} \ketbra{+}{+}_1 V_x\right) \ket{w} \ket{0}^{\otimes n_0} \ket{+}^{\otimes n_+};\\
\innerprod{R_0}{R_1} &= \bra{w}\bra{0}^{\otimes n_0}\bra{+}^{\otimes n_+} \left(V_x^{\dagger} X_1 V_x\right) \ket{w} \ket{0}^{\otimes n_0} \ket{+}^{\otimes n_+}.
\end{aligned}
\end{equation}

Note that $\ketbra{+}{+} = (X+I)/2$ and $\frac{1}{2}\|\ket{R_0}-\ket{R_1}\|_2^2 = 1-\innerprod{R_0}{R_1}$, we thereby complete the $\StoqMA$ hardness proof by <Ref>:

\[ \Pr{V_x \text{ accepts } \ket{w}} = \frac{1}{2} + \frac{1}{2} \innerprod{R_0}{R_1} = 1-\frac{1}{2} \cdot \frac{1}{2} \|\ket{R_0}-\ket{R_1}\|_2^2. \]

Now it is left to show the $\StoqMA\left(1-\alpha/2,1-\beta/2 \right)$ containment of $(\alpha,\beta)$-Reversible Circuit Distinguishability.
Given reversible circuits $C_0,C_1$, we construct a $\StoqMA$ verifier as <Ref>.

$\ket{+}$     1          |+⟩

$\ket{w}$     [3,bundle=1,2,3]V_x^† X_1 V_x     [alternate]     [alternate]

$\ket{0}^{\otimes n_0}$         [alternate]     [alternate]

$\ket{+}^{\otimes n_+}$         [alternate]     [alternate]

RCD is $\StoqMA$-hard

$\ket{+}$     1     X     1     |+⟩

$\ket{w}$     [3,bundle=1,2,3]C_0     [alternate]     [3,bundle=1,2,3]C_1     [alternate]

$\ket{0}^{\otimes n_0}$         [alternate]         [alternate]

$\ket{+}^{\otimes n_+}$         [alternate]         [alternate]

RCD is in $\StoqMA$

Hence, we obtain the state before measuring the output qubit (viz. the red dash line in <Ref>):

\[
{\rm Ctrl-}C_1 \cdot X_1 \cdot {\rm Ctrl-}C_0 \left[ \left( \frac{1}{\sqrt{2}} \ket{0} + \frac{1}{\sqrt{2}} \ket{1} \right) \otimes \ket{w} \ket{0}^{\otimes n_0} \ket{+}^{\otimes n_+} \right]
= \frac{1}{\sqrt{2}} \ket{0} \ket{R_0} + \frac{1}{\sqrt{2}} \ket{1} \ket{R_1}.
\]

We thus complete the $\StoqMA$ containment proof:

\[\Pr{V_x \text{ accepts } \ket{w}}
= \left\| \ketbra{+}{+}_1 \left( \frac{1}{\sqrt{2}} \ket{0} \ket{R_0} + \frac{1}{\sqrt{2}} \ket{1} \ket{R_1} \right) \right\|_2^2
=1-\frac{1}{2} \cdot \frac{1}{2} \|\ket{R_0}-\ket{R_1}\|_2^2. \]

§.§ Exact Reversible Circuit Distinguishability is $\NP$-complete

We will prove that the exact variant of the Reversible Circuit Distinguishability is $\NP$-complete.
Moreover, it will signifies that $\StoqMA$ with perfect soundness (even the completeness-soundness gap is arbitrarily small[As comparison, the precise variant of $\StoqMA$ encompasses $\NP^{\PP}$, since $\MA$ with an inverse-exponential completeness-soundness gap is equal to $\NP^{\PP}$ [33]. ]) is in $\NP$.

Exact Reversible Circuit Distinguishability (RCD), namely $(\alpha,1)$-Reversible Circuit Distinguishability for any $0 \leq \alpha < 1$, is $\NP$-complete

Exact RCD is $\NP$-hard, namely $\NP \subseteq \StoqMA\left(1,1/2\right)$, straightforwardly follows from the proof of <Ref>. It suffices to prove that the exact RCD is in $\NP$.

By <Ref>, $(2-2\alpha,1)$-Reversible Circuit Distinguishability is $\StoqMA\left(\alpha,1/2\right)$-complete. Let $\ket{w}$ be an $n_w$-qubit non-negative witness such that $\ket{w} := \sum_{s_i \in \supp{w}} \sqrt{D_w(s_i)} \ket{s_i}$, then

\[ \frac{1}{2} \| \ket{R_0}-\ket{R_1} \|_2^2 = 1-\innerprod{R_0}{R_1}=1-\bra{w}\bra{0}^{\otimes n_0} \bra{+}^{\otimes n_+} C_0^{\dagger} C_1 \ket{w}\ket{0}^{\otimes n_0} \ket{+}^{\otimes n_+}.\]

For yes instances, note that $\frac{1}{2}\|\ket{R_0}-\ket{R_1}\|_2^2 = 2-2a < 1$, we have derived

\[
\innerprod{R_0}{R_1} = \sum_{s_i,s_j\in\supp{w}} \sum_{r,r'\in\binset^{n_+}} \frac{\sqrt{D_w(s_i)D_w(s_j)}}{2^{n_+}} \bra{s_i}\bra{0^{n_0}}\bra{r} C_0^{\dagger} C_1 \ket{s_j}\ket{0^{n_0}}\ket{r'} > 0.
\]

Since $\forall s_i,s_j$, $D_w(s_i) D_w(s_j) \geq 0$, there exists $s_i,s_j \in \supp{w}$ and $r,r'\in\binset^{n_+}$ such that

\begin{equation}
\label{eq:StoqMA-perfect-soundness-yes}
\bra{s_i}\bra{0^{n_0}}\bra{r} C_0^{\dagger} C_1 \ket{s_j}\ket{0^{n_0}}\ket{r'} = 1.
\end{equation}

For no instances, we obtain $\innerprod{R_0}{R_0}=0$ due to $\frac{1}{2}\|\ket{R_0}-\ket{R_1}\|_2^2 = 1$, which infers

\begin{equation}
\label{eq:StoqMA-perfect-soundness-no}
\forall s_i,s_j\in \supp{w}, \forall r,r'\in\binset^{n_+}, \bra{s_i}\bra{0^{n_0}}\bra{r} C_0^{\dagger} C_1 \ket{s_j}\ket{0^{n_0}}\ket{r'} = 0.
\end{equation}

We finally construct an $\NP$ verifier as follows.
The input is the classical description of two reversible circuits $C_0$ and $C_1$, and the witness is two pairs of binary strings $(s_0,r_0)$ and $(s_1,r_1)$. The verifier accepts iff $C_0(s_0,0^{n_0},r_0)$ and $C_1(s_1,0^{n_0},r_1)$ are identical where $C_i (i=0,1)$ takes $(s_i,0^{n_0},r_i)$ as an input and permutes it as the output.
Notice these strings $s_0,r_0,s_1,r_1$ exists for yes instances owing to (<ref>), whereas they do not exist for no instances due to (<ref>), which achieves the proof.

As a corollary, <Ref> will imply $\StoqMA$ with perfect soundness is contained in $\NP$:

\[\mathop{\bigcup_{a>1/2}} \StoqMA\left(a,\tfrac{1}{2}\right) = \NP. \]

$\StoqMA$ without any randomized ancillary bit is in $\NP$.
We will prove that distinguishing reversible circuits without any randomized ancillary bit is $\NP$-complete, which provides an alternating proof of Strong Equivalence of Reversible Circuits is $\coNP$-complete [26].

$\StoqMA$ without any randomized ancillary bit is $\NP$-complete.

It suffices to show that $\StoqMA$ without any randomized ancillary bit (viz. ancillary qubits which is initially $\ket{+}$) is in $\NP$.
As a straightforward corollary of <Ref>, distinguishing reversible circuits without $\ket{+}$ ancillary qubit is complete for $\StoqMA$ without $\ket{+}$ ancillary qubit.

Consider reversible circuits $C_0,C_1$ act on $n_w+n_0$ qubits where $n_0$ is the number of $\ket{0}$ ancillary qubits, we observe that if $C_0$ and $C_1$ are not equivalent, then

\begin{equation}
\label{eq:StoqNP-diagonal}
\forall s_i\in\binset^{n_w}, \bra{s_i}\bra{0}^{\otimes n_0} C_0^{\dagger} C_1 \ket{s_i}\ket{0}^{\otimes n_0} = 0;
\end{equation}

\begin{equation}
\label{eq:StoqNP-off-diagonal}
\exists s_i,s_j \in \binset^{n_w}, \text{ s.t. } \bra{s_i}\bra{0}^{\otimes n_0} C_0^{\dagger} C_1 \ket{s_j}\ket{0}^{\otimes n_0} = 1
\end{equation}

Hence, for any $\StoqMA$ verifier $V_x$ without any $\ket{+}$ ancillary qubit, the acceptance probability of all classical witness $s_i$ is $1/2$, since $\Pr{V_x \text{ accepts } s_i} = 1/2 + \bra{s_i}\bra{0}^{\otimes n_0} C_0^{\dagger} C_1 \ket{s_i}\ket{0}^{\otimes n_0} /4 = 1/2$ due to (<ref>).
If classical witness is not optimal, then there exists some size-$2$ support witness $\ket{w}=(\ket{s_i}+\ket{s_j})/\sqrt{2}$ according to (<ref>), because $\Pr{V_x \text{ accepts } w} = 1/2+\bra{w}\bra{0}^{\otimes n_0} C_0^{\dagger} C_1 \ket{w}\ket{0}^{\otimes n_0}/4 =1$.

We thus conclude that $\StoqMA$ without $\ket{+}$ ancillary qubit is in $\StoqMA\left(1, 1/2 \right)$, which completes the proof by combining with <Ref>.

§ SOUNDNESS ERROR REDUCTION OF $\STOQMA$

In this section, we will partially solve <Ref> by providing a procedure that reduces the soundness error of any $\StoqMA$ verifier.

For any $r =\poly(n)$,

\[ \StoqMA\left(\frac{1}{2}+\frac{a}{2},\frac{1}{2}+\frac{b}{2}\right) \subseteq \StoqMA\left( \frac{1}{2}+\frac{a^r}{2}, \frac{1}{2}+\frac{b^r}{2} \right). \]

Consequently, <Ref> infers a direct error reduction for $\StoqMA_1$:

For any $s$ such that $1/2 \leq s \leq 1$ and $1-s \geq 1/\poly(n)$,

\[ \StoqMA(1,s) \subseteq \StoqMA\left( 1,\frac{1}{2} + 2^{-n} \right).  \]

§.§ Taking the conjunction of $\StoqMA$ verifiers' parallel repetition

We now proceed with the proof of <Ref>.
The main idea is essentially doing a parallel repetition of a $\StoqMA$ verifier $V_x$, and taking conjunction of the outcomes cleverly: equipped with the gadget (as <Ref>) in the proof of the reversible circuit distinguishability's $\StoqMA$-hardness, we could simulate the conjunction of single-qubit Hadamard-basis measurement outcomes on many copies of $V_x$ by a single-qubit Hadamard-basis measurement, as <Ref>.

Given a promise problem $\calL=(\calL_{\rm yes},\calL_{\rm no}) \in \StoqMA(1/2+a/2,1/2+b/2)$.
For any input $x\in \calL$, we have a $\StoqMA$ verifier $V_x$ which is equivalent to a new $\StoqMA$ verifier $\tilde{V}_x$ as <Ref>, by the $\StoqMA$-hardness proof of reversible circuit distinguishability as <Ref>. Namely, $\tilde{V}_x$ is starting on a $\ket{+}$ ancillary qubit, applying a controlled-unitary $V_x^{\dagger} X_1 V_x$ on $n_w+n_0+n_+$ qubits, and measuring the designated output qubit.

Let $\ket{R_w}:=\ket{w}\ket{0}^{\otimes n_0}\ket{+}^{\otimes n_+}$ where $\ket{w}$ is a witness, we obtain

\begin{equation}
\label{eq:PaccX-modified-StoqMA-verifier}
\left\| \ketbra{+}{+}_1 \left( \frac{1}{\sqrt{2}} \ket{0} \otimes \ket{R_w} + \frac{1}{\sqrt{2}} \ket{1} \otimes \left(V_x^{\dagger} X_1 V_x\right) \ket{R_w} \right) \right\|_2^2
= \| \ketbra{+}{+}_1 V_x \ket{R_w}\|_2^2.
\end{equation}

By an observation used in the $\QMA$ error reduction, namely Lemma 14.1 in [31], we notice that the maximum acceptance probability of a $\StoqMA$ verifier $V_x$ is proportion to the maximum eigenvalue of a matrix $M_x:=\bra{0}^{\otimes n_0} \bra{+}^{\otimes n_+} V_x^{\dagger} X_1 V_x \ket{0}^{\otimes n_0} \ket{+}^{\otimes n_+}$ associated with $V_x$:

\begin{equation}
\label{eq:StoqMA-verifier-maxeigenval}
\Pr{V_x \text{ accepts } \ket{w}} = \frac{1}{2} + \frac{1}{2} \max_{\ket{w}} \Tr(M_x \ketbra{w}{w}) =  \frac{1}{2} + \frac{1}{2} \lambda_{\max}(M_x).
\end{equation}

AND-type repetition procedure of a $\StoqMA$ verifier.
We now construct a new $\StoqMA$ verifier $V'_x$ using $r$ copies of the witness $\ket{w}$ on $r(n_w+n_0+n_+)+1$ qubits.
As <Ref>, $V'_x$ is starting from a $\ket{+}$ ancillary qubit as a control qubit, then applying controlled-unitary $V_x^{\dagger} X_1 V_x$ on qubits associated with different copies of the witness $\ket{w^{(i)}}$ for any $1 \leq i \leq r$.

$\ket{+}$      1      …     5     |+⟩

$\ket{w^{(1)}}$     [3,bundle=1,2,3]V_x^† X_1 V_x     … [alternate]     [alternate]     [alternate]

$\ket{0}^{\otimes n_0}$         … [alternate]     [alternate]     [alternate]

$\ket{+}^{\otimes n_+}$         … [alternate]     [alternate]     [alternate]

$\ket{w^{(r)}}$     [alternate]     … [alternate]     [3,bundle=1,2,3]V_x^† X_1 V_x     [alternate]

$\ket{0}^{\otimes n_0}$     [alternate]     … [alternate]     [alternate]     [alternate]

$\ket{+}^{\otimes n_+}$     [alternate]     … [alternate]     [alternate]     [alternate]

AND-type repetition procedure of a $\StoqMA$ verifier

By an analogous calculation of <Ref>, we have derived the acceptance probability of a witness $w^{(1)} \otimes \cdots \otimes w^{(k)}$ of the new $\StoqMA$ verifier $V'_x$:

\[\begin{aligned}
\Pr{V'_x \text{ accepts } \left( w^{(1)}\otimes \cdots \otimes w^{(r)} \right) }
= \frac{1}{2} + \frac{1}{2} \Tr\left(\ketbra{w^{(i)}}{w^{(i)}} M_x^{\otimes r} \right),
\end{aligned}\]

where $M_x$ is defined in <Ref>.
Hence, the maximum acceptance probability of $V'_x$ is

\begin{equation}
\label{eq:AND-error-reduction-tensor-product-pacc}
\max_{\ket{w'}} \Pr{V'_x \text{ accepts } \ket{w'}}
= \frac{1}{2} + \frac{1}{2} \lambda_{\max} \left( M_x^{\otimes r} \right)
= \frac{1}{2} + \frac{1}{2} \left( \lambda_{\max}(M_x) \right)^r,
\end{equation}

where the second equality thanks to the property of the tensor product of matrices.
<Ref> indicates that entangled-state witnesses are harmless since any entangled-state witness' acceptance probability is not larger than a tensor-product state witness'.

Finally, we complete the proof by analyzing the maximum acceptance probability of the new $\StoqMA$ verifier $V'_x$ regarding the promises: For yes instances, we obtain $\lambda_{\max}(M_x) \geq a$ since there exists $\ket{w}$ such that $\Pr{V_x \text{ accepts } \ket{w}} \geq 1/2+a/2$. By <Ref>, we have derived

\[ \Pr{V'_x \text{ accepts } \ket{w}^{\otimes r}} = \frac{1}{2}+\frac{1}{2} \left(\lambda_{\max}(M_x)\right)^r \geq \frac{1}{2}+\frac{a^r}{2}. \]

For no instances, we have $\lambda_{\max}(M_x) \leq b$ since $\Pr{V_x \text{ accepts } \ket{w}} \leq 1/2+b/2$ for all witness $\ket{w}$. By <Ref>, we further deduce

\[ \forall w', \Pr{V'_x \text{ accepts } \ket{w'}} =\frac{1}{2}+\frac{1}{2} \left( \lambda_{\max}(M_x) \right)^r \leq \frac{1}{2}+\frac{b^r}{2}. \]

<Ref> thus immediately infers <Ref>.

Choosing $a$ and $b$ such that $1=1/2+a/2$ and $s = 1/2+b/2$, we have $a=1$ and $b=2s-1$. By <Ref>, we obtain that

\[ \StoqMA\left(\frac{1}{2}+\frac{1}{2}\cdot 1, \frac{1}{2} + \frac{1}{2} (2s-1) \right) \subseteq \StoqMA\left(1, \frac{1}{2} + \frac{1}{2} (2s-1)^r \right). \]

To finish the proof, it remains to choose a parameter $r$ such that $r \geq (n+1)/\log_2\left(1/(2s-1)\right)$, since $(2s-1)^r/2 \leq 2^{-n}$ implies that $2^{-r\log_2\left(1/(2s-1)\right)-1} \leq 2^{-n}$.

§ ACKNOWLEDGMENTS

The author thanks Alex B. Grilo for his contribution during the early stage of <Ref> in this article, also pointing out the proof of <Ref>.
Additionally, the author thank Dorit Aharonov for helpful discussion.
The author was gratefully supported by ISF Grant No. 1721/17.
Circuit diagrams were drawn by the Quantikz package [28].

[1]
Dorit Aharonov and Alex B. Grilo.
Two combinatorial $\mathsf{MA}$-complete problems.
arXiv preprint arXiv:2003.13065, 2020.

[2]
Dorit Aharonov, Alex B Grilo, and Yupan Liu.
$\mathsf{StoqMA}$ vs. $\mathsf{MA}$: the power of error reduction.
arXiv preprint arXiv:2010.02835, 2020.

[3]
Scott Aaronson, Robin Kothari, William Kretschmer, and Justin Thaler.
Quantum lower bounds for approximate counting via laurent
arXiv preprint arXiv:1904.08914, 2019.

[4]
Scott Aaronson and Patrick Rall.
Quantum approximate counting, simplified.
In Symposium on Simplicity in Algorithms, pages 24–32. SIAM,

[5]
László Babai.
Trading group theory for randomness.
In Proceedings of the seventeenth annual ACM symposium on Theory
of computing, pages 421–429, 1985.

[6]
Sergey Bravyi, Arvid J Bessen, and Barbara M Terhal.
Merlin-arthur games and stoquastic complexity.
arXiv preprint quant-ph/0611021, 2006.

[7]
Harry Buhrman, Richard Cleve, John Watrous, and Ronald de Wolf.
Quantum fingerprinting.
Physical Review Letters, 87(16):167902, 2001.

[8]
Sergey Bravyi, David P Divincenzo, Roberto I Oliveira, and Barbara M Terhal.
The complexity of stoquastic local hamiltonian problems.
arXiv preprint quant-ph/0606140, 2006.

[9]
Itay Berman, Akshay Degwekar, Ron D Rothblum, and Prashant Nalini Vasudevan.
Statistical difference beyond the polarizing regime.
In Theory of Cryptography Conference, pages 311–332. Springer,

[10]
Elmar Böhler, Christian Glaßer, and Daniel Meister.
Error-bounded probabilistic computations between $\mathsf{MA}$ and
Journal of Computer and System Sciences, 72(6):1043–1076,

[11]
Sergey Bravyi and Matthew Hastings.
On complexity of the quantum ising model.
Communications in Mathematical Physics, 349(1):1–45, 2017.

[12]
Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp.
Quantum amplitude amplification and estimation.
Contemporary Mathematics, 305:53–74, 2002.

[13]
Sergey Bravyi and Barbara Terhal.
Complexity of stoquastic frustration-free hamiltonians.
SIAM Journal on Computing, 39(4):1462–1485, 2010.

[14]
Clément L Canonne.
A survey on distribution testing: Your data is big. but is it blue?
Theory of Computing, pages 1–100, 2020.

[15]
Nai-Hui Chia, András Gilyén, Tongyang Li, Han-Hsuan Lin, Ewin Tang, and
Chunhao Wang.
Sampling-based sublinear low-rank matrix arithmetic framework for
dequantizing quantum machine learning.
arXiv preprint arXiv:1910.06151, 2019.

[16]
Toby Cubitt and Ashley Montanaro.
Complexity classification of local hamiltonian problems.
SIAM Journal on Computing, 45(2):268–316, 2016.

[17]
Clément Canonne and Ronitt Rubinfeld.
Testing probability distributions underlying aggregated data.
In International Colloquium on Automata, Languages, and
Programming, pages 283–295. Springer, 2014.

[18]
Constantinos Daskalakis, Gautam Kamath, and John Wright.
Which distribution distances are sublinearly testable?
In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on
Discrete Algorithms, pages 2747–2764. SIAM, 2018.

[19]
Martin Furer, Oded Goldreich, Yishay Mansour, Michael Sipser, and Stathis
On completeness and soundness in interactive proof systems.
Advainces in Computing Research: A Research Annual,,
5:429–442, 1989.

[20]
Bill Fefferman, Hirotada Kobayashi, Cedric Yen-Yu Lin, Tomoyuki Morimae, and
Harumichi Nishimura.
Space-efficient error reduction for unitary quantum computations.
In 43rd International Colloquium on Automata, Languages, and
Programming (ICALP 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik,

[21]
Bill Fefferman and Cedric Yen-Yu Lin.
A complete characterization of unitary quantum space.
In 9th Innovations in Theoretical Computer Science Conference
(ITCS 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018.

[22]
Alex B. Grilo.
Private communication.

[23]
Shafi Goldwasser and Michael Sipser.
Private coins versus public coins in interactive proof systems.
In Proceedings of the eighteenth annual ACM symposium on Theory
of computing, pages 59–68, 1986.

[24]
Roger A Horn and Charles R Johnson.
Matrix analysis.
Cambridge university press, 2012.

[25]
Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson.
In search of an easy witness: Exponential time vs. probabilistic
polynomial time.
Journal of Computer and System Sciences, 65(4):672–694, 2002.

[26]
Stephen P Jordan.
Strong equivalence of reversible circuits is
Quantum Information & Computation, 14(15-16):1302–1307, 2014.

[27]
Dominik Janzing, Pawel Wocjan, and Thomas Beth.
"non-identity-check" is $\mathsf{QMA}$-complete.
International Journal of Quantum Information, 3(03):463–473,

[28]
Alastair Kay.
Tutorial on the quantikz package.
arXiv preprint arXiv:1809.03842, 2018.

[29]
Alexei Kitaev.
Quantum $\mathsf{NP}$.
Talk at AQIP, 99, 1999.

[30]
Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami.
Quantum merlin-arthur proof systems: Are multiple merlins more
helpful to arthur?
In International Symposium on Algorithms and Computation, pages
189–198. Springer, 2003.

[31]
Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi.
Classical and quantum computation.
Number 47. American Mathematical Soc., 2002.

[32]
Adam R Klivans and Dieter van Melkebeek.
Graph nonisomorphism has subexponential size proofs unless the
polynomial-time hierarchy collapses.
SIAM Journal on Computing, 31(5):1501–1526, 2002.

[33]
Tomoyuki Morimae and Harumichi Nishimura.
Merlinization of complexity classes above bqp.
Quantum Information & Computation, 17(11-12):959–972, 2017.

[34]
Peter Bro Miltersen and N Variyam Vinodchandran.
Derandomizing arthur–merlin games using hitting sets.
Computational Complexity, 14(3):256–279, 2005.

[35]
Michael A Nielsen and Isaac Chuang.
Quantum computation and quantum information, 2002.

[36]
Ronitt Rubinfeld and Rocco A Servedio.
Testing monotone high-dimensional distributions.
Random Structures & Algorithms, 34(1):24–44, 2009.

[37]
Amit Sahai and Salil Vadhan.
A complete problem for statistical zero knowledge.
Journal of the ACM (JACM), 50(2):196–249, 2003.

[38]
Yu Tanaka.
Exact non-identity check is $\mathsf{NQP}$-complete.
International Journal of Quantum Information, 8(05):807–819,

[39]
Ewin Tang.
A quantum-inspired classical algorithm for recommendation systems.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 217–228, 2019.

[40]
Ramgopal Venkateswaran and Ryan O'Donnell.
Quantum approximate counting with nonadaptive grover iterations.
arXiv preprint arXiv:2010.04370, 2020.

[41]
Ilya Volkovich.
The untold story of sbp.
In International Computer Science Symposium in Russia, pages
393–405. Springer, 2020.

[42]
John Watrous.
Succinct quantum proofs for properties of finite groups.
In Proceedings 41st Annual Symposium on Foundations of Computer
Science, pages 537–546. IEEE, 2000.

[43]
Thomas Watson.
The complexity of estimating min-entropy.
computational complexity, 25(1):153–175, 2016.

§ $\SETCSP_{0,1/\POLY}$ IS $\STOQMA_1$-COMPLETE

We start from the definition of $\SetCSP$ with frustration:

Given a sequence of $k$-local set-constraints $C=(C_1,\cdots,C_m)$ on $\binset^n$, where $k$ is a constant, $n$ is the number of variables, and $m$ is a polynomial of $n$. A set-constraint $C_i$ acts on $k$ distinct elements of $[n]$, and it consists of a collection $Y(C_i) = \{Y_1^{(i)},\cdots,Y_{l_i}^{(i)}\}$of disjoint subsets $Y_j^{(i)} \subseteq \binset^k$. Promise that one of the following holds, decide whether

* Yes: There exists a subset $S \subseteq \binset^n$ s.t. $\setunsat(C,S) \leq \epsilon_1(n)$;

* No: For any subset $S \subseteq \binset^n$, $\setunsat(C,S) \geq \epsilon_2(n)$,

where $\epsilon_1$ and $\epsilon_2$ are efficiently computable function and $\epsilon_2-\epsilon_1 \geq 1/\poly(n)$.

Now we briefly define a $\SetCSP$ instance $C$'s frustration. We leave the formal definition in <Ref>.
The frustration of a set-constraint $C$ regarding a subset $S$ is

\[\setunsat(C,S) = \frac{1}{m} \sum_{i=1}^m \setunsat(C_i,S) = \frac{1}{m} \sum_{i=1}^m \frac{|B_i(S)|}{|S|} + \frac{|L_{i}(S)|}{|S|}, \]

where $B_{i}(S)$ is the set of bad strings of $C_i$, namely $\forall s \in B_{i}(S)$, $s|_{\supp{C_i}} \notin \cup_{j=1}^{l_i} Y_j^{(i)}$; And $L_i(S)$ is the set of longing strings of the subset $S$ regarding $C_i$.

We will prove <Ref> in the remainder of this section.

$\SetCSP_{0,1/\poly}$ is $\StoqMA_1$-complete.

§.§ $\SetCSP_{\negl,1/\poly}$ is $\StoqMA(1-\negl,1/\poly)$-hard

To prove <Ref>, we will first show that $\SetCSP_{0,1/\poly}$ is $\StoqMA_1$-hard.

For any super-polynomial $q(n)$ and polynomial $q_1(n)$, there exists a polynomial $q_2(n)$ such that

\[ \SetCSP_{\frac{1}{q(n)},\frac{1}{p_2(n)}} \text{ is } \StoqMA\left(1-\frac{1}{q(n)},\frac{1}{p_1(n)}\right)\text{-hard }. \]

The $\StoqMA\left(1-1/q(n),1/p_1(n)\right)$-hardness proof is straightforwardly analogous to the circuit-to-Hamiltonian construction used in $\MA$-hardness proof of $\SetCSP$ in [1].
The only difference is replacing $Y(C^{\rm out})=\{\{00\},\{01\},\{11\}\}$ by
$Y(C^{\rm out})=\{\{00\},\{01\},\{10,11\}\}$ in Section 4.4.2, since the final measurement on the $(T+1)$-qubit is on the Hadamard basis instead of the computational basis.
The rest of the proof follows from an inspection of Section 4.4 in [1].

Then <Ref> is an immediate corollary of <Ref> by substituting $0$ for $1/q(n)$:

$\SetCSP_{0,1/\poly}$ is $\StoqMA_1$-hard.

§.§ $\SetCSP_{a,b}$ is in $\StoqMA(1-a/2,1-b/2)$

It now remains to show a $\StoqMA_1$ containment of $\SetCSP_{0,1/\poly}$.
We will complete the proof by mimicking the $\StoqMA$ containment of the stoquastic local Hamiltonian problem in Section 4 in [6].
The starting point is an alternating characterization of the frustration of a set-constraint $C_i$ in a $\SetCSP$ instance $C$.
The proof of <Ref> is deferred in the end of this section.

For any $k$-local set-constraint $C_i (1 \leq i \leq m)$, given a subset $S \subseteq \binset^n$, the frustration

\[\setunsat(C_i,S) = 1- \sum_{j=1}^{|Y(C_i)|} \sum_{x,y \in Y_j^{(i)}} \tfrac{1}{|Y_j^{(i)}|} \braket{S}{ \left(\ketbra{x}{y} \otimes I_{n-k}\right) }{S}. \]

Now we state the $\StoqMA$ containment of $\SetCSP$, as <Ref>.

For any $0 \leq a < b \leq 1$, $\SetCSP_{a,b} \in \StoqMA\left(1-a/2,1-b/2\right)$.
Moreover, for a subset $S \subseteq \binset^n$ such that $S = \argmin_{S'}\setunsat(C,S')$, the subset state $\ket{S}$ is an optimal witness of the resulting $\StoqMA$ verifier.

The proof of <Ref> tightly follows from Section 4 in [6].
We here provide a fairly simplified proof using the $\SetCSP$ language by avoiding unnecessary normalization.

Given a $\SetCSP_{a,b}$ instance $C=(C_1,\cdots,C_m)$. For each set-constraint $C_i (1 \leq i \leq m)$, we first construct a local Hermitian matrix $M_i$ preserves the frustration, then construct a family of $\StoqMA$ verifiers for such a $M_i$.

For any set-constraint $C_i$, we obtain a $k$-local matrix $M_i$ by <Ref> such that

\begin{equation}
\label{eq:SetCSP-in-eStoqMA-frustration}
\forall S\subseteq \binset^n, \setunsat(C_i,S)=1-\braket{S}{M_i \otimes I_{n-k}}{S} \text{ where } M_i=\sum_{j=1}^{|Y(C_i)|} \sum_{x,y \in Y_j^{(i)}} \frac{1}{|Y_j^{(i)}|} \ketbra{x}{y}.
\end{equation}

Moreover, for a set $Y_j^{(i)}$ of strings associated with the set-constraint $C_i$, we further have

\begin{equation}
\label{eq:SetCSP-in-eStoqMA-decomposition}
\begin{aligned}
\sum_{x,y \in Y_j^{(i)}} \ketbra{x}{y} &= \sum_{x\in Y_j^{(i)}} \ketbra{x}{x} + \frac{1}{2} \sum_{x\neq y\in Y_j^{(i)}} \left( \ketbra{x}{y} + \ketbra{y}{x} \right)\\
&= \sum_{x\in Y_j^{(i)}} V_x \ketbra{0}{0}^{\otimes k} V_x^{\dagger} + \frac{1}{2} \sum_{x\neq y \in Y_j^{(i)}} V_{x,y} \left( X\otimes \ketbra{0}{0}^{\otimes k-1} \right) V_{x,y}^{\dagger},
\end{aligned}
\end{equation}

where $V_x$ is a depth-$1$ reversible circuit with $X$ such that $\forall x, \ket{x}=U_x\ket{0^k}$, and $V_{x,y}$ is a $O(k)$-depth reversible circuit with CNOT and X such that $\forall x,y, U_{x,y} \ket{0^k}\ket{10^{k-1}} U_{x,y}^{\dagger}$.

Notice that the resulting local observables in <Ref> are either $\ketbra{0}{0}^{\otimes k}$ (i.e. a single-qubit computational-basis measurement) or $X\otimes \ketbra{0}{0}^{\otimes k-1}$ (i.e. a single-qubit Hadamard-basis measurement).
To construct a $\StoqMA$ verifier, we only allow local observables in form $X\otimes I^{\otimes O(k)}$.
Namely, we are supposed to simulate a computational-basis measurement by ancillary qubits and a Hadamard-basis measurement, which is achieved by <Ref>.

* For any integer $k$, there exists an $O(k)$-depth reversible circuit $W$ using $k$ $\ket{0}$ ancillary qubits and a $\ket{+}$ ancillary qubits s.t.

\[\forall \ket{\psi}, \braket{\psi}{\ketbra{0}{0}^{\otimes k}}{\psi} = \bra{\psi}\bra{0}^{\otimes k}\bra{+} W^{\dagger} \left(X \otimes I^{\otimes 2k}\right) W \ket{\psi} \ket{0}^{\otimes k} \ket{+}.\]

* For any integer $k$, there exists an $O(k)$-depth circuit $V$ using $k-1$ $\ket{0}$ ancillary qubits s.t.

\[\forall \ket{\psi}, \braket{\psi}{X\otimes \ketbra{0}{0}^{\otimes k-1}}{\psi} = \bra{\psi} \bra{0}^{\otimes k-1} W^{\dagger} \left( X\otimes I^{\otimes 2k-2} \right) W \ket{\psi} \ket{0}^{\otimes k-1}.\]

It is worthwhile to mention that the gadgets used in the proof (see Section A.4 in [6]) further provide proof of $\MA \subseteq \StoqMA$ that preserves both completeness and soundness parameters.

Let $\Idx{C_i}$ be the set of indices, and let $\alpha_{(j,x,y)}$ be the weight of an index $(j,x,y)$,

\[\begin{aligned}
\Idx{C_i} &:=\left\{(j,x,y): 1 \leq j \leq |Y_i(C)|, (x,y)\in \binom{Y_j^{(i)}}{2} \sqcup \left\{(x,x): x\in Y_j^{(i)}\right\}\right\};\\
\alpha_{(j,x,y)} &:= \frac{1}{(1+\mathbb{I}(x\neq y))m|Y_j^{(i)}|}, \text{ where the indicator } \mathbb{I}(x\neq y))=1 \Leftrightarrow x\neq y.
\end{aligned}\]

Plugging <Ref> and <Ref> into <Ref>, we have derived

\begin{equation}
\label{eq:set-unset-Ci}
1-\setunsat(C_i,S) = \sum_{l \in \Idx{C_i}} \alpha_l \braket{S}{ \left(\bra{0}^{\otimes k}\bra{+} U_k^{\dagger} \left(X\otimes I^{\otimes 2k}\right) U_k \ket{0}^{\otimes k} \ket{+}\right) \otimes I_{n-k}}{S}.
\end{equation}

For a $\SetCSP$ instance $C=(C_1,\cdots,C_m)$, by <Ref>, by substituting  $\ketbra{+}{+}=\frac{1}{2}(X+I)$ into <Ref>, we thus arrive at a conclusion that

\begin{equation}
\label{eq:SetCSP-PaccX}
\begin{aligned}
\Pr{V_x \text{ accepts } \ket{S}}
&= \frac{1}{m} \sum_{i=1}^m \left( 1-\frac{1}{2} \cdot \setunsat(C_i,S) \right)
&= 1 - \frac{1}{2} \cdot \setunsat(C,S).
\end{aligned}
\end{equation}

Note that the set of $\StoqMA$ verifiers $V_x$ with the same number of input qubits and witness qubits is linear, namely a convex combination of $l$ $\StoqMA$ verifiers $(V_1,p_1),\cdots,(V_l,p_l)$ can be implemented by additional $\ket{+}$ ancillary qubits and controlled $V_i (1 \leq i \leq l)$.
Therefore, by <Ref>, we conclude that $\forall a,b$, $\SetCSP_{a,b}$ is in $\StoqMA\left(1-a/2,1-b/2\right)$.

Finally, we achieve proof of <Ref>:

Given a $k$-local set-constraint $C_i$,
the set of good strings $G_i = \sqcup_{1 \leq j \leq |Y(C_i)|} Y_j^{(i)}$,
and the set of bad strings $B_i = \binset^{|J(C_i)|} \setminus G_i$.
Also, for any subset $S \binset^n$, the set of bad strings in $S$ is $B_i(S)$.
By direction calculation, notice that

\begin{equation}
\label{eq:SetCSP-contribution}
\begin{aligned}
\frac{|B_i(S)|}{|S|} &= \braket{S}{ \left( \sum_{x\in B_i} \ketbra{x}{x}\otimes I_{n-k} \right) }{S}\\
\sum_{j=1}^{|Y(C_i)|} \frac{|L_j^{(i)}(S)|}{|S|} &= \braket{S}{ \left( \sum_{x\in G_i} \ketbra{x}{x}\otimes I_{n-k} \right) }{S} - \sum_{j=1}^{|Y(C_i)|} \sum_{x,y\in Y_j^{(i)}} \frac{1}{|Y_j^{(i)}|} \braket{S}{ \left(\ketbra{x}{y} \otimes I_{n-k}\right) }{S}.
\end{aligned}
\end{equation}

Plugging <Ref> and $\binset^{|J(C_i)|} = B_i \sqcup G_i$ into $\setunsat(C_i,S)
= \frac{|B_i(S)|}{|S|} + \sum_{j=1}^{|Y(C_i)|} \frac{|L_j^{(i)}(S)|}{|S|}$, we then finish the proof.