An Information-Minimal Geometry for Qubit-Efficient Optimization
Gordon Ma, Dimitris G. Angelakis · 2025
Read An Information-Minimal Geometry for Qubit-Efficient Optimization by Gordon Ma, Dimitris G. Angelakis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-08362.txt.
Introduction
Gordon Ma and Dimitris Angelakis recast qubit lean quantum tuning as a question about the minimal geometry an objective function truly needs. Quadratic binary tuning problems depend only on one and two body statistics, yet standard variational quantum algorithms wander exponentially large Hilbert spaces with far wider circuits than the variable count demands. The authors ask what representation the objective itself requires, independent of any algorithm.
Enforcing consistency among pairwise statistics defines a convex body, the level two Sherali Adams polytope, capturing exactly the needed information. Their pipeline uses a logarithmic width circuit for pairwise moments, a differentiable projection for local feasibility, and a maximum entropy decoder. On large Max-Cut instances it reaches near optimal ratios at shallow depth.
Catalog record
| CREATOR | Gordon Ma, Dimitris G. Angelakis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 109 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-08362
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Information-Minimal Geometry for Qubit-Efficient Optimization Gordon Ma, Dimitris G. Angelakis Abstract Qubit-efficient optimization seeks to represent an N N -variable combinatorial problem within a Hilbert space smaller than 2 N 2^{N} , 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 𝒪 ( N 2 ) \mathcal{O}(N^{2}) 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 ) \mathrm{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 ) \mathrm{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 ⌈ log 2 N ⌉ + 2 2\lceil\log_{2}N\rceil{+}2 qubits) that is classically simulable yet achieves strong empirical performance. On GSET Max-Cut instances ( N = 800 N{=}800 – 2000 2000 ), depth-2–3 circuits reach near-optimal ratios ( r ⋆ ≈ 0.99 r^{\star}{\approx}0.99 ), surpassing direct SA ( 2 ) \mathrm{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 ) \mathrm{SA}(2) naturally leads to spectrahedral geometries, where curvature encodes global coherence and genuine quantum structure becomes necessary. 1 Introduction The qubit bottleneck. Variational quantum algorithms (VQE [ 31 ] , QAOA [ 15 ] ) remain leading candidates for near-term combinatorial optimization. Most advances pursue expressivity and trainability —better ansatz [ 40 ] , problem-informed mixers [ 16 ] , warm-starting [ 12 ] —motivated by the common intuition, summarized in [ 38 , 6 ] , that efficiently exploring a larger portion of Hilbert space may confer greater variational power. Yet present-day quantum processors expose a simpler constraint: coherent circuit volume [ 13 ] , the product of usable width and depth below the noise floor. Although current hardware now hosts hundreds of physical qubits, only tens can participate in circuits of meaningful depth before decoherence dominates. The practical limitation is therefore width : how many variables can be represented coherently at once without inflating gate count or sampling overhead. This motivates a sharper question— can we solve an N -variable optimization problem using fewer than N qubits, without a compensating increase in circuit depth or total gate volume? This work addresses that question directly. From expressivity to efficiency. When the number of qubits available is smaller than the number of optimization variables, three pragmatic routes emerge. One is to decompose large instances into smaller subproblems that fit within hardware limits before recombining their partial solutions [ 26 , 1 , 2 ] . A second is to compress —encode multiple logical variables per qubit through shared bases or correlators, whether linearly [ 17 ] , polynomially [ 32 ] , or exponentially [ 35 ] . A third is to leverage classical compute by embedding small quantum modules within hybridized pipelines, where quantum correlations or relaxations improve classical preconditioning, rounding, or local-searching [ 10 , 11 , 2 , 36 ] . Each direction addresses the same width constraint from a different angle, and a working architecture may ultimately integrate all three. Here we focus on the compression primitive – the minimal representation of information that a quadratic objective truly requires. Qubit-efficient compression schemes. Among the three routes above, compression has evolved into a field of its own. It asks how many qubits are truly necessary to represent a combinatorial objective of N variables. Early approaches drew inspiration from quantum random access codes (QRACs) [ 17 ] , which encode several classical variables probabilistically into the expectation values of a single qubit – achieving linear compression and providing a modest approximation ratio guarantee [ 37 ] . Contemporary to this, a line of qubit-efficient encodings [ 35 , 21 , 25 ] achieved exponential width reduction by encoding multiple optimization variables within shared measurement bases, effectively capturing single-variable statistics while approximating pairwise correlations heuristically and conditionally. Between these extremes, Pauli Correlation Encoding (PCE) [ 32 ] achieves polynomial compression, distributing logical variables across commuting Pauli correlators up to N=8000 variables of a QUBO problem. A complementary compression of the physical process such as the qubit-efficient QAOA [ 34 ] reduce qubit count by block-encoding the QAOA Hamiltonian itself. Together, these studies reveal that width can be reduced by orders of magnitude– but also sharpen a deeper question: if linear, polynomial, and exponential compression are all possible, how much is enough? For concreteness and tractability, both prior work and the present study limit this analysis to quadratic unconstrained binary optimization (QUBO) problems, where costs and correlations are well defined and theoretical comparisons are possible; the same reasoning is expected to generalize to broader combinatorial models. Intuitively, a quadratic objective on N binary variables contains \mathcal{O}(N^{2}) pairwise terms, since Q\in\mathbb{R}^{N\times N} defines coefficients Q_{ij}=Q_{ji} . Computing its expected value, \mathbb{E}[x^{\top}Qx] , depends only on expectations of single variables and their pairwise products—no higher-order correlations enter—although finding parameters that minimize this expectation remains an NP-hard search over 2^{N} configurations. The Hilbert space of an N -qubit circuit, by contrast, spans all 2^{N} amplitudes—far more information than is needed to represent or evaluate a quadratic objective, which depends only on these low-order correlations. Leveraging this observation, we can focus training on a compact space of consistent local statistics rather than on the full state vector. The next section develops this idea by expressing the objective directly in this reduced set of expectations and treating their consistency as a geometric constraint. Figure 1 : The information-minimal two-body framework as geometric transport. The framework treats optimization as a sequence of geometric maps, each conserving information while changing representation. (Left) A quadratic objective E_{Q}=\mathbb{E}[x^{\top}Qx] depends only on the one- and two-body moments of its variables. A log-width quantum circuit of n_{q}=2\lceil\log_{2}N\rceil{+}2 qubits produces a Born distribution p_{\theta}(z) whose expected local statistics (\hat{\mu},\hat{\nu}) define the pseudo-moment space . (Center) A \rho -damped, KL-regulated iterative-proportional-fitting (IPF) step softly projects these moments toward the Sherali–Adams level-2 polytope SA(2)—the convex body of locally consistent marginals—yielding near-feasible (\tilde{\mu},\tilde{\nu}) . The information distance D_{\mathrm{KL}}((\tilde{\mu},\tilde{\nu})\|(\hat{\mu},\hat{\nu})) enters the loss, guiding training toward natural feasibility. (Right) A maximum-entropy mapping converts the repaired moments into an Ising surrogate with fields (h,J) ; Gibbs sampling (dotted arrow) realizes discrete bit-strings x from distribution implied by the learned moments. The lower panel summarizes this information–geometric transport from parameters to bit-strings— linking the variational circuit, convex relaxation, and probabilistic decoding within one minimal representation. This work: geometric representation anchored to pairwise consistency. Having asked what information a quadratic objective truly requires, we begin by rewriting the cost in those minimal terms. In a variational algorithm, the cost is normally written as a global expectation \displaystyle\mathbb{E}_{p}[f]=\sum_{x}p(x)x^{T}Qx (1) or, in quantum form, \braket{\psi|H_{Q}|\psi}=\sum_{x}|\braket{x|\psi}|^{2}x^{T}Qx