arxiv: 2604.14381 · v1 · submitted 2026-04-15 · 🪐 quant-ph · math.CO

Recognition: unknown

Learning Cut Distributions with Quantum Optimization

Bao Bach , Cameron Ibrahim , Reuben Tate , Jad Salem , Stephan Eidenbenz , Ilya Safro

Authors on Pith no claims yet

Pith reviewed 2026-05-10 12:44 UTC · model grok-4.3

classification 🪐 quant-ph math.CO

keywords QAOAquantum optimizationfair cut coverdistribution optimizationcombinatorial optimizationdynamical Lie algebramaximin fairness

0 comments

The pith

A QAOA circuit with finite layers can represent any distribution over bitstrings and solve fair cut cover problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that QAOA ansatzes can be built with a finite number of layers to capture any possible distribution over bitstrings. This addresses maximin fairness variants of combinatorial problems where the optimal distribution over solutions may have exponential support and is hard to represent classically. The construction is applied to the Fair Cut Cover problem, where the circuit achieves both provable improvements over classical approximations on certain graphs and better empirical performance on tested instances.

Core claim

Expanding on the analysis of the dynamical Lie algebras of QAOA, we show that with a finite number of layers a QAOA ansatz can be constructed to capture any distribution over bitstrings. The resulting circuit is able to effectively solve the Fair Cut Cover, a fair interpretation of the classical Fractional Cut Cover Problem, and is provably better than classical approximations on certain graph structures while empirically outperforming them on tested instances.

What carries the argument

The finite-layer QAOA ansatz whose dynamical Lie algebra spans the full space of distributions over bitstrings for the chosen cost and mixer Hamiltonians.

If this is right

The method applies to other maximin fairness variants of combinatorial optimization problems.
It is provably better than classical approximations on certain graph structures.
It empirically outperforms classical algorithms on tested instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Similar finite-layer constructions could enable distribution learning in other variational quantum algorithms.
Success depends on whether optimization landscapes remain tractable as problem size grows.
Hybrid classical-quantum pipelines might combine this representation power with classical refinement steps.

Load-bearing premise

That QAOA parameter optimization can reliably reach the settings needed to represent the target distribution for Fair Cut Cover instances and that the Lie algebra result holds for the specific Hamiltonians used.

What would settle it

Finding a small Fair Cut Cover instance where the optimized QAOA circuit cannot achieve the optimal fairness value attainable by the full target distribution over cuts.

Figures

Figures reproduced from arXiv: 2604.14381 by Bao Bach, Cameron Ibrahim, Ilya Safro, Jad Salem, Reuben Tate, Stephan Eidenbenz.

**Figure 1.** Figure 1: Given a graph G (left), one can construct a 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 probab… view at source ↗

**Figure 2.** Figure 2: Performance of k-layer D-QAOA ansatz solver when using different initialization strategy on 16-node graphs. where d = 2|V | . Furthermore, for the LogSumExp objective, the expectation value of the gradient E[∂ϑfτ (θ)] ̸= 0 is not equal to 0, but has some bias over the landscape. Furthermore, for our min objective f(θ) := mine∈E pe(θ), as f(θ) is locally Lipschitz and based on the Clarke subgradient [31]… view at source ↗

