Learning Cut Distributions with Quantum Optimization

Bao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro, [1ex] Quantum Science, Engineering, University of Delaware, Newark, DE, USA · 2026

Read Learning Cut Distributions with Quantum Optimization by Bao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro, [1ex] Quantum Science, Engineering, University of Delaware, Newark, DE, USA (2026) 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-2604-14381.txt.

Introduction

Bach and five colleagues tackle fair variants of combinatorial optimization, where the goal is a distribution over solutions that maximizes the expected worst case. An optimal distribution can need exponential support, so the team turns to the Quantum Approximate Optimization Algorithm, showing a finite-layer ansatz can capture any spread over bitstrings. Their circuit solves the Fair Cut Cover well, beats classical approximations provably on some graph shapes, and beats them in tests. The result links dynamical Lie algebra work on QAOA to practical fair optimization.

Catalog record

CREATORBao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro, [1ex] Quantum Science, Engineering, University of Delaware, Newark, DE, USA
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93368
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.14381

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Learning Cut Distributions with Quantum Optimization Bao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro, [1ex] Quantum Science, Engineering, University of Delaware, Newark, DE, USA Abstract Many combinatorial optimization problems admit a maximin fairness variant, where the aim is to find a distribution over possible solutions which maximizes an expected worst-case outcome. However, the support for an optimal distribution may be exponential, which can be intractable to represent in the worst case. To this end, we propose a quantum based approach to solving distribution optimization problems. Expanding on work analyzing the Dynamical Lie Algebras of the Quantum Approximate Optimization Algorithm (QAOA), we show that with a finite number of layers a QAOA ansatz can be constructed to capture any distribution over bitstrings. We show that the resulting circuit is able to effectively solve the Fair Cut Cover, a fair interpretation of the classical Fractional Cut Cover Problem. In addition, we show that our algorithm is provably better than classical approximations on certain graph structures and empirically outperforms these classical algorithms on tested instances. 1 Introduction Classical optimization methods are typically designed to find a single feasible solution that minimizes or maximizes a scalar objective function 10 ; 51 . However, in some applications, this is not the only quantity of interest. When fairness, robustness, or coverage matter, the relevant question is often not which one solution is best, but whether the worst-served part of the application domain can be protected reliably 13 ; 7 . This naturally shifts attention from individual solutions to distributions over solutions, which can express variability, balance, and protection against worst-case outcomes in a way that any single solution cannot. This distributional viewpoint is especially relevant in quantum computation, where the output of an algorithm is inherently probabilistic. Rather than treating this probabilistic output as an obstacle that must be post-processed into one good solution, we treat it as the optimization target itself. This perspective is particularly appropriate for objectives in which performance is determined by the least-favored component and is therefore naturally defined over distributions rather than individual configurations 20 . It also raises a basic question: can quantum optimization directly learn useful structured distributions, rather than merely sample candidate solutions from which one keeps the best observed outcome? Prior work in quantum generative modeling has explored whether parameterized quantum circuits can learn or engineer useful probability distributions 35 ; 21 . Here, we consider this question in a different setting by studying combinatorial optimization problems in which the goal is to learn a distribution that maximizes a worst-case criterion over the underlying discrete structure. Our setting is specifically inspired by the maximin fairness paradigm 44 . Such problems provide a natural setting for comparing classical methods, which typically return one solution together with an approximation guarantee, with quantum methods, which manipulate and measure distributions natively. We make this concrete in the setting of graph cuts, where distributions over cuts offer a simple but expressive model for studying fairness-oriented optimization objectives. Each cut distribution naturally defines, for each edge, a probability that that edge is cut. These probabilities encode rich structural information, which we can use to explore how robustly different parts of the graph are separated under a given distribution. Therefore, optimizing over cut distributions opens the door to fairness, coverage, and robustness objectives that are uniquely suited to the probabilistic nature of quantum computing. Figure 1: Given a graph G (left), one can construct a \mathcal{D} -QAOA circuit from which to sample cuts on G (bottom-right). Each layer added to the circuit expands the space of representable distributions (top-right). The optimal cut distribution for fair cut cover (red) is representable after k layers, and consists of 6 possible cuts with uniform probability (equal normalized weight among cuts), yielding an edge cut probability of 2/3 for each edge. Every \mathbb{Z}_{2} -symmetric cut distribution on n vertices is representable in L layers, and the space of hyperplane rounding distributions (HR) will also eventually be entirely contained in this space. Graph problems over cut distributions We explore this idea through the lens of the Fractional Cut Cover problem 45 ; 41 . Given all cuts, the Cut Cover problem asks for the smallest set of cuts (a cut is a subset of edges that partitions graph vertices into two disjoint sets ) such that every edge e\in E is cut at least once. Its linear relaxation is the Fractional Cut Cover problem, which assigns non-negative weights to all cuts so that the total weight is minimized and each edge is covered by cuts with a total weight of at least one 41 . An example of this is given in Figure 1 . Fractional Cut Cover is closely related to the geometry of the cut cone and has recently been shown to be APX-Complete by 4 . The authors provide an algorithm based on semidefinite programming (SDP) and hyperplane rounding, which achieves the best possible polynomial-time approximation ratio under the Unique Games Conjecture 5 . A solution to Fractional Cut Cover can be interpreted probabilistically: after normalizing the cut weights, it becomes a distribution over cuts. Under this interpretation, the value of the solution is determined by the edge that is least likely to be cut, so the problem becomes one of maximizing the minimum edge-cut probability. This recasts Fractional Cut Cover as a maximin optimization problem over distributions rather than individual cuts, making it a natural model for fairness-oriented objectives in which worst-case performance is the quantity of interest. It also makes the problem an attractive testbed for our setting, because it combines a clear probabilistic interpretation with strong geometric and algorithmic structure as it is both structurally rich (via its connections to Grothendieck symmetric inequalities 17 and theta functions 29 ) and algorithmically sharp (via SDP with randomized rounding, and Unique Game Conjecture tight hardness results 4 ). Summary of the results We study the Fractional Cut Cover problem through the lens of cut distributions and establish a sharp contrast between the best known polynomial-time classical approach and a quantum variational algorithm. On the classical side, we analyze the semidefinite programming (SDP) relaxation together with hyperplane rounding, clarifying the structural limitations of this pipeline for optimizing the fair-cut objective. On the quantum side, we formulate the problem as a distribution-learning task with QAOA ansatz, where the resulting quantum state \ket{\psi(\beta,\gamma)} induces a cut distribution chosen to maximize the minimum edge cut probability. Our main findings show that the quantum approach is not just an alternativeview, but provably results in better performance on important graph families. In particular, for highly symmetric instances such as the complete graph family, we prove that SDP combined with randomized hyperplane rounding cannot reproduce the optimal Fractional Cut Cover distribution, whereas given enough layers, \mathcal{D} -QAOA (introduced later) can realize any distribution exactly. This yields a concrete quantum–classical separation at the level of cut distributions, rather than only objective values, and highlights a qualitative advantage of quantum circuits in navigating the cut cone. More broadly, our results position near-term quantum optimization as a natural framework for learning combinatorial distributions that are difficult to access through classical relaxations and rounding alone. Rather than serving only as approximate solvers

Read the complete text