pith. sign in

arxiv: 2602.05956 · v3 · pith:JJLGLWOInew · submitted 2026-02-05 · 🪐 quant-ph · math-ph· math.MP· math.OC

Quantum Approximate Optimization of Integer Graph Problems and Surpassing Semidefinite Programming for Max-k-Cut

Anuj Apte , Sami Boulebnane , Yuwei Jin , Sivaprasad Omanakuttan , Michael A. Perlin , Ruslan Shaydulin This is my paper

Pith reviewed 2026-05-22 11:37 UTC · model grok-4.3

classification 🪐 quant-ph math-phmath.MPmath.OC
keywords QAOAMax-k-Cutqudit encodinginteger optimizationsemidefinite programmingapproximation ratiohigh-girth graphsregular graphs
0
0 comments X

The pith

QAOA with qudit encoding outperforms SDP for Max-k-Cut on high-girth regular graphs at depth 4 in specific regimes.

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

The paper extends QAOA from binary to integer optimization by encoding each variable in a qudit and applies it to graph problems such as Max-k-Cut. It derives a general iterative formula for the depth-p expectation value that works on high-girth d-regular graphs of arbitrary size, with cost exponential only in p. Direct evaluation of the formula for p at most 4 identifies concrete regimes where this QAOA beats the Frieze-Jerrum SDP, the strongest classical worst-case guarantee. The authors also introduce a degree-of-saturation heuristic that currently leads on regular graphs but may be overtaken by QAOA at depths up to 20.

Core claim

Encoding integer variables in qudits and deriving an iterative formula for QAOA expectation on high-girth d-regular graphs reveals that, for Max-k-Cut at p less than or equal to 4, the quantum algorithm exceeds the approximation ratio of the Frieze-Jerrum SDP when k equals 3 and degree is at most 10 or when k equals 4 and degree is at most 40.

What carries the argument

Iterative formula for the depth-p QAOA expectation value on high-girth d-regular graphs, which computes performance independently of graph size.

If this is right

  • For Max-3-Cut on d-regular graphs with d at most 10, QAOA at depth 4 exceeds the SDP approximation ratio.
  • For Max-4-Cut on d-regular graphs with d at most 40, QAOA at depth 4 exceeds the SDP approximation ratio.
  • A new degree-of-saturation heuristic achieves strong results on GSet benchmarks with quasi-linear runtime in the number of edges.
  • Numerical evidence indicates QAOA at depth up to 20 may surpass the new heuristic on regular graphs.

Where Pith is reading between the lines

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

  • The qudit approach could be tested on other integer problems such as graph coloring or scheduling to see if similar size-independent formulas appear.
  • If real-world graphs are locally tree-like, the outperformance regimes might translate to practical instances even without perfect high girth.
  • Extending the formula to mixed binary-integer problems could reveal broader classes where shallow QAOA competes with classical methods.

Load-bearing premise

The graphs are high-girth and d-regular, allowing the local tree-like unfolding that makes the iterative formula exact and size-independent.

What would settle it

Direct computation or measurement of the QAOA expectation on a high-girth 3-regular graph for Max-3-Cut at p=4 showing a value below the Frieze-Jerrum ratio would disprove the reported outperformance.

Figures

Figures reproduced from arXiv: 2602.05956 by Anuj Apte, Michael A. Perlin, Ruslan Shaydulin, Sami Boulebnane, Sivaprasad Omanakuttan, Yuwei Jin.

