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

Question

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

Answer 1

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)

Answer 2

Kitaev showed the following that gives the result:

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.

---