[BFL+24] Quantum Merlin-Arthur with an Internally Separable Proof

Authors: Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, Pei Wu | Venue: arXiv 2024 | Source

Abstract

We introduce a QMA variant where each proof must be “internally separable”: after tracing out one register, a small number of qubits must be separable from the rest of the state. This is a restriction on the entanglement structure of the witness. We show that with a single such proof, the class is strictly less powerful than QMA(2) assuming EXP ≠ NEXP. This provides a new route toward proving QMA(2) = NEXP that avoids a key technical obstacle in prior approaches based on product-state witnesses.