Figure 1
Figure 1. Figure 1: Qudit Quantum Approximate Optimization Algorithm for Max-k-Cut (A) Example input graph for the Max-k-Cut problem and its solution for k = 3. Cuttable edges (between vertices belonging to different sets) are shown as dashed lines, while uncuttable edges (between vertices belonging to the same set) are depicted as solid lines. The dashed box represents the mapping the Max-k-Cut problem to an integer labeling… view at source ↗
Figure 2
Figure 2. Figure 2: Qudit QAOA for Max-k-Cut: Mixer comparison. The performance of QAOA for Max-k-Cut using the mixers considered in this work is studied for k = 3 (A) and k = 4 (B). For k = 3, both the Grover and BKKT mixer are studied; notably, after optimization, the latter exhibits behavior indistinguishable from the Grover mixer, a phenomenon already observed for other discrete constraint satisfaction problems [39]. For … view at source ↗
Figure 3
Figure 3. Figure 3: QAOA for Max-k-Cut at larger circuit depths for the Grover mixer. QAOA performance on Max-k-Cut using the Grover mixer is examined as circuit depth p increases, with optimal parameters studied for k = 3 (p = 7) in (A) and k = 4 (p = 6) in (B). The results show that increasing the QAOA depth leads to improved performance across the range of graph degrees considered. To further explore the relationship betwe… view at source ↗
Figure 4
Figure 4. Figure 4: Comparison of Heuristic and SDP classical solvers. Cut fractions for the Frieze–Jerrum SDP algorithm and the heuristic algorithm are evaluated for k = 3 and k = 4 over varying node counts n and graph degrees. The heuristic algorithm consistently outperforms the SDP solver for all tested values of graph degree. The dashed vertical line indicates the bound for the maximum colorable graph degree, as given in … view at source ↗
Figure 5
Figure 5. Figure 5: Gate-level implementation of the Max-k-Cut on qubit hardware. (A) The circuit that implements one of the terms of the QAOA phaser, e −iγPvi ,vj [30]. This requires in total of 2 × log2 k CNOT gates and a 2 C log2 kX gate, where each C log2 kX gate can be decomposed into log2 k − 1 Toffoli gates. (B) The circuit that implements the Grover mixer which requires a total of 2C log2 k+1X gate when k is a power o… view at source ↗
Figure 6
Figure 6. Figure 6: Performance of qudit QAOA for Max-k-Cut. Cut fractions for the Grover mixer are evaluated as a function of graph degree for k = 6 and k = 8. Consistent with results for k = 3 and k = 4, qudit QAOA outperforms the semidefinite programming (SDP) baseline for these values of k. However, within the circuit depths examined here (up to p = 3), the heuristic algorithm attains higher cut fractions than QAOA. The d… view at source ↗
Figure 7
Figure 7. Figure 7: QAOA for Max-k-Cut at larger circuit depths for the Grover mixer. QAOA performance on Max-k-Cut using the Grover mixer is examined as circuit depth p increases, with optimal parameters studied for k = 5 (p = 5) in (A) and k = 6 (p = 4) in (B). Performance improves with depth across the tested graph degrees. To explore behavior at larger p, we fit the cut fraction to the function in Eq. (58). The fit sugges… view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of classical algorithms for Max-k-Cut across k = 5 to k = 8. Cut fractions achieved by the semidefinite programming (SDP) and heuristic algorithms on random regular graphs are presented for k ∈ {5, 6, 7, 8} across varying graph degrees and node counts n. Similar to k = 3 and k = 4, the heuristic algorithm consistently outperforms the SDP solver for all tested values of graph degree. For a broad … view at source ↗
Figure 9
Figure 9. Figure 9: Shell-based labeling of a tree graph, obtained as the [PITH_FULL_IMAGE:figures/full_fig_p022_9.png] view at source ↗
read the original abstract

Quantum algorithms for binary optimization problems have been the subject of extensive study. However, the application of quantum algorithms to integer optimization problems remains comparatively unexplored. In this paper, we study the Quantum Approximate Optimization Algorithm (QAOA) applied to integer problems on graphs, with each integer variable encoded in a qudit. We derive a general iterative formula for depth-$p$ QAOA expectation on high-girth $d$-regular graphs of arbitrary size. The cost of evaluating the formula is exponential in the QAOA depth $p$ but does not depend on the graph size. Evaluating this formula for Max-$k$-Cut problem for $p\leq 4$, we identify parameter regimes ($k=3$ with degree $d \leq 10$ and $k=4$ with $d \leq 40$) in which QAOA outperforms the Frieze-Jerrum semi-definite programming (SDP) algorithm, which provides the best worst-case guarantee on the approximation ratio. To strengthen the classical baseline, we introduce a new heuristic algorithm based on the degree-of-saturation that achieves strong results on the \texttt{GSet} benchmark with quasi-linear runtime in the number of edges. It empirically outperforms both the Frieze-Jerrum algorithm and shallow-depth QAOA on regular graphs. Nevertheless, we provide numerical evidence that QAOA may overtake this heuristic at depth $p\leq 20$. Our results show that moving beyond binary to integer optimization problems can open up new avenues for quantum advantage.

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.

