Curator's Take
AI Commentary
This article establishes a fundamental limit on how aggressively classical decision variables can be compressed into few‑qubit quantum relaxations, showing that the worst‑case “universal margin’’ for the quadratic‑Majorana encoding drops only as 1⁄n rather than the more favorable 1/√n seen for random sign patterns. By proving that even non‑Gaussian fermionic states cannot enlarge the achievable covariance body and by tying the bound to quantum random access code limits, the work clarifies why qubit‑efficient encodings cannot replace the linear scaling of hardware resources in large combinatorial optimizations. The result warns designers of QAOA‑style algorithms and VQE relaxations that any substantial reduction in qubit count will inevitably require either many circuit repetitions or a loss of robustness, setting realistic expectations for near‑term quantum advantage.
— Mark Eatherly
Summary
Qubit-efficient quantum relaxations compress classical decision variables into expectation values on substantially fewer qubits. We ask what resource tradeoffs this compression entails for quantum optimization. For the complete quadratic-Majorana encoding on $n$ qubits, pairwise correlators can represent $m=Θ(n^2)$ binary variables. We define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign assignment. We show that it is exactly $Δ_{\rm Maj}(n)=\tan\!\left(\fracπ{4n}\right)=Θ(1/n)$, whereas uniformly random sign assignments retain $Θ(1/\sqrt n)$ target-specific margins. The stronger $1/n$ worst-case scaling is Majorana-specific. Moreover, arbitrary density operators and fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. Beyond Majoranas, standard quantum random access code bounds provide general information-theoretic baselines. For any fixed family of $m$ designated binary observables on $n$ qubits, the universal margin is at most $\sqrt{(2\ln2\;n/m)}$, while arbitrary random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=Ω(m)$. For a fixed Pauli correlation encoding required to work uniformly over all targets, maintaining a fixed nonzero decoded magnitude under smooth sign decoding therefore requires a rescaling parameter that grows as the available margin shrinks. Thus, while providing substantial qubit savings, compression can shift cost into restricted expectation value geometry, smaller expectation value magnitudes, or more demanding information recovery rather than eliminate it.