2026-08-25T11:01:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27302 2026-08-25T07:42:36Z ddc:004 open_access

Quantum Merlin-Arthur with an Internally Separable Proof Bassirian, Roozbeh Fefferman, Bill Leigh, Itai Marwaha, Kunal Wu, Pei entanglement structures unentanglement quantum complexity QMA(2) NEXP While the role of entanglement in quantum proof systems has been extensively studied, the computational power of unentanglement remains poorly understood. Since entanglement admits many inequivalent multipartite structures, it is natural to ask how more fine-grained structural promises affect computational power. In this work we investigate a mild promise: each proof is internally separable, meaning that after tracing out one register, a designated constant-size subsystem is separable from the rest - even though the overall proof may still be entangled across every bipartition. We prove a qualitative jump from one proof to two: with one internally separable proof, the resulting class is contained in EXP (even allowing an inverse-exponential completeness–soundness gap), whereas with two unentangled internally separable proofs, the class equals NEXP at constant gap. Notably, in the NEXP construction, the second proof is used solely to implement a SWAP-based purity test. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Roozbeh Bassirian and Bill Fefferman and Itai Leigh and Kunal Marwaha and Pei Wu 2026 Is Part Of LIPIcs, Volume 389, 21st Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TQC.2026.5 urn:nbn:de:0030-drops-273022 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2026.5 eng https://creativecommons.org/licenses/by/4.0/legalcode