Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2611.02819

unitaryQIP = unitaryPSPACE

Entong He, Fengning Ou, Mingnan Zhao

quant-phSubmitted Nov 2, 2026• Announced Nov 3, 2026• 0 citations
arXivHTMLPDF

Abstract

Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: $\mathsf{unitaryQIP}$ and $\mathsf{unitaryPSPACE}$ for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$ and thereby establish a unitary-complexity analogue of $\mathsf{QIP} = \mathsf{PSPACE}$ (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and $\mathsf{stateQIP}=\mathsf{statePSPACE}$ (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023). To prove $\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}$, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that $\mathsf{unitaryPSPACE}$ families can be synthesized in polynomial time with a $\mathsf{PSPACE}$ oracle. We then implement the oracle queries using auxiliary states prepared via the $\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}$ protocol (Rosenthal and Yuen, ITCS 2022). Beyond the equality, we show that our protocol for $\mathsf{unitaryPSPACE}$ can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of $\mathsf{EFI}$ pairs.

AI Summary

The paper asks whether interactive proofs characterize polynomial-space computation for worst-case unitary synthesis: applying a target unitary to an arbitrary unknown quantum input, rather than preparing a fixed state. It proves $\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}$, with both classes defined using arbitrarily inverse-polynomial synthesis error. The interactive characterization has perfect completeness and soundness threshold $1/2$; soundness bounds the conditional output error whenever a prover is accepted above that threshold. For $\mathsf{unitaryQIP}\subseteq\mathsf{unitaryPSPACE}$, an acceptance-rigidity lemma shows that soundness constrains a fixed prover’s acceptance probability across inputs. This allows a polynomial-space prover optimized for the all-zero input to work on every input. The simulation incurs error at most $c+\varepsilon+7\delta$, under stated completeness–soundness gap conditions. For the reverse inclusion, the construction builds on a recently announced positive solution to the unitary synthesis problem, establishing that polynomial-space unitaries admit polynomial-size synthesis circuits querying a fixed $\mathsf{PSPACE}$ language. Oracle queries are replaced by adaptive phase-state injection, with resource states verified through existing state-synthesis protocols. Quantitatively, $\mathsf{unitaryPSPACE}_{\delta^2/2^{14}}\subseteq\mathsf{unitaryQIP}_{0,s,\delta}$ for inverse-polynomially bounded parameters. Further results give three-round synthesis with polynomially many input copies and show that EFI pairs imply $\mathsf{BQP}\ne\mathsf{PSPACE}$, using polynomial-space Helstrom measurements and oracle synthesis. The three-round result does not establish constant-round synthesis with one input copy. Single-copy gap amplification, constant-round parallelization, and complete problems for the worst-case synthesis classes remain open.

Some signs of AI-generated textAI use disclosed
OpenAI GPT-6 was used extensively throughout the preparation of this manuscript, including for mathematical formulation, checking proof arguments, typesetting, and language polishing.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
102 pages

Related papers

Interactive Proofs for Synthesizing Quantum States and Unitaries

Gregory Rosenthal, Henry Yuen

Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion $\mathsf{PSPACE} \subseteq \mathsf{IP}$: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.

arXiv:2108.07192•Leibniz international proceedings in informatics•Aug 16, 2021•22 citations

Unitary complexity in polynomial space

William Kretschmer, Ewin Tang

We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or $\mathsf{BPP} \neq \mathsf{NEXP}$. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in $\mathsf{unitaryPSPACE}$ either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for $\mathsf{NEXP}$ search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving $\mathsf{unitaryPSPACE}$ would imply breakthrough classical lower bounds such as $\mathsf{NC} \neq \mathsf{NP}$. Along the way, we propose new definitions for the unitary complexity classes $\mathsf{unitaryP}$ and $\mathsf{unitaryPSPACE}$. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that $\mathsf{unitaryPSPACE}$ has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that $\mathsf{unitaryPSPACE}$ can generically erase garbage, a result that provably fails relative to unitary oracles.

quant-pharXiv:2610.03705•Oct 5, 2026•2 citations

stateQIP = statePSPACE

Tony Metger, Henry Yuen

Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE $\subseteq$ stateQIP.Our main result is the reverse inclusion, stateQIP $\subseteq$ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.

arXiv:2301.07730•Annual Symposium on Foundations of Computer Science•Nov 6, 2023•27 citations

Explicit Separations for One-Query Unitary Synthesis

Fangqi Dong, Alex Lombardi, Fermi Ma

