How powerful are two unentangled quantum proofs?

Unresolved.

QMA(2) allows a verifier two proofs guaranteed to be unentangled. Harrow and Montanaro showed that two proofs can simulate many, and tied the log-sized version of QMA(2) to separability testing.

Still unknown

Only the trivial bounds QMA ⊆ QMA(2) ⊆ NEXP are known. If proofs are restricted to non-negative amplitudes the class equals NEXP at suitable constant gaps, but that does not yet transfer to QMA(2) without gap amplification.

Connections

Part of: Detection
See also: Deciding separability is NP-hard

Sources

The power of unentangled quantum proofs with non-negative amplitudes. F. G. Jeronimo, P. Wu, 2024.
Testing product states, quantum Merlin-Arthur games and tensor optimisation. A. W. Harrow, A. Montanaro, 2010.
Quantum Merlin-Arthur and proofs without relative phase. R. Bassirian, B. Fefferman, K. Marwaha, 2023.

Checked 2026-10-30.