1

Is QMA(2) in BQEXP?

by kunal 2026-01-19
Impact 3.0
Solvability 2.0
(1 rating)

The complexity class QMA(2) has no known upper bounds aside from NEXP.

It is unknown whether this class lies in BQEXP, which gives a quantum computer exponential time to decide a problem with $\ge 2/3$ accuracy.

If true, this makes it less likely that QMA(2) = NEXP, since it is unlikely that NEXP $\subseteq$ BQEXP.

Discussion (1)

kunal 2026-07-28 01:20

One could try to find an analogy between (MA, SBP), (QMA, SBQP), and (QMA(2), X) where X is some to-be-defined complexity class which ideally is not closed under intersection (I think this happens because SBP and SBQP are one-sided). Then perhaps an idea from https://arxiv.org/abs/1904.08914 or https://people.cs.georgetown.edu/jthaler/adegFnT.pdf might separate QMA(2) from X or even from SBP.

← Back to all problems