The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every $n$-qubit unitary $U$ is computable by efficient quantum circuits relative to some classical oracle $f = f_U$ depending on $U$. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly$(n)$ parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries $P\lvert x\rangle = \lvert π(x)\rangle$, as well as random alternating-basis phase unitaries $F_2 \cdot H^{\otimes n} \cdot F_1$. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries $\lvert x\rangle\mapsto α_x \lvert x\rangle$, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.

quant-pharXiv:2607.26478•Jul 30, 2026•3 citations

State Synthesis with an NP oracle

Aniruddha Sen

In this note, I describe a quantum algorithm that prepares an arbitrary state $|ψ\rangle$ to inverse exponential precision in polynomial time by making queries to an $\mathsf{NP}$ oracle, assuming one can directly query entries of the state vector corresponding to $|ψ\rangle$. The previous best upper bound on the complexity class required by an oracle for this task was $\mathsf{PP}$. I provide evidence that $\mathsf{NP}$ is the best possible upper bound by showing that any quantum algorithm using a $\mathsf{P}$ oracle, or even a $\mathsf{P/poly}$ oracle, requires exponentially many queries. I also discuss some implications of this result for the $\mathsf{QMA}$ search-to-decision problem and unitary synthesis.

quant-pharXiv:2611.02370•Nov 3, 2026•0 citations

Quantum Merlin-Arthur proof systems for synthesizing quantum states

Hugo Delavenne, François Le Gall, Yupan Liu +1 more

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 NP , referred to as stateQMA , 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 stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, 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 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 ( stateBQP ) and space-uniform polynomial-space quantum circuits ( statePSPACE ). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA . Additionally, we demonstrate that stateQCMA achieves perfect completeness.

