Quantum Merlin-Arthur proof systems for synthesizing quantum states
2,1]Hugo Delavenne
1]François Le Gall
1]Yupan Liu
1]Masayuki Miyamoto

[1]Graduate School of Mathematics, Nagoya University
[2]ENS Paris-Saclay, Université Paris-Saclay

Complexity theory typically focuses on the difficulty of solving computational problems using classical inputs and outputs, even with a quantum computer. In the quantum world, it is natural to apply a different notion of complexity, namely the complexity of synthesizing quantum states. We investigate a state-synthesizing counterpart of the class , referred to as , which is concerned with preparing certain quantum states through a polynomial-time quantum verifier with the aid of a single quantum message from an all-powerful but untrusted prover. This is a subclass of the class  recently introduced by Rosenthal and Yuen (ITCS 2022), which permits polynomially many interactions between the prover and the verifier.
Our main result consists of error reduction of this class and its variants with an exponentially small gap or a bounded space, as well as how this class relates to other fundamental state synthesizing classes, i.e., states generated by uniform polynomial-time quantum circuits () and space-uniform polynomial-space quantum circuits ().
Furthermore, we establish that the family of  witnesses, considered as one of the most natural candidates, is in . Additionally, we demonstrate that  achieves perfect completeness.

§ INTRODUCTION

Classical and quantum complexity theory typically concentrates on the computational difficulty of solving problems with classical inputs and outputs. However, quantum computers have the ability to handle not only classical problems, but also quantum tasks, such as synthesizing quantum states. The most famous example is preparing ground states of a physical system [47, 53], which even dates back to Feynman's original ideas [17]. Analogous tasks are also commonplace in quantum cryptography and generalized notions of the pseudorandomness, such as quantum money [1] and pseudorandom quantum states [34]. This motivates the study of complexity of synthesizing quantum states.

In [2], Aaronson investigated the concept on quantum state complexity, leading to the state synthesis problem. This problem involves generating a quantum state $\rho$ from the all-zero state based on a quantum circuit with a succinct description acting on $n$ qubits with the depth up to exponential. The resulting state $\rho$ is supposed to be close to the designated target state $\ket{\psi}$[We measure the closeness between $\rho$ and $\ket{\psi}$ by the trace distance, see <Ref> for the definition]. This problem is solvable in (quantum) polynomial space (), i.e., a quantum computer running in exponential time but using polynomially many gates can generate a state that well approximates the target state.

Quantum computers are seemingly not capable of solving any  problem in polynomial time, while polynomially many messages interactive protocols with the help of an all-powerful and untrusted prover (known as interactive proofs, ) captures the full computational power of polynomial-space computation, referred to as the celebrated $\IP=\PSPACE$ theorem [44, 57].
A recent line of works [56, 30, 50] initializes the study on the interactive state synthesis problem.
Rosenthal and Yuen [56] denote the polynomial-space-preparable state families as [The definition of  is a bit subtle: although all quantum states can be well-approximated by an exponentially long gate sequence owing to the Solovay-Kitaev theorem [39], this exponential gate sequence is not necessarily space-uniform.] and show that such state families are preparable by polynomial-message interactive synthesis protocols, which belongs to the class .  Afterwards in [30], the authors explore the state synthesis problem by taking advantage of fairly powerful and trusted oracles. Recently, Metger and Yuen [50] manage to prove the equivalence between state families that are preparable using polynomial space and those generated by interactive synthesis protocols, that is, $\stateQIP=\statePSPACE$, which is the state-synthesizing counterpart of the $\IP=\PSPACE$ theorem (and its quantum analogue [31]).
Very recently (after our work was released), Rosenthal [55] strengthened the inclusion $\statePSPACE \subseteq \stateQIP$ by presenting a constant-message  protocol.
This result, combined with the other direction, can be considered as a parallelization technique counterpart for , highlighting that the behavior of  aligns more closely with  rather than .

However, there is currently a lack of fine-grained characterizations of computationally easier state families, viz., state families that are efficiently preparable (e.g., efficiently simulating view of quantum statistical zero-knowledge [62]), or state families that are synthesizable via simply one-message interactive protocols (e.g., efficient verification of pure quantum states in the adversarial scenario [64]). This opens up opportunities for our main results.

§.§ Main results

In this work, we are particularly interested in state families that are preparable by one-message protocol, denoted as , which is obviously a subclass of .
Let us first devote to defining  informally (see <Ref> for a formal definition).
A state family in  is a family $\{\ket{\psi_x}\}_{x\in\calL}$ indexed by binary strings in the corresponding language $\calL$ such that there is a verifier that has the following properties, verifying whether the target state $\ket{\psi_x}$ corresponds to a given input $x\in \calL$ is well-approximated. The verifier's computation, which is a polynomial-size unitary quantum circuit[In particular, extending to general quantum circuits does not change the class  owing to the principle of deferred measurement. However, such extensions do not immediately work for the space-bounded counterpart, namely $\stateQMAPSPACEoff$, see <Ref>.], takes a quantum-proof state $\ket{w}$ (with no limitations on the preparation method) and ancillary qubits in the state $\ket{0}$ as input. After performing the verification circuit, a designated output qubit will be measured on the computational basis, and the verifier accepts if the measurement outcome is $1$. If the verifier accepts, the verification circuit has prepared the resulting state $\rho_{x,w}$ on the remaining qubits that is a good approximation of the target state $\ket{\psi_x}$ (if the verifier rejects, the resulting state could be anything). The acceptance probability is viewed the success probability for approximately preparing $\ket{\psi_x}$.

More precisely, the state family is in the class $\stateQMA_{\delta}[c,s]$ for some $0 \leq s < c \leq 1$ and $\delta \geq 0$, if the resulting state $\rho_{x,w}$ is $\delta$-close to the target state $\ket{\psi_x}$ provided that the verifier accepts with probability at least $s$ (soundness condition); and additionally there exists a quantum witness that makes the verifier accepts with probability at least $c$ (completeness condition).

