The living QMA(2) reference

updated 2022-05-10

What is QMA(2)?

QMA(2) is a class where the verifier (“Arthur”), a quantum computer, checks a computation from two unentangled provers (“Merlins”). The verifier receives two quantum (“witnesses”), which are guaranteed to be unentangled. This is the key difference from QMA.

In QMA(2), the verifier is given the extra power of “unentanglement” [ABDFS08]. When a quantum computer’s input is guaranteed two be two separable states, it might be able to “do more” than if it was initialized with an unknown quantum state. But how much more?

For more info, see this QMA(2) primer from Bill Fefferman.

QMA(\(k\)), QMA(2), QMA

We can imagine a generalization of QMA(2), where we are given \(k\) quantum states that are guaranteed to be unentangled. In general, QMA(\(k_1\)) \(\subseteq\) QMA(\(k_2\)), for \(k_1 \le k_2\). If Arthur can verify given \(k_1\) unentangled quantum states, then Arthur can verify given any \(k_2 \ge k_1\) unentengled states, where the extra unentangled states can be ignored.

It turns out that QMA(\(k\)) = QMA(2) [HM13]. Their approach uses the SWAP test (checking that two quantum states are similar); this primitive can be used for any \(k \ge 2\).

But what about the standard class QMA; i.e., when \(k=1\)? This is still open, even in the oracle setting:

Open problem [Problem 2, Aaronson 2021]: Is there any (classical or quantum) oracle \(\mathcal{O}\) where QMA \(\ne\) QMA(2)?

It’s unlikely that QMA \(=\) QMA(2), since determining whether a state is entangled or not is at least NP-hard [Gharibian 2008].

QMA(2)-complete problems

One natural problem for QMA(2) is the sparse separable Hamiltonian problem [CD10]: Decide if there is a separable state that has ground state \(\le a\), or all states are \(\ge b\), where \(b-a = \Omega(1/poly(n))\). This is related to the sparse Hamiltonian problem, which is QMA-complete.

One strange result is that both the k-local Hamiltonian problem and the k-local separable Hamiltonian problem are QMA-complete. This means that knowing that the Hamiltonian is a sum of terms operating on only a constant number of qubits, even deciding whether a separable state is of low-energy is possible “without the power of unentanglement”.

A natural open question here is: why is there a difference between the sparse setting and the k-local setting?

Pure state N-representability is in QMA(2), but may not be QMA(2)-complete [LCV06].

Features of QMA(2)

Surprisingly, both QMA and QMA(2) are equal to their “subset state” variants, where the input witness must be a uniform superposition over some subset of basis elements [GKS16].

Upper bounds for QMA(2) have been hard to track down, except for QMA(2) \(\subseteq\) NEXP. [GSSSY18] shows that unless QMA(2) equals the third level of the quantum polynomial hierarchy, QMA(2) \(\subsetneq\) NEXP. [Ambainis 2014] and [GPY19] consider a complete problem for the class \(P^{QMA[\log]} = P^{||QMA}\), which contains both \(coQMA\) and \(QMA\).

There are QMA(\(k\)) protocols for 3-SAT [ABDFS08] and 3-coloring [BT07] (both NP-complete problems) that have sublinear-sized proofs. (Classically, we expect linear-sized proofs by the exponential time hypothesis (ETH)).

There was some problems amplifying success probabilities in QMA(2); something about “strong error reduction” vs “in-place error reduction”. But it is now resolved.

Other resources:


Thanks to Justin Yirka for direction when starting this document.

More to add? Email me at kmarw@uchicago.edu.