# How can I show that $\mathsf{QMA}\subseteq \mathsf{PSPACE}$

Lately I have seen the claim that $$\mathsf{QMA}\subseteq \mathsf{PSPACE}$$, and I wonder how can it be proved. Thanks

Well, it is not such hard to show a $$\mathsf{PSPACE}$$-containment of $$\mathsf{QMA}$$...

Recall that the maximum acceptance probability of a $$\mathsf{QMA}$$ verifier $$V_x$$ is $$\max_{|\psi\rangle} \| |1\rangle\langle 1|_{out} V_x|\psi\rangle|\bar{0}\rangle\|_2^2$$, where $$|\bar{0}\rangle$$ are ancillary qubits. This formula is a quadratic form, namely $$p_{acc}(\psi)=\langle \psi|M_x|\psi\rangle$$ where $$M_x:=\langle\bar{0}|V_x^{\dagger}|1\rangle\langle 1|_{out}V_x|\bar{0}\rangle$$. In other words, to decide whether the maximum acceptance probability of a $$\mathsf{QMA}$$ verifier $$V_x$$ is larger than $$a$$, or smaller than $$b$$; it suffices to decide whether the largest eigenvalue of $$M_x$$ is larger than $$a$$ or smaller than $$b$$.

Note that $$V_x$$ consists of polynomially many local gates, $$M_x$$ thus is an exponential-size sparse matrix. Therefore, we could solve this kind of linear-algebraic task regarding a sparse matrix, i.e. the largest eigenvalue of $$M_x$$, in polynomially-bounded depth Boolean circuit. This indicates that $$\mathsf{QMA} \subseteq \mathsf{NC(poly)}$$ Then it is evident that $$\mathsf{NC(poly)} \subseteq \mathsf{PSPACE}$$ (it is effectively an equivalence) since polynomially bounded depth Boolean circuit can be simulated by polynomially bounded space Boolean circuit employed with a backtracking algorithm.

If you are not comfortable with this $$\mathsf{NC(poly)}$$ fact mentioned above, you also can check the proof of Proposition 14.5 in Kitaev-Shen-Vyalyi's textbook.

Additionally, in case you are also interested in proofing $$\mathsf{QMA} \subseteq \mathsf{PP}$$, you need another linear-algebraic trick called Jordan lemma -- it decomposes the Hilbert space into a bunch of one-dimensional and two-dimensional spaces that are invariant under both $$V_x^{\dagger} |1\rangle\langle 1|_{out} V_x$$ and $$|\bar{0}\rangle\langle\bar{0}|\otimes I$$. Further details could be found in Oded Regev's lecture notes, and this proof is initially proposed by Marriott and Watrous (see Theorem 3.4)

• Thank's for the answer, I shall re-evaluate my answer given the overstatement. Att. R.W.
– R.W
Commented Mar 16, 2022 at 15:55

Kitaevs Theorem: $$\mathsf{QMA} \subseteq \mathsf{P}^{\# \mathsf{P}} \subseteq \mathsf{PSPACE}$$.

Later it was shown an even stronger result:

Kitaev and Watrous's Theorem: $$\mathsf{QMA} \subseteq \mathsf{PP}$$, proof can be found here pg 13.

You can then build upon the last result to make the argument as follows: From the very first paper defining $$\mathsf{PP}$$ we see how to show that $$\mathsf{PP} \subseteq \mathsf{PSPACE}$$ since "every polynomial bounded Turing machine can be simulated in polynomial space" (Pg. 685, John Gill). Therefore we get the wanted result by $$\mathsf{QMA} \subseteq \mathsf{PP}\subseteq \mathsf{PSPACE}$$.

As a reminder, there are always many important underlying assumptions in proofs regarding complexity classes.