Source-linked AI summary
PureSuperQMA(exp) = BellPureSymQMA(poly) = QMA via Dimension-Free Bosonic Argmax
William Gay, Fernando Granha Jeronimo, Lenny Liu, Itai Leigh, Pei Wu, Haochen Xu
TL;DR
The consistency question asks whether reduced states arise from one global state. The simulations combine a dimension-free symmetric-tensor stability comparison with lifted verification tests and a random-pair SWAP test. PureSuperQMA(exp) and BellPureSymQMA(poly) both equal QMA.
Problem
The consistency question asks whether reduced states arise from one global state.
Source: §1 · p. 3Method
The simulations combine a dimension-free symmetric-tensor stability comparison with lifted verification tests and a random-pair SWAP test.
Source: §1.3 · pp. 8–9Results
PureSuperQMA(exp) and BellPureSymQMA(poly) both equal QMA.
Source: §2.2 · p. 12Takeaways & Limitations
The common-pure-state promise adds no verification power in either model.
Source: §1.2 · p. 6The stated bosonic stability condition requires N ≥ 2e5m^2R, which ensures m<N.
Source: §6 · p. 25, §6.3 · p. 28
Abstract
from arXiv · showhide
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.
1 Introduction
Local quantum data pose a compatibility problem, and purity complicates the usual consistency reasoning. The paper resolves this for two pure-state verification models using dimension-free symmetric-tensor stability, obtaining QMA collapses and completeness consequences.
1.1 Purity and quantum proof systems
- Purity complicates consistency because the average marginal of a many-register witness may be mixed, outside the pure-state soundness promise.Pure-state marginal problems also arise in entanglement theory and quantum coding theory.Source: §1 · p. 3, §1.1 · p. 4
1.2 Our results
- The simulations establish QMA = PureSuperQMA = PureSuperQMA(exp) = BellPureSymQMA(poly), yielding QMA-completeness for fixed-k pure consistency and exact bosonic and fermionic pure N-representability.The exponential-check collapse holds with inverse-polynomial violation margin and fraction; the conclusion extends beyond the polynomial-check case needed for completeness.Source: §1.2 · p. 6
1.3 Proof overview
- A dimension-free argmax bound compares symmetric-subspace extremal values with tensor powers via eigenvector contraction, even when the maximizing overlap is tiny.The one-transverse-factor term vanishes, and higher-order terms share the overlap factor, which can be divided out.Source: §1.3 · pp. 7–8
- For exponentially indexed pure-super checks, check sampling, outcome counting, and random-pair SWAP testing yield inverse-polynomial NO rejection without enumerating the checks.The honest rejection probability is O(1/N), while rejection is Ω(1/N) on the symmetric subspace and its orthogonal complement in NO instances.Source: §1.3 · p. 8
- For Bell-pure verification, N = Θ(m^2R) registers and a Bell branch plus random-pair SWAP testing provide Ω(1/N) NO rejection and O(1/N) honest rejection.The short-output assumption keeps the outcome alphabet R polynomial, allowing the stability loss to remain below the original constant gap.Source: §1.3 · p. 9
2 Notation, Complexity Classes, and Main Results
The section defines the pure super-verifier and Bell-pure symmetric models, then proves that both collapse to QMA. Its simulations use one-witness verifiers with inverse-polynomial gaps.
2.1 Quantum Merlin–Arthur Complexity Classes
- PureSuperQMA(exp) allows exponentially many checks, while PureSuperQMA uses polynomially many; the checks are uniformly generated from the input and index.The verifier circuits and acceptance intervals are generated in polynomial time from the input and check index.Source: §2.1 · p. 11
- BellPureSymQMA(poly) gives the verifier polynomially many copies of one pure state, measures each copy locally, and jointly processes the ordered outcomes.The local circuits produce designated output registers, which are measured before the referee circuit acts on their outcomes.Source: §2.1 · pp. 11–12
2.2 Main Results
- PureSuperQMA(exp) and BellPureSymQMA(poly) equal QMA; their one-witness simulations have gaps 103/(512N) and Ω((m^2R)^-1), respectively.The Bell-pure simulation’s implicit constants are independent of witness-space dimension.Source: §2.2 · p. 12
3 Dimension-Free Bosonic Argmax Stability
The argmax stability analysis extends a complex-sphere estimate to control every transverse order, which the applications require. Its proof eliminates the linear term and derives higher-order bounds using Fourier extraction and polarization.
3 Dimension-Free Bosonic Argmax Stability
- Theorem 9 extends the complex-sphere argmax estimate from first-order vanishing and a sharp second-order bound to control at every transverse order.The applications below require this all-orders control.Source: §3 · p. 13
- The maximizing overlap and phase are chosen so the maximum exists and is positive before the transverse-order argument proceeds.The passage establishes existence by compactness and positivity of the diagonal restriction.Source: §3 · p. 13
- The first-order coefficient γ1(v) vanishes, and multilinearity gives the product of norms in Equation (3), completing the proof.The proof uses ∥wθ∥2 ≤ k.Source: §3 · p. 14
4 Dimension-Free Stability of Repeated Count POVMs
The section develops a dimension-independent comparison between lifted repeated-count tests on symmetric states and their values on tensor powers. It builds the comparison from count-test effects, a transverse expansion, and a bosonic stability argument.
4 Dimension-Free Stability of Repeated Count POVMs
- Theorem 13 compares the extremal value of a lifted repeated-count test with its tensor-power value without dependence on dim H.Its proof combines eigenvector contraction, transverse expansion, and Bernstein-polynomial estimates.Source: §4 · p. 14
4.1 Count-Test Effects
- Weights in [0,1] assigned to exact-count outcomes define a permutation-invariant count-test effect.The exact-count effects form a POVM, and the construction uses the Bernstein basis.Source: §4.1 · p. 15
4.2 Transverse Expansion of Count-Test Effects
- In the transverse expansion, the coefficient for a tensor with j orthogonal factors depends only on j, through the Bernstein derivative identity.This makes the expansion depend on the number of transverse positions, not their locations.Source: §4.2 · p. 16
4.3 Bosonic Stability of Count-Test Effects
- The bosonic stability argument proves the upper bound needed for the dimension-free comparison of lifted count tests and tensor powers.The proof analyzes permutation-invariant lifts and compares a symmetric minimizer with a tensor-power witness.Source: §4.3 · pp. 16–18
5 Simulating PureSuperQMA(exp) in QMA
The section constructs a QMA verifier for PureSuperQMA(exp) using multiple registers, a random-pair symmetry test, and sampled acceptance-window count tests. The analysis establishes a completeness–soundness gap inverse-polynomial in the register count and yields the class collapse.
5.1 Acceptance Windows as Count-Test Energies
- The count-test energy rejects violated acceptance windows with high probability, while satisfied windows have bounded rejection probability.The analysis uses repeated independent outcomes from the same pure tensor-power witness.Source: §5.1 · pp. 19–20
5.2 The Symmetry-and-Count Verifier
- The verifier randomly tests a pair of registers for antisymmetry or samples a check and a register subset for a count test.Sampling one check implements the averaged count-test effect.Source: §5.2 · p. 21
5.3 Completeness and Soundness
- The ideal verifier has completeness at least 1 − O(N^-1), soundness at most 1 − Ω(N^-1), and a gap Ω(N^-1).Its soundness bound applies to arbitrary pure or mixed witnesses.Source: §5.3 · pp. 22–23
5.4 Uniform Implementation and the Class Collapse
- Uniform implementation has polynomially bounded circuit-generation time and size, with reversible routing and sampling for the verifier’s random choices.The checks are generated from the input and sampled index rather than enumerated.Source: §5.4 · pp. 23–24
- PureSuperQMA(exp) equals QMA, as the section proves both the QMA lower containment and the QMA upper simulation.The verifier uses polynomial resources and has an inverse-polynomial raw gap.Source: §5.4 · pp. 24–25
6 Dimension-Free Stability of Product POVMs
The section defines product-POVM effects and lifts them to a larger register space by averaging over placements. It then proves an upper bound in the bosonic stability argument.
6 Dimension-Free Stability of Product POVMs
- The section’s stability setup assumes local outcome sets of size at most R and m no greater than N.These parameters govern the product measurements and the larger lifted register space.Source: §6 · p. 25
6.1 Product-POVM Effects
- The product-POVM effect combines local POVM outcomes through a function taking outcome tuples to values in [0,1].The local outcome sets have size at most R.Source: §6.1 · p. 25, §6 · p. 25
6.2 The Ordered Lift
- Averaging placements of the local effect across distinct registers defines an ordered lift that is permutation invariant.Tensor-power and permutation-invariant states give the same expectation and contraction for each placement.Source: §6.2 · p. 27
6.3 Bosonic Stability of Product-POVM Effects
- The bosonic stability argument establishes an upper bound for the symmetric extremum.The proof selects a symmetric maximizer and compares it with a tensor-power vector.Source: §6.3 · pp. 27–28
7 Simulating BellPureSymQMA(poly) in QMA
The section lifts a Bell verifier’s local measurements to randomly selected registers and combines that test with a random-pair SWAP test. The resulting one-witness verifier has an inverse-register-count ideal gap and gives a QMA simulation with polynomial resources.
7.1 The Product-POVM Effect of a Bell Verifier
- The Bell verifier’s product-POVM effect lifts to the experiment that randomly injects local measurements into N registers before running the referee.The verifier implements the experiment directly rather than enumerating the joint outcome space.Source: §7.1 · p. 29
7.2 The One-Witness Verifier
- The ideal one-witness verifier achieves a completeness–soundness gap of 13/(48N).The theorem states completeness and soundness bounds for the verifier.Source: §7.2 · p. 30
7.3 Uniformity and the Collapse
- The simulation has polynomially bounded witness length, circuit size, and reciprocal raw gap, yielding a QMA containment.The argument uses the bound N < 8192m(n)^2R and standard amplification.Source: §7.3 · p. 32
AI Usage
The authors disclose that the idea’s framing was human, while ChatGPT 5.6 Pro assisted with technical development, proof development, and manuscript editing. The appendix also records a Bernoulli specialization of Hoeffding’s inequality and its concentration-bound proof.
AI Usage
- The authors say humans developed the initial high-level framing and contributed substantially to exposition, organization, and presentation.They take full responsibility for the results and say they independently verified all claims, proofs, and references.Source: AI Usage · p. 32
- ChatGPT 5.6 Pro assisted with technical execution, substantial parts of proof development, and editorial preparation of the manuscript.The authors also state that the technical development and execution built on the human-framed idea.Source: AI Usage · p. 32
A.1 A Bernoulli Concentration Bound
- The appendix proves a Bernoulli specialization of Hoeffding’s inequality for independent, identically distributed {0, 1}-valued variables with common mean p.The proof uses exponential tilting for one tail, applies the same argument to the complemented variables for the other tail, then adds the tail probabilities.Source: §A.1 · pp. 35–36
A.2 Bernstein Polynomials
This section gives a derivative identity for Bernstein-basis polynomials in terms of forward differences, then uses the basis’s nonnegativity and unit sum to obtain a derivative bound.
A.2 Bernstein Polynomials
- The section relates derivatives of Bernstein-basis polynomials to iterated forward differences of their coefficient vector.The stated identity uses falling factorials, with out-of-range basis indices interpreted as zero.Source: §A.2 · pp. 36–37
- For coefficients in [0, 1], the alternating finite-difference formula bounds each iterated difference using positive and negative binomial-coefficient mass.The derivative bound follows because Bernstein basis polynomials are non-negative and sum to one on [0, 1].Source: §A.2 · p. 37
A.3 Polarization and Elementary Estimates
The section presents a Fourier-form polarization identity for symmetric multilinear forms and records elementary estimates used in the appendix. The polarization result implies that a symmetric multilinear form vanishing on every diagonal input is zero.
A.3 Polarization and Elementary Estimates
- The Fourier-form polarization principle recovers a symmetric multilinear form from its diagonal values [BS71].The proof’s integral retains only terms in which each input index appears exactly once, and symmetry makes the surviving values equal.Source: §A.3 · p. 37
- If B(w, . . . , w) = 0 for every w, then the symmetric multilinear form B is identically zero.This is the stated consequence of the polarization identity.Source: §A.3 · p. 37
- The appendix also invokes a geometric-series estimate for ρ in [0, 1/2] and derives a factorial bound using an integral comparison.The remaining estimate is identified as the sum of a geometric series.Source: §A.3 · pp. 37–38
B The Random-Transposition Test
The random-pair SWAP test has rejection effect that vanishes on the symmetric subspace and is bounded below on nontrivial permutation components. The proof analyzes the transposition sum through symmetric-group representations.
B The Random-Transposition Test
- The proof expresses the central transposition sum through Jucys–Murphy elements, whose Young-basis eigenvalues are box contents.It compares partition content sums by moving a box from a lower row to the first row.Source: B The Random-Transposition Test · pp. 38–39
- The proof also identifies the partition (N − 1, 1) after the stated operation is repeated.This step precedes the lower-bound argument for nontrivial components.Source: B The Random-Transposition Test · p. 39
- The random-pair SWAP rejection effect vanishes on the trivial component and has a positive lower eigenvalue bound on every nontrivial component.The trivial component is the symmetric subspace W_N(H), so the test’s kernel is that subspace.Source: B The Random-Transposition Test · pp. 38–39
C Finite Sampling
Finite sampling shows that an ideal verifier making polynomially many classical random choices can be approximated by a polynomial-time uniform circuit. The construction handles efficiently computable Bernoulli and uniform choices, with an error bound set by the chosen tolerance.
C Finite Sampling
- Under the stated computability and circuit-generation conditions, a uniform circuit approximates the ideal verifier's acceptance probability within any specified polynomial-time computable rational ξ on every witness.The verifier makes at most polynomially many classical random choices, each conditionally Bernoulli or uniform over a set with an efficiently evaluable unranking map.Source: C Finite Sampling · p. 39
- For a uniform choice from K outcomes, the sampler draws a k-bit integer and maps it to rank 1+(Z mod K).Here k is ⌈log2 K⌉+κ.Source: C Finite Sampling · p. 40
- The implementation uses reversible sampling arithmetic and computes, evaluates, then uncomputes choice-dependent circuit descriptions while retaining sampled strings through acceptance to keep transcripts orthogonal.The controlled circuit is padded and evaluated over the specified controlled extension of G.Source: C Finite Sampling · p. 40
- Unranking constructs subsets in at most N stages and ordered injections in m stages; the unordered-pair case t=2 completes the assertion.Unordered pairs, t-element subsets, and ordered injections satisfy the unranking hypothesis for the parameters in Sections 5 and 7.Source: C Finite Sampling · pp. 39–40