Itai Leigh

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