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=Θ(n2) 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 ΔMaj(n)=tan (π/4n)=Θ(1/n), whereas uniformly random sign assignments retain Θ(1/√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 √((2ln2 n/m)), and 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.
Related
- Complexity Amplification from Compression in Quantum Random Access Optimization
- Efficient SPAD reconstruction framework with time-frequency domain compression and lightweight joint depth-intensity optimization
- Optimal compression with quantum retrieval
- Quantum Simulation of Non-Markovian Open Quantum Systems via Low-Rank Kernel Compression and Coupling Dilution
- Image Compression Using Quantum Wavelet Transform and Quantum Convolutional Networks
BibTeX
@misc{hadfield2026free,
title = {{No Free Compression in Quantum Relaxations for Optimization}},
author = {Stuart Hadfield},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2608.25151},
eprint = {2608.25151},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.25151},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - No Free Compression in Quantum Relaxations for Optimization
AU - Stuart Hadfield
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2608.25151
UR - https://arxiv.org/abs/2608.25151
AB - 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=Θ(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 Δ_Maj(n)=tan (π/4n)=Θ(1/n), whereas uniformly random sign assignments retain Θ(1/√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 √((2ln2 n/m)), and 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.
ER -