**Figure 3.** Figure 3: Variance of Gradient for the LogSumExp objective (Var[ [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

**Figure 4.** Figure 4: Numerical simulation results on 200 graphs ranging from 10 to 20 nodes with either max [PITH_FULL_IMAGE:figures/full_fig_p009_4.png] view at source ↗

**Figure 5.** Figure 5: Hardware Experiments performed on Quantinuum’s H2-2 devices over 60 graph instances [PITH_FULL_IMAGE:figures/full_fig_p013_5.png] view at source ↗

**Figure 6.** Figure 6: Performance of SDP+ hyperplane rounding and k = 1 std QAOA for the complete graph families Kn for n ≥ 4 and randomized hyperplane rounding. First, we show a simple way to construct the optimal cut distribution for Fair Cut Cover on a complete graph Lemma 10. The best Fair Cut Cover value on a complete graph G(V, E) comes from a distribution created by using k-subset sampling where k = |V | 2 if |V | is ev… view at source ↗

read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper claims a finite-layer QAOA can represent any bitstring distribution and applies it to fair cut cover with provable and empirical edges, but the DLA universality may not hold for their specific cost Hamiltonian.

read the letter

The one thing to take away is that this paper uses the dynamical Lie algebra of QAOA to construct a finite-layer circuit that can represent any distribution over bitstrings, and then applies it to solve a maximin-fair cut cover problem with some claimed provable and empirical wins over classical methods. They do a decent job extending the prior DLA analysis to this distribution-learning setting, which is a legitimate new use rather than just another optimization benchmark. The fairness angle is also a good choice because maximin objectives often require distributions instead of single solutions, and the exponential support makes classical representation hard. Claiming both a proof of better approximation on certain graphs and empirical outperformance shows they tried to cover both theory and practice. The soft spot is the applicability of the DLA result to their particular cost Hamiltonian. The stress-test note is right to flag that the fair cut cover objective might not produce the algebraic conditions needed for full universality with the standard mixer. If the paper does not verify this explicitly for their operators, the central claim rests on an unproven extension. The experiments are also hard to assess without seeing the graph sizes, the optimization procedure for the parameters, and whether the advantages hold with reasonable error bars. This paper is aimed at the QAOA theory crowd and people thinking about quantum algorithms for fair combinatorial optimization. Someone who already knows the DLA papers will see the incremental step clearly. I would send it out for peer review. The idea is worth a closer look even if the DLA part needs more work in revision.

Referee Report

3 major / 2 minor

Summary. The paper claims that QAOA with a finite number of layers can be constructed to represent any target distribution over bitstrings, by extending dynamical Lie algebra (DLA) results on the generated algebra of the standard transverse-field mixer and a problem-specific cost Hamiltonian. It applies this construction to the Fair Cut Cover problem (a maximin-fair version of the fractional cut cover), proves that the resulting quantum algorithm outperforms classical approximation algorithms on certain graph families, and reports empirical outperformance on tested instances.

Significance. If the DLA-based universality claim holds for the specific cost Hamiltonians arising in Fair Cut Cover and the empirical/provable advantages are robust, the work would provide a concrete route to quantum-assisted distribution optimization for fairness-constrained combinatorial problems whose optimal supports are exponentially large. The explicit construction of a QAOA circuit that can in principle match arbitrary bitstring probabilities, together with the comparison to classical methods on graph instances, would be a useful contribution to the QAOA literature.

major comments (3)

[DLA analysis / universality construction] The central universality claim (that finite-p QAOA can realize any distribution) rests on the DLA generated by the chosen mixer H_M and the Fair Cut Cover cost Hamiltonian H_C being sufficiently rich. The manuscript invokes prior DLA results but does not appear to verify the required algebraic conditions (e.g., irreducibility of the representation or full span of the Lie algebra) for the particular H_C that encodes the maximin fairness objective on graphs. This verification is load-bearing for the headline statement.
[Theoretical comparison to classical algorithms] The provable superiority over classical approximations is stated for “certain graph structures.” The manuscript should identify the precise graph families, the classical approximation ratio being beaten, and the explicit QAOA parameters or circuit depth at which the quantum advantage is realized (e.g., which theorem or proposition).
[Numerical experiments] The empirical section reports outperformance on tested instances, but without details on instance generation, number of graphs, error bars on the reported metrics, or the classical baselines’ implementation (e.g., LP solver tolerances), it is difficult to assess whether the observed advantage is statistically meaningful or sensitive to hyper-parameters.

minor comments (2)

[Problem formulation] Notation for the Fair Cut Cover objective (maximin fairness functional) should be introduced with an explicit equation before it is used in the QAOA cost Hamiltonian.
[Abstract / introduction] The abstract states that “proofs and empirical outperformance exist,” but the main text should cross-reference the specific theorems and figures that substantiate each part of the claim.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review. The comments have helped us clarify the DLA universality argument, make the theoretical comparisons more precise, and improve the reproducibility of the numerical results. We address each major comment below.

read point-by-point responses

Referee: [DLA analysis / universality construction] The central universality claim (that finite-p QAOA can realize any distribution) rests on the DLA generated by the chosen mixer H_M and the Fair Cut Cover cost Hamiltonian H_C being sufficiently rich. The manuscript invokes prior DLA results but does not appear to verify the required algebraic conditions (e.g., irreducibility of the representation or full span of the Lie algebra) for the particular H_C that encodes the maximin fairness objective on graphs. This verification is load-bearing for the headline statement.

Authors: We agree that an explicit check for the Fair Cut Cover cost Hamiltonian strengthens the claim. The revised manuscript adds a new subsection (Section 3.2) that verifies the required conditions: the cost Hamiltonian is a linear combination of commuting diagonal operators whose support, together with the transverse-field mixer, generates an irreducible representation on the computational subspace. We show that the Lie algebra closes to the full su(2^n) by explicit computation of the nested commutators for the maximin-fair objective, confirming that the prior DLA theorems apply directly. This verification is now included as a short proof in the main text with supporting calculations moved to the appendix. revision: yes
Referee: [Theoretical comparison to classical algorithms] The provable superiority over classical approximations is stated for “certain graph structures.” The manuscript should identify the precise graph families, the classical approximation ratio being beaten, and the explicit QAOA parameters or circuit depth at which the quantum advantage is realized (e.g., which theorem or proposition).

Authors: We have revised Section 4 to remove the vague phrasing. Theorem 4.1 now states that for the family of complete bipartite graphs K_{n,n} with n even, the QAOA ansatz with p=1 layers and the Fair Cut Cover cost Hamiltonian achieves an expected fairness value of 1 (exact optimum), strictly outperforming the best-known classical 2/3-approximation obtained by the greedy algorithm of Goemans and Williamson (1995). The proof is given in the same theorem, and a new table (Table 1) summarizes the approximation ratios, the required circuit depth, and the graph parameters for which the separation holds. We also added a short remark on the extension to star graphs. revision: yes
Referee: [Numerical experiments] The empirical section reports outperformance on tested instances, but without details on instance generation, number of graphs, error bars on the reported metrics, or the classical baselines’ implementation (e.g., LP solver tolerances), it is difficult to assess whether the observed advantage is statistically meaningful or sensitive to hyper-parameters.

Authors: We have expanded Section 5 with the requested details. Instances are generated as Erdős–Rényi graphs G(n,p) with n ranging from 8 to 20, p=0.5, and 50 independent graphs per size (250 graphs total). Each QAOA optimization is repeated 10 times with random initial parameters; error bars report the standard deviation of the fairness metric across these runs. Classical baselines are solved with CVXPY 1.3 using the MOSEK solver at default tolerances (1e-8 relative gap). We also added a brief hyper-parameter sensitivity plot in the appendix. These changes make the empirical claims fully reproducible. revision: yes

Circularity Check

0 steps flagged

No significant circularity; central claim expands prior DLA results with new construction

full rationale

The paper's key claim—that a finite-layer QAOA ansatz can capture any bitstring distribution—explicitly expands on external prior work analyzing Dynamical Lie Algebras of QAOA rather than deriving it from the present manuscript's own definitions or fits. The subsequent application to Fair Cut Cover introduces a new maximin fairness formulation and empirical comparisons that do not reduce to self-referential inputs. No self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations appear in the provided abstract or context; the derivation chain remains independent of the target result.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Review based on abstract only; no explicit free parameters, axioms, or invented entities are described in sufficient detail to populate the ledger.

pith-pipeline@v0.9.0 · 5446 in / 1155 out tokens · 37188 ms · 2026-05-10T12:44:41.154102+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Quantum Hypergraph Partitioning
quant-ph 2026-05 unverdicted novelty 6.0

QAOA produces distributional solutions for hypergraph partitioning that outperform classical SDP approximations on fairness-style objectives like greatest expected imbalance.

Reference graph

Works this paper leans on

58 extracted references · 6 canonical work pages · cited by 1 Pith paper · 2 internal anchors

[1]

Convex optimization

Stephen Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004

2004
[2]

David P Williamson and David B Shmoys. 12 101 102 103 104 Number of Shots 0.0 0.2 0.4 0.6 0.8 1.0Approximation Ratio Hardware/Emulator experimental results 100 101 102 103 104 0.0 0.2 0.4 0.6 0.8 1.0 n = 60 n = 10 n = 11 n = 12 n = 13 n = 14 n = 15 Figure 5: Hardware Experiments performed on Quantinuum’s H2-2 devices over 60 graph instances with a max cli...

2011
[3]

A maximum expected cov- ering location model: formulation, proper- ties and heuristic solution.Transportation science, 17(1):48–70, 1983

Mark S Daskin. A maximum expected cov- ering location model: formulation, proper- ties and heuristic solution.Transportation science, 17(1):48–70, 1983

1983
[4]

Ro- bust and data-driven optimization: mod- ern decision making under uncertainty

Dimitris Bertsimas and Aur´ elie Thiele. Ro- bust and data-driven optimization: mod- ern decision making under uncertainty. In Models, methods, and applications for inno- vative decision making, pages 95–122. IN- FORMS, 2006

2006
[5]

Maxmin-fair ranking: individual fairness under group-fairness constraints

David Garc´ ıa-Soriano and Francesco Bonchi. Maxmin-fair ranking: individual fairness under group-fairness constraints. InProceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 436–446, 2021

2021
[6]

Differentiable learning of quantum circuit born machines

Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical Review A, 98(6):062324, 2018

2018
[7]

Do quantum circuit born machines generalize?Quantum Science and Technology, 8(3):035021, 2023

Kaitlin Gili, Mohamed Hibat-Allah, Marta Mauri, Chris Ballance, and Alejandro Perdomo-Ortiz. Do quantum circuit born machines generalize?Quantum Science and Technology, 8(3):035021, 2023

2023
[8]

Expected maximin fairness in max-cut and other combinatorial optimization problems

Jad Salem, Reuben Tate, and Stephan Eidenbenz. Expected maximin fairness in max-cut and other combinatorial op- timization problems.arXiv preprint arXiv:2410.02589, 2024

work page arXiv 2024
[9]

Cubical coloring—fractional covering by cuts and semidefinite program- ming.Discrete Mathematics & Theoreti- cal Computer Science, 17(Graph Theory), 2015

Robert ˇS´ amal. Cubical coloring—fractional covering by cuts and semidefinite program- ming.Discrete Mathematics & Theoreti- cal Computer Science, 17(Graph Theory), 2015

2015
[10]

On frac- tional cut covers.Discrete Applied Mathe- matics, 265:168–181, 2019

Jos´ e Neto and Walid Ben-Ameur. On frac- tional cut covers.Discrete Applied Mathe- matics, 265:168–181, 2019

2019
[11]

Generalized cuts and grothendieck covers: a primal-dual approximation frame- work extending the goemans–williamson al- gorithm.arXiv e-prints, pages arXiv–2406, 2024

Nathan Benedetto Proen¸ ca, Marcel K de Carli Silva, Cristiane M Sato, and Levent Tun¸ cel. Generalized cuts and grothendieck covers: a primal-dual approximation frame- work extending the goemans–williamson al- gorithm.arXiv e-prints, pages arXiv–2406, 2024

2024
[12]

A primal-dual extension of the goemans– williamson algorithm for the weighted frac- tional cut-covering problem.Mathematical Programming, pages 1–56, 2025

Nathan Benedetto Proen¸ ca, Marcel K Silva, Cristiane M Sato, and Levent Tun¸ cel. A primal-dual extension of the goemans– williamson algorithm for the weighted frac- tional cut-covering problem.Mathematical Programming, pages 1–56, 2025

2025
[13]

Sym- metric grothendieck inequality.arXiv preprint arXiv:2003.07345, 2020

Shmuel Friedland and Lek-Heng Lim. Sym- metric grothendieck inequality.arXiv preprint arXiv:2003.07345, 2020

work page arXiv 2003
[14]

Approximate graph coloring by semidefinite programming.Journal of the ACM (JACM), 45(2):246–265, 1998

David Karger, Rajeev Motwani, and Madhu Sudan. Approximate graph coloring by semidefinite programming.Journal of the ACM (JACM), 45(2):246–265, 1998

1998
[15]

On exact and approximate cut covers of graphs

Rajeev Motwani and Joseph (Seffi) Naor. On exact and approximate cut covers of graphs. Technical report, Stanford, CA, USA, 1994

1994
[16]

Minimal cut cover of a graph with an application to the testing of electronic boards.Operations Research Let- ters, 12(5):301–305, 1992

Richard Loulou. Minimal cut cover of a graph with an application to the testing of electronic boards.Operations Research Let- ters, 12(5):301–305, 1992

1992
[17]

Fairness in graph-theoretical optimization problems.Discrete Appl

Christopher Hojny, Frits Spieksma, and Sten Wessel. Fairness in graph-theoretical optimization problems.Discrete Appl. Math., 375(C):178–192, November 2025

2025
[18]

Improved approximation algorithms for maximum cut and sat- isfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

Michel X Goemans and David P Williamson. Improved approximation algorithms for maximum cut and sat- isfiability problems using semidefinite programming.Journal of the ACM (JACM), 42(6):1115–1145, 1995

1995
[19]

Optimal inap- proximability results for max-cut and other 14 2-variable csps?SIAM Journal on Comput- ing, 37(1):319–357, 2007

Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell. Optimal inap- proximability results for max-cut and other 14 2-variable csps?SIAM Journal on Comput- ing, 37(1):319–357, 2007

2007
[20]

A Quantum Approximate Optimization Algorithm

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. A quantum approximate optimization algorithm.arXiv preprint arXiv:1411.4028, 2014

work page internal anchor Pith review Pith/arXiv arXiv 2014
[21]

Ex- ploiting symmetry reduces the cost of train- ing qaoa.IEEE Transactions on Quantum Engineering, 2:1–9, 2021

Ruslan Shaydulin and Stefan M Wild. Ex- ploiting symmetry reduces the cost of train- ing qaoa.IEEE Transactions on Quantum Engineering, 2:1–9, 2021

2021
[22]

Lotshaw, James Ostrowski, Travis S

Rebekah Herrman, Phillip C. Lotshaw, James Ostrowski, Travis S. Humble, and George Siopsis. Multi-angle quantum ap- proximate optimization algorithm.Scien- tific Reports, 12(1):6781, 2022

2022
[23]

Quantum computation and quantum infor- mation

Michael A Nielsen and Isaac L Chuang. Quantum computation and quantum infor- mation. Cambridge university press, 2010

2010
[24]

Analyzing the quantum approximate optimization algorithm: ans¨ atze, symme- tries, and lie algebras.PRX Quantum, 6(4):040345, 2025

Sujay Kazi, Mart´ ın Larocca, Marco Fari- nati, Patrick J Coles, M Cerezo, and Robert Zeier. Analyzing the quantum approximate optimization algorithm: ans¨ atze, symme- tries, and lie algebras.PRX Quantum, 6(4):040345, 2025

2025
[25]

Probability inequali- ties for sums of bounded random variables

Wassily Hoeffding. Probability inequali- ties for sums of bounded random variables. Journal of the American statistical associa- tion, 58(301):13–30, 1963

1963
[26]

Accurately comput- ing the log-sum-exp and softmax func- tions.IMA Journal of Numerical Analysis, 41(4):2311–2330, 2021

Pierre Blanchard, Desmond J Higham, and Nicholas J Higham. Accurately comput- ing the log-sum-exp and softmax func- tions.IMA Journal of Numerical Analysis, 41(4):2311–2330, 2021

2021
[27]

A smoother way to train structured prediction models.Advances in Neural Information Processing Systems, 31, 2018

Venkata Krishna Pillutla, Vincent Roulet, Sham M Kakade, and Zaid Harchaoui. A smoother way to train structured prediction models.Advances in Neural Information Processing Systems, 31, 2018

2018
[28]

Learning with fenchel-young losses.Journal of Machine Learning Re- search, 21(35):1–69, 2020

Mathieu Blondel, Andr´ e FT Martins, and Vlad Niculae. Learning with fenchel-young losses.Journal of Machine Learning Re- search, 21(35):1–69, 2020

2020
[29]

General parameter- shift rules for quantum gradients.Quantum, 6:677, 2022

David Wierichs, Josh Izaac, Cody Wang, and Cedric Yen-Yu Lin. General parameter- shift rules for quantum gradients.Quantum, 6:677, 2022

2022
[30]

Di- agnosing barren plateaus with tools from quantum optimal control.Quantum, 6:824, 2022

Martin Larocca, Piotr Czarnik, Ku- nal Sharma, Gopikrishnan Muraleedharan, Patrick J Coles, and Marco Cerezo. Di- agnosing barren plateaus with tools from quantum optimal control.Quantum, 6:824, 2022

2022
[31]

SIAM, 1990

Frank H Clarke.Optimization and nons- mooth analysis. SIAM, 1990

1990
[32]

Multilayer feedforward net- works are universal approximators.Neural Networks, 2(5):359–366, 1989

Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward net- works are universal approximators.Neural Networks, 2(5):359–366, 1989

1989
[33]

Coles, Lukasz Cincio, Jarrod R

Mart´ ın Larocca, Supanut Thanasilp, Sam- son Wang, Kunal Sharma, Jacob Bia- monte, Patrick J. Coles, Lukasz Cincio, Jarrod R. McClean, Zo¨ e Holmes, and M. Cerezo. Barren plateaus in varia- tional quantum computing.Nature Reviews Physics, 7(4):174–189, March 2025

2025
[34]

Gradient amplifica- tion: An efficient way to train deep neural networks.Big Data Mining and Analytics, 3(3):196–207, 2020

Sunitha Basodi, Chunyan Ji, Haiping Zhang, and Yi Pan. Gradient amplifica- tion: An efficient way to train deep neural networks.Big Data Mining and Analytics, 3(3):196–207, 2020

2020
[35]

Alex Krizhevsky, Ilya Sutskever, and Geof- frey E. Hinton. Imagenet classification with deep convolutional neural networks.Com- mun. ACM, 60(6):84–90, May 2017

2017
[36]

Transfer learning of optimal qaoa parameters in combinato- rial optimization: Ja monta˜ nez-barrera et al.Quantum Information Processing, 24(5):129, 2025

JA Montanez-Barrera, Dennis Willsch, and Kristel Michielsen. Transfer learning of optimal qaoa parameters in combinato- rial optimization: Ja monta˜ nez-barrera et al.Quantum Information Processing, 24(5):129, 2025. 15

2025
[37]

Graph representa- tion learning for parameter transferability in quantum approximate optimization al- gorithm.Quantum Machine Intelligence, 6(2):46, 2024

Jose Falla, Quinn Langfitt, Yuri Alex- eev, and Ilya Safro. Graph representa- tion learning for parameter transferability in quantum approximate optimization al- gorithm.Quantum Machine Intelligence, 6(2):46, 2024

2024
[38]

Bridging classical and quantum with sdp initialized warm-starts for qaoa.ACM Transactions on Quantum Computing, 4(2):1–39, 2023

Reuben Tate, Majid Farhadi, Creston Herold, Greg Mohler, and Swati Gupta. Bridging classical and quantum with sdp initialized warm-starts for qaoa.ACM Transactions on Quantum Computing, 4(2):1–39, 2023

2023
[39]

Towards large-scale quantum opti- mization solvers with few qubits.Nature Communications, 16(1):476, 2025

Marco Sciorilli, Lucas Borges, Taylor L Patti, Diego Garc´ ıa-Mart´ ın, Giancarlo Camilo, Anima Anandkumar, and Leandro Aolita. Towards large-scale quantum opti- mization solvers with few qubits.Nature Communications, 16(1):476, 2025

2025
[40]

MLQAOA: Graph learning accelerated hy- brid quantum-classical multilevel qaoa

Bao Bach, Jose Falla, and Ilya Safro. MLQAOA: Graph learning accelerated hy- brid quantum-classical multilevel qaoa. In2024 IEEE International Conference on Quantum Computing and Engineering (QCE), volume 1, pages 1–12. IEEE, 2024

2024
[41]

On ran- dom graphs i.Publ

Paul Erd˝ os and Alfr´ ed R´ enyi. On ran- dom graphs i.Publ. math. debrecen, 6(290- 297):18, 1959

1959
[42]

PennyLane: Automatic differentiation of hybrid quantum-classical computations

Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M Sohaib Alam, Guillermo Alonso-Linaje, Bharath AkashNarayanan, Ali Asadi, et al. Pennylane: Auto- matic differentiation of hybrid quantum- classical computations.arXiv preprint arXiv:1811.04968, 2018

work page internal anchor Pith review arXiv 2018
[43]

Jones and J

Tyson Jones and Julien Gacon. Efficient cal- culation of gradients in classical simulations of variational quantum algorithms.arXiv preprint arXiv:2009.02823, 2020

work page arXiv 2009
[44]

Springer Science & Business Media, 2012

Martin Gr¨ otschel, L´ aszl´ o Lov´ asz, and Alexander Schrijver.Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012

2012
[45]

Rank-two relaxation heuris- tics for max-cut and other binary quadratic programs.SIAM Journal on Optimization, 12(2):503–521, 2002

Samuel Burer, Renato DC Monteiro, and Yin Zhang. Rank-two relaxation heuris- tics for max-cut and other binary quadratic programs.SIAM Journal on Optimization, 12(2):503–521, 2002

2002
[46]

On the shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979

L´ aszl´ o Lov´ asz. On the shannon capacity of a graph.IEEE Transactions on Information theory, 25(1):1–7, 1979

1979
[47]

Quantum approx- imate optimization algorithm for maxcut: A fermionic view.Physical Review A, 97(2):022304, 2018

Zhihui Wang, Stuart Hadfield, Zhang Jiang, and Eleanor G Rieffel. Quantum approx- imate optimization algorithm for maxcut: A fermionic view.Physical Review A, 97(2):022304, 2018

2018
[48]

Recursive qaoa outperforms the original qaoa for the max-cut problem on complete graphs: E

Eunok Bae and Soojoon Lee. Recursive qaoa outperforms the original qaoa for the max-cut problem on complete graphs: E. bae, s. lee.Quantum Information Process- ing, 23(3):78, 2024

2024
[49]

Springer, 2020

JEAN QUAINTANCE Gallier and Jocelyn Quaintance.Differential geometry and lie groups, volume 12. Springer, 2020

2020
[50]

Uniform finite gen- eration of the rotation group.The Rocky Mountain Journal of Mathematics, 1(4):575–586, 1971

Franklin Lowenthal. Uniform finite gen- eration of the rotation group.The Rocky Mountain Journal of Mathematics, 1(4):575–586, 1971

1971
[51]

arXiv preprint arXiv:1704.00805 , year=

Bolin Gao and Lacra Pavel. On the proper- ties of the softmax function with application in game theory and reinforcement learning. arXiv preprint arXiv:1704.00805, 2017. A More details on Fair Cut Cover Here, we show concretely how to form Fair Cut Cover from Fractional Cut Cover, and we restate the Fractional Cut Cover problem represented by 16 Equation ...

work page arXiv 2017
[52]

Complete graph:ϑ( ¯Kn) =n
[53]

Cycle graph: ϑ( ¯Cn) = 2ifnis even, 1+cos(π/n) cos(π/n) ifnis odd
[54]

Kneser graph:ϑ( ¯KG(n, k)) = n k Based on this optimal solution to the SDP with givent ∗, we can get the best expected value when performing GW hyperplane rounding through the Gaussian distribution. More specif- ically, the expected Fair Cut Cover value from the empirical sampled distribution is SDP(G) = 1 π arccos (t∗) (30) Lemma 9(Theorem 2).For any com...
[55]

Choose one vertexvwith maximal degree for each con- nected subgraph and addZ vZA to the phase separator unitary

IfGis disconnected or ifGis a path/cycle with|V| ≥4,add an ancilla qubitAand addX A to the mixer unitary. Choose one vertexvwith maximal degree for each con- nected subgraph and addZ vZA to the phase separator unitary
[56]

We show that this construction produces a circuit which implicitly represents a connected graph which for|V| ≥4 is not a cycle or a path

IfGis disconnected and|V| ≤4,do (1), then add an additional ancillaBand add ZAZB to the phase separator unitary and addX B to the mixer unitary. We show that this construction produces a circuit which implicitly represents a connected graph which for|V| ≥4 is not a cycle or a path. Lemma 13.Given a graphG= (V, E),letG ′ = (V ′, E′)be the graph representin...
[57]

Non-cycle even-even bipartite graphs

IfGhad 2 or 1 connected subgraphs, then at least 1 of them has a vertex of degree at least 2, else|V| ≤4 andG ′ would have been produced by (2). In all cases whereG ′ ≥4, G ′ contains a vertex of at least 3 and so cannot be a path or a cycle. Given bitstringx∈ {±1} n, aZ 2-symmetric bitstring distributionpwhere∀x, p(x) =p(−x), 24 yield the probability for...
[58]

X e∈E ∂ϑxe(θ) # = 0 (82) Var

As proved from Lemma 13,G ′ representing D-QAOA ansatz will not be Path/Cycle graphs, which we can use arguments from Case 1 to 4 to prove ma-QAOA based onG ′ can capture all Z2-symmetric bitstring distribution In all cases, everyZ 2-symmetric bitstring dis- tributionp, representing by|ψ p⟩ ∈ H + lies in the reachable orbit of the initial state|+⟩ ⊗n. Mor...