Referee Report

2 major / 2 minor

Summary. The manuscript derives a general iterative formula for the depth-p QAOA expectation value on high-girth d-regular graphs for integer optimization problems such as Max-k-Cut, with evaluation cost exponential in p but independent of graph size. For p ≤ 4 it identifies regimes (k=3 with d ≤ 10; k=4 with d ≤ 40) in which the QAOA approximation ratio exceeds that of the Frieze-Jerrum SDP. A new degree-of-saturation heuristic is introduced that empirically outperforms both the SDP and shallow QAOA on the GSet benchmark, yet numerical evidence is provided that QAOA may surpass the heuristic for p ≤ 20.

Significance. If the iterative formula and the reported outperformance hold, the work supplies a scalable analytic tool for QAOA on large regular graphs and opens integer-variable encodings as a route toward quantum advantage in graph problems. The size-independent formula and the explicit high-girth assumption are strengths that allow concrete, falsifiable numerical comparisons.

major comments (2)
  1. [Results on Max-k-Cut (evaluation of iterative formula for p≤4)] The central outperformance claim (abstract and results section on Max-k-Cut) compares the QAOA ratios obtained from the iterative formula to the Frieze-Jerrum worst-case guarantee rather than to the SDP value attained on the same high-girth d-regular instances. Because the SDP is a relaxation whose guarantee need not be tight on locally tree-like regular graphs, the actual SDP output on these graphs could exceed its guarantee and thereby reduce or eliminate the reported gap; this comparison must be addressed explicitly, for example by evaluating the SDP on representative high-girth instances or by proving tightness under the girth assumption.
  2. [Discussion of heuristic comparison and higher-depth extrapolation] The claim that QAOA may overtake the new heuristic at p≤20 rests on unspecified numerical evidence whose independence from post-hoc regime selection is unclear. The iterative formula is stated to be general, yet the concrete evaluation procedure, truncation, or extrapolation used to reach p=20 should be detailed so that the independence of the crossing point from the choice of test graphs can be verified.
minor comments (2)
  1. Clarify the precise runtime of the degree-of-saturation heuristic (abstract states 'quasi-linear in the number of edges'); an explicit big-O expression would aid reproducibility.
  2. [Derivation of iterative formula] The notation for the iterative formula (presumably Eq. (X) in the derivation section) should include an explicit statement of the base case and the girth threshold required for the local-tree approximation to hold exactly.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thorough review and valuable suggestions. We address the major comments point by point below. We will make revisions to strengthen the comparisons and provide additional details as requested.

