No Free Compression in Quantum Relaxations for Optimization

Abstract

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 of $m=\Theta(n^2)$ binary variables on~$n$ qubits, we define the universal margin as the smallest correlator magnitude that can be guaranteed with prescribed signs for every target sign (bit) assignment. We show that it is exactly $\Delta_{\rm Maj}(n)=\tan\!\left(\frac{\pi}{4n}\right)=\Theta(1/n)$, whereas uniformly random sign assignments retain $\Theta(1/\sqrt n)$ target-specific margins. Arbitrary density operators and mixed fermionic Gaussian states generate the same quadratic-Majorana covariance body, so non-Gaussian state resources cannot enlarge this two-point relaxation. More generally, 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)}$, and random access decoding from $N$ copies with constant success probability above $1/2$ requires $nN=\Omega(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.