arXiv:2303.01877•Quantum•Apr 3, 2025•9 citations
Unitary synthesis complexity studies the computational cost of applying a target unitary to an unknown quantum state, extending complexity theory beyond its traditional focus on problems with classical inputs and outputs. Rosenthal and Yuen (ITCS 2022) introduced two complexity classes for unitary synthesis: unitaryQIP\mathsf{unitaryQIP}unitaryQIP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE for the unitary families implementable via interactive proofs and in polynomial space, respectively. In this work, we prove the equality unitaryQIP=unitaryPSPACE\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}unitaryQIP=unitaryPSPACE and thereby establish a unitary-complexity analogue of QIP=PSPACE\mathsf{QIP} = \mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, and Watrous, J. ACM 2011) and stateQIP=statePSPACE\mathsf{stateQIP}=\mathsf{statePSPACE}stateQIP=statePSPACE (Rosenthal and Yuen, ITCS 2022; Metger and Yuen, FOCS 2023).
To prove unitaryQIP⊆unitaryPSPACE\mathsf{unitaryQIP} \subseteq \mathsf{unitaryPSPACE}unitaryQIP⊆unitaryPSPACE, we use an acceptance rigidity lemma derived from the soundness condition to show that the polynomial-space prover constructed for a fixed input in state synthesis (Metger and Yuen, FOCS 2023) implements the target unitary on every input, leading to a polynomial-space simulation of the protocol. For the reverse inclusion, we build on OpenAI's recently announced solution to the unitary synthesis problem (Aaronson and Kuperberg, Theory Comput. 2007), and show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE families can be synthesized in polynomial time with a PSPACE\mathsf{PSPACE}PSPACE oracle. We then implement the oracle queries using auxiliary states prepared via the statePSPACE⊆stateQIP\mathsf{statePSPACE} \subseteq \mathsf{stateQIP}statePSPACE⊆stateQIP protocol (Rosenthal and Yuen, ITCS 2022).
Beyond the equality, we show that our protocol for unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can be parallelized to constant rounds when the verifier receives polynomially many copies of the input, and we also obtain a complexity-theoretic barrier to proving the existence of EFI\mathsf{EFI}EFI pairs.
The paper asks whether interactive proofs characterize polynomial-space computation for worst-case unitary synthesis: applying a target unitary to an arbitrary unknown quantum input, rather than preparing a fixed state. It proves unitaryQIP=unitaryPSPACE\mathsf{unitaryQIP}=\mathsf{unitaryPSPACE}unitaryQIP=unitaryPSPACE, with both classes defined using arbitrarily inverse-polynomial synthesis error. The interactive characterization has perfect completeness and soundness threshold 1/21/21/2; soundness bounds the conditional output error whenever a prover is accepted above that threshold.
For unitaryQIP⊆unitaryPSPACE\mathsf{unitaryQIP}\subseteq\mathsf{unitaryPSPACE}unitaryQIP⊆unitaryPSPACE, an acceptance-rigidity lemma shows that soundness constrains a fixed prover’s acceptance probability across inputs. This allows a polynomial-space prover optimized for the all-zero input to work on every input. The simulation incurs error at most c+ε+7δc+\varepsilon+7\deltac+ε+7δ, under stated completeness–soundness gap conditions. For the reverse inclusion, the construction builds on a recently announced positive solution to the unitary synthesis problem, establishing that polynomial-space unitaries admit polynomial-size synthesis circuits querying a fixed PSPACE\mathsf{PSPACE}PSPACE language. Oracle queries are replaced by adaptive phase-state injection, with resource states verified through existing state-synthesis protocols. Quantitatively, unitaryPSPACEδ2/214⊆unitaryQIP0,s,δ\mathsf{unitaryPSPACE}_{\delta^2/2^{14}}\subseteq\mathsf{unitaryQIP}_{0,s,\delta}unitaryPSPACEδ2/214​⊆unitaryQIP0,s,δ​ for inverse-polynomially bounded parameters.
Further results give three-round synthesis with polynomially many input copies and show that EFI pairs imply BQP≠PSPACE\mathsf{BQP}\ne\mathsf{PSPACE}BQP=PSPACE, using polynomial-space Helstrom measurements and oracle synthesis. The three-round result does not establish constant-round synthesis with one input copy. Single-copy gap amplification, constant-round parallelization, and complete problems for the worst-case synthesis classes remain open.
Whereas quantum complexity theory has traditionally been concerned with problems arising from classical complexity theory (such as computing boolean functions), it also makes sense to study the complexity of inherently quantum operations such as constructing quantum states or performing unitary transformations. With this motivation, we define models of interactive proofs for synthesizing quantum states and unitaries, where a polynomial-time quantum verifier interacts with an untrusted quantum prover, and a verifier who accepts also outputs an approximation of the target state (for the state synthesis problem) or the result of the target unitary applied to the input state (for the unitary synthesis problem); furthermore there should exist an "honest" prover which the verifier accepts with probability 1. Our main result is a "state synthesis" analogue of the inclusion PSPACE⊆IP\mathsf{PSPACE} \subseteq \mathsf{IP}PSPACE⊆IP: any sequence of states computable by a polynomial-space quantum algorithm (which may run for exponential time) admits an interactive protocol of the form described above. Leveraging this state synthesis protocol, we also give a unitary synthesis protocol for polynomial space-computable unitaries that act nontrivially on only a polynomial-dimensional subspace. We obtain analogous results in the setting with multiple entangled provers as well.
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis problem, or BPP≠NEXP\mathsf{BPP} \neq \mathsf{NEXP}BPP=NEXP. Thus, showing unconditionally that quantum commitments exist would require answering at least one of two longstanding open questions in complexity theory. We prove our main result as a consequence of a more general lemma, which shows that every unitary in unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE either cannot be synthesized efficiently relative to any classical oracle, or can be synthesized efficiently with an oracle for NEXP\mathsf{NEXP}NEXP search problems. Our lemma has other noteworthy consequences, including that certain oracle separations involving unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE would imply breakthrough classical lower bounds such as NC≠NP\mathsf{NC} \neq \mathsf{NP}NC=NP. Along the way, we propose new definitions for the unitary complexity classes unitaryP\mathsf{unitaryP}unitaryP and unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE. Our changes address the biggest conceptual issues with definitions suggested in prior work, and lead to elegant proofs. We study both implementations that erase garbage and implementations that allow it, because we cannot rule out the possibility that the two definitions differ. Nevertheless, we show that both definitions can be viewed as special cases of each other. We also showcase many other ways in which our definitions are robust. For example, we show that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE has an equivalent characterization as the set of unitary transformations whose entries can be computed to arbitrary precision in polynomial space. Consequently, we deduce that unitaryPSPACE\mathsf{unitaryPSPACE}unitaryPSPACE can generically erase garbage, a result that provably fails relative to unitary oracles.
Complexity theory traditionally studies the hardness of solving classical computational problems. In the quantum setting, it is also natural to consider a different notion of complexity, namely the complexity of physically preparing a certain quantum state. We study the relation between two such state complexity classes: statePSPACE, which contains states that can be generated by space-uniform polynomial-space quantum circuits, and stateQIP, which contains states that a polynomialtime quantum verifier can generate by interacting with an all-powerful untrusted quantum prover. The latter class was recently introduced by Rosenthal and Yuen (ITCS 2022), who proved that statePSPACE ⊆\subseteq⊆ stateQIP.Our main result is the reverse inclusion, stateQIP ⊆\subseteq⊆ statePSPACE, thereby establishing equality of the two classes and providing a natural state-complexity analogue to the celebrated QIP = PSPACE theorem of Jain, et al. (J. ACM 2011). To prove this, we develop a polynomial-space quantum algorithm for solving a large class of exponentially large “PSPACE-computable” semidefinite programs (SDPs), which also prepares an optimiser encoded in a quantum state. Our SDP solver relies on recent blockencoding techniques from quantum algorithms, demonstrating that these techniques are also useful for complexity theory.Using similar techniques, we also show that optimal prover strategies for general quantum interactive protocols can be implemented in quantum polynomial space. We prove this by studying an algorithmic version of Uhlmann’s theorem and establishing an upper bound on the complexity of implementing Uhlmann transformations.
The unitary synthesis problem (Aaronson-Kuperberg, CCC 2007) asks whether every nnn-qubit unitary UUU is computable by efficient quantum circuits relative to some classical oracle f=fUf = f_Uf=fU​ depending on UUU. Recently, Lombardi-Ma-Wright (STOC 2024) proved that Haar-random unitaries cannot be efficiently synthesized by algorithms that make 1 query (or poly(n)(n)(n) parallel queries) to an arbitrary classical oracle. In this work, we prove several results about the hardness (and easiness!) of variants of unitary synthesis. Our results include: (1) 1-query vs. 2-query unitary synthesis: we prove 1-query lower bounds for synthesizing random permutation unitaries P∣x⟩=∣π(x)⟩P\lvert x\rangle = \lvert π(x)\rangleP∣x⟩=∣π(x)⟩, as well as random alternating-basis phase unitaries F2⋅H⊗n⋅F1F_2 \cdot H^{\otimes n} \cdot F_1F2​⋅H⊗n⋅F1​. This gives 1-query lower bounds for "explicit" families of unitaries that have efficient (even 2-query) synthesis algorithms. (2) Upper bound for complex phase unitaries: we also consider complex phase unitaries ∣x⟩↦αx∣x⟩\lvert x\rangle\mapsto α_x \lvert x\rangle∣x⟩↦αx​∣x⟩, which have a clean 2-query synthesis algorithm with no obvious 1-query algorithm. In this case, we prove an upper bound: there are 1-query algorithms (relative to binary phase oracles) that constant-approximate these unitaries in diamond distance. In order to prove our lower bounds, we introduce and analyze two new cryptographic games: the oracle state search game and the oracle Choi state game. Compared to prior work, our framework is mathematically simple, more flexible in what it can prove, and more accurately captures the hardness of synthesizing unitaries that are not "fully random". Finally, we also use the search game to prove a new hardness-of-approximation result for quantum programs (synthesizing unitaries relative to quantum advice) for phase unitaries, giving a sharper separation between 1-query unitary synthesis and quantum programs.
In this note, I describe a quantum algorithm that prepares an arbitrary state ∣ψ⟩|ψ\rangle∣ψ⟩ to inverse exponential precision in polynomial time by making queries to an NP\mathsf{NP}NP oracle, assuming one can directly query entries of the state vector corresponding to ∣ψ⟩|ψ\rangle∣ψ⟩. The previous best upper bound on the complexity class required by an oracle for this task was PP\mathsf{PP}PP. I provide evidence that NP\mathsf{NP}NP is the best possible upper bound by showing that any quantum algorithm using a P\mathsf{P}P oracle, or even a P/poly\mathsf{P/poly}P/poly oracle, requires exponentially many queries. I also discuss some implications of this result for the QMA\mathsf{QMA}QMA search-to-decision problem and unitary synthesis.
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 NP , referred to as stateQMA , 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 stateQIP recently introduced by Rosenthal and Yuen (ITCS 2022) \cite{RY22}, 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 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 ( stateBQP ) and space-uniform polynomial-space quantum circuits ( statePSPACE ). Furthermore, we establish that the family of UQMA witnesses, considered as one of the most natural candidates for stateQMA containments, is in stateQMA . Additionally, we demonstrate that stateQCMA achieves perfect completeness.