Back to Search
Start Over
Quantum Merlin-Arthur with an internally separable proof
- Publication Year :
- 2024
-
Abstract
- We find a modification to QMA where having one quantum proof is strictly less powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our modification endows each proof with a form of *multipartite* unentanglement: after tracing out one register, a small number of qubits are separable from the rest of the state.<br />Comment: 30+17 pages, 1+2 figures, 1+1 tables
- Subjects :
- Quantum Physics
Computer Science - Computational Complexity
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2410.19152
- Document Type :
- Working Paper