[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.

BibTeX

Copy

@misc{BFL+24,
  author       = {Roozbeh Bassirian and Bill Fefferman and Itai Leigh and Kunal Marwaha and Pei Wu},
  title        = {Quantum {Merlin-Arthur} with an Internally Separable Proof},
  howpublished = {arXiv:2410.19152},
  year         = {2024},
  url          = {https://arxiv.org/abs/2410.19152}
}