A mathematical analysis has put a precise price on one form of qubit compression. In the complete quadratic-Majorana model, n qubits carry m = Θ(n²) classical binary variables through pairwise correlators. Its exact universal worst-case margin is ΔMaj(n) = tan(π/(4n)), which shrinks on the order of 1/n.
Here, margin means the smallest guaranteed gap between the expectation value used for a sign decision and the decision boundary across the target patterns under consideration. The formula says that the weakest guaranteed signal narrows as n grows, leaving a decoder less room to distinguish the intended sign.
Where the margin comes from
The exact result is analytical rather than an estimate from a collection of runs. Its proof links sign realizability to tournament theory and uses a rank-two certificate that matches the bound.
The operational consequence is a readout cost. For the complete Majorana family, the stated uniform fixed-magnitude nonlinear decoder requires a rescaling factor α = Ω(n). In other words, a decoder seeking a common fixed output magnitude must compensate for the shrinking worst-case scale.
The hardest targets are structured
The hardest target patterns are also highly structured. The minimizing sign patterns are exactly those equivalent, through relabeling and switching, to the transitive tournament. In plain terms, the transitive tournament is the acyclic orientation produced by imposing a total order on its vertices.
That worst-case result does not describe every target. Uniformly random sign patterns have target-specific margins of order n⁻¹ᐟ² with high probability. This is an asymptotic mathematical comparison, not an empirical estimate, and it is larger in scale than the universal 1/n guarantee.
A broader information limit
The analysis broadens the comparison beyond Majorana encodings. For any fixed family of m designated binary observables on n qubits, the universal margin obeys δ ≤ √(2 ln 2 n/m). When n = o(m), the bound rules out a constant margin.
That universal bound is an upper envelope, and the paper notes it need not be sharp for a particular observable family. To study a chosen family more closely, it gives an equivalent minimax and spectral characterization using Sion's minimax theorem.
Copies become part of the cost
Random access adds another condition: a decoder must recover whichever coordinate is requested. Under that worst-case requirement, if each requested coordinate is recovered from N copies with success probability p > 1/2, then nN ≥ m[1 − H2(p)], including collective measurements. H2(p) is the binary entropy function in the bound.
For the isolated weakest-correlator sign problem, the copy requirement scales as Ncoord = Ω(cot²(π/(4n))) = Ω(n²) = Ω(m). Direct measurement reaches the same scaling. This result is about one isolated coordinate and does not characterize joint decoding across many coordinates.
The state model has limits
The analysis also asks whether a broader state class changes the quadratic picture. For the quadratic-observable maps studied, arbitrary density operators and fermionic Gaussian states have exactly the same covariance body and the same attainable expectation-value vectors. Within that scope, non-Gaussian states do not enlarge the analyzed relaxation.
That conclusion is deliberately narrow. Gaussian completeness concerns quadratic, or two-point, expectation values; it does not settle nonlinear objectives, higher-order observables or restricted preparation families.
A mathematical result, not a hardware test
This is a modeling result, not an empirical optimization test. All reported results are analytical, with numerical spot checks serving as consistency checks; no external data or separate research software are required.
The exact inverse-linear statement is conditional on the complete quadratic-Majorana geometry, while the general information bound may be non-sharp for a particular observable family. The paper therefore speaks to specified encodings, margins and readout requirements, not to a universal performance claim for every quantum optimization scheme.
What the result actually measures
Taken together, the results make qubit count only one part of the resource calculation. A comparison also has to track the margin, the decoder's rescaling and the number of copies or measurements needed for recovery, because the bounds tie those quantities to the number of encoded variables.
The document is an arXiv version 1 preprint in quantum physics dated 25 Aug 2026. It acknowledges support from AFRL Contract No. FA8750-25-C-B0040.
Paper data and sources
Original title: No Free Compression in Quantum Relaxations for Optimization
Authors: Stuart Hadfield
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-25
DOI: Not available
Original paper · Full text