QMA (Quantum Merlin Arthur), is the quantum analog of NP, and QMA(k) is the class with $k$ Merlins. These are important classes when studying Quantum Complexity theory. QMA(k) is QMA with $k$ unentangled provers ($k$ Merlins), or BQP verfiers. These classes enable us to formally study the complexity of Entanglement. For instance the class QMA(2) could help us to study the separability of quantum states, and resources required for telling whether these states are separable or far from separable.

A natural question arises - What are the upper bounds for these classes (QMA, QMA(k))- do these classes have nontrivial upper bounds(could they have upper bounds such as PSPACE?


You probably want to check out the complexity zoo for known results. For example, the listing on QMA(2) states:

It was shown in ABD+08 that a conjecture they call the Strong Amplification Conjecture implies that QMA(2) is contained in PSPACE.

It was shown in HM13 that QMA(k) = QMA(2) for k >= 2. However we still do not know if QMA(2) = QMA. The best known upper bound is NEXP.

  • $\begingroup$ I updated the entry on the zoo. Could you requote? $\endgroup$ Apr 22 '18 at 23:36

Before talking about upper bounds for $\mathsf{QMA(k)}$, let us first concentrate on upper bounds for $\mathsf{QMA(k)}$.

Recall that the maximum acceptance probability of a $\mathsf{QMA(k)}$ 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. It is a quadratic form, so $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$.

Then we could show a series of upper bounds of $\mathsf{QMA}$:

  • $\mathsf{NEXP}$: Note that $|\psi\rangle$ consists of exponentially many parameters, also we only need to distinguish $p_{acc} \geq c$ from $p_{acc} \leq s$ where the completeness-soundness gap $c-s$ is at least inverse polynomial. We can simply guess a $|\psi\rangle$, and calculate $\langle \psi| M_x |\psi\rangle$ by an $\mathsf{EXP}$ machine.
  • $\mathsf{EXP}$: Notice the maximum acceptance probability of a $\mathsf{QMA}$ verifier $V_x$ is equal to the maximum eigenvalue of the associated matrix $M_x$. We can find the maximum eigenvalue of the exponential-size matrix $M_x$ by some convex optimization algorithm, which polynomially depends on the size of $M_x$.
  • $\mathsf{PSPACE}$: By Prop. 14.5 in [KSV02], the maximum eigenvalue of $M_x$ can be well-approximated by a few linear algebraic operations, which can be done in $\mathsf{NC}(poly)=\mathsf{PSPACE}$.

The upper bound for $\mathsf{QMA}$ could be further improved to $\mathsf{PP}$ [MW05] (or slightly stronger, namely, $\mathsf{A_0PP}$ [Vyalyi03]).

Now let us move back to $\mathsf{QMA(k)}$: merely the first $\mathsf{NEXP}$ upper bound works for $\mathsf{QMA(k)}$, and all other uppers are unfortunately failed. The reason why is the maximum acceptance probability of a $\mathsf{QMA(k)}$ verifier regards all $k$-product states, so maximizing $p_{acc}(\psi)$ is no longer a convex optimization problem. Still, when people first thinking about $\mathsf{QMA(k)}$, namely in [KMY03], they show that $\mathsf{QMA(k)}$ with perfect soundness will collapse to $\mathsf{QMA}$ in the same condition (which is equivalent to $\mathsf{NQP}$).

Furthermore, [KMY03] is sort of proving that $\mathsf{QMA(k)} = \mathsf{QMA(2)}$, just the soundness parameter differs from the standard scenario. In fact, if we could do error reduction $\mathsf{QMA(k)}$ (they improve to $\mathsf{QMA(2)}$ in the journal version), then [KMY03] will imply the actual equivalence. It is worthwhile to mention that the standard approach (i.e., do parallel repetition and accept if at least $\alpha$ ratio of copies is accepted) for error reduction only works in the completeness error for $\mathsf{QMA(k)}$. Few years later, [HM10] points out $\mathsf{QMA(2)}$ can be strengthened a bit, namely $\mathsf{QMA(2)}=\mathsf{QMA^{SEP}(2)}$, where $\mathsf{QMA^{SEP}(2)}$ means that the equivalent measurement $\{V_x^{\dagger} |0\rangle\langle 0|_{out} V_x, V_x^{\dagger} |1\rangle\langle 1|_{out} V_x\}$ can be further restricted to be separable (regarding mixed states). It turns out proving that $\mathsf{QMA(k)} = \mathsf{QMA(2)}$ since reducing soundness error is easy for $\mathsf{QMA^{SEP}(2)}$!

There are still a few more to say about upper bounds for $\mathsf{QMA(2)}$. There is a very early paper [KM03] claiming that $\mathsf{QMA(k)}$ with perfect completeness is upper bounded by $\mathsf{EXP}$. The proof outline is based on a new complete problem for $\mathsf{QMA(2)}$ and a deterministic exponential-time algorithm for it, but there is no further detail. There is also a failed attempt for an $\mathsf{EXP}$ upper bound [Schwarz15] several years ago. Beyond that, [ABDFS08] and [GSSSY17] provide a few conditional upper bounds, such as $\mathsf{PSPACE}$ or the counting hierarchy (which is contained in $\mathsf{PSPACE}$), based on various assumptions.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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