Quantum proof systems with pure states collapse into single QMA class
PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
Computational Complexity
Summary
Deciding if a single pure quantum state can satisfy many constraints is a challenging problem linked to quantum complexity classes. The authors show that several previously different quantum proof classes, including one with exponentially many checks and another requiring many copies of a pure state, are all actually equivalent to the standard class QMA. This means that verifying pure quantum states is not harder than well-known quantum verification problems. Their proof uses new mathematical bounds on symmetric quantum states that do not depend on system dimension.
What this means in practice
- •For quantum algorithm developers: Focus on QMA verification techniques knowing pure-state consistency problems do not require more complex models.
- •For quantum chemistry software teams: Use QMA-completeness of pure bosonic and fermionic N-representability problems to guide verification algorithm design.
A theory result. No direct application yet.
Authors
William Gay, Fernando Granha Jeronimo, Lenny Liu, Itai Leigh, Pei Wu, Haochen Xu
Abstract
Pure-state consistency problems naturally lead to quantum proof systems in which a single pure witness must satisfy many acceptance constraints. The corresponding class $\mathsf{PureSuperQMA}$ was previously known to lie between $\mathsf{QMA}$ and $\mathsf{QMA}(2)$, and Kamminga and Rudolph (ITCS'26) conjectured that both containments are strict. In this paper, we prove the following surprising complexity collapses $$ \mathsf{QMA} = \mathsf{PureSuperQMA} = \mathsf{PureSuperQMA}(\text{exp}) = \mathsf{BellPureSymQMA}(\text{poly}) $$ Here $\mathsf{PureSuperQMA}(\text{exp})$ allows exponentially many checks which are uniformly indexed and efficiently generated, while requiring an inverse-polynomial violation margin and an inverse-polynomial fraction of violated checks for the NO cases. $\mathsf{BellPureSymQMA}(\text{poly})$ is a related model that requires the prover to give the verifier polynomially many copies of a pure state, which the verifier measures separately with logarithmic output length for each local measurement, before processing the outcomes jointly. The main technical ingredient is a dimension-free stability bound for symmetric tensor states. Our simulations use polynomially many witness registers and combine a random-pair SWAP test with a permutation-invariant lift of the original verification procedure. The key step is to show that, on the symmetric subspace, the extremal verification value is close to that of some tensor-power witness with dimension-independent error. Applying this argument to the two verification models yields both simulations. As a consequence, exact $k$-local pure-state consistency is $\mathsf{QMA}$-complete for every fixed $k\ge2$, and so are the corresponding exact bosonic and fermionic pure $N$-representability problems.