← Kartik Anand

Separations, explained

A proof is a string you hand a verifier. Quantum complexity keeps running into the same question in different clothes: does it matter what the string is made of, and does it matter how many pieces it arrives in? Three of those questions, with the machinery you can push on yourself.

QMA is the quantum analogue of NP. A prover hands over a witness, a polynomial-time quantum verifier checks it, and the local Hamiltonian problem is complete for it. Change one thing about the witness and you get a different class nobody can relate to the first one.

QMA versus QCMA

Does the witness have to be quantum?

QCMA is QMA with a classical witness: the prover sends bits, the verifier is still a quantum computer. Aharonov and Naveh asked in 2002 whether that costs you anything, and the question is still open. Everyone believes they differ. Nobody can prove it, for the same reason nobody can prove P ≠ NP, so the field does what complexity theory does when it is stuck and builds oracles.

The point of an oracle separation is to rule out a class of proof technique. If QMAA ≠ QCMAA for some A, then no argument that relativizes can prove QMA = QCMA. But oracles come in strengths, and a separation is only as convincing as the oracle is ordinary. This is the part worth understanding before reading any headline in this area.

How ordinary is the oracle?

2007 · quantum oracle

The 2025 construction is the one that closes the ladder, and its mechanism is worth the price of admission. Bostanci, Haferkamp, Nirkhe and Zhandry separate the classes using a problem they call spectral Forrelation: the oracle hands you two subsets of the Boolean hypercube through membership queries, and you must decide whether some quantum state is concentrated on the first set in the standard basis while its Fourier transform is concentrated on the second.

The lower bound comes from an observation you can state in one sentence. A classical witness is a string, so the verifier can rerun on it as many times as it likes and collect as many samples as it likes. A quantum witness is used up the moment you measure it, and no-cloning means you cannot make more. So proving that QCMA cannot solve the problem reduces to proving a sampling hardness result, and sampling hardness is something we know how to prove without it accidentally ruling out QMA too.

A string can be reread. A state cannot.

4 verification runs
Samples from a classical witness4
Samples from a quantum witness1

The prover sends the same object in both lanes. On the left it is w ∈ {0,1}m, which sits in memory and can be fed to the circuit again and again. On the right it is |ψ⟩, and the first measurement collapses it. That asymmetry is the whole lower bound: it turns a statement about QCMA into a statement about how many samples you need, and the sampling version does not also apply to QMA.

QMA versus QMA(2)

Does it help if the witness arrives in two pieces that cannot be entangled?

QMA(2), from Kobayashi, Matsumoto and Yamakami, gives the verifier two witnesses with a promise: they come from two provers who have never met, so the joint state is a product. That promise sounds like a restriction. It is actually a gift, because checking a property of a state is much easier when you know it is not entangled, and the verifier gets that for free.

How much it buys is embarrassingly unknown. The only bounds anyone has are the ones you get for free: QMA ⊆ QMA(2) ⊆ NEXP. Not EXP. NEXP. Harrow and Montanaro showed that more provers do not help beyond two, so QMA(k) = QMA(2) for every k ≥ 2, which at least means there is one question rather than a family of them. Two restricted variants have since been pinned exactly at NEXP: QMA+(2), where the amplitudes are real and non-negative, and an internally separable variant. Neither settles the real thing.

Underneath it all is that unentanglement is a testable property. Give a verifier two copies of a bipartite state and it can run a swap test on the halves; the pass rate is exactly the purity of the reduced state, which is 1 for a product state and drops as you entangle. Slide the Schmidt coefficient and watch the test notice.

The promise the verifier gets for free

product state
Purity Tr ρ²1.000
Swap test passes100.0%
Entropy of entanglement0.000

The state is √λ|00⟩ + √(1−λ)|11⟩. A swap test on the A halves of two copies passes with probability (1 + Tr ρA²)/2, which is 1 for a product state and 3/4 for a Bell pair. That gap is what a QMA(2) verifier can lean on and a QMA verifier cannot, and it is why the promise of unentanglement is suspected to be worth real computational power.

StoqMA and the sign problem

What if the Hamiltonian is the kind physicists can actually simulate?

A Hamiltonian is stoquastic when all its off-diagonal entries are real and non-positive in the computational basis. That sounds like a technicality and it is the single most consequential technicality in quantum Monte Carlo. Flip the signs the wrong way and the weights in the path integral start cancelling, the estimator's variance blows up exponentially, and the simulation stops working. This is the sign problem, and stoquastic Hamiltonians are exactly the ones that do not have it.

Bravyi, Bessen and Terhal defined StoqMA in 2006 as the class for which the stoquastic local Hamiltonian problem is complete. It sits between the classical and quantum worlds: MA ⊆ StoqMA ⊆ SBP ∩ QMA. Drag the slider and watch the ground state pick up signs.

Where the sign problem comes from

stoquastic · no sign problem
Ground energy0.000
Negative amplitudes0
Average sign1.000

A real 6 × 6 Hamiltonian, diagonalised in your browser. While every off-diagonal entry is non-positive, Perron–Frobenius guarantees a ground state with all amplitudes of one sign, so the path-integral weights are probabilities and Monte Carlo converges. Flip entries positive and the ground state develops signs; the average sign is the quantity whose decay makes the sampling cost explode. Only the first failure matters: one positive off-diagonal entry is enough to leave the stoquastic world.

The open question here is error reduction. Every class you would expect has it, and for StoqMA nobody knows, twenty years on. Aharonov, Grilo and Liu showed why that matters: if StoqMA admits error reduction, then StoqMA collapses to MA. So the gap between a class that looks quantum and a class that is plainly classical hinges on whether you are allowed to repeat the protocol and take a majority.

The two threads met in 2026. Liu and Wu opened up StoqMA(2), which is the unentangled promise from QMA(2) bolted onto the stoquastic setting, and the point of doing that is to isolate what unentanglement contributes when destructive interference is off the table. They also show StoqMA(k)log ⊆ MA and StoqMAlog = BPP.

arXiv:2604.27886, revised July 2026. New enough that I would read it before citing it.

Reading list

Every claim above, in order, so you can check me.

If you work on any of this and I have got something wrong, I would rather know: Kartik.anand@tuhh.de. More on the main page, and there is a playable spin glass next door.