2025/11/11 by Ma, Gordon, Angelakis, Dimitris G.
#FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.2511.08362
Qubit-efficient optimization seeks to represent an N-variable combinatorial problem within a Hilbert space smaller than 2N, using only as much quantum structure as the objective itself requires. Quadratic unconstrained binary optimization (QUBO) problems, for example, depend only on pairwise information -- expectations and correlations between binary variables -- yet standard quantum circuits explore exponentially large state spaces. We recast qubit-efficient optimization as a geometry problem: the minimal representation should match the O(N2) structure of quadratic objectives. The key insight is that the local-consistency problem -- ensuring that pairwise marginals correspond to a realizable global distribution -- coincides exactly with the Sherali-Adams level-2 polytope SA(2), the tightest convex relaxation expressible at the two-body level. Previous qubit-efficient approaches enforced this consistency only implicitly. Here we make it explicit: (a) anchoring learning to the SA(2) geometry, (b) projecting via a differentiable iterative-proportional-fitting (IPF) step, and (c) decoding through a maximum-entropy Gibbs sampler. This yields a logarithmic-width pipeline (2\lceillog2 N\rceil + 2 qubits) that is classically simulable yet achieves strong empirical performance. On Gset Max-Cut instances (N=800--2000), depth-2--3 circuits reach near-optimal ratios (r^* ≈ 0.99), surpassing direct SA(2) baselines. The framework resolves the local-consistency gap by giving it a concrete convex geometry and a minimal differentiable projection, establishing a clean polyhedral baseline. Extending beyond SA(2) naturally leads to spectrahedral geometries, where curvature encodes global coherence and genuine quantum structure becomes necessary.