6
$\begingroup$

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

$\endgroup$

2 Answers 2

5
$\begingroup$

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)

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

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.


$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.