It is pretty evident that $\stateQMA_{\delta}[c,s] \subseteq \stateQMA_{\delta'}[c',s']$ if $c'\leq c$, $s'\geq s$ and $\delta' \geq \delta$. However, how crucially does $\stateQMA_{\delta}[c,s]$ depend on its parameters? For commonplace complexity classes, viz. , , , etc., the dependence on such parameters is very weak: the class remains the same so long as the completeness $c$ and soundness $s$ differ by at least some inverse polynomial of $n:=|x|$ where $x\in \calL$. This is known as error reduction, which typically involves performing the verification circuit in parallel and taking the majority vote.

However, error reduction for  requires a more nuanced approach. A simple parallel repetition of the verification circuit ends with a tensor product of the resulting state that evidently differs from the original state family.
Therefore, error reduction for  does need to preserve not only the quantum witness state $\ket{w}$, but also the resulting state $\rho_{x,w}$, referred to as the doubly-preserving error reduction (ending with negligible errors):

For any $c(n)-s(n) \geq 1/\poly(n)$ and $0 \leq c(n),s(n) \leq 1$, we have

\[\stateQMA_{\delta}[c,s] \subseteq \stateQMA_{\delta}[1-\negl,\negl].\]

Nevertheless, applying <Ref> to a polynomial-space-bounded variant of $\stateQMA_{\delta}[c,s]$, which we denote by $\stateQMAPSPACEoff$[We emphasize that $\stateQMAPSPACEoff$ is not a state-synthesizing counterpart of the class , see <Ref>.], will result in exponential space. To address this, we generalize <Ref> in a manner that preserves the polynomial space complexity, as presented in <Ref>.
Here in the class $\stateQMAPSPACEoff$, the verifier's computation stays polynomially space-bounded but may take exponential time and the gap between the completeness $c$ and the soundness $s$ is at least some inverse-exponential of $n:=|x|$.

For any $c(n)-s(n) \geq \exp(-\poly(n))$ and $0 \leq c(n),s(n) \leq 1$, we have

\[\stateQMAPSPACEoff_{\delta}[c,s] \subseteq \stateQMAPSPACEoff_{\delta}[1-\negl,\negl].\]

We note that <Ref> is a state-synthesis counterpart of the witness-preserving error reduction for  [49, 52]. Likewise, <Ref> shares similarities with error reduction for unitary quantum computations [18] in the context of synthesizing states. Along the line of Marriott and Watrous [49], we demonstrate that logarithmic-size quantum witness states are useless for  (this variant is referred to as $\stateQMA[\log]$), as shown in <Ref>. Here  is defined as a subclass of  with only polynomially many quantum gates.

$\stateQMA_{\delta}[\log] = \stateBQP_{\delta}.$

Resembling the approach of Fefferman and Lin [19], we demonstrate that a variant of  that admits an exponentially small gap between completeness and soundness, known as , is contained in :

$\statePreciseQMA_{\delta} \subseteq \statePSPACE_{\delta}$.

Surprisingly, Corollary <ref> shows that the distance parameter $\delta$ remains unchanged, while a similar  containment following from [50] will worsen the distance parameter $\delta$, namely $\stateQMA_{\delta} \subseteq \statePSPACE_{\delta+1/\poly}$.

Furthermore, we demonstrate a natural instance of  that illustrates the state family of  witness, as described in <Ref>. It is noteworthy that we concentrate on  witness rather than  witness because  comprises state families whereas  witnesses typically correspond to a subspace, such as the ground space $\calS_H$ of a local Hamiltonian $H$ with a dimension $\dim(\calS_H) > 1$.

For any promise problem $\calL=(\calL_{\yes},\calL_{\no})$, we have

* If $\calL\in \UQMA$, the family of witness state $\ket{w_x}_{x\in \calL_{\yes}}$ corresponding to yes instances is in $\stateQMA_{1/\poly}$;

* If $\calL\in \PreciseUQMA_{1-{1/\exp}}$ , the family of witness state $\ket{w_x}_{x\in \calL_{\yes}}$ corresponding to yes instances is in $\statePreciseQMA_{1/\exp}$.

In addition, we prove that , which is a variant of  in which the optimal quantum witness state is classical (i.e., a binary string) for the completeness condition, can archive perfect completeness:

For any $c(n) - s(n) \geq 1/\poly(n)$ and $0 \leq c(n), s(n) \leq 1$, we have
$\stateQCMA_{\delta}[c,s] \subseteq \stateQCMA_{\delta}[1,s']$ for some $s'$ such that $1-s'(n) \geq 1/\poly(n)$.

This result is analogous to the $\QCMA=\QCMA_1$ theorem [35, 33] for synthesizing quantum states.
In addition, it is worth noting that <Ref> also straightforwardly extends to .

§.§ Proof techniques

The proof of <Ref> and <Ref> employs the quantum linear algebra techniques developed by Gilyén, Su, Low, and Wiebe [28], specifically the quantum singular value discrimination.

Error reduction for  by manipulating singular values. To elaborate on the intuition, we begin by briefly reviewing the witness-preserving error reduction for  [49, 52]. Consider a  verification circuit $V_x$ that takes a quantum witness state $\ket{w}$ (on the register $\sfW$) and ancillary qubits in the state $\ket{0}$ as input. The corresponding acceptance probability is $\|\ket{1}\bra{1}_{\Out} V_x \ket{w}\ket{\bar{0}}\|_2^2$, which is equal to a quadratic form $\bra{w} M_x \ket{w}$ where the matrix $M_x:=\bra{\bar{0}} V_x^{\dagger} \ket{1}\bra{1}_{\Out} V_x \ket{\bar{0}}$. It is not hard to see the maximum acceptance probability of $V_x$ is the largest eigenvalue of $M_x$.
We then view $M_x=\Pi_{\In}\Pi\Pi_{\In}$ as a product of Hermitian projectors $\Pi_{\In}$ and $\Pi$ where $\Pi_{\In}=I_{\sfW}\otimes\ket{\bar{0}}\bra{\bar{0}}$ and $\Pi=V_x^{\dagger} \ket{1}\bra{1}_{\Out} V_x$. Remarkably, there exists an orthogonal decomposition of the Hilbert space, which the projectors $\Pi_{\In}$ and $\Pi$ act on, into one-dimensional and two-dimensional common invariant subspaces. This elegant decomposition property is referred as to the Jordan lemma[See [54] for the detailed statement of the Jordan lemma, as well as a simple proof.] [36]. Marriott and Watrous [49] then take advantage of the Jordan lemma and present error reduction for  that preserves the quantum witness state.

However, this error reduction technique does not automatically preserve the resulting state, as required in , we thus need a more sophisticated technique, namely the quantum singular value transformation [28]. This technique generalizes the qubitization technique introduced by Low and Chuang [43] that inspired by the aforementioned decomposition property.
Moving on to the maximum acceptance probability of a  verifier $V_x$, it corresponds to the square root of the largest singular value of the matrix $A_x=\Pi_{\Out} V_x \Pi_{\In}$ where $\Pi_{\Out}:=\ket{1}\bra{1}_{\Out}$ is the final measurement. In Section 3.2 of [28], the authors extend the Jordan lemma to the singular value scenarios. In particular, $\Img(\Pi_{\In})$ and $\Img(\Pi_{\Out})$ can be decomposed into one-dimensional or two-dimensional common invariant subspaces. Now let us focus on the specific case of , we notice that the right singular vectors of $A_n$ correspond to the quantum witness state $\ket{w}$, as well as the left singular vectors correspond to the resulting state $\rho_{x,w}$. Therefore, we result in doubly-preserving error reduction for (<Ref>) by manipulating the singular values accordingly[Concretely speaking, the analysis of error reduction based on majority votes essentially corresponds to obtaining tail bounds for the Binomial distribution. By leveraging the central limit theorem, it becomes sufficient to estimate tail bounds for the normal distribution, referred to as the error function $\erf(x)$. The approximation polynomials of the sign function in [42] then achieve this task. ].

It is noteworthy that <Ref> differs from Theorem 38 in [28] since our construction is based on the projected unitary encoding (e.g., the presented matrix $A_n$) instead of the block-encoding.
Furthermore, for establishing <Ref>, we make use of an exponential-degree approximation polynomial of the sign function that all coefficients within the exponential precision are computable in  [50]. We additionally observe that the proof techniques in [50] can be straightforwardly adapted to projected unitary encodings instead of the block-encodings originally utilized in their work.

Applications of error reduction for . Along the line of Theorem 3.13 in [49], with <Ref>, it seems to straightforwardly make for <Ref>. Nevertheless, the resulting state raises some concern upon initial inspection. We fortunately circumvent this caveat by a careful analysis. Specifically, utilizing the error reduction for , we begin with a verifier with completeness $1-2^{-p(n)}$ and soundness $2^{-p(n)}$ where $p$ is a polynomial of $n:=|x|$. Then we replace the short quantum witness state $\ket{w}$ with a completely mixed state $I_{\sfW}$, which gives us a computation meeting the soundness condition such that the soundness $s$ is preserved and the gap between the completeness and the soundness shrinks to some inverse-polynomial of $n:=|x|$. Although the new resulting state $\rho_{I_{\sfW}}$ may greatly differ from $\rho_{x,w}$, the definition of  guarantees that $\rho_{I_{\sfW}}$ is also close to the target state because the acceptance probability of the verifier with $I_{\sfW}$ is greater than the soundness $s$. This proof also easily extends to <Ref> employing <Ref>.
In addition, it is noteworthy that  achieves perfect completeness with a worsening distance parameter $\delta'$. By incorporating error techniques for both  and $\stateUPSPACE$, the difference between the new distance parameter $\delta'$ and the original one can be made exponentially small.
Furthermore, we remark that  is not trivially contained in , still this is effortless[See <Ref> (in particular, <Ref>) for a detailed elaboration. ].
We therefore complete the other direction in <Ref>.

witness family is in . To establish <Ref>, we start by employing a weighted circuit-to-Hamiltonian construction [5, 10] to generate a ground state (also known as the history state) that provides a $\delta_1$-close approximation of the output state produced by a  verifier $V_x$ with maximum acceptance probability $1-\nu$. The resulting Hamiltonian $H^{(x)}$ possesses several crucial properties: the ground energy of $H^{(x)}$ is $\nu$, and the spectral gap satisfies $\Delta(H^{(x)}) \geq q(\nu \delta_1/T^3)$ for some polynomial $q$, where $T$ is the size of $V_x$.

Next, we construct a $\stateQMA_{\delta}[c',s']$ verifier primarily based on the one-bit precision phase estimation [38], often referred to as Hadamard test [4]. Through a fairly complicated analysis, we demonstrate that the promise gap $c'-s' \geq q'(v\delta_1 t/T^3)-2\epsilon$ for some polynomial $q'$ and the distance parameter $\delta\leq O(\max\{(1-\cos{\nu})/2,\delta_1,q(\nu \delta_1 t/T^3)\})$. Here, $\epsilon$ represents the implementation error of $\exp(-iH^{(x)}t)$ guaranteed by space-efficient Hamiltonian simulation <cit.>. We then achieve <Ref> by appropriately choosing parameters.

achieves perfect completeness. Our proof for <Ref> takes inspiration from [35, 33], but it requires several modifications. Note that our concern in  is not only the maximum acceptance probability but also the resulting state after performing the verification circuit and the final measurement. To meet these requirements, we must choose a specific universal gateset $\calS$ such that $\calS$ can generate a dense subgroup of $\mathrm{SU}(2^n)$ where $n$ is the number of qubits utilized in the quantum circuit, and all quantum states generated by these gates in $\calS$ have rational entries. For this reason, we opt for the “Pythagorean gateset”[See <Ref> for the details.] [35, 15].
To ensure that the resulting state is indeed close to the target state, we slightly adjust the construction outlined in [33].

§.§ Related works

In addition to the state-synthesizing complexity classes explored in prior works [56, 30, 50] and the present study, there are other investigations focusing on the quantum state synthesis problem from diverse perspectives, including cryptography and distributed computing. From a cryptographic standpoint, a recent work [14] examines non-interactive zero-knowledge (NIZK) proofs for quantum states, with a relevance to the setting of . Another concurrent study [16] addresses zero-knowledge proofs for quantum states, considering scenarios that pertinent to both  and  scenarios. On the other hand, in the realm of distributed computing, another recent work [45] delves into quantum state synthesis through the utilization of distributed quantum Merlin-Arthur protocols.

§.§ Discussion and open problems

Reduction and completeness in state-synthesizing complexity theory. In the context of state-synthesizing complexity theory, including prior works [30, 50, 56] and our own, the concepts of reduction and completeness have not been defined. However, these concepts hold significant importance in (quantum) complexity theory. The immediate challenge lies in appropriately defining these concepts, such as reduction, in a manner that ensures the resulting states exhibit reasonable behavior before and after the application of the reduction.
Nevertheless, a very recent work [11] introduced notions of reduction and completeness within the context of unitary-synthesising complexity theory.

The computational power of . Although Corollary <ref> establishes that a $\statePSPACE$ containment of $\statePreciseQMA$, the reverse inclusion, namely $\statePSPACE \subseteq \statePreciseQMA$, remains an open problem. The main challenge lies in adapting existing proof techniques that demonstrate $\PSPACE \subseteq \PreciseQMA$ [19, 20, 46], as these techniques heavily rely on notions of completeness or reduction for the class $\PSPACE$.

§ PRELIMINARIES

In this paper we assume the reader is familiar with the basic concepts and notions of quantum computation (see, e.g., [51] for the reference). We begin by introducing some useful linear-algebraic notations. Let $M$ be an Hermitian matrix, and we denote the largest eigenvalue of $M$ as $\lambda_{\max}(M)$, as well as the largest singular value of $M$ as $\sigma_{\max}(M)$. Also, $I_k$ is an identity matrix of size $2^k \times 2^k$. In addition, we will employ three Schatten norms of matrices in this paper, which include:

* Trace norm $\|M\|_1:=\Tr \sqrt{M^{\dagger} M}$;

* Frobenius norm $\|M\|_2:=\sqrt{\Tr(M^{\dagger} M)}$;

* Operator norm $\|M\|_{\infty}:=\sigma_{\max}(A) = \sqrt{\lambda_{\max}(A^{\dagger} A)}$.

§.§ Distances for quantum states

For any (probably mixed) quantum states $\rho_0$ and $\rho_1$, we measure the closeness between these states by the trace distance $\td(\rho_0,\rho_1):=\frac{1}{2}\|\rho_0-\rho_1\|_1$.
Moreover, we will employ the following properties of the trace distance, which are explained in detail in Section 9.2.1 of [51]:

Contractivity For any quantum channel $\Phi$, we have $\td(\Phi(\rho_0),\Phi(\rho_1)) \leq \td(\rho_0,\rho_1)$;

Convexity For any non-negative coefficients $\{p_i\}_i$ such that $\sum\nolimits_{i} p_i=1$, we have
\[\td\big( \rho_0, \sum\nolimits_i p_i \rho_1^{(i)} \big) \leq \sum\nolimits_i p_i \td\big(\rho_0,\rho_1^{(i)}\big).\]

In addition, we utilize the (Uhlmann) fidelity defined as fidelity $\F(\rho_0,\rho_1):=\Tr\sqrt{\sqrt{\rho_0} \rho_1 \sqrt{\rho_0}}$.
Importantly, when considering a pure state $\rho_0:=\ket{\psi_0}\bra{\psi_0}$ and a mixed state $\rho_1$, the fidelity simplifies to $\F(\rho_0,\rho_1)=\sqrt{\bra{\psi_0} \rho_1 \ket{\psi_0}}$.
Furthermore, the well-known Fuchs-van de Graaf inequality [22] states the following:

For any quantum states $\rho_0$ and $\rho_1$,
\[1-\F(\rho_0,\rho_1) \leq \td(\rho_0,\rho_1) \leq \sqrt{1-\F^2(\rho_0,\rho_1)}.\]

§.§ Gatesets matter for synthesizing quantum states

A gateset is a finite set of unitary matrices each of which acts on a finite-dimensional quantum system.
A gateset $\calS$ is universal if the subgroup generated by $\cal{S}$ is dense in $\mathrm{SU}(2^n)$ for large enough $n$.
We mainly use the common universal gateset $\{\CNOT, \Hadamard, \T\}$ for convenience, and further note that complexity classes remain unchanged for all reasonable choices of gatesets that all entries are algebraic numbers[For a comprehensive explanation of the conditions on choosing gatesets, see Theorem 2.10 in [41].], owing to the Solovay-Kitaev theorem [39] and its space-efficient variant [60].

Additionally, to achieve perfect completeness, we require a particular “Pythagorean” gateset in <Ref>, introduced by Jordan and Nagaj[35], which consists of  and “Pythagorean” gates[An analogous gateset is also utilized in [15] with a slightly different “Pythagorean” gate.]
\begin{psmallmatrix}
4 & -3 \\
3 & 4
\end{psmallmatrix}$ and
\begin{psmallmatrix}
4 & 3i \\
3i & 4
\end{psmallmatrix}$.

We end with <Ref> which states changing the gateset of a family of quantum circuits that prepares a certain family of quantum states will make the resulting state negligibly far from the target state. <Ref> highlights the robustness of the state-synthesizing procedure with respect to the choice of gateset. For convenience, we will define $\psi:=\ket{\psi}\bra{\psi}$.

Consider a family of (verification) circuits $\{Q_x\}_{x\in\calL}$ that prepares the corresponding family of resulting states $\{\rho_x\}_{x\in\calL}$[In particular, we first perform (verification) circuit $Q_x$ on the input state, which is not necessarily an all-zero state, then we measure the designated output qubit. If the measurement outcome is $1$, we obtain the resulting state corresponding to $Q_x$ on the remained qubits.].
Then we construct a circuit family $\{Q'_x\}_{x\in\calL}$ that prepares $\{\rho'_x\}_{x\in\calL}$, using a designated gateset $\calG$ that is closed under adjoint, such that $\td(\rho_x,\rho'_x) \leq \exp(-\poly(n))$ where $n:=|x|$.

Consider a quantum channel $\Phi(\rho):=\frac{\Pi_{\Out} \rho \Pi_{\Out}}{\Tr\left( \Pi_{\Out} \rho \Pi_{\Out} \right)}$ where $\Pi_{\Out}:=\ket{1}\bra{1}_{\Out}$ that post-selects the output qubit to be $1$, and let $\ket{w}$ be a (quantum) witness[If $Q_x$ and $Q'_x$ are not verification circuits, then this witness state is simply an all-zero state.], we have derived that

\[\begin{aligned}
\td(\rho_x,\rho'_x)&=\td\left(\Phi\left(Q_x(\ket{w}\bra{w}\otimes\ket{\bar{0}}\bra{\bar{0}})Q_x^\dagger\right), \Phi\left(Q'_x(\ket{w}\bra{w}\otimes\ket{\bar{0}}\bra{\bar{0}})(Q'_x)^{\dagger}\right)\right)\\
&\leq \td\left(Q_x(\ket{w}\bra{w}\otimes\ket{\bar{0}}\bra{\bar{0}})Q^\dagger, Q'_x(\ket{w}\bra{w}\otimes\ket{\bar{0}}\bra{\bar{0}})(Q'_x)^{\dagger}\right)\\
&= \sqrt{1-\bra{w}\bra{\bar{0}}Q_x^{\dagger}Q'_x\ket{w}\ket{\bar{0}}}\\
&\leq \|Q_x\ket{w}\ket{\bar{0}}-Q'_x\ket{w}\ket{\bar{0}}\|_2\\
&= \|Q_x-Q'_x\|_{\infty} \|\ket{w}\ket{\bar{0}}\|_2,
\end{aligned}\]

where the second line owing to the contractive property, the fourth line due to the fact that $(\innerprod{\psi}{\phi}-1)^{\dagger}(\innerprod{\psi}{\phi}-1) \geq 0$ for any pure states $\ket{\psi}$ and $\ket{\phi}$.

Note that the gates of $\mathcal{G}$ are closed under adjoint. By a space-efficient Solovay-Kitaev theorem (i.e., Theorem 4.3 in [60]), we can construct $Q'_x$ such that $\|Q_x-Q'_x\|_{\infty}\leq \epsilon$ by a deterministic algorithm running in time $\poly\log(1/\epsilon)$ and space $O(\log(1/\epsilon))$. We thus obtain $\td(\rho_x,\rho'_x) \leq \|Q_x-Q'_x\|_{\infty}\ \leq \exp(-\poly(n))$ as desired.

§.§ Unique-witness

A promise problem $\calL=(\calL_{\yes},\calL_{\no})$ is in $\UQMA[c,r,s]$ if there exists a uniformly generated polynomial-size quantum circuit $\{V_x\}_{x\in \calL}$ having $k(n)$ qubits for the witness register and requiring $m(n)$ ancillary qubits initialized to $\ket{0^m}$, where $k$ and $m$ are polynomials of $n:=|x|$ such that

* Completeness. If $x \in \calL_{\yes}$, then there exists a witness $\ket{w}$ such that $\Pr{V_x \text{ accepts } \ket{w}} \geq c(n)$. Furthermore, for all states $\ket{\phi}$ orthogonal to $\ket{w}$, $\Pr{V_x \text{ accepts } \ket{\phi}} \leq r(n)$.

* Soundness. If $x \in \calL_{\no}$, then for all states $\ket{\phi}$, $\Pr{V_x \text{ accepts } \ket{\phi}} \leq s(n)$.

Here, $c,r,s\colon \bbN \rightarrow [0,1]$ are efficiently computable functions such that $c(n) > \max\{r(n),s(n)\}$.

Following the witness-preserving error reduction for  by Marriott and Watrous [49], we know that  admits error reduction.

Consider $x\in \calL$ where $\calL \in \UQMA$.
Let $c,r,s\colon \bbN \rightarrow [0,1]$ be efficiently computable functions such that $c(n) > \max\{r(n),s(n)\}+1/q(n)$ for some polynomial $q$ of $n:=|x|$.
Then for any polynomial $l(n)$, we have that

\[\UQMA[c,r,s] \subseteq \UQMA\left[1-2^{-l},2^{-l},2^{-l}\right].\]

The witness length of the new  verifier remains preserved.

Furthermore, we can similarly define a variant of $\UQMA$ that corresponds to a promise gap, specifically $c-\max\{r,s\}$, exponentially approaching zero. This variant is denoted as $\PreciseUQMA$. Additionally, we introduce the notations $\UQMA_{1-\nu}$ and $\PreciseUQMA_{1-\nu}$ when the completeness error of these classes is $\nu$:

\[\begin{aligned}
\UQMA_{1-\nu}&:=\cup_{1-\nu-\max\{r(n),s(n)\} \geq 1/\poly(n)} \UQMA[1-\nu,r,s],\\
\PreciseUQMA_{1-\nu}&:=\cup_{1-\nu-\max\{r(n),s(n)\} \geq \exp(-\poly(n))} \UQMA[1-\nu,r,s].
\end{aligned}\]

In particular, if $\nu$ is exponentially small (negligible), we use the notations $\UQMA_{1-\negl}$ and $\PreciseUQMA_{1-\negl}$.

§.§ Tools from random walks on graphs

In this subsection, we recapitulate several useful lemmas concerning random walks on an undirected path graph $G=(V,E)$ and their associated spectral properties. These lemmas have been employed in [5] and <cit.>. A random walk on such a graph corresponds to a reversible Markov chain $(\Omega,P,\pi)$ on the state space $\Omega=V$ with a stationary distribution $\pi$ and a transition matrix $P$. For detailed definitions of these terminologies, we refer to [48].

Consider an $(T+1)$-node path graph $G=(V,E)$ and a strictly positive probability distribution $\pi$ on $V$[A probability distribution $\pi$ is strictly positive if all components $\pi_t$ are positive.]. We can construct a Markov chain $(V,P,\pi)$ with Metropolis transition probabilities $P$ that is reversible with respect to the given stationary distribution $\pi$ as below:

* For $0 < t < T$, $P_{t,t+1}:=\frac{1}{4}\min\big\{1,\frac{\pi_{t+1}}{\pi_t}\big\}$, $P_{t+1,t}:=\frac{1}{4}\min\big\{ 1,\frac{\pi_{t-1}}{\pi_t} \big\}$, and $P_{t,t}:=1-P_{t,t+1}-P_{t+1,t}$;

* For $t=0$, $P_{0,1}:=\frac{1}{2} \min\big\{ 1,\frac{\pi_1}{\pi_0} \big\}$, $P_{0,-1}:=0$, and $P_{0,0}:=1-P_{0,1}$;

* For $t=T$, $P_{T,T-1}:=\frac{1}{2}\min\big\{ 1,\frac{\pi_{T-1}}{\pi_T} \big\}$, $P_{T,T+1}:=0$, and $P_{T,T}:=1-P_{T,T-1}$.

Furthermore, we have a corresponding stoquastic frustration-free $O(\log n)$-local Hamiltonian $H^{(T)}_{\path}:=\sum_{t=0}^T H_{\path}(t)$ such that the spectral gap $\Delta(H^{(T)}_{\path})$ is the same as the spectral $\Delta_P$[Specifically, $\Delta(H^{(T)}_{\path})$ is the difference between the second smallest eigenvalue of $H^{(T)}_{\path}$ and the smallest eigenvalue, whereas $\Delta_P$ is the difference between the largest eigenvalue of $P$ and the second largest eigenvalue. ]. Here, the local term $H_{\path}(t)$ for any $0 \leq t \leq T$ is defined as:

\[H_{\path}(t) := (1-P_{t,t})\ket{t}\bra{t}
- \tfrac{\sqrt{\pi_t}}{\sqrt{\pi_{t-1}}} P_{t,t-1} \ket{t}\bra{t-1}
- \tfrac{\sqrt{\pi_{t-1}}}{\sqrt{\pi_t}} P_{t-1,t} \ket{t-1}\bra{t}\]

Our construction and the analysis closely parallel the proof of <cit.>. Through a direct calculation, we can establish that the matrix $P$ satisfies the condition of being a transition matrix: $\sum_{t=0}^T \pi_t P_{t,t'} = \pi_{t'}$. Additionally, the constructed Markov chain is reversible as the transition probabilities satisfy $\pi_t P_{t,t'} = \pi_{t'} P_{t',t}$ for all $0 \leq t,t' \leq T$.

According to the equivalent conditions for a reversible Markov chain (see [59]), this construction gives rise to a symmetric matrix $A:=D^{1/2} P D^{-1/2}$, where $D:={\rm diag}(\pi_0,\pi_1,\cdots,\pi_T)$.
Since we obtain $A$ by applying a similarity transformation to $P$, all eigenvalues of $A$ coincide with those of $P$. Consequently, we arrive at $H^{(T)}_{\path}=I-A$ where $I$ is a $(T+1)\times (T+1)$ identity matrix. Notably, $H^{(T)}_{\path}$ is both stoquastic and frustration-free because $P$ is entry-wise non-negative and the fact that the largest eigenvalue of $P$ is $1$.

Then we will provide a lower bound for the spectral gap $\Delta_P$ based on the conductance of the underlying graph $G=(V,E)$, which characterizes the graph's connectivity. In particular, for any nonempty subset $S \subseteq V$, we define the conductance as $\Phi_{G}(S):=\frac{1}{\min\{\pi(S),\pi(\bar{S})\}} \sum_{x \in S, y\in \bar{S}} \pi_x P_{x,y}$, and the conductance of the graph $G$ is denoted by $\Phi_{G}:=\min_{S \subseteq V} \Phi(S)$.
The well-known Cheeger's inequality demonstrates a spectral gap lower bound as follows:

For a reversible Markov chain with the underlying (weighted) graph $G$, the spectral gap $\Delta_P$ of the transition matrix $P$ satisfies
$\tfrac{1}{2} \Phi_G^2 \leq \Delta_P$.

§.§ Space-efficient Hamiltonian simulation

We adopt the following definition of efficient encodings of matrices adapted from [20]:

Let $M$ be a $2^k\times 2^k$ matrix, and let $\calA$ be a classical algorithm (e.g., a Turing machine) specified using $n$ bits.
We say that $\calA$ provides an efficient encoding of $M$ if, given an input $i \in \binset^k$, $\calA$ outputs the indices and contents of the nonzero entries of the $i$-th row, using at most $\poly(n)$ time and $O(k)$ workspace (excluding the output size).
Consequently, $M$ has at most $\poly(n)$ nonzero entries in each row.

In the following scenario, we will specify a matrix $M$ in the input by providing an efficient encoding of $M$, where the size of the encoding is the input size denoted by $n$.

We now proceed with a Hamiltonian simulation procedure achieving exponential precision with only polynomial space. The techniques come from [6, 7, 9], with an observation on the space complexity made in [20].

Consider the size-$n$ efficient encoding of a $2^{k(n)} \times 2^{k(n)}$ Hermitian matrix $H$ as an input, and treat this matrix $H$ as a Hamiltonian. Then the time evolution $exp(-iHt)$ can be simulated using $\poly(n, k, \|H\|_{\infty}, t, \log(1/\epsilon))$ operations and $O(k + \log(t/\epsilon))$ space.

§ BASIC STATE-SYNTHESIZING COMPLEXITY CLASSES

In this section, we will define state-synthesizing complexity classes involved in this paper.

§.§ State-synthesizing complexity classes with bounded time or space

We begin with two crucial notations on circuit families.
A family of quantum circuits $\{Q_x\}_{x\in \calL}$ associated with the language $\calL \subseteq \binset^*$ is uniformly generated if there exists a deterministic polynomial-time Turing machine (and thus polynomially space-bounded) that on input $x \in \calL$ outputs the description of $Q_x$.
Likewise, a family of quantum circuits $\{Q_x\}_{x\in \calL}$ is space-uniformly generated if $Q_x$ acts on polynomially many qubits and there exists a deterministic polynomial-space Turing machine that on input $x \in \calL$ outputs the description of $Q_x$.
Then we move on to the class that captures efficiently preparable quantum state families.

A family of quantum states $\{\ket{\psi_x}\}_{x\in\calL}$ is in $\stateBQP_{\delta}[\gamma]$ if each $\ket{\psi_x}$ is an $n$-qubit state where $n:=|x|$, and there exists a uniformly generated quantum circuit family $\{Q_x\}_{x \in \calL}$, which takes no inputs, such that for all $x \in \calL$:

* The circuit $Q_x$ outputs a (probably mixed) quantum state $\rho_x$ satisfying $\td(\rho_x,\psi_x)\leq \delta(n)$ if $Q_x$ successes. Here, we define the success of circuit $Q_x$ as the measurement outcome of the designated output qubit being $1$.

* The success probability of $Q_x$ is at least $\gamma$.

For convenience, we define $\stateBQP_{\delta}:=\stateBQP_{\delta}[2/3]$. Similarly, we denote  with an exponentially small success probability as $\statePreciseBQP_{\delta} := \cup_{\gamma\geq \exp(-\poly(n))} \stateBQP_{\delta}[\gamma]$.
Afterwards, we consider a state-synthesizing counterpart of unitary quantum polynomial space $\UnitaryBQPSPACE$ in [20]. In particular, we define  in terms of unitary quantum computation, denoted as $\stateUPSPACE$.

A family of quantum states $\{\ket{\psi_x}\}_{x\in\calL}$ is in $\stateUPSPACE_{\delta}[\gamma]$ if each $\ket{\psi_x}$ is an $n$-qubit state where $n:=|x|$, and there exists a space-uniform family of unitary quantum circuits $\{Q_x\}_{x \in \calL}$, which takes no inputs, such that for all $x \in \calL$:

* The circuit $Q_x$ outputs a (probably mixed) quantum state $\rho_x$ satisfying $\td(\rho_x,\psi_x)\leq \delta(n)$ if $Q_x$ successes. Here, we define the success of circuit $Q_x$ as the measurement outcome of the designated output qubit being $1$.

* The success probability of $Q_x$ is at least $\gamma$.

We denote $\stateUPSPACE_{\delta} := \stateUPSPACE_{\delta}[2/3]$.
It is worth noting that there are three differences between our definition  $\stateUPSPACE$ and  as defined in [56, 50]: 1) our definition only admits unitary quantum computation whereas  also permits general quantum circuits (see <Ref>); 2) our definition does not assume perfect completeness, even though this property is always achievable for our definition with a worsening distance parameter; and 3) our definition merely deals with pure state families, while  in [50] also accommodates mixed state families.

General quantum circuits allow not only unitary quantum gates but also intermediate measurements and resetting qubits.
Because of the principle of deferred measurement, admitting intermediate measurements does not make the time-efficient class more powerful. Recent developments on eliminating intermediate measurements in quantum logspace [21, 27, 25] improve this to the space-efficient scenario. Nevertheless, these new techniques do not automatically extend to state-synthesizing classes since they do not (even approximately) preserve the resulting state.

and $\stateUPSPACE$ achieve perfect completeness.
It is worth noting that the family of states constructed by the simulator used in quantum statistical zero-knowledge [62] is an instance of . Interestingly, one can assume that the corresponding simulator achieves perfect completeness with a worsening distance parameter $\delta'$[To be specific, this fact is demonstrated in the -hardness proof of the Quantum State Distinguishability Problem, as presented in Theorem 6 in [62].]. To achieve this, one can simply replace the designated output qubit of the  simulator, or a  circuit in general, with a qubit in state $\ket{1}$. This technique applies to any state-synthesizing complexity class with bounded time or space, including  and $\stateUPSPACE$:

For any $0 \leq \delta(n),\gamma(n) \leq 1$, choosing $\delta':=\gamma \delta+1-\gamma$, then

\[\stateBQP_{\delta}[\gamma]\subseteq \stateBQP_{\delta'}[1] \text{ and } \stateUPSPACE_{\delta}[\gamma] \subseteq \stateUPSPACE_{\delta'}[1].\]

Moreover, we note that achieving perfect completeness has little effect on the distance parameter when combined with the error reduction techniques employed by the aforementioned classes. Specifically, the new distance parameter $\delta'$ can be made exponentially close to $\delta$.

Let $\rho$ be the resulting state upon acceptance with respect to either a  circuit or a $\stateUPSPACE$ circuit, and similarly let $\rho_*$ be the resulting state upon rejection.
Also, let $\hat{\rho}$ be the resulting state when we replace the output qubit with a qubit in state $\ket{1}$. Then we obtain:

\[\begin{aligned}
\td(\ket{\psi_x}\bra{\psi_x},\hat{\rho}) &= \td(\ket{\psi_x}\bra{\psi_x},\gamma\cdot\rho+(1-\gamma)\cdot \rho_*)\\
&\leq \gamma\cdot \td(\ket{\psi_x}\bra{\psi_x},\rho) + (1-\gamma)\cdot \td(\ket{\psi_x}\bra{\psi_x},\rho_*)\\
&\leq \gamma\delta+1-\gamma.
\end{aligned}\]

Here, the second line follows from the convexity of the trace distance, and the third line holds because the trace ditance is at most $1$.

§.§ Quantum Merlin-Arthur proof systems for synthesizing quantum states

We will now discuss , which is a state-synthesizing counterpart of the class . Moreover, it is a natural subclass of , as defined [56], since we merely admit one message from the prover to the verifier.

Consider efficiently computable functions $c(n),s(n),\delta(n)$ satisfying $c(n)-s(n)\geq 1/\poly(n)$, $0 \leq s(n) < c(n) \leq 1$, and $0 \leq \delta(n) \leq 1$.
A family of quantum states $\{\ket{\psi_x}\}_{x \in \calL}$ is in $\stateQMA_{\delta}[c,s]$ if each $\ket{\psi_x}$ is an $n$-qubit state where $n:=|x|$, and there is a uniformly generated polynomial-size unitary quantum circuits family $\{V_x\}_{x \in \calL}$ acting on $m+k$ qubits, where $m$ is the number of working qubits and $k$ is the number of ancillary qubits where both $m(n)$ and $k(n)$ are polynomials of $n$, such that the following conditions hold:

* Completeness. There is an $m$-qubit state $\ket{w}$ such that
$\Pr{V_x \text{ accepts } \ket{w}} \geq c(n)$.

* Soundness. For any $m$-qubit state $\ket{w}$ such that $\td(\rho_{x,w}, \ket{\psi_x}\bra{\psi_x}) \geq \delta(n)$, we have $\Pr{V_x \text{ accepts } \ket{w}} \leq s(n)$, where $\rho_{x,w}$ is the resulting state of $V_x$ on the input $\ket{w}\ket{0^k}$ conditioned on the measurement outcome of the output qubit is $1$.  Here, we allow the verifier to trace out some qubits in the resulting state for convenience.

In addition, we use the notation $\stateQMA_{\delta}[l,c,s]$ to represent  with witness states of bounded length, where $l(n)$ is the number of qubits employed by the witness states. If $l(n)$ is a polynomial function of $n:=|x|$, we will omit the parameter $l$.

We define $\stateQMA_{\delta}:=\stateQMA_{\delta}{[2/3,1/3]}$. Additionally, we also define the variant of  with an exponentially small promise gap[To be specific, the gap between the acceptance probability in completeness and soundness is inverse-exponential.] and the variant of  with a logarithmic-length witness:

* $\statePreciseQMA_{\delta} := \cup_{c-s\geq \exp(-\poly(n))} \stateQMA_{\delta}[c,s]$;

* $\stateQMA_{\delta}[\log,c,s]:= \cup_{l(n) \leq O(\log{n})} \stateQMA_{\delta}[l,c,s]$.

Furthermore, we need to define $\stateQMAPSPACEoff$, a polynomial-space-bounded variant of , which corresponds to state families that are preparable by a polynomial-space-uniform unitary quantum circuit family $\{V_x\}_{x\in\calL}$ and the size of the witness is a polynomial of $n$. It is noteworthy that $\stateQMAPSPACEoff$ is not a state-synthesizing counterpart of , as explained in <Ref>.

Online and offline access to a classical witness in the class  are equivalent, but the models significantly differs in space-bounded classical computation and so do quantum counterparts[See Section 5.3.1 in [24] for elaborations on space-bounded classical computation. Regarding quantum scenarios, recent advancements in [26] signifies that quantum analogues of  with online access to an exponential-length witness are more powerful than the offline-access variant $\mathsf{QMAPSPACE}$ defined in [21], implying a quantum analogue of Savitch's theorem is unlikely to hold.]. The class  has online access to an exponential-length classical witness, whereas $\stateQMAPSPACEoff$ has offline access to a polynomial-length quantum witness, suggesting $\stateQMAPSPACEoff$ is not a state-synthesizing analogue of .

By restricting the optimal witness for the completeness condition to be classical (i.e., binary strings), we result in the class , and so does the precise variant  that has an exponentially small promise gap.
Likewise, we define $\stateQCMA_{\delta}:=\stateQCMA_{\delta}[2/3,1/3].$

is in  is non-trivial but effortless.
Finally, we remark that  is not trivially contained in . The issue is that for a circuit $Q_x$ associated with a state family in , the soundness condition of  may not hold. In particular, if the resulting state (for any input quantum state of $Q_x$) is far apart from the target state, then there is no guarantee that the corresponding acceptance probability is at most some threshold $s$.

To resolve this issue, we measure the input quantum state of $Q_x$ (also viewed as a quantum witness state for a  verifier) on the computational basis, and reject if the outcome is not an all-zero string. We now proceed with a formal statement with a proof:

For any $1/\poly(n) \leq \gamma(n) \leq 1$ and $0 \leq \delta \leq 1$,
$\stateBQP_{\delta}[\gamma] \subseteq \stateQMA_{\delta}[\gamma,\gamma']$ for some $\gamma'(n) > 0$ such that $\gamma(n) - \gamma'(n) \geq 1/\poly(n)$.

For any given $\stateBQP_{\delta}[\gamma]$ circuit $C_x$ with $m(n)$ working qubits, we construct a new $\stateQMA{}$ verification circuit $V_x$. We first introduce a new register $\sfW$ for the $m(n)$-qubit witness state $\ket{w}$, and the remaining is the given  circuit. Then the construction of $V_x$ follows from <Ref>.

1. Perform the  circuit $C_x$ without the final measurement
2. Measure all qubits in $\sfW$ (the witness state $\ket{w}$) on the computational basis.
Reject if the measurement outcome is not $0^m$
3. Measure the designated output qubit in the  circuit.
Accept and produce the resulting state if the measurement outcome is $1$, otherwise reject.
verification circuit $V_x$

It suffices to analyze this protocol. For the completeness condition, it is evident that the optimal witness is $0^m$. Then guaranteed by the given  circuit, we obtain $\Pr{V_x \text{ accepts } 0^m}\geq\gamma$. For the soundness condition, since any witness $\ket{w}$ that is orthogonal to $\ket{0^m}$ will be simply rejected, then we have derived that

\[\Pr{V_x \text{ accepts } \ket{w}}
=|\innerprod{w}{0^m}|^2\cdot \Pr{C_x \text{ accepts}} \geq \gamma |\innerprod{w}{0^m}|^2.\]

Therefore, for any witness state $\ket{w}$, we conclude that $\Pr{V_x \text{ accepts } \ket{w}} > 0$, and the resulting state $\rho_{x,w}$ satisfies $\td(\rho_{x,w},\ket{\psi_x}\bra{\psi_x})=\td(\rho_{x,0^m},\ket{\psi_x}\bra{\psi_x})\leq \delta$ as desired.

§ QUANTUM SINGULAR VALUE DISCRIMINATION, REVISITED

In this section, we aim to prove <Ref>, which serves as a “meta theorem” for singular value discrimination using different approximation polynomials with varying parameters.
Our approach differs from Theorem 3.2.9 in [23] as we employ the projected unitary encoding with an odd polynomial to preserve the output of the verification circuit, as specified in <Ref>.

We will start by defining the projected unitary encoding. We say that $U$ is a project unitary encoding of linear operator $A$ if $\|A- \tilde{\Pi} U \Pi\|_{\infty} \leq \epsilon$ where orthogonal projectors $\tilde{\Pi}$ and  $\Pi$ may also act on some ancillary qubits.

[Singular value discrimination with bounded time and space]theoremsingularValueDiscrimination

Consider $0 \leq a < b \leq 1$ and a projected unitary encoding $A := \tilde{\Pi}U\Pi$, where $U$ acts on $s_1(n)$ qubits. Let $\ket{\psi}$ be an unknown quantum state, a right singular vector of $A$ with a singular value either below $a$ or above $b$.
Suppose there exists a degree-$d$ odd polynomial $S$ satisfying $|S(x) - \sign(x)| \leq \epsilon$ for all $x \in [-1,1] \setminus (-\delta,\delta)$, where $d = O\left(\delta^{-1}\log(1/\epsilon)\right)$ and $\delta$ linearly depends on $b-a$.
We can implement the QSVT with respect to $S$ that distinguishes between the two cases with error probability at most $\epsilon$.
In particular, the description of quantum circuit implementation (classical prepossessing) can be computed in deterministic time $\poly(d)$ and space $s_2(n)$, and the circuit implementation takes $\poly(d)$ quantum gates and acts on at most $s_1(n)+O(\log{d})+1$ qubits, where $s_2(n)$ is decided by the construction of $S$.

Our construction is heavily influenced by [28] (and <Ref> taken from [50]) and we utilize specific statements from [23] for ease of use. We will show that, for any $\epsilon$ equal to $1/\poly(n)$ or $1/\exp(-\poly(n))$, when equipped with different approximation polynomials for the sign function, the space complexity parameters $s_1(n)$ and $s_2(n)$ remain $\poly(n)$ whereas the time complexity parameter $t(n)$ may differ greatly.

§.§ A general framework

Let us now define the singular value decomposition for projected unitary encodings.

Consider a projected unitary encoding of $A$, denoted by $U$, associated with orthogonal projectors $\Pi$ and $\tilde{\Pi}$ on a finite-dimensional Hilbert space $\calH_U$.
Namely, $A=\tilde{\Pi} U \Pi$. Then there exist orthonormal bases of $\Pi_i$ and $\tilde{\Pi}_i$ such that $\Pi$: $\left\{ \ket{\psi_{i}}: i \in [d] \right\}$, where $d:=\rank(\Pi)$, of a subspace $\Img(\Pi)=\span\left\{\ket{\psi_i}\right\}$;
$\tilde{\Pi}$: $\big\{ \ket{\tilde{\psi}_i}: i\in[\tilde{d}] \big\}$, where $\tilde{d}:=\rank(\tilde{\Pi})$, of a subspace $\Img(\tilde{\Pi})=\span\big\{\ket{\tilde{\psi}_i}\big\}$.
These bases ensure that the singular value decomposition $A = \sum_{i=1}^{\min\{d,\tilde{d}\}} \sigma_i \ket{\tilde{\psi}_i}\bra{\psi_i}$ where singular values $\sigma_i > \sigma_j$ for any $i < j \in [\min\{d,\tilde{d}\}]$.

With these definitions in place, we present the alternating phase modulation as <Ref>, which serves as the key ingredient for implementing quantum singular value transformations.
It is worth noting that Lemma <ref> deviates from Theorem 2.3.7 in [23] due to our assumption that the sequence of rotation angles is already provided. The rotation angles $\Phi$ in this context correspond to the polynomial $P$ and will be utilized in computing the descriptions of quantum circuits implementing QSVT corresponding to $P$.

Let $P\in\bbC[x]$ be a polynomial and $\Phi\in\bbR^n$ be the corresponding sequence of rotation angles. We can construct $P^{\rm (SV)}(\tilde{\Pi} U \Pi) = \tilde{\Pi} U_{\Phi} \Pi$ with a single ancillary qubit when $n$ is odd. Here, $U_{\Phi}$ represents a quantum circuit that implements the QSVT associated with $P$ using the corresponding rotation angles specified by $\Phi$.

We will now proceed with proving <Ref>.

Given an exact projected unitary encoding $\tilde{\Pi}U\Pi$ with a singular value decomposition $W\Sigma V^\dagger=\tilde{\Pi}U\Pi$, equipped with <Ref>, it suffices to construct an odd polynomial $P$ associated with a sequence angles $\Phi\in\bbR^m$ where $m=O(\log(1/\varepsilon)/\delta)$ such that
$\big\|\tilde{\Pi}_{\geq t+\delta} U_{\Phi} \Pi_{\geq t+\delta} - I\otimes \sum\nolimits_{i:\sigma_i \geq t+\delta} \ket{\tilde{\psi}_i}\bra{\psi_i} \big\| \leq \varepsilon$ and $\|\big( \bra{+}\otimes\tilde{\Pi}_{\leq t-\delta}\big) U_{\Phi} \left( \ket{+}\otimes \Pi_{\leq t-\delta} \right) - 0\| \leq \varepsilon$.

We here define singular value threshold projectors as $\Pi_{\geq \delta}:=\Pi V \Sigma_{\geq \delta} V^{\dagger} \Pi$, so does $\Pi_{\leq\delta}$. Similarly, $\tilde{\Pi}_{\geq\delta}:=\Pi U \Sigma_{\geq \delta} U^{\dagger} \Pi$, and so does $\tilde{\Pi}_{\leq\delta}$.
With construction of this procedure, we then apply an $\epsilon$-approximate singular value projector by choosing $t=(a+b)/2$ and $\delta=(b-a)/2$. Then, we measure $\ketbra{+}{+}\otimes \Pi$:
If the final state is in $\Img(\ketbra{+}{+}\otimes \Pi)$, there exists a singular value $\sigma_i$ above $b$;
Otherwise, all singular values $\sigma_i$ must be below $a$.

It is left to implement singular value threshold projectors. In fact, $U_{\Phi}$ can be achieved using a single ancillary qubit with $m$ uses of $U$,$U^\dagger$, $\rm C_\Pi NOT$, $\rm C_{\tilde{\Pi}} NOT$, and single qubit gates.

Implementing singular value threshold projectors. We begin by constructing an odd polynomial $P\in\bbR[x]$ of degree $m=O(\log(1/\epsilon^2)/\delta)$ that approximates the function $\frac{1}{2}[(1-\epsilon)\cdot\sign(x+t) + (1-\epsilon)\cdot\sign(x-t) + 2\epsilon \cdot\sign(x)]$  with $\epsilon^2/4$ precision on the interval $[-1,1] \setminus (-t-\delta,-t+\delta) \cup (t-\delta,t+\delta)$.

This construction of $P$ is based on the degree-$d$ approximation polynomial $S(x)$ specified in theorem statement. This polynomial $S(x)$ satisfies the condition $|S(x)-\sign(x)| \leq \epsilon$ for all $x \in [-1,1] \setminus (-\delta,\delta)$ where $d=O(\delta^{-1} \log(1/\epsilon))$.
Additionally, we have $|P(x)| \leq 1$ for any $-1 \leq x \leq 1$, together with: $(-1)^z P(x) \in [0,\epsilon]$ if $(-1)^z x \in [0,t-\delta]$ and $(-1)^z P(x) \in [1-\epsilon,1]$ if $(-1)^z \in [t+\delta,1]$ for $z \in \binset$.

Now it suffices to construct a projected unitary encoding $U$ such that $\|\tilde{\Pi} U_{\Phi}\Pi - P^{\rm (SV)}(\tilde{\Pi} U \Pi)\| \leq \epsilon$, which is achieved by <Ref> as long as rotation angles $\Phi$ corresponding to $P(x)$ can be computed in deterministically $\poly(d)$ time and $s_2(n)$ space.
Moreover, the gate complexity follows from Lemma 2.3.9 in [23].

§.§ Scenarios in time-efficient and space-bounded

Equipped with <Ref>, utilizing a polynomial approximation of the sign function in Corollary 6 of [42], as well as the angle finding algorithms in Theorems 2.2.1-2.2.3 of  [23], we conclude the time-efficient singular value discrimination.

Consider $0\leq a,b \leq 1$ and an exact projected unitary encoding $A:=\tilde{\Pi} U \Pi$. Let $\ket{\psi}$ be an unknown state, a right singular vector of $A$ with a singular value either below $a$ or above $b$ such that $b-a \geq 1/\poly(n)$. Employing the quantum singular value transform (QSVT) with a degree-$O\big(\frac{\log{1/\epsilon}}{b-a}\big)$ odd polynomial, one can distinguish the two cases with error probability at most $\epsilon$. Moreover, the time complexity of implementing this QSVT is $\poly\log(1/\epsilon)\cdot\poly(1/(b-a))$, and we can compute the description of this quantum circuit implementation in .

It suffices to construct a degree-$d$ approximation polynomial of the sign function, as well as find rotation angles used in <Ref>, in . The approximation polynomial is achievable in [28, 23] equipped with <Ref>.

For all $\delta > 0$, $\epsilon \in (0,1/2)$, there exists an efficiently computable odd polynomials $P \in \bbR[x]$ of degree $n=O(\log(1/\epsilon)/\delta)$ s.t.
$\forall x \in [-2,2], |P(x)| \leq 1$ and $\forall x \in[-2,2] \setminus (-\delta, \delta): |P(x)-\sign(x)|\leq \epsilon$.

Regarding finding angles, this is achievable in time $\tilde{O}(d^3\poly\log(1/\epsilon))$ using the recent developments [29, 13]. This results in a quantum circuit implementing the desired QSVT, and the description of this quantum circuit implementation can be computed in .

Now we move to the space-bounded scenario, stated in <Ref>.

Consider $0\leq a,b \leq 1$ and an exact projected unitary encoding $A:=\tilde{\Pi} U \Pi$. Let $\ket{\psi}$ be an unknown state, a right singular vector of $A$ with a singular value either below $a$ or above $b$ such that $b-a \geq \exp(-\poly(n))$. Employing the quantum singular value transform (QSVT) with a degree-$O\big(\frac{\log{1/\epsilon}}{b-a}\big)$ odd polynomial, one can distinguish the two cases with error probability at most $\epsilon$.
In addition, quantum circuits implementing this QSVT utilizes $\poly(n)$ qubits, and we can compute the description of this quantum circuit implementation in .

The proof of <Ref> is closely derived from the space-bounded quantum singular value transformation techniques in <cit.>. This is because their proof techniques can be straightforwardly adapted to the context of projected unitary encodings.

Analogous to the time-efficient scenario (e.g., <Ref>), it is sufficient to implement the QSVT corresponding to the sign function, as long as we have an exponentially good (bounded) polynomial approximation of the sign function, as stated in <Ref>.

For any $\epsilon \geq 2^{-\poly(n)}$, there exists a degree $d=O(\epsilon^{-1}\log(1/\epsilon))=O(2^{\poly(n)})$ and -computable coefficients $c_0,\cdots,c_d$ such that
$\forall x \in [-1,1] \setminus [-\epsilon,\epsilon]$, $\left|\sign(x)-P^{\sign}_d(x)\right| \leq \epsilon$  where  $P_d^{\sign}:=\sum_{i=0}^d c_i T_i$ and $T_i(x)$ is the Chebyshev polynomial (of the first kind)[ The Chebyshev polynomials (of the first kind) $T_k(x)$ are defined via the following recurrence relation: $T_0(x)=1$, $T_1(x)=x$, and $T_{k+1}(x)=2x T_k(x)-T_{k-1}(x)$. For $x \in [-1,1]$, an equivalent definition is $T_k(\cos \theta) = \cos(k \theta)$.].
Furthermore, the coefficient vector $c=(c_1,\cdots,c_d)$ has norm bounded by $\|c\|_1 \leq O(\log d)$.

However, instead of directly constructing the sequence of rotation angles in the time-efficient scenario, we employ the linear combination of unitaries (LCU) technique [8]. This technique can be readily adapted to space-bounded scenarios (as demonstrated in Lemma 3.6 in [50]) and is also applicable to projected unitary encodings. Next, we focus on implementing the quantum singular value transformation (QSVT) for the Chebyshev polynomials $T_i(x)$ with odd $i\in [1,d]$ utilized in <Ref>. To achieve this, we examine the proof of Lemma 2.2.7 in [23] and straightforwardly adapt it to the context of projected unitary encodings. Consequently, implementing an exponential-degree QSVT corresponding to the sign function requires polynomially many qubits, and the description of this circuit implementation can be computed in .

§ DOUBLY-PRESERVING ERROR REDUCTION FOR STATE-SYNTHESIZING CLASSES

In this section, we will present error reduction for  and its variants which preserves not only the (quantum) witness state but also the resulting state that well-approximates the target state facilities.

§.§ Doubly-preserving error reduction for  and more

We start by stating error reduction for , this leads to

\[\stateQMA{}_\delta = \cup_{c-s\geq 1/\poly(n)} \stateQMA_{\delta}[c,s].\]

For any efficiently computable $c(n),s(n),\delta(n)$ such that $0 \leq s(n) < c(n) \leq 1$, $c(n)-s(n)\geq 1/\poly(n)$, we have that for any polynomial $l(n)$,

\[\stateQMA_{\delta}[c,s] \subseteq \stateQMA_{\delta}[1-2^{-l},2^{-l}].\]

Moreover, the number of repetitions  is $O(l/(\sqrt{c}-\sqrt{s}))$.

Our proof closely relates to Theorem 38 in [28] besides an additional analysis on resulting states.

Amplifying the promise gap by QSVT.
Note that the acceptance probability of a  verifier $V_x$ taking $\ket{w}$ as a quantum witness is
$\Pr{V_x \text{ accepts } \ket{\psi}} = \| \ket{1}\bra{1}_{\Out} V_x \ket{0^k}\ket{w} \|_2^2 \geq c$ or $\leq s$.
Then consider a projected unitary encoding $M_x:=\Pi_{\Out} V_x \Pi_{\In}$ such that
$\| M_x \| \geq \sqrt{c}$ or $\sqrt{s}$ where $\Pi_{\In}:= (\ketbra{0}{0}^{\otimes k}\otimes I_m)$ and $\Pi_{\Out}:= \ket{1}\bra{1}_{\Out} \otimes I_{m+k-1}$.
Since $\|M_x\|=\sigma_{\max}(M_x)$ where $\sigma_{\max}(M_x)$ is the largest singular value of $M_x$, it suffices to distinguish the largest singular value of $M_x$ are either below $\sqrt{s}$ or above $\sqrt{c}$. By setting $a=\sqrt{s},b=\sqrt{c}$, and $\varepsilon=2^{-l(n)}$, this task is a straightforward corollary of the time-efficient singular value discrimination (<Ref>).

QSVT preserves both the witness state and the resulting state.
Utilizing notations of <Ref>, we notice that the construction in the proof of <Ref> essentially maps $M_x=\sum_i \sigma_i \ket{\tilde{\psi}_i}\bra{\psi_i}$ to $f(M_x)=\sum_i f(\sigma_i) \ket{\tilde{\psi}_i}\bra{\psi_i}$, for an odd polynomial $f$, such that $f(x)\in[1-\varepsilon,1]$ if $x \geq b$ and $f(x)\in[0,\varepsilon]$ if $x \leq a$ for any $0 \leq x \leq 1$.
Since both left and right singular vectors are invariant in $f(M_x)$, the resulting state and the witness state are clearly preserved after reducing errors.

Utilizing the space-bounded quantum singular value discrimination (<Ref>), we will now improve <Ref> to $\stateQMAPSPACEoff$, which may have exponential precision. This is partially analogous to [18] since <Ref> works merely for polynomial space.

Given any efficiently computable $c(n)$ and $s(n)$, also $\delta(n)$ such that $0 \leq s(n) < c(n) \leq 1$ and $c(n)-s(n) \geq \exp(-\poly(n))$, then for any polynomial $l(n)$,

\[\stateQMAPSPACEoff_{\delta}[c,s] \subseteq \stateQMAPSPACEoff_{\delta}[1-2^{-l},2^{-l}].\]

Here $t'(n)=t(n)\cdot R(n)$ where the number of repetitions $R(n) = O(l(n)/(\sqrt{c}-\sqrt{s}))$. Moreover, we need an additional ancillary qubit.

In addition, by forcing the input state of the “verification circuit” to be an all-zero state in the proof of <Ref>, namely replacing the projector $\Pi_{\In}:= (\ketbra{0}{0}^{\otimes k}\otimes I_m)$  with $\Pi'_{\In}:= \ketbra{0}{0}^{\otimes k+m}$, we will straightforwardly result in error reduction for .

For any polynomials $p(n)$ such that $1/p(n) \leq \gamma(n) < 1$, we have that for any polynomial $l(n)$,

\[\stateBQP_{\delta}[\gamma] \subseteq \stateBQP_{\delta}[1-2^{-l}].\]

Moreover, the number of repetitions is $O(l/\sqrt{\gamma})$.

<Ref> implies that $\stateBQP_{\delta} = \cup_{1 \leq \gamma^{-1} \leq \poly(n)} \stateBQP_{\delta}[\gamma]$. Also, combining with <Ref>,  achieves perfect completeness with a slightly modified distance parameter $\delta'$. Particularly, $\stateBQP_{\delta}[\gamma] \subseteq \stateBQP_{\delta'}[1]$ where $\delta'(n):=\delta(n)+\exp(-\poly(n))$.

Likewise, together with the projector $\Pi'_{\In}:= \ketbra{0}{0}^{\otimes k+m}$ and the space-bounded quantum singular value discrimination (<Ref>), we will deduce error reduction for $\stateUPSPACE$.

For any efficiently computable $\gamma(n),\delta(n)$ such that $\exp(-\poly(n)) \leq \gamma(n) \leq 1$, we have that for any polynomial $l(n)$,

\[\stateUPSPACE_{\delta}[\gamma] \subseteq \stateUPSPACE_{\delta}[1-2^{-l}].\]

Moreover, the number of repetitions is $O\left(l/\sqrt{\gamma}\right)$, and we need an additional ancillary qubit.

A direct consequence of <Ref> is that $\stateUPSPACE_{\delta} = \cup_{\gamma \geq 2^{-\poly(n)}} \stateUPSPACE_{\delta}[\gamma]$. Similarly, by utilizing <Ref>, we can also conclude that

\[\stateUPSPACE_{\delta}[\gamma] \subseteq \stateUPSPACE_{\delta'}[1] \text{ where } \delta'(n)=\delta(n)+\exp(-\poly(n)).\]

§.§ Application 1:  with a short message is as weak as

Recall that $\stateQMA_{\log}$ is a variant of  where the witness state is logarithmic-size.
Analogous to Theorem 3.10 in [49], a short message is also useless for .

For any $0 \leq s(n) < c(n) \leq 1$ and $c(n)-s(n) \geq 1/\poly(n)$, there exists a polynomial $q(n)$ such that

\[\stateQMA_{\delta}[\log,c,s] \subseteq \stateBQP_{\delta}[1/q].\]

Consider a state family $\{\ket{\psi_x}\}_{x\in\calL}$ that is in $\stateQMA_{\delta}[\log,c,s]$, we then notice that this state family is also in $\stateQMA_{\delta}[\log,1-2^{-p},2^{-p}]$ where $p(n)$ is a polynomial of $n:=|x|$ after performing error reduction (<Ref>). Now let $\{V_x\}_{x \in \calL}$ be the family of quantum verifiers with negligible errors.

Removing the witness by a “random-guess” state.
Now consider a  algorithm that applies $V_x$ with the witness being a completely mixed state $\tilde{I}_m:=2^{-m}I_m$ on $m(n)=O(\log{n})$ qubits. It accepts iff $V_x$ accepts.
For the analysis, we define $M_x:=(\ket{1}\bra{1}_{\Out}\otimes \ketbra{0}{0}^{\otimes m+k-1}) V_x (I_m\otimes \ketbra{0}{0}^{\otimes k})$. Then $\Pr{V_x \text{ accepts} \ket{w}}=\|M_x \ket{w}\|_2^2$, which infers that the acceptance probability of the  algorithm is

\begin{equation}
\label{eq:pacc-stateQMAlog-in-stateBQP}
\mathrm{Pr}\big[V_x \text{ accepts } \tilde{I}_m\big]=\Tr(M_x^{\dagger} M_x 2^{-m}I_m)=2^{-m} \Tr(M_x^{\dagger} M_x)=2^{-m}\lambda_{\max}(M_x^{\dagger}M_x),
\end{equation}

where $\lambda_{\max}(M_x^{\dagger}M_x)$ is the largest eigenvalue of $M_x^{\dagger}M_x$.
For the completeness, there exists $\ket{w}$ such that $\lambda_{\max}(M_x^{\dagger}M_x) \geq \Pr{V_x \text{ accepts } \ket{w}} \geq 1-2^{-p(n)}$. Plugging it into <Ref>, we have $\Pr{V_x \text{ accepts } \tilde{I}_m} \geq 2^{-m(n)}(1-2^{-p(n)}) \geq 1/q(n)$, where $q(n):=2^{O(m(n))}$ is a polynomial of $n:=|x|$.
For the soundness, we obtain $\Pr{V_x \text{ accepts } \tilde{I}_m} \geq 2^{-p(n)}$, it guarantees that $\td(\rho_{\tilde{I}_m},\psi_x) \leq \delta$ owing to <Ref>.

We remark that <Ref> straightforwardly adapts to any  verifier with witness states of polynomial-size, which is a state-synthesizing counterpart of $\QMA{} \subseteq \PP$ [61, 49].

$\stateQMA{}_\delta \subseteq \statePreciseBQP{}_\delta$.

Consider a family of quantum states $\{\ket{\psi_x}\}_{n\in\bbN} \in \stateQMA_m[c,s,\delta]$ where $m(n)$ is the size of the witness state. Analogous to <Ref>, we have derived that

\[\stateQMA_{\delta}[m,c,s] \subseteq \stateQMA_{\delta}[m,1-2^{-m'}, 2^{-m'}] \subseteq \stateBQP_{\delta}[2^{-m}],\]

where $m'(n)=m(n)\cdot n^2$.

§.§ Application 2:  is in

Finally, we provide a state-synthesizing analogue of $\PreciseQMA\subseteq\BQPSPACE$ [19, 20].

$\statePreciseQMA_{\delta} \subseteq \stateUPSPACE_{\delta}$.

Consider a family of quantum states $\{\ket{\psi_x}\}_{x\in\calL}$ that is in $\statePreciseQMA_{\delta}[m,c,s]$ where $m(n)$ is the size of witness state. We begin by observing that

\[\statePreciseQMA_{\delta}[m,c,s] \subseteq \mathsf{stateQMA_{U}PSPACE}^\mathsf{off}_{\delta}[m,c,s].\]

Then we replace the witness with a “random-guess” state analogous to the proof of <Ref>. Utilizing error reduction for $\stateQMAPSPACEoff$ (<Ref>), we have derived that

\[\statePreciseQMA_{\delta}[m,c,s] \subseteq \mathsf{stateQMA_{U}PSPACE}^\mathsf{off}_{\delta}[m,1-2^{-m'},2^{-m'}] \subseteq \stateUPSPACE_{\delta}[2^{-m}],\]

where $m'(n)=m(n)\cdot n^2$. Employing error reduction for $\stateUPSPACE$ (<Ref>), we conclude that

\[\statePreciseQMA_{\delta}[m,c,s] \subseteq \stateUPSPACE_{\delta}[2^{-m}] \subseteq \stateUPSPACE_{\delta}[1-2^{-l}],\]

where $l(n)$ is a polynomial of $n:=|x|$. This completes the proof.

§  WITNESS FAMILY IS IN

In this section, we will provide a natural example of  state families. Specifically, the family of yes-instance witness states of verifiers corresponding to $\calL_{\rm yes}$, where $(\calL_{\rm yes},\calL_{\rm no})\in \UQMA$, is in :

For any promise problem $\calL = (\calL_{\rm yes},\calL_{\rm no})$ that is in $\UQMA_{1-\nu}$, the family of unique witness states $\{\ket{w_x}\}_{x\in \calL_{\rm yes}}$ corresponding to yes instances is in $\stateQMA_{\delta}[c',s']$, where $c'=(1+\cos{\nu})/2-\epsilon$, $s'=(1+\cos(\lambda_1 t))(2+\cos(\nu t) - \cos(\lambda_1 t))/4+\epsilon$, and $\delta=O(\max\{(1-\cos{\nu})/2,\delta_1,q(\nu\delta_1 t/T^3)\})$ for some polynomial $q$.
Here, let $H^{(x)}$ be the Hamiltonian corresponding to a  verifier $V_x$ with the parameter $\delta_1$ specified in <Ref>, $\lambda_1$ is the second smallest eigenvalue of $H^{(x)}$ respectively, $T$ is the size of verification circuit $V_x$, as well as $t$ satisfies that $\lambda_{\max}\big(H^{(x)}\big) t \leq \pi$, and $\epsilon$ is the implementation error of $\exp(-iH^{(x)}t)$.

By employing <Ref>, we can determine that the promise gap of the new  verifier is given by

\[c'-s' = (1-\cos(\lambda_1 t))(\cos(\nu t)-\cos(\lambda_1 t)) - 2\epsilon \geq q'(\nu\delta_1 t/T^3) - 2\epsilon.\]

Here, $q'$ represents a polynomial due to the bound $\Delta(H^{(x)}) = \lambda_1-\nu \geq \Omega(\nu\delta_1/T^3)$ stated in <Ref>. According to <Ref>, we know that the implementation error $\epsilon$ is exponentially small. Consequently, by utilizing  error reduction (<Ref>), we establish $\UQMA \subseteq \UQMA_{1/\poly}$ and thus <Ref> implies <Ref> by choosing $\delta_1 = 1/\poly(n)$:

For any promise problem $\calL = (\calL_{\rm yes},\calL_{\rm no})$ in $\UQMA$, the family of unique witness states $\{\ket{w_x}\}_{x\in \calL_{\rm yes}}$ corresponding to yes instances is in $\stateQMA_{\delta}$, where $\delta(n)=1/\poly(n)$.

Similarly, <Ref> implies <Ref> by setting $\delta_1=\exp(-\poly(n))$:

For any promise problem $\calL = (\calL_{\rm yes},\calL_{\rm no})$ in $\PreciseUQMA_{1-\negl}$, the family of unique witness states $\{\ket{w_x}\}_{x\in \calL_{\rm yes}}$ corresponding to yes instances is in $\statePreciseQMA_{\delta}$, where $\delta(n)=\exp(-\poly(n))$.

§.§ Proof of Theorem <ref>

To establish <Ref>, we begin with a weighted circuit-to-Hamiltonian construction [5, 10], as stated in <Ref>, where the resulting ground state (also known as the history state) provides a good approximation of the output state produced by the  verifier. The proof of <Ref> can be found in <Ref>.

For any $x \in \calL_{\rm yes}$, where $\calL=(\calL_{\rm yes},\calL_{\rm no})$ is a promise problem that is in $\UQMA$, we can construct an $O(\log{n})$-local Hamiltonian $H^{(x)}$ with ground energy $\nu$ from the  verifier family $\{V_x\}_{x \in \calL}$ with maximum acceptance probability $1-\nu$, along with the corresponding unique witness state family $\{\ket{w_x}\}_{x\in \calL}$. This unique ground state of $H^{(x)}$ is given by

\[\ket{\Omega_x} = \sum_{t=0}^{T-1} \frac{\sqrt{\delta_1}}{\sqrt{T}} \ket{t}\otimes U_t\cdots U_1 \ket{w_x} + \sqrt{1-\delta_1} \ket{T} \otimes U_T\cdots U_1 \ket{w_x}.\]

Here $T$ denotes the number of quantum gates utilized by $V_x$.
Furthermore, the spectral gap of $H^{(x)}$ satisfies $\Delta(H^{(x)}) \geq \Omega(\nu\delta_1/T^{3})$.

With <Ref> established, we proceed to prove the main theorem in this section.

We begin by constructing a  verifier $V'_x$.
Let $H^{(x)}$ be the $O(\log n)$-local Hamiltonian, which is obtained by applying <Ref> to a  verifier $V_x$ with the unique witness $\ket{w_x}$.
Our construction is primarily relies on the one-bit precision phase estimation [38], often referred to as Hadamard test [4], as illustrated in <Ref>.

1. Apply one-bit precision phase estimation on registers $\sfO$, $\sfW$, and $\sfC$. Here, register $\sfO$ is the controlled qubit, while registers $\sfW$ and $\sfC$ are the target qubits. Specifically, (clock) register $\sfC$ consists os $\lceil \log{T} \rceil$ qubits, and the number of qubits in register $\sfW$ matches the number of qubits that $V_x$ acts on
2. Apply the circuit $V_x^{\dagger}$ to register $\sfW$
3. Measure the designated output qubit, and we say that $V'_x$ accepts $\ket{\psi}$ if the final measurement outcome is $0$
4. If $V'_x$ accepts, trace out all qubits in $\sfC$. The resulting state,  denoted as $\rho_{\psi}$, is located in register $\sfW$
verification circuit $V'_x$

Here, we choose the parameter $t=\frac{\pi}{p(n) \max\limits_{s,t}|H^{(x)}(s,t)|} \leq \frac{\pi}{\|H^{(x)}\|_{\infty}}$ such that all eigenvalues of $H^{(x)} t$ is in $[0,\pi]$. The corresponding circuit implementation has demonstrated in <Ref>.

$\ket{0}_{\sfO}$     H      1     H     0?

[wires=2]$\ket{\psi}_{\sfW,\sfC}$     [alternate]     [2,bundle=1]exp(-iH^(x) t)     [bundle=1][6ex][6ex]V_x^†     [alternate] $\rho_{\psi}$

[]⌈logT ⌉         []⌈logT ⌉     trace

verification circuit $V'_x$

Through direct calculation, we can express the acceptance probability as follows:

\[p'_{\rm acc}:=\Pr{V'_x \text{ accepts } \ket{\psi}} = \frac{1}{4}\big\|V_x^{\dagger}(I+e^{-iH^{(x)}t}) \ket{\psi}\big\|_2^2 = \frac{1}{2}+\frac{1}{2}\operatorname{Re}(\bra{\psi} e^{-iH^{(x)}t} \ket{\psi}).\]

We denote the resulting state by $\rho_{\psi}$ when $\exp(-iH^{(x)}t)$ is perfectly implemented, whereas the resulting state is $\rho'_{\psi}$ if the implementation error $\epsilon$ of $\exp(-iH^{(x)}t)$ is considered (e.g., <Ref>).
Simultaneously, $\rho_{\psi}$ is given by
$\rho_{\psi}:=\frac{1}{4 p'_{\rm acc}} V_x^{\dagger} \Tr_{\sfC}\!\left(  (I+e^{-iH^{(x)}t}) \ket{\psi}\bra{\psi} (I+e^{iH^{(x)}t}) \right) V_x.$

Completeness. We first prove that this  verifier $V'_x$ meets the completeness condition.
Consider the unique ground state $\ket{\Omega_x}$ of the Hamiltonian $H^{(x)}$ specified in <Ref> as a witness state of $V'_x$, and let $\lambda_0:=\lambda_{\min}\big(H^{(x)}\big)=1-p_{\rm acc}=\nu$ be the ground energy of $H^{(x)}$ corresponding to the maximum acceptance probability $p_{\rm acc}$ of $V_x$.
Consequently, we obtain the following by combining with the implementation error $\epsilon$ of $\exp(-H^{(x)} t)$ specified in <Ref>:

\[\Pr{V'_x \text{ accepts } \ket{\Omega_x}} = \frac{1+\cos(\nu t)}{2}
\text{ and }
c'(n) = \frac{1+\cos(\nu t)}{2}-\epsilon.\]

Soundness. For the soundness condition, we consider a quantum state $\ket{\psi}=\alpha_0 \ket{\Omega_x} + \sum_{1 \leq j < N} \alpha_j \ket{\Phi_x^{(j)}}$, where the coefficients $\{\alpha_j\}_{0 \leq j < N}$ satisfies that $\sum_{0 \leq j < N} |\alpha_j|^2=1$ and $\ket{\Phi_x^{(j)}}$ is the $j$-th excited state of $H^{(x)}$, as a witness state of the verifier $V'_x$, we thus obtain the corresponding acceptance probability $p'_{\rm acc}$ and the resulting state $\rho_{\psi}$, respectively:

\begin{equation}
\label{eq:pcc-soundness-all}
p'_{\rm acc} =\Pr{V'_x \text{ accepts } \ket{\psi}} = |\alpha_0|^2 \cdot \frac{1+\cos(\lambda_0)}{2} + \sum_{1 \leq j < N} |\alpha_j|^2 \cdot \frac{1+\cos(\lambda_j t)}{2} \geq s(n),
\end{equation}

\begin{equation}
\label{eq:resulting-state-soundness}
\begin{aligned}
\rho_{\psi} = \frac{1}{4 p'_{\rm acc}} V_x^{\dagger} \Tr_{\sfC} \Bigg(&\Big(\alpha_0(1+e^{-i\lambda_0 t}) \ket{\Omega_x} + \sum_{1\leq j < N} \alpha_j (1+e^{-i\lambda_j t}) \ket{\Phi_x^{(j)}}\Big) \\
&\Big( \alpha^*_0(1+e^{i\lambda_0 t}) \bra{\Omega_x} + \sum_{1\leq j < N} \alpha^*_j (1+e^{i\lambda_j t}) \bra{\Phi_x^{(j)}} \Big) \Bigg) V_x.
\end{aligned}
\end{equation}

Here, $\lambda_j$ (${1 \leq j < N}$) is the $j$-th excited energy corresponding to $j$-th excited state $\ket{\Phi_x^{(j)}}$ such that $\lambda_1 \leq \cdots \leq \lambda_{N-1} \leq \pi$.
It is noteworthy that the fidelity (overlap) between the resulting state $\rho_{\psi}$ and the unique witness state $\ket{w_x}\bra{w_x}$ is mostly decided by $|\alpha_0|^2$.
To upper-bound $\td(\rho_{\psi},\ket{w_x}\bra{w_x})$, it suffices to minimize $|\alpha_0|^2$ amongst all quantum states $\ket{\psi}$ such that $V'_x$ accepts $\ket{\psi}$ with probability at least $s(n)$.
Accordingly, we need to maximize $|\alpha_1|^2$ because $\exp(-i\lambda_1 t)$ contributes the largest possible weight amongst all eigenvalues of $H^{(x)}$ except for $\lambda_0$. Meanwhile, we can without loss of generality assume that $\alpha_2=\cdots=\alpha_{N-1}=0$, then we obtain the following derived from <Ref>:

\begin{equation}
\label{eq:pcc-soundness}
p'_{\rm acc} = |\alpha_0|^2 \cdot \frac{1+\cos(\lambda_0 t)}{2} + (1-|\alpha_0|^2)\cdot \frac{1+\cos(\lambda_1 t)}{2} \geq s'(n).
\end{equation}

Furthermore, we can assume that $(1+\cos(\lambda_1 t)/2) \leq s'(n) \leq (1+\cos(\lambda_0 t))/2$, otherwise $\ket{\psi}$ will be orthogonal to $\ket{\Omega_x}$ which means that $|\alpha_0|^2=0$. By adapting $\rho_{\psi}$ in <Ref> according to the choice of $\{\alpha_i\}_{2\leq i < N}$ with $\lambda_0=\nu$, we have derive that:

\begin{equation}
\label{eq:fidelity-lower-bound}
\begin{aligned}
\F^2(\rho_{\psi},\ket{w_x}\bra{w_x}) &= \bra{w_x} \rho_{\psi} \ket{w_x}\\
&\geq \frac{1}{4 p'_{\rm acc}} \bra{w_x} V_x^{\dagger} \Tr_{\sfC} \big( |\alpha_0|^2 (1+e^{-i\nu t}) \ket{\Omega_x}\bra{\Omega_x} (1+e^{i\nu t}) \big) V_x \ket{w_x}\\
& \geq \frac{|\alpha_0|^2}{p'_{\rm acc}} \cdot \frac{(1+\cos(\nu t))^2}{4} \cdot (1-\delta_1)\\
& := \frac{|\alpha_0|^2}{p'_{\rm acc}} \cdot (1-\delta_0)^2 \cdot (1-\delta_1)
\end{aligned}
\end{equation}

Here, the third line is because of $\bra{w_x} V_x^{\dagger} \Tr_{\sfC} \big(  \ket{\Omega_x}\bra{\Omega_x} \big) V_x \ket{w_x} \geq 1-\delta_1$, and the last line defines $\delta_0:=(1-\cos(\nu t))/2$.
By employing <Ref> on <Ref>, we obtain:

\begin{equation}
\label{eq:trace-dist-upper-bound}
\begin{aligned}
\td(\rho_{\psi},\ket{w_x}\bra{w_x}) &\leq 1-\F(\rho_{\psi},\ket{w_x}\bra{w_x})
= 1-(1-\delta_0)\cdot \sqrt{1-\delta_1} \cdot \frac{|\alpha_0|}{p'_{\rm acc}}.
\end{aligned}
\end{equation}

We then establish a lower bound of $|\alpha_0|^2/p'_{\rm acc}$ and the corresponding soundness parameter $s'$ in <Ref>, and the proof will be deferred.

$|\alpha_0|^2/p'_{\rm acc} \geq 1-q(\nu\delta_1 t/T^3)$ for some polynomial $q$.
Moreover, the choice of parameters implies that $s'(n) = \frac{1}{4} \big((1+\cos(\lambda_1 t)\big)\big(2+\cos(\nu t) - \cos(\lambda_1 t)\big) + \epsilon$.

Plugging <Ref> into <Ref> with  $\delta':= \max\{\delta_0,\delta_1,q(\nu\delta_1 t/T^3)\}$, we obtain:

\[\td(\rho_{\psi}, \ket{w_x}\bra{w_x}) \leq 1-(1-\delta_0)\sqrt{(1-\delta_1)(1-q(\nu\delta_1 t/T^3))} \leq 1-(1-\delta')^2 = 2\delta'-(\delta')^2 \leq 2\delta'.\]

By utilizing <Ref>, we note that the implementation error $\epsilon$ of $\exp(-H^{(x)}t)$ is exponentially small, and thus finish the proof by noticing $\td(\rho'_{\psi}, \ket{w_x}\bra{w_x}) \leq O(\delta')$.

At the end of this subsection, we provide the proof of <Ref>.

We establish a lower bound for $|\alpha_0|^2/p'_{\rm acc}$ by a direct calculation:

\begin{equation*}
\label{eq:UQMAwitness-bound1}
\begin{aligned}
\frac{|\alpha_0^2|}{p'_{\rm acc}} &= \frac{|\alpha_0|^2}{|\alpha_0|^2 \cdot \frac{1+\cos(\lambda_0 t)}{2} + (1-|\alpha_0|^2)\cdot \frac{1+\cos(\lambda_1 t)}{2}} ~{\color{teal}:= f(|\alpha_0|^2)}\\
&\geq \frac{(2s(n)-1) - \cos(\lambda_1 t)}{s(n) \cdot (\cos(\lambda_0 t) - \cos(\lambda_1 t))}\\
&= \frac{2\xi}{1+\xi \cos(\lambda_0 t) + (1-\xi) \cos(\lambda_1 t)} ~{\color{teal}:= g(\xi)}\\
&\geq \frac{2}{1+\cos(\lambda_1 t)} \cdot \xi - \frac{2(\cos(\lambda_0 t)-\cos(\lambda_1 t))}{(1+\cos(\lambda_1 t)^2)} \cdot \xi^2.
\end{aligned}
\end{equation*}

Here, the second line is due to the fact that the function $f(|\alpha_0|^2)$ is monotonically increasing on the interval $[0,1]$, and the minimum achieves when $|\alpha_0|^2 = \frac{(2s(n)-1) - \cos(\lambda_1 t)}{\cos(\lambda_0 t) - \cos(\lambda_1 t)}$ following from <Ref>. The third line owing to choose $s:=\xi \cdot \frac{1+\cos(\lambda_0)}{2} + (1-\xi) \cdot \frac{1+\cos(\lambda_1 t)}{2}$ for $0 \leq \xi \leq 1$, and the last line is because of truncated Taylor series of the function $g(\xi)$.

By choosing $\xi = (1+\cos(\lambda_1 t))/2$ and utilizing the bound $\Delta\big(H^{(x)}\big)=\lambda_1 - \lambda_0 = \lambda_1 - \nu \geq \Omega(\nu\delta_1/T^3)$ in <Ref>, we have the following for some polynomial $q$:

\begin{equation*}
\label{eq:UQMAwitness-bound2}
\frac{2}{1+\cos(\lambda_1 t)} \cdot \xi - \frac{2(\cos(\nu t)-\cos(\lambda_1 t))}{(1+\cos(\lambda_1 t)^2)} \cdot \xi^2 = 1- \frac{\cos(\nu t) - \cos(\lambda_1 t)}{2} \geq 1-q\Big( \frac{\nu\delta_1 t}{T^3} \Big).
\end{equation*}

Accordingly, we obtain the soundness parameter $s$ by combining the implementation error $\epsilon$ of $\exp(-iH^{(x)}t)$ specified in <Ref>:
$s'(n) = \big((1+\cos(\lambda_1 t)\big)\big(2+\cos(\nu t) - \cos(\lambda_1 t)\big)/4 + \epsilon.$

§.§ Weighted circuit-to-Hamiltonian construction, revisited

Finally, we demonstrate the weighted circuit-to-Hamiltonian construction with a spectral gap lower bound, aligning the line of [5, 10].

We consider an  verifier $V_x$ with maximum acceptance probability $1-\nu$, where the verification circuit consists of a sequence of local quantum gates $U_1,\cdots,U_T$. To begin, we specify a weighted circuit-to-Hamiltonian construction $H^{(x)}:=H^{(x)}_{\rm prop} + H_{\rm in} + H_{\rm out}$ proposed in [5][We note that by utilizing a spacetime circuit-to-Hamiltonian construction outlined in [10], we can achieve a constantly improved distance parameter $\delta$.]. Here, $H_{\rm in}:=\ket{\bar{0}}\bra{\bar{0}} \otimes \Pi_{\rm in}$ and $H_{\rm out}:=\ket{T}\bra{T} \otimes \Pi_{\rm out}$ correspond to input and output constraints, respectively. It is straightforward to see that the ground energy of $H^{(x)}$ is $1-(1-\nu)=\nu$. This construction closely resembles the standard circuit-to-Hamiltonian construction [40], except for the weighted ground state resulting from the distinct propagation term $H^{(x)}_{\rm prop}$.

Constructing the propagation term.
Next, we proceed to construct the propagation term $H^{(x)}{\rm prop}$ for the given weights, specifically a probability distribution $\pi$. We define the ground state of $H^{(x)}$ as $\ket{\Omega_x} := \sum_{t=0}^T \sqrt{\pi_t} \ket{t} \otimes (U_t\cdots U_1) \ket{w_x}$, where $\ket{w_x}$ represents the unique witness state of $V_x$, and $\pi=(\delta_1/T,\cdots,\delta_1/T,1-\delta_1)$ is a probability distribution on $[T]=\{0,1,\cdots,T\}$.

Our construction of the propagation term is based on the transition matrix $P$ of random walks on a $(T+1)$-node path with the stationary distribution $\pi$. Here, the specific form of the matrix $P$ is provided in <Ref> for the given $\pi$. By employing <Ref>, we obtain an $O(\log n)$-local stoquastic frustration-free Hamiltonian $H^{(T)}_{\rm path}$ derived from $P$. Let us consider a unitary operator $W_x:=\sum_{t=0}^{T} \ket{t}\bra{t}\otimes U_t\cdots U_1$ associated with the given $V_x$. By combining $H^{(T)}_{\rm path}$ with Lemma 2 in [5], we arrive at the expression for the propagation term $H^{(x)}_{\rm prop}$:

\[\begin{aligned}
H^{(x)}_{\rm prop} &= W_x (H^{(T)}_{\rm path} \otimes I) W_x^{\dagger} \\
&=\sum_{t=0}^T (1-P_{t,t})\ket{t}\bra{t}\otimes I-\sum_{t=0}^T \left(\tfrac{\sqrt{\pi_t}}{\sqrt{\pi_{t-1}}}P_{t,t-1} \ket{t}\bra{t-1}\otimes U_t + \tfrac{\sqrt{\pi_{t-1}}}{\sqrt{\pi_t}} P_{t-1,t} \ket{t-1}\bra{t}\otimes U_t^{\dagger} \right).
\end{aligned}\]

Lower-bounding the spectral gap.
It is left to establish a lower bound for the spectral gap $\Delta(H^{(x)})$.
By applying Cheeger's inequality (<Ref>), we obtain $\Delta(H^{(x)}_{\rm prop}) = \Delta_P \geq \frac{1}{2} \Phi_G^2$, where $\Phi_G$ is the conductance of the underlying $(T+1)$-node path graph $G$.
Notably, the weights in $G$ are primarily concentrated on the $(T+1)$-th node since $\delta_1$ is tiny.
The minimum conductance $\Phi_G=\min_{S \subseteq [T]} \Phi_G(S)$ is thus achieved at the subset $S=[T-1]:=\{0,1,\cdots,T-1\}$. Consequently, we can deduce:

\begin{equation}
\label{eq:conductance-lower-bound}
\Phi_G = \Phi_G([T-1]) = \frac{1}{\pi_{[T-1]}} \pi_{T-1} P_{T-1,T} = \frac{1}{\delta_1} \cdot \pi_{T-1} \cdot \frac{1}{4}\min\left\{1,\frac{\pi_T}{\pi_{T-1}}\right\} = \frac{1}{4T}.
\end{equation}

From <Ref>, we infer that $\Delta(H^{(x)}{\rm prop}) \geq \Omega(T^{-2})$.

Now, let $C(\tau,T)$ be the set of quantum circuits of size $T$ that achieve the maximum acceptance probability $\tau$ amongst states satisfying the input and output constraints $\Pi_{\In}$ and $\Pi_{\Out}$, respectively. In particular, $C(\tau,T):=\big\{U_1,\cdots,U_T: \max\limits_{\ket{\xi}\in\ker(\Pi_{\In}),\ket{\eta}\in\ker(\Pi_{\Out})} |\bra{\xi} U_1\cdots U_T \ket{\eta}|^2 =\tau\big\}$. By employing Lemma 3 in [5], we obtain the following when $\tau=1-\nu$:

\begin{equation}
\label{eq:spectral-gap-lower-bound}
\begin{aligned}
\Delta(H^{(x)}) &\geq \min_{U:=U_1,\cdots, U_T \in C(1-\nu,T)} \left( \lambda_{\min}\big(H^{(U)}\big) - \lambda_{\min} \big(H^{(U)}_{\rm prop}\big) \right)\\
&\geq \Delta\big(H_{\rm path}^{(T)}\big) \cdot \frac{1-\sqrt{1-\nu}}{4} \cdot \min\{\pi_0,\pi_T\} \\
&= \Omega\left( \frac{\nu\delta_1}{T^3} \right).
\end{aligned}
\end{equation}

Here, the last line is because $\sqrt{1-x} \leq 1-x/2$ when $0 \leq x \leq 1$.
As <Ref> establishes the desired spectral gap lower bound, this thus finishes the proof.

§  ACHIEVES PERFECT COMPLETENESS

In this section, we will present a state-synthesizing analogue of the $\QCMA=\QCMA_1$ theorem [33].

[ is closed under perfect completeness]theoremstateQCMAPerfectCompleteness

For any efficiently computable functions $c(n)$, $s(n)$ and $\delta(n)$ such that $c(n)-s(n) \geq 1/\poly(n)$, we have that

\[\stateQCMA_{\delta}[c,s] \subseteq \stateQCMA_{\delta'}[1,s'],\]

where $s' = \tfrac{1}{2}\left( \tfrac{s}{c}\right)^3 - 2\left( \tfrac{s}{c}\right)^2 + \tfrac{5}{2}\left( \tfrac{s}{c}\right)$ and $\delta'(n)=\delta(n)+\exp(-\poly(n))$.

Furthermore, for any  verifier utilizing the “Pythagorean” gateset, we have $\delta'=\delta$.

It is noteworthy that while error reduction for  (a corollary of <Ref>) preserves the distance between the resulting state and the target state, this distance-preserving property in <Ref> is gateset-dependent since changing gatesets will worsen the distance parameter (<Ref>). This is because the key insight from [33], that the maximum acceptance probability of a (or ) verifier can be expressed with polynomially many bits, only applies to certain gatesets, elaborating in <Ref>.

For state-synthesizing complexity classes, we require to deal with not only the maximum acceptance probability but also the resulting states after the computation. To well-approximate any quantum states with a designated gateset $\calS$, this gateset $S$ must generate a dense subgroup of $\mathrm{SU}(2^n)$ for large enough $n$. However, this does not hold for the gateset used in [33][To be specific, the proof of Theorem 3.2 in [58] indicates that the gateset consists of  and  merely generates a dense subgroup of $\mathrm{SO}(8)$.].
We then use the “Pythagorean” gateset in [35] where real and imaginary parts of all matrix entries are rational numbers.

Analogous to [33], to achieve perfect completeness, we also utilize the quantum rewinding lemma [63] with a single iteration. As stated in <Ref>, it suffices to construct a new  verifier that the acceptance probability is exactly $1/2$ for the completness condition.

Our construction of the new $\stateQCMA$ verifier with perfect completeness tightly follows the construction for  (i.e., Figure 1 in [33]). The only difference is that the unitary transformation $Q$ since the original construction in [33] cannot preserve the resulting states, which also leads to a slightly different analysis for the soundness condition.

We begin with two lemmas that are crucial for our analysis.

For all unitary transform $U$ on an $n$-qubit system that consists of $l(n)$ gates from the “Pythagorean” gateset where $l$ is a polynomial, the probability $p_{acc}$ that the first qubit of $U\ket{0^n}$ is found in the state $\ket{1}$ (i.e., the measurement on the computational basis) is expressed as $p_{acc}=\frac{k}{5^{l(n)}}$ where $k$ is an integer from the range $[0,5^{l(n)}]$.

Let $Q$ be a quantum circuit such that $Q\ket{\psi}=\sqrt{p(\psi)}\ket{0}\ket{\psi_0}+\sqrt{1-p(\psi)}\ket{1}\ket{\psi_1}$, and $p:=p(\psi)\in (0,1)$ is constant over all choices of the input $\ket{\psi}$.
Then the probability of producing $\ket{\psi_0}$ within $t$ iterations is $1-(1-p)(1-2p)^{2t}$.

Particularly, the probability of producing $\ket{\psi_0}$ by the single-iteration quantum rewinding of $Q$ is $p+4p(1-p)^2$, as well as this achieves the perfect success probability when $p=1/2$.

Now we proceed with the actual proof.

Let $V_{x,w}$ be a $\stateQCMA_{\delta}[c,s]$ verification circuit with a classical witness $w$ of size $m(n)$ where $n:=|x|$ and $c(n)$ is a sufficiently large constant[This is achievable by first applying error reduction on the given  verifier.]. Using Lemma <ref>, we first convert $V_{x,w}$ to another circuit that utilizes a polynomial number of gates from the gateset $\mathcal{G}$. Note that while we can assume that the completeness parameter $c(n)$ does not increase by this conversion, the trace distance error increases to $\delta'(n):=\delta(n) + \exp(-\poly(n))$ owing to the triangle inequality.
In the rest of the proof, we use $V_{x,w}$ as the converted circuit. So $V_{x,w}$ is assumed to be a $\stateQCMA_{\delta'}[c,s]$ circuit. Utilizing by Lemma <ref>, the acceptance probability of each $V_{x,w}$ is expressed as $k_{x,w}/5^{l(n)}$ for some integer $k_{x,w}\in\{0,1,\cdots,5^{l(n)}\}$ and polynomial $l$ which represents the size of the circuit $V_{x,w}$.

$\ket{0}_{\sfO}$     [4,steps=3,style=dashed, rounded corners,fill=red!20, inner xsep=2pt, inner ysep=2pt, background]$Q_{x,w,k}$               1?     [4,bundle=3,4]Q^†_x,w,k     [4,bundle=3,4]2|0̅⟩⟨0̅|_(,,)-I     [4,bundle=3,4]Q_x,w,k     1?

[wires=2]$\ket{\bar{0}}_{\sfR}$         [2,bundle=2]V_x,w     -1

[alternate]     	    [alternate]     [alternate]                 [alternate]

$\ket{\bar{0}}_{\sfS}$     [alternate]     [1,bundle=1]Uniform_2k     [1,bundle=1]< 5^l(n)?-3     [alternate]                 [alternate]

The new verification circuit $\tilde{V}_{x,w}$

Now we construct a $\stateQCMA_{\delta'}[1,s']$ verifier such that the verification circuit $\tilde{V}_{x,w}$ is the single-iteration quantum rewinding of $Q_{x,w,k}$ with a pre-processing, where the unitary transformation $Q_{x,w,k}$ is shown in <Ref>.
To be precise, $\tilde{V}_{x,w}$ will simply reject if $k/5^{l(n)} < c(n)$[The claimed maximum acceptance probability $k/5^{l(n)}$ are supposed to correspond to legal witnesses.], then $\tilde{V}_{x,w}$ will perform the construction in <Ref>.

1. Prepare the uniform superposition $\frac{1}{\sqrt{2k}}\sum_{z\in\{0,1,\cdots,2k-1\}} \ket{z}$ in $\sfS$
2. Apply $V_{x,w}$ on $\sfR$
3. Apply a  gate that targets at $\sfO$, and the first control qubit is the designated output qubit in $\sfR$, as well as the second control qubit is decided by whether the integer in $\sfS$ at most $5^{l(n)}$.
Unitary Transformation $Q_{x,w,k}$

In <Ref>, all registers $\sfO,\sfR,\sfS$ are assumed to be initialized to all-zero state, where $\sfO$ is a single-qubit register, and $\sfR$ is the $(q(n) + n)$-qubit register for some polymonial $q$, on which the verification circuit $V_{x,w}$ acts (and the last $n$-qubit of $\sfR$ is assumed to contain the output), as well as $\sfS$ is a $t$-qubit register where $t$ is the minimum integer satisfying $2^t \geq 5^{l(n)}$.
Moreover, the first step in <Ref> can be implemented by the exact amplitude amplification.[Note that any integer in $[0,5^{l(n)}-1]$ can be decomposed into a product of some power of $2$ and some odd integer. Then we can employ with the construction in Figure 12 in [12].]
We then show that the unitary transformation $Q_{x,w,k}$ indeed preserves the resulting states of the verification circuit $V_{x,w}$ as <Ref>, whose proof is deferred to the last part of this section.

For the unitary transformation $Q_{x,w,k}$ specified in <Ref>, the success probability is $\Pr{Q_{x,w,k} \text{ accepts}}:=\| \Pi_{\rm acc} Q_{x,w,k} \ket{\bar{0}}_{(\sfO,\sfR,\sfS)} \|^2 = k_{x,w}/(2k)$ where $\Pi_{\rm acc}:=\ket{1}\bra{1}_{\sfO}\otimes I_{(\sfR,\sfS)}$. Moreover, $Q_{x,w,k}$ preserves the state synthesized by $V_{x,w}$.

Plugging <Ref> into <Ref>, we obtain that

\begin{equation}
\label{eq:stateQCMA-Pacc}
\Pr{\tilde{V}_{x,w} \text{ accepts }} = \frac{1}{2}\left( \frac{k_{x,w}}{k}\right)^3 - 2\left( \frac{k_{x,w}}{k}\right)^2 + \frac{5}{2}\left( \frac{k_{x,w}}{k}\right):=g\left(\frac{k_{x,w}}{k}\right),
\end{equation}

as guaranteed that $k \geq c(n)\cdot 2^{l(n)}$. We further notice the following fact[<Ref> follows from the facts that $t=1$ and $t=5/3$ are roots of $g'(t)=0$, as well as $g'(0) > 0$.]:

For $0 \leq t \leq 1$, $g(t)$ defined in <Ref> is monotonically increasing.

It is thus left to analyze the maximum acceptance probability of $\tilde{V}_{x,w}$.

* For the completeness condition, equipped with <Ref>, the maximum achieves if $t:=k_{x,w}/k=1$. Namely, the claimed maximum acceptance probability $k$ of $V_{x,w}$ is indeed the maximum acceptance probability $k_{x,w}$.

* For the soundness condition, we observe below for any illegal witness $w\in\binset^{m(n)}$:

\[\frac{k_{x,w}}{k} \leq \frac{s(n)\cdot 5^{l(n)}}{c(n)\cdot 5^{l(n)}} = \frac{s(n)}{c(n)}.\]

Since $k_{x,w}/k\leq s(n)/c(n)$,
this indicates that the acceptance probability of $V_{x,w}$ is $s'(n)\leq g(s(n)/c(n))$. By <Ref>, $\Pr{V_{x,w} \text{ accepts }}\leq s'(n)$ holds for any choice of $k$ as long as the witness $w$ is illegal.
Note that $c$ is a constant and the promise gap $c(n)-s(n)\geq 1/p(n)$ where $p(n)$ is a polynomial of $n$, this deduces that

\begin{equation}
\label{eq:stateQCMA1-soundness}
s'(n)\leq g\left(1-\frac{c(n)}{p(n)}\right)=1-\frac{1}{2}\left[\left(\frac{c(n)}{p(n)}\right)^2+\left(\frac{c(n)}{p(n)}\right)^3\right]:=1-\frac{1}{q(n)}.
\end{equation}

We complete the proof by noticing $q(n)$ is a polynomial of $n$.

In the remaining of this section, we complete the proof of <Ref>.

Let $V_{x,w}\ket{\bar{0}}_{\sfR} = \ket{0}\ket{\phi_0} + \ket{1}\ket{\phi_1}$ be the quantum state just before the final measurement of the verification circuit $V_{x,w}$ where $n:=|x|$. This deduces that

\[\Pr{V_{x,w} \text{ accepts }}=\|\ket{1}\bra{1}_{\Out}V_{x,w}\ket{\bar{0}}_{\sfR}\|_2^2=\innerprod{\phi_1}{\phi_1}=k_{x,w}/5^{l(n)}.\]

The output state conditioned on accepting is then defined as the state we obtain by tracing out all but the last $n$-qubit of the density matrix $\frac{5^{l(n)}}{k_{x,w}}\ket{\phi_1}\bra{\phi_1}$.
The quantum state in $(\mathsf{O,R,S})$ before the last step in <Ref> is then

\begin{equation*}
\ket{0}_{\mathsf{O}}\otimes \big[ \ket{0}\ket{\phi_0}+\ket{1}\ket{\phi_1} \big]_{\mathsf{R}}\otimes \frac{1}{\sqrt{2k}} \sum_{0\leq z <2k} \ket{z}_{\mathsf{S}}
\end{equation*}

and therefore the state after applying <Ref> is $Q_{x,w,k}\ket{\bar{0}}_{(\mathsf{O,R,S})}$ as below:

\[\ket{0}_{\mathsf{O}}\otimes \ket{0}\ket{\phi_0}_{\mathsf{R}} \otimes \frac{1}{\sqrt{2k}}\sum_{z=0}^{2k-1} \ket{z}_{\mathsf{S}}
+\ket{0}_{\mathsf{O}}\otimes \ket{1}\ket{\phi_1}_{\mathsf{R}} \otimes \frac{1}{\sqrt{2k}}\sum_{z=5^{l(n)}}^{2k-1} \ket{z}_{\mathsf{S}}
+\ket{1}_{\mathsf{O}}\otimes \ket{1}\ket{\phi_1}_{\mathsf{R}} \otimes \frac{1}{\sqrt{2k}}\sum_{z=0}^{5^{l(n)}-1} \ket{z}_{\mathsf{S}}\]

We thus conclude that

\[\begin{aligned}
\Pr{Q_{x,w,k} \text{ accepts}}
= \innerprod{\phi_1}{\phi_1} \cdot \bigg\|\frac{1}{\sqrt{2k}}\sum_{z=0}^{5^{l(n)}-1} \ket{z}_{\mathsf{S}}\bigg\|^2_2 = \frac{k_{x,w}}{5^{l(n)}} \cdot \frac{5^{l(n)}}{2k} = \frac{k_{x,w}}{2k}.
\end{aligned}\]

Furthermore, we notice that the resulting state of $Q_{x,w,k}$ is

\[(\ket{1}\bra{1}\otimes(\ket{\phi_1}\bra{\phi_1})_{\sfR}\otimes \left(\ket{0}\bra{0}\otimes \ket{+}\bra{+}^{\otimes l(n)}\right)_{\sfS}.\]

By tracing out $\mathsf{S}$ and all but the last $n$-qubit of $\mathsf{R}$, we get the resulting state of $V_{x,w}$.

§ ACKNOWLEDGMENTS

The authors were supported by JSPS KAKENHI Grants Nos. JP19H04066, JP20H00579, JP20H05966, JP20H04139, JP21H04879 and MEXT Quantum Leap Flagship Program (MEXT Q-LEAP) Grants Nos. JPMXS0118067394 and JPMXS0120319794. MM was also supported by JST, the establishment of University fellowships towards the creation of science technology innovation, Grant No. JPMJFS2120.
We are grateful to Henry Yuen and Chinmay Nirkhe for insightful discussions and for bringing [10] to our attention. Additionally, YL thanks Naixu Guo for helpful discussions on quantum singular value transformations.
Circuit diagrams were drawn by the Quantikz package [37].

[1]
Scott Aaronson.
Quantum copy-protection and quantum money.
In 2009 24th Annual IEEE Conference on Computational
Complexity, pages 229–242. IEEE, 2009.

[2]
Scott Aaronson.
The complexity of quantum states and transformations: from quantum
money to black holes.
arXiv preprint arXiv:1607.05256, 2016.

[3]
Dorit Aharonov, Michael Ben-Or, Fernando GSL Brandao, and Or Sattath.
The pursuit of uniqueness: Extending valiant-vazirani theorem to the
probabilistic and quantum settings.
Quantum, 6:668, 2022.

[4]
Dorit Aharonov, Vaughan Jones, and Zeph Landau.
A polynomial quantum algorithm for approximating the Jones
Algorithmica, 55(3):395–421, 2009.

[5]
Johannes Bausch and Elizabeth Crosson.
Analysis and limitations of modified circuit-to-hamiltonian
Quantum, 2:94, 2018.

[6]
Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D
Exponential improvement in precision for simulating sparse
In Proceedings of the forty-sixth annual ACM symposium on Theory
of computing, pages 283–292, 2014.

[7]
Dominic W Berry, Andrew M Childs, Richard Cleve, Robin Kothari, and Rolando D
Simulating hamiltonian dynamics with a truncated Taylor series.
Physical review letters, 114(9):090502, 2015.

[8]
Dominic W. Berry, Andrew M. Childs, Richard Cleve, Robin Kothari, and
Rolando D. Somma.
Simulating Hamiltonian dynamics with a truncated Taylor series.
Physical Review Letters, 114(9):090502, 2015.

[9]
Dominic W Berry, Andrew M Childs, and Robin Kothari.
Hamiltonian simulation with nearly optimal dependence on all
In 2015 IEEE 56th annual symposium on foundations of computer
science, pages 792–809. IEEE, 2015.

[10]
Thomas C Bohdanowicz, Elizabeth Crosson, Chinmay Nirkhe, and Henry Yuen.
Good approximate quantum LDPC codes from spacetime circuit
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing, pages 481–490, 2019.

[11]
John Bostanci, Yuval Efron, Tony Metger, Alexander Poremba, Luowen Qian, and
Henry Yuen.
Unitary complexity and the Uhlmann transformation problem.
arXiv preprint arXiv:2306.13073, 2023.

[12]
Ryan Babbush, Craig Gidney, Dominic W Berry, Nathan Wiebe, Jarrod McClean,
Alexandru Paler, Austin Fowler, and Hartmut Neven.
Encoding electronic spectra in quantum circuits with linear T
Physical Review X, 8(4):041015, 2018.

[13]
Rui Chao, Dawei Ding, Andras Gilyen, Cupjin Huang, and Mario Szegedy.
Finding angles for quantum signal processing with machine precision.
arXiv preprint arXiv:2003.02831, 2020.

[14]
Léo Colisson, Frédéric Grosshans, and Elham Kashefi.
Non-destructive zero-knowledge proofs on quantum states, and
multi-party generation of authorized hidden GHZ states.
arXiv preprint arXiv:2104.04742, 2021.

[15]
Marcos Crichigno and Tamara Kohler.
Clique Homology is $\mathsf{QMA}_1$-hard.
arXiv preprint arXiv:2209.11793, 2022.

[16]
Léo Colisson, Garazi Muguruza, and Florian Speelman.
Oblivious transfer from zero-knowledge proofs, or how to achieve
round-optimal quantum oblivious transfer and zero-knowledge proofs on quantum
arXiv preprint arXiv:2303.01476, 2023.

[17]
Richard P Feynman.
Simulating physics with computers.
International Journal of Theoretical Physics, 21(6-7):467–488,

[18]
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), volume 55, page 14. Schloss
Dagstuhl–Leibniz-Zentrum fuer Informatik, 2016.

[19]
Bill Fefferman and Cedric Lin.
Quantum Merlin Arthur with exponentially small gap.
arXiv preprint arXiv:1601.01975, 2016.

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

[21]
Bill Fefferman and Zachary Remscrim.
Eliminating intermediate measurements in space-bounded quantum
In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory
of Computing, pages 1343–1356, 2021.

[22]
Christopher A Fuchs and Jeroen van de Graaf.
Cryptographic distinguishability measures for quantum-mechanical
IEEE Transactions on Information Theory, 45(4):1216–1227,

[23]
András Gilyén.
Quantum singular value transformation & its algorithmic
PhD thesis, University of Amsterdam, 2019.

[24]
Oded Goldreich.
Computational Complexity: A Conceptual Perspective.
Cambridge University Press, 2008.

[25]
Uma Girish and Ran Raz.
Eliminating intermediate measurements using pseudorandom generators.
In 13th Innovations in Theoretical Computer Science Conference,
ITCS 2022, page 76. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik, 2022.

[26]
Sevag Gharibian and Dorian Rudolph.
Quantum Space, Ground Space Traversal, and How to Embed Multi-Prover
Interactive Proofs into Unentanglement.
In 14th Innovations in Theoretical Computer Science Conference
(ITCS 2023), pages 53:1–53:23, 2023.

[27]
Uma Girish, Ran Raz, and Wei Zhan.
Quantum logspace algorithm for powering matrices with bounded norm.
In 48th International Colloquium on Automata, Languages, and
Programming (ICALP 2021), page 73. Schloss Dagstuhl-Leibniz-Zentrum für
Informatik, 2021.

[28]
András Gilyén, Yuan Su, Guang Hao Low, and Nathan Wiebe.
Quantum singular value transformation and beyond: exponential
improvements for quantum matrix arithmetics.
In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing (STOC 2019), pages 193–204, 2019.

[29]
Jeongwan Haah.
Product decomposition of periodic functions in quantum signal
Quantum, 3:190, 2019.

[30]
Sandy Irani, Anand Natarajan, Chinmay Nirkhe, Sujit Rao, and Henry Yuen.
Quantum search-to-decision reductions and the state synthesis
In Proceedings of the 37th Computational Complexity Conference,
pages 1–19, 2022.

[31]
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous.
Journal of the ACM (JACM), 58(6):1–27, 2011.

[32]
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, and
Shengyu Zhang.
On the power of a unique quantum witness.
Theory of Computing, 8(1):375–400, 2012.

[33]
Stephen P Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura.
Achieving perfect completeness in classical-witness quantum
Merlin-Arthur proof systems.
Quantum Information & Computation, 12(5-6):461–471, 2012.

[34]
Zhengfeng Ji, Yi-Kai Liu, and Fang Song.
Pseudorandom quantum states.
In Advances in Cryptology–CRYPTO 2018: 38th Annual
International Cryptology Conference, pages 126–152. Springer, 2018.

[35]
Stephen P Jordan and Daniel Nagaj.
QCMA with one-sided error equals QCMA with two-sided error.
arXiv preprint arXiv:1111.5306, 2011.

[36]
Camille Jordan.
Essai sur la géométrie à $ n $ dimensions.
Bulletin de la Société mathématique de France,
3:103–174, 1875.

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

[38]
Alexei Yu Kitaev.
Quantum measurements and the Abelian stabilizer problem.
arXiv preprint quant-ph/9511026, 1995.

[39]
Alexei Yu Kitaev.
Quantum computations: algorithms and error correction.
Russian Mathematical Surveys, 52(6):1191, 1997.

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

[41]
Greg Kuperberg.
How hard is it to approximate the Jones polynomial?
Theory of Computing, 11(1):183–219, 2015.

[42]
Guang Hao Low and Isaac L Chuang.
Hamiltonian simulation by uniform spectral amplification.
arXiv preprint arXiv:1707.05391, 2017.

[43]
Guang Hao Low and Isaac L Chuang.
Hamiltonian simulation by qubitization.
Quantum, 3:163, 2019.

[44]
Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan.
Algebraic methods for interactive proof systems.
Journal of the ACM (JACM), 39(4):859–868, 1992.

[45]
François Le Gall, Masayuki Miyamoto, and Harumichi Nishimura.
Distributed Merlin-Arthur synthesis of quantum states and its
arXiv preprint arXiv:2210.01389, 2022.

[46]
Yulong Li.
A simple proof of $\mathsf{PreciseQMA}=\mathsf{PSPACE}$.
arXiv preprint arXiv:2206.09230, 2022.

[47]
Seth Lloyd.
Universal quantum simulators.
Science, 273(5278):1073–1078, 1996.

[48]
David A Levin and Yuval Peres.
Markov chains and mixing times, volume 107.
American Mathematical Soc., 2017.

[49]
Chris Marriott and John Watrous.
Quantum Arthur–Merlin games.
computational complexity, 14(2):122–152, 2005.

[50]
Tony Metger and Henry Yuen.
arXiv preprint arXiv:2301.07730, 2023.

[51]
Michael A Nielsen and Isaac Chuang.
Quantum computation and quantum information.
American Association of Physics Teachers, 2002.

[52]
Daniel Nagaj, Pawel Wocjan, and Yong Zhang.
Fast amplification of $\mathsf{QMA}$.
Quantum Information & Computation, 9(11):1053–1068, 2009.

[53]
David Poulin and Pawel Wocjan.
Preparing ground states of quantum many-body systems on a quantum
Physical review letters, 102(13):130503, 2009.

[54]
Oded Regev.
Witness-preserving amplification of $\mathsf{QMA}$.
<https://cims.nyu.edu/ regev/teaching/quantum_fall_2005/ln/qma.pdf>,

[55]
Gregory Rosenthal.
Efficient quantum state synthesis with one query.
arXiv preprint arXiv:2306.01723, 2023.

[56]
Gregory Rosenthal and Henry Yuen.
Interactive proofs for synthesizing quantum states and unitaries.
In 13th Innovations in Theoretical Computer Science Conference
(ITCS 2022), volume 215, page 112. Schloss Dagstuhl–Leibniz-Zentrum f
$\{$$\backslash$" u$\}$ r Informatik, 2022.

[57]
Adi Shamir.
Journal of the ACM (JACM), 39(4):869–877, 1992.

[58]
Yaoyun Shi.
Both Toffoli and controlled-NOT need little help to do universal
quantum computation.
arXiv preprint quant-ph/0205115, 2002.

[59]
Alistair Sinclair and Mark Jerrum.
Approximate counting, uniform generation and rapidly mixing markov
Information and Computation, 82(1):93–133, 1989.

[60]
Dieter van Melkebeek and Thomas Watson.
Time-space efficient simulations of quantum computations.
Theory of Computing, 8(1):1–51, 2012.

[61]
Mikhail Vyalyi.
$\mathsf{QMA}=\mathsf{PP}$ implies that $\mathsf{PP}$ contains
In ECCCTR: Electronic Colloquium on Computational Complexity,
technical reports. Citeseer, 2003.

[62]
John Watrous.
Limits on the power of quantum statistical zero-knowledge.
In The 43rd Annual IEEE Symposium on Foundations of Computer
Science, 2002. Proceedings., pages 459–468. IEEE, 2002.

[63]
John Watrous.
Zero-knowledge against quantum attacks.
SIAM Journal on Computing, 39(1):25–58, 2009.

[64]
Huangjun Zhu and Masahito Hayashi.
Efficient verification of pure quantum states in the adversarial
Physical review letters, 123(26):260504, 2019.