Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.14381 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914477139558400 |
|---|---|
| author | Bach, Bao Ibrahim, Cameron Tate, Reuben Salem, Jad Eidenbenz, Stephan Safro, Ilya |
| author_facet | Bach, Bao Ibrahim, Cameron Tate, Reuben Salem, Jad Eidenbenz, Stephan Safro, Ilya |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14381 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning Cut Distributions with Quantum Optimization Bach, Bao Ibrahim, Cameron Tate, Reuben Salem, Jad Eidenbenz, Stephan Safro, Ilya Quantum Physics Combinatorics 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. |
| title | Learning Cut Distributions with Quantum Optimization |
| topic | Quantum Physics Combinatorics |
| url | https://arxiv.org/abs/2604.14381 |