Learning Cut Distributions with Quantum Optimization

Quantum Physics [Submitted on 15 Apr 2026] Learning Cut Distributions with Quantum Optimization Bao Bach, Cameron Ibrahim, Reuben Tate, Jad Salem, Stephan Eidenbenz, Ilya Safro 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. Comments: 29 pages, 6 figures, 2 tables Subjects: Quantum Physics (quant-ph); Combinatorics (math.CO) Cite as: arXiv:2604.14381 [quant-ph]   (or arXiv:2604.14381v1 [quant-ph] for this version)   https://doi.org/10.48550/arXiv.2604.14381 Focus to learn more Submission history From: Bao Bach [view email] [v1] Wed, 15 Apr 2026 19:55:14 UTC (1,706 KB) Access Paper: HTML (experimental) view license Current browse context: quant-ph < prev   |   next > new | recent | 2026-04 Change to browse by: math math.CO References & Citations INSPIRE HEP NASA ADS Google Scholar Semantic Scholar Export BibTeX Citation Bookmark Bibliographic Tools Bibliographic and Citation Tools Bibliographic Explorer Toggle Bibliographic Explorer (What is the Explorer?) Connected Papers Toggle Connected Papers (What is Connected Papers?) Litmaps Toggle Litmaps (What is Litmaps?) scite.ai Toggle scite Smart Citations (What are Smart Citations?) Code, Data, Media Demos Related Papers About arXivLabs Which authors of this paper are endorsers? | Disable MathJax (What is MathJax?)