read point-by-point responses

  1. Referee: [Results on Max-k-Cut (evaluation of iterative formula for p≤4)] The central outperformance claim (abstract and results section on Max-k-Cut) compares the QAOA ratios obtained from the iterative formula to the Frieze-Jerrum worst-case guarantee rather than to the SDP value attained on the same high-girth d-regular instances. Because the SDP is a relaxation whose guarantee need not be tight on locally tree-like regular graphs, the actual SDP output on these graphs could exceed its guarantee and thereby reduce or eliminate the reported gap; this comparison must be addressed explicitly, for example by evaluating the SDP on representative high-girth instances or by proving tightness under the girth assumption.

    Authors: We appreciate this important observation. Our comparison to the Frieze-Jerrum guarantee is motivated by the fact that it represents the best known worst-case approximation ratio for the Max-k-Cut problem among classical algorithms. However, we agree that to rigorously demonstrate outperformance on the specific class of high-girth d-regular graphs, it is necessary to compare against the actual SDP performance on those instances. We will revise the manuscript to include numerical evaluations of the SDP on large high-girth d-regular graphs for the relevant parameter regimes (k=3, d≤10 and k=4, d≤40). Since these graphs are locally tree-like, the SDP can be approximated using belief propagation or other scalable methods, and we will report the achieved ratios to show whether the gap persists. This addition will clarify the strength of the QAOA results relative to the SDP on the instances of interest. revision: yes

  2. Referee: [Discussion of heuristic comparison and higher-depth extrapolation] The claim that QAOA may overtake the new heuristic at p≤20 rests on unspecified numerical evidence whose independence from post-hoc regime selection is unclear. The iterative formula is stated to be general, yet the concrete evaluation procedure, truncation, or extrapolation used to reach p=20 should be detailed so that the independence of the crossing point from the choice of test graphs can be verified.

    Authors: We thank the referee for highlighting the need for more transparency in our higher-depth analysis. The numerical evidence for QAOA potentially surpassing the degree-of-saturation heuristic at p ≤ 20 was obtained by evaluating the iterative formula directly for p up to 10 and then extrapolating the trend in the approximation ratio for higher p based on the observed convergence behavior. To address this, we will expand the manuscript with a detailed description of the evaluation procedure, including the specific truncation thresholds used in the iterative computation, the extrapolation method (e.g., fitting to an exponential decay model), and the set of test graphs employed (multiple independent high-girth d-regular graphs with varying d). We will also include plots showing the ratio as a function of p for different graphs to demonstrate that the crossing point is robust and not dependent on particular graph choices. This will be added to the results section and supplementary information for full reproducibility. revision: yes

Circularity Check

0 steps flagged

No circularity: iterative QAOA formula derived independently; outperformance claims rest on explicit evaluation against external guarantees

full rationale

The paper states an explicit assumption of high-girth d-regular graphs when introducing the iterative formula for depth-p QAOA expectation values. This formula is presented as a general derivation whose evaluation cost scales with p but is independent of graph size. The reported regimes where QAOA exceeds the Frieze-Jerrum SDP guarantee for p≤4 are obtained by direct substitution into the derived expression, not by fitting parameters to target data. The new degree-of-saturation heuristic is introduced separately and benchmarked on GSet; the claim that QAOA may surpass it at p≤20 is supported by additional numerical evaluation of the same formula. No step reduces by construction to a self-citation, a fitted input renamed as prediction, or an ansatz smuggled from prior work. The derivation chain is self-contained against the stated assumptions and external SDP bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the high-girth regular-graph assumption required for the iterative formula and on the correctness of the numerical evaluations performed with that formula. No explicit free parameters or invented entities are stated in the abstract.

axioms (1)
  • domain assumption Graphs are high-girth and d-regular
    Invoked when the iterative formula is introduced; performance claims are reported only for this class.

pith-pipeline@v0.9.0 · 5837 in / 1421 out tokens · 39651 ms · 2026-05-22T11:37:52.649443+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

62 extracted references · 62 canonical work pages · 6 internal anchors

  1. [1]

    Frieze-Jerrum Algorithm In this section, we briefly review the algorithm of Ref. [5]. To reformulate the Max-k-Cut objective geo- metrically, we seek a way to encodeklabels as vectors such that the indicator for a cut edge can be expressed in terms of their inner products. The standard simplex provides a natural encoding: it placeskpoints inR k−1 so that ...

    work page

  2. [2]

    Encode labels with vertices of a centered regular simplex

    work page

  3. [3]

    Relax to a SDP over the Gram matrix

    work page

  4. [4]

    Factor the Gram matrix to get vectors

    work page

  5. [5]

    Round with random directions to obtain a solution. The approximation ratio for any graph averaged over the randomized rounding procedure as proven in the orig- inal paper and follow up work are tabulated here [5, 46, 47]: k 2 3 4 5 6 7 8 100 αk 0.878 0.836 0.857 0.876 0.891 0.903 0.926 0.990 Table III. Worst-case approximation ratio for the Frieze- Jerrum...

    work page

  6. [6]

    Given an undi- rected graphG= (V, E)and a fixed number of labels k, Algorithm 1 builds a cutχ:V→ {1,

    Heuristic Algorithm We now describe the heuristic algorithm that outper- forms both SDP and small-depth QAOA. Given an undi- rected graphG= (V, E)and a fixed number of labels k, Algorithm 1 builds a cutχ:V→ {1, . . . , k}by iter- atively selecting an unlabeled vertex and assigning it a label. 10 Algorithm 1:Heuristic Max-k-Cut with Local Improvement Input...

    work page

  7. [7]

    [10] (special casek= 2)

    Analysis of Max-2-Cut QAOA on high-girth regular graphs The analysis of Max-k-Cut QAOA developed in this work generalizes the analysis of Max-Cut QAOA intro- duced in Ref. [10] (special casek= 2). The cost function Eq. (14) can in this case be expressed as the qubit diag- onal Hamiltonian CG = X {u,v}∈E 1−Z uZv 2 .(26) Assuming a(d+ 1)-regular graph of gi...

    work page

  8. [8]

    [10] to Max-k-Cut (with Max-Cut corresponding to special casek= 2)

    Generalization to Max-k-Cut We now introduce our generalization of the analysis of Ref. [10] to Max-k-Cut (with Max-Cut corresponding to special casek= 2). First, we state a general proce- dure (Proposition 1) of time complexityO pk4p+4 and space complexityO k2p+2 for evaluating the QAOA expectation for a broad class of objectives defined on graphs, gener...

    work page 2000

  9. [9]

    Abbas, A

    A. Abbas, A. Ambainis, B. Augustino, A. Bärtschi, H. Buhrman, C. Coffrin, G. Cortiana, V. Dunjko, D. J. Egger, B. G. Elmegreen, N. Franco, F. Fratini, B. Fuller, J. Gacon, C. Gonciulea, S. Gribling, S. Gupta, S. Had- field, R. Heese, G. Kircher, T. Kleinert, T. Koch, G. Ko- rpas, S. Lenk, J. Marecek, V. Markov, G. Mazzola, S. Mensa, N. Mohseni, G. Nannici...

    work page 2024

  10. [10]

    Ebadi, A

    S. Ebadi, A. Keesling, M. Cain, T. T. Wang, H. Levine, D. Bluvstein, G. Semeghini, A. Omran, J.-G. Liu, R. Samajdar, X.-Z. Luo, B. Nash, X. Gao, B. Barak, E. Farhi, S. Sachdev, N. Gemelke, L. Zhou, S. Choi, H.Pichler, S.-T.Wang, M.Greiner, V.Vuletić,andM.D. Lukin, Quantum optimization of maximum independent set using rydberg atom arrays, Science376, 1209–...

    work page 2022

  11. [11]

    Kellerer, U

    H. Kellerer, U. Pferschy, and D. Pisinger, Knapsack Problems (Springer Berlin Heidelberg, 2004)

    work page 2004

  12. [12]

    Pistoia, and Y

    D.Herman, C.Googin, X.Liu, Y.Sun, A.Galda, I.Safro, M. Pistoia, and Y. Alexeev, Quantum computing for fi- nance, Nature Reviews Physics5, 450 (2023)

    work page 2023

  13. [13]

    Frieze and M

    A. Frieze and M. Jerrum, Improved approximation al- gorithms for max-k-cut and max bisection, Algorithmica 18, 67–81 (1997)

    work page 1997

  14. [14]

    C. H. Papadimitriou and M. Yannakakis, Optimization, approximation, and complexity classes, Journal of Com- puter and System Sciences43, 425–440 (1991)

    work page 1991

  15. [15]

    M. X. Goemans and D. P. Williamson, Improved approx- imation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM42, 1115–1145 (1995)

    work page 1995

  16. [16]

    Quantum Optimization

    T. Hogg and D. Portnov, Quantum optimization (2000), arXiv:quant-ph/0006090 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2000

  17. [17]

    A Quantum Approximate Optimization Algorithm

    E. Farhi, J. Goldstone, and S. Gutmann, A quan- tum approximate optimization algorithm (2014), arXiv:1411.4028 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2014

  18. [18]

    Basso, E

    J. Basso, E. Farhi, K. Marwaha, B. Villalonga, and L. Zhou, The Quantum Approximate Optimization Al- gorithm at High Depth for MaxCut on Large-Girth Reg- ular Graphs and the Sherrington-Kirkpatrick Model, in TQC 2022, Leibniz International Proceedings in Infor- matics (LIPIcs), Vol. 232, edited by F. Le Gall and T. Morimae (Schloss Dagstuhl – Leibniz-Zent...

    work page 2022

  19. [19]

    Z. Wang, S. Hadfield, Z. Jiang, and E. G. Rieffel, Quan- tum approximate optimization algorithm for maxcut: A fermionic view, Physical Review A97, 10.1103/phys- reva.97.022304 (2018)

    work page doi:10.1103/phys- 2018

  20. [20]

    Farhi, S

    E. Farhi, S. Gutmann, D. Ranard, and B. Villalonga, Lower bounding the maxcut of high girth 3-regular graphs using the qaoa (2025), arXiv:2503.12789

    work page arXiv 2025

  21. [21]

    Marwaha, Local classical max-cut algorithm outper- formsp= 2qaoa on high-girth regular graphs, Quantum 5, 437 (2021)

    K. Marwaha, Local classical max-cut algorithm outper- formsp= 2qaoa on high-girth regular graphs, Quantum 5, 437 (2021)

    work page 2021

  22. [22]

    Shaydulin and M

    R. Shaydulin and M. Pistoia, Qaoawithn·p≥200, in 2023 IEEE QCE, Vol. 01 (2023) pp. 1074–1077

    work page 2023

  23. [23]

    Z. He, R. Raymond, R. Shaydulin, and M. Pistoia, Non- variational quantum random access optimization with al- ternating operator ansatz, Scientific Reports15, 29191 (2025). 15

    work page 2025

  24. [24]

    Borregaard, M

    M. Medvidović and G. Carleo, Classical variational sim- ulation of the quantum approximate optimization algo- rithm, npj Quantum Information7, 10.1038/s41534-021- 00440-z (2021)

    work page doi:10.1038/s41534-021- 2021

  25. [25]

    Bravyi, A

    S. Bravyi, A. Kliesch, R. Koenig, and E. Tang, Hybrid quantum-classical algorithms for approximate graph col- oring, Quantum6, 678 (2022)

    work page 2022

  26. [26]

    Newman, Complex semidefi- nite programming and max-k-cut, in Proceedings of the Symposium on Simplicity in Algorithms (Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    A. Newman, Complex semidefi- nite programming and max-k-cut, in Proceedings of the Symposium on Simplicity in Algorithms (Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

    work page

  27. [27]

    creative Commons Attribution 3.0 Unported license

    work page

  28. [28]

    Farhi, J

    E. Farhi, J. Goldstone, S. Gutmann, and L. Zhou, The quantum approximate optimization algorithm and the sherrington-kirkpatrick model at infinite size, Quantum 6, 759 (2022)

    work page 2022

  29. [29]

    Generalized quantum signal processing,

    S. Boulebnane and A. Montanaro, Solving boolean sat- isfiability problems with the quantum approximate opti- mization algorithm, PRX Quantum5, 10.1103/prxquan- tum.5.030348 (2024)

    work page doi:10.1103/prxquan- 2024

  30. [30]

    Basso, D

    J. Basso, D. Gamarnik, S. Mei, and L. Zhou, Perfor- mance and limitations of the qaoa at constant levels on large sparse hypergraphs and spin glass models, in 2022 IEEE FOCS (IEEE, 2022) p. 335–343

    work page 2022

  31. [31]

    L. Zhou, J. Basso, and S. Mei, Statistical estimation in the spiked tensor model via the quantum approximate optimization algorithm (2024), arXiv:2402.19456

    work page arXiv 2024

  32. [32]

    A Multiple Search Operator Heuristic for the Max-k-cut Problem

    F. Ma and J.-K. Hao, A multiple search operator heuris- tic for the max-k-cut problem (2015), arXiv:1510.09156 [cs.DM]

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  33. [33]

    J. R. Weggemans, A. Urech, A. Rausch, R. Spreeuw, R. Boucherie, F. Schreck, K. Schoutens, J. Minář, and F. Speelman, Solving correlation clustering with qaoa and a rydberg qudit system: a full-stack approach, Quan- tum6, 687 (2022)

    work page 2022

  34. [34]

    Bartschi and S

    A. Bartschi and S. Eidenbenz, Grover mix- ers for qaoa: Shifting complexity from mixer design to state preparation, in 2020 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, 2020) p. 72–82

    work page 2020

  35. [35]

    Golden, A

    J. Golden, A. Bärtschi, D. O’Malley, and S. Eidenbenz, Numerical evidence for exponen- tial speed-up of qaoa over unstructured search for approximate constrained optimization, in 2023 IEEE International Conference on Quantum Computing and Engineering (QCE) (IEEE, 2023) p. 496–505

    work page 2023

  36. [36]

    Barahona, M

    F. Barahona, M. Grötschel, M. Jünger, and G. Reinelt, An application of combinatorial optimization to statis- tical physics and circuit layout design, Operations Re- search36, 493–513 (1988)

    work page 1988

  37. [37]

    Boykov and M.-P

    Y. Boykov and M.-P. Jolly, Interactive graph cuts for optimal boundary &; region segmentation of objects in n- dimages,in ICCV 2001,ICCV-01, Vol.1(IEEEComput. Soc) p. 105–112

    work page 2001

  38. [38]

    Tsvelikhovskiy, I

    B. Tsvelikhovskiy, I. Safro, and Y. Alexeev, Equivari- ant quantum approximate optimization algorithm, IEEE Transactions on Quantum Engineering (2026)

    work page 2026

  39. [39]

    F. G. Fuchs, H. Ø. Kolden, N. H. Aase, and G. Sartor, Efficient encoding of the weighted max k-cut on a quan- tum computer using qaoa, SN Computer Science2, 89 (2021)

    work page 2021

  40. [40]

    F. G. Fuchs, R. Pariente Bassa, and F. Lien, Encod- ings of the weighted max k-cut problem on qubit sys- tems, Frontiers in Quantum Science and Technology4, 10.3389/frqst.2025.1636042 (2025)

    work page doi:10.3389/frqst.2025.1636042 2025

  41. [41]

    Vandenberghe and S

    L. Vandenberghe and S. Boyd, Semidefinite program- ming, SIAM Review38, 49–95 (1996)

    work page 1996

  42. [42]

    Ma and J.-K

    F. Ma and J.-K. Hao, A multiple search operator heuris- tic for the max-k-cut problem, Annals of Operations Re- search248, 365–403 (2016)

    work page 2016

  43. [43]

    Exploiting Low-Rank Structure in Max-K-Cut Problems

    R. Stevens, F. Liao, B. Su, J. Li, and A. Kyrillidis, Exploiting low-rank structure in max-k-cut problems (2026), arXiv:2602.20376 [cs.DS]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  44. [44]

    Brélaz, New methods to color the vertices of a graph, Communications of the ACM22, 251–256 (1979)

    D. Brélaz, New methods to color the vertices of a graph, Communications of the ACM22, 251–256 (1979)

    work page 1979

  45. [45]

    Kemkes, X

    G. Kemkes, X. Pérez-Giménez, and N. Wormald, On the chromatic number of random d-regular graphs, Advances in Mathematics223, 300–328 (2010)

    work page 2010

  46. [46]

    T. A. Davis and Y. Hu, The university of florida sparse matrix collection, ACM Transactions on Mathematical Software38, 1–25 (2011)

    work page 2011

  47. [47]

    J. Gui, Z. Jiang, and S. Gao, Pci planning based on bi- nary quadratic programming in lte/lte-a networks, IEEE Access7, 203–214 (2019)

    work page 2019

  48. [48]

    Boulebnane, X

    S. Boulebnane, X. Lucas, A. Meyder, S. Adaszewski, and A. Montanaro, Peptide conformational sampling us- ing the quantum approximate optimization algorithm, npj Quantum Information9, 10.1038/s41534-023-00733- 5 (2023)

    work page doi:10.1038/s41534-023-00733- 2023

  49. [49]

    Zhou, S.-T

    L. Zhou, S.-T. Wang, S. Choi, H. Pichler, and M. D. Lukin, Quantum approximate optimization algorithm: Performance, mechanism, and implementation on near- term devices, Phys. Rev. X10, 021067 (2020)

    work page 2020

  50. [50]

    Lykov, R

    D. Lykov, R. Shaydulin, Y. Sun, Y. Alexeev, and M. Pistoia, Fast simulation of high-depth qaoa cir- cuits, in Proceedings of the SC ’23 Workshop, SC-W 2023 (ACM, 2023) p. 1443–1451

    work page 2023

  51. [51]

    A. Apte, S. H. Sureshbabu, R. Shaydulin, S. Boulebnane, Z. He, D. Herman, J. Sud, and M. Pistoia, Iterative in- terpolationschedulesforquantumapproximateoptimiza- tion algorithm, arXiv preprint arXiv:2504.01694 (2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  52. [52]

    Virtanen, R

    P. Virtanen, R. Gommers, T. E. Oliphant, M. Haber- land, T. Reddy, D. Cournapeau, E. Burovski, P. Pe- terson, W. Weckesser, J. Bright, S. J. van der Walt, M. Brett, J. Wilson, K. J. Millman, N. Mayorov, A. R. J. Nelson, E. Jones, R. Kern, E. Larson, C. J. Carey, İ. Po- lat, Y. Feng, E. W. Moore, J. VanderPlas, D. Laxalde, J. Perktold, R. Cimrman, I. Henri...

    work page 2020

  53. [53]

    Spin-Boson Mapping of the Quantum Approximate Optimization Algorithm

    S. Boulebnane, A. Khan, M. Liu, J. Larson, D. Herman, R. Shaydulin, and M. Pistoia, Evidence that the quan- tum approximate optimization algorithm optimizes the sherrington-kirkpatrick model efficiently in the average case (2025), arXiv:2505.07929 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  54. [54]

    J. K. Thompson, O. Parekh, and K. Marwaha, An explicit vector algorithm for high-girth max- cut, in Symposium on Simplicity in Algorithms (SOSA) (SIAM, 2022) pp. 238–246

    work page 2022

  55. [55]

    de Klerk, D

    E. de Klerk, D. V. Pasechnik, and J. P. Warners, On approximate graph colouring and max-k-cut algorithms based on theθ-function, Journal of Combinatorial Opti- mization8, 267 (2004)

    work page 2004

  56. [56]

    M. F. Anjos and J. Neto, A class of spectral bounds for max k-cut, Discrete Applied Mathematics279, 12 16 (2020)

    work page 2020

  57. [57]

    Fino and Algazi, Unified matrix treatment of the fast walsh-hadamard transform, IEEE Transactions on Com- putersC-25, 1142 (1976)

    work page 1976

  58. [58]

    Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections.arXiv preprint arXiv:2211.15465, 2022

    D. Litinski and N. Nickerson, Active volume: An ar- chitecture for efficient fault-tolerant quantum comput- ers with limited non-local connections, arXiv preprint arXiv:2211.15465 (2022)

    work page arXiv 2022

  59. [59]

    Kemkes, X

    G. Kemkes, X. Pérez-Giménez, and N. Wormald, On the chromatic number of random d-regular graphs, Advances in Mathematics223, 300 (2010)

    work page 2010

  60. [60]

    Linial and M

    N. Linial and M. Simkin, A randomized construction of high girth regular graphs (2020), arXiv:1911.09640 [math.CO]

    work page arXiv 2020

  61. [61]

    R. M. Damerell, On moore graphs, Mathematical Pro- ceedings of the Cambridge Philosophical Society74, 227–236 (1973)

    work page 1973

  62. [62]

    shell-based

    A. A. Hagberg, D. A. Schult, and P. J. Swart, Exploring network structure, dy- namics, and function using networkx, in Proceedings of the 7th Python in Science Conference, edited by G. Varoquaux, T. Vaught, and J. Millman (Pasadena, CA USA, 2008) pp. 11 – 15. DISCLAIMER This paper was prepared for informational purposes by the Global Technology Applied Re...

    work page 2008