PaperlayerView exact revision on arXiv

Source-linked AI summary

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

arXiv:2602.05956v3quant-phmath-phmath.MPmath.OC

TL;DR

Integer optimization has received less quantum-algorithm study than binary optimization, while Max-k-Cut is hard and its best known worst-case approximation guarantee comes from Frieze–Jerrum SDP. This paper develops an iterative qudit-QAOA expectation formula for high-girth graphs and tests Max-k-Cut performance. At p = 4, QAOA outperforms SDP in specified degree regimes, while a DSatur-inspired heuristic beats shallow QAOA and SDP in tested cases; deeper QAOA may overtake that heuristic.

  • Problem

    Max-k-Cut is APX-hard, and Frieze–Jerrum SDP provides its highest provable worst-case approximation ratio; QAOA analysis for integer-valued graph problems remains comparatively limited.

    Source: §I · pp. 1–2

  • Method

    The paper derives an iterative formula for qudit-QAOA expectations on high-girth graphs, independent of graph size, and uses it to optimize parameters and evaluate Max-k-Cut.

    Source: §I · p. 2, §III · p. 8

  • Results

    At p = 4, QAOA surpasses Frieze–Jerrum SDP for k = 3 with d ≤10 and k = 4 with d ≤40, while the DSatur-inspired heuristic beats SDP and p = 4 QAOA on tested instances.

    Source: §III · p. 8

  • Takeaways & Limitations

    Qudit QAOA may surpass the DSatur-inspired heuristic at modest depths on high-girth regular graphs, suggesting opportunities for quantum advantage in integer optimization.

    Source: §I · p. 2, §III · p. 8

    The expectation formula applies to high-girth graphs and has evaluation cost exponential in QAOA depth p.

    Source: §III · p. 8

Abstract

from arXiv · show

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.

I. INTRODUCTION

Integer optimization has received less attention in quantum optimization than binary problems. The paper develops a high-girth QAOA analysis for Max-k-Cut and compares its performance with classical algorithms.

I. INTRODUCTION

  • Integer-valued problems are less studied than binary optimization, and Max-k-Cut is APX-hard; Frieze–Jerrum SDP has the highest provable worst-case approximation ratio described here.QAOA has been studied extensively for Max-2-Cut, while prior Max-k-Cut work includes recursive QAOA on graphs up to 300 vertices.Source: §I · p. 1
  • The authors derive an instance-independent iterative formula for qudit QAOA expectations on high-girth graphs, covering arbitrary k, degree d, and depth p when girth is at least 2p + 2.The formula supports parameter optimization across graphs of a given degree.Source: §I · p. 2
  • At p = 4, QAOA surpasses the empirical average-case performance of Frieze–Jerrum SDP for k = 3 with d ≤ 10 and k = 4 with d ≤ 40.These regimes are reported for random d-regular graphs.Source: §I · p. 2
  • The degree-of-saturation-inspired heuristic runs in O(|E| log |V|) time and empirically outperforms SDP and shallow-depth QAOA; extrapolation suggests QAOA may overtake it at p ≤ 20.The extrapolation concerns high-girth regular graphs.Source: §I · p. 2
  • On GSet, the heuristic achieves results within ten percent of the state-of-the-art multi-operator heuristic [23], with an average speedup of nearly 17,000-fold.The reported tests include nonregular graphs with positive and negative edge weights.Source: §I · p. 2

A. Quantum Approximate Optimization Algorithm (QAOA) on Qudits

  • Each integer label maps to a qudit basis state, while QAOA alternates cost-encoding phasers and solution-space mixers, including transverse-field and BKKT choices.The paper also considers a Grover mixer; the transverse-field mixer assumes k is a power of two and binary encoding into log2 k qubits.Source: A. Quantum Approximate Optimization… · p. 2, Figure 1 · p. 3

B. Qudit QAOA Expectation Values at High Girth

The paper extends a light-cone and iteration-based QAOA analysis to qudits, deriving edge-expectation evaluations for high-girth graphs. Locality and cost-function symmetries make these evaluations independent of graph size and enable more efficient computation under translation-invariant edge costs.

B. Qudit QAOA Expectation Values at High Girth

  • When girth is at least 2p + 2, QAOA locality confines an edge expectation to a tree neighborhood, allowing its evaluation without dependence on graph size.The relevant neighborhood has depth at most 2p + 1; tree tensor network contractions provide the evaluation procedure.Source: B. Qudit QAOA Expectation Values at… · pp. 3–4
  • The analysis extends the high-girth framework to qudit QAOA for arbitrary k, degree d, and depth p, under a girth condition.The cost function is assumed edge-independent, the initial state is a product state, and the mixer factors over qudits.Source: B. Qudit QAOA Expectation Values at… · p. 4
  • For edge costs translation-invariant in Zk, exploiting symmetry and efficient Hadamard-transform evaluation reduces the computational cost of the iterative procedure.Translation invariance means the edge penalty and loss depend only on the difference between endpoint labels.Source: B. Qudit QAOA Expectation Values at… · p. 4
  • The procedure evaluates local QAOA expectations for a broad class of integer-valued graph problems, providing a basis for analyzing performance on large regular graphs.The expectation is independent of the edge when the edge cost is independent of the edge.Source: B. Qudit QAOA Expectation Values at… · p. 4

C. QAOA for Max-k-Cut

The paper defines Max-k-Cut and compares QAOA with classical algorithms, including a new DSatur-inspired heuristic. On the studied high-girth regular graphs, shallow QAOA can outperform SDP in specified regimes, while the heuristic outperforms shallow QAOA; greater-depth extrapolations suggest a possible crossover but require direct validation.

C. QAOA for Max-k-Cut

  • Max-k-Cut seeks a vertex partition into k subsets maximizing edges between different subsets; a uniformly random assignment has expected approximation ratio at least 1 − 1/k.The paper focuses on k ≤ 8 and compares against the Frieze–Jerrum SDP algorithm, which provides the best known worst-case guarantees for general k.Source: C. QAOA for Max-k-Cut · p. 5, D. Classical Algorithms for Max-k-Cut · p. 6

D. Classical Algorithms for Max-k-Cut

  • The DSatur-inspired heuristic selects vertices by saturation degree, assigns labels to maximize immediate crossing edges, and then accepts only cut-improving relabelings.Its runtime is O(|E| log |V |), and it handles positive and negative edge weights.Source: D. Classical Algorithms for Max-k-Cut · p. 6
  • On GSet, the heuristic produces cuts within 10% of MOH at about 17,000× faster average runtime, and cuts 25% larger than Rank-1 at about 100× speedup.The GSet benchmark includes 71 instances with 800 to 20,000 vertices and weighted as well as unweighted graphs.Source: D. Classical Algorithms for Max-k-Cut · p. 6

E. Comparing QAOA with Classical Algorithms

  • QAOA parameters are optimized for each fixed k, d, p, and mixer using the large-girth edge-local expectation, with the previous depth's parameters used to initialize the next.For larger-depth tests, optimization reached p = 7 for k = 3 and p = 6 for k = 4; evaluation beyond these depths was intractable with current techniques.Source: E. Comparing QAOA with Classical… · p. 6
  • QAOA beats SDP for k = 3 when d ≤ 10 and across the shown degrees for k = 4, but the classical heuristic outperforms shallow QAOA.The figure reports results for circuit depths up to p = 4.Source: E. Comparing QAOA with Classical… · p. 6, Figure 2 · p. 7
  • For k = 3 and k = 4, fitted depth trends suggest a finite threshold beyond which QAOA may surpass the heuristic, but direct simulations at larger depths are needed to validate the extrapolation.The fit models performance as F(p) = m/(p^a + c) + b.Source: E. Comparing QAOA with Classical… · p. 8
  • For k = 5, 6, 7, and 8, the authors report trends similar to those for k = 3 and k = 4, and characterize the evidence as suggesting possible QAOA advantage on tested instance families.This conclusion is scoped to the tested Max-k-Cut instance families.Source: E. Comparing QAOA with Classical… · p. 8

III. DISCUSSION AND CONCLUSION

The paper develops qudit QAOA for Max-k-Cut, compares it with classical algorithms, and identifies both shallow-depth gains over SDP and a stronger heuristic baseline. Its projected crossover with that heuristic remains tentative.

III. DISCUSSION AND CONCLUSION

  • For Max-k-Cut on high-girth graphs, the iterative formula evaluates depth-p edge expectations in O(pk4p+4) time independent of graph size, reduced to O(p2k2p+2 log k) for translation-invariant costs.The reduced cost uses Hadamard transforms.Source: §III · p. 8
  • At p = 4, QAOA outperforms the Frieze-Jerrum SDP algorithm for k = 3 with d ≤10 and k = 4 with d ≤40 on random d-regular graphs.The authors describe these as rigorous comparisons against the best known worst-case classical guarantees for an integer combinatorial optimization problem at scale.Source: §III · p. 8
  • The DSatur-inspired heuristic empirically surpasses both SDP and p = 4 QAOA across tested instances, while its GSet cuts are within 10% of MOH and nearly 17,000 times faster on average.The heuristic's stated runtime is quadratic in the number of graph edges.Source: §III · p. 8
  • An extrapolation from p = 7 for k = 3 and p = 6 for k = 4 estimates that QAOA may overtake the heuristic near p ≲20, but direct verification remains beyond current methods.The authors cite exponential runtime scaling as the reason larger-depth verification is out of reach.Source: §III · p. 8
  • A proposed high-girth Max-k-Cut vector algorithm would provide a provable classical baseline for QAOA comparisons on random d-regular graphs.The proposed generalization is analogous to Frieze-Jerrum's extension of Goemans-Williamson beyond k = 2.Source: §III · p. 8

A. Classical Algorithms for Max-k-Cut

  • Random d-regular graphs are asymptotically almost surely k-colorable when d ≤2(k −1) log(k −1), but this does not guarantee a polynomial-time algorithm can find a perfect coloring.A perfect coloring makes the optimal Max-k-Cut fraction unity.Source: A. Classical Algorithms for Max-k-Cut · p. 8, Table II · p. 8

1. Frieze-Jerrum Algorithm

  • The Frieze-Jerrum guarantee is a worst-case, graph-agnostic lower bound, unlike the empirical randomized-rounding cut fractions used for comparisons on random d-regular graphs.Its SDP bottleneck requires O(n2) memory and often scales as Ω(n3) in practice, making graphs with more than a few thousand vertices challenging.Source: §1 · p. 9

2. Heuristic Algorithm

The heuristic combines DSatur-style vertex ordering with greedy label assignment and local improvement. It performs strongly on random regular graphs and GSet, with runtime depending on the number of improvement rounds.

repeat

  • The construction phase selects the unlabeled vertex with the most distinct neighbor labels, breaking ties by total incident edge weight.This weighted saturation ordering is borrowed from DSatur graph coloring.Source: then · p. 10

then

  • For each selected vertex, the greedy label maximizes incident cut weight against already-labeled neighbors; ties favor the label with the smallest neighbor-weight sum.The algorithm then performs single-vertex relabelings that strictly improve the global cut until none remain.Source: then · p. 10
  • For connected graphs with constant k, construction costs O(|E| log |V |), while r local-improvement rounds cost O(r|E|), giving O(|E| log |V |) overall when r = O(log |V |).The algorithm uses O(|V |) additional space.Source: then · p. 10
  • On random regular graphs, the heuristic outperforms Frieze-Jerrum SDP in every tested case and finds the optimum for most tested degrees below the colorability threshold.The benchmark results are shown in Figures 4 and 8.Source: then · pp. 10–11
  • On GSet, the heuristic achieves cuts within 10% of MOH while running four orders of magnitude faster on average.The reported evaluation covers all 71 instances and uses a single-threaded implementation.Source: then · p. 11

B. Analysis of Max-k-Cut QAOA on high-girth regular graphs

The high-girth analysis reduces Max-2-Cut QAOA expectation evaluation to a tree-based calculation using locality and regular-graph symmetry. The method's numerical depth is limited by tensor-network bond-dimension growth.

1. Analysis of Max-2-Cut QAOA on high-girth regular graphs

  • For a (d + 1)-regular graph of girth at least 2p + 2, every edge has an isomorphic treelike QAOA neighborhood, so its expectation can be evaluated on a regular tree.The tree tensor network has O(dp) sites, but regular-tree symmetries allow contractions with degree-independent cost and a single site tensor in memory.Source: §1 · p. 11
  • The tensor-network bond dimension O(4p) limits numerical applicability, with the stated time complexity O(p16p) and memory footprint O(4p).The text notes a large-d reduction when only the leading-order contribution in 1/d is required.Source: §1 · p. 11

2. Generalization to Max-k-Cut

The analysis extends iterative QAOA expectation evaluation to Max-k-Cut and translation-invariant objectives on qudits. A Hadamard-transform-based procedure improves the computation of matrix-vector products used in the evaluation.

Generalization to Max-k-Cut

  • The procedure generalizes earlier QAOA expectation methods to Max-k-Cut and broader graph objectives, with Max-Cut recovered at k = 2.The text identifies the earlier results as Ref. and the quadratic improvement as consistent with Ref. [12] at k = 2.Source: §2 · pp. 11–12
  • For translation-invariant objectives in Z_k, the Hadamard transform enables a quadratically improved procedure for evaluating QAOA expectations, including Max-k-Cut.Translation invariance means the edge function depends only on (x − y) mod k.Source: §2 · pp. 11–12
  • The edge expectation procedure applies to p-layer QAOA on (d + 1)-regular graphs with girth at least 2p + 2.The stated proposition allows an arbitrary edge function; the improved procedure further assumes translation-invariant edge costs.Source: §2 · pp. 11, 14
  • The iterative derivation uses that an edge expectation depends only on a subgraph of depth 2p + 1.The tree depth grows by one with each application of the phaser.Source: §2 · p. 12
  • The improved expectation-evaluation procedure has complexity independent of graph degree d.The cited passages describe the Hadamard-transform improvement but do not give a complete complexity expression.Source: §2 · p. 12

DISCLAIMER

The paper is informational and disclaims investment advice, recommendations, and liability for the document’s contents.

DISCLAIMER

  • The paper was prepared for informational purposes by JPMorgan Chase’s Global Technology Applied Research center.The disclaimer says it is not a product of the Research Department or its affiliates.Source: DISCLAIMER · p. 16
  • The document is not investment research or investment advice, nor a recommendation or offer concerning financial products or services.Source: DISCLAIMER · p. 16
  • JPMorgan Chase and its affiliates disclaim representations, warranties, and liability regarding the document, including its completeness, accuracy, and reliability.Source: DISCLAIMER · p. 16

V. GATE-LEVEL IMPLEMENTATION OF MAX-k-CUT ON QUBIT HARDWARE

The implementation encodes each vertex label in log2 k qubits when k is a power of two. The paper describes qubit circuits for the Max-k-Cut phaser and Grover mixer, with logarithmic gate overhead as k increases.

V. GATE-LEVEL IMPLEMENTATION OF MAX-k-CUT ON QUBIT HARDWARE

  • Each vertex label is represented by a qudit encoded in log2 k qubits when k is a power of two.This maps the k possible labels directly to quantum basis states.Source: §V · p. 17
  • The Max-k-Cut phaser uses 2 log2 k CX gates and two multi-controlled X gates, with each multi-controlled gate decomposable into log2 k − 1 Toffoli gates.Temporary-AND-compute-and-uncompute gates can further reduce the required gates by half.Source: §V · p. 17, Figure 5 · p. 17
  • The Grover mixer is implemented using Hadamard gates and a multi-qubit Toffoli gate, decomposable into log2 k standard Toffoli gates.The transverse-field mixer is equivalent to applying the standard qubit mixer independently to each encoded qubit; the BKKT mixer has large qubit-hardware overhead.Source: §V · p. 17, Figure 5 · p. 17

VI. RESULTS FOR OTHER VALUES OF k

For k = 5 to 8, the heuristic outperforms the SDP algorithm and reaches cut fraction 1 over a broad range of degrees. At the examined depths for k = 6 and 8, QAOA also beats SDP, while the heuristic remains ahead; fitted depth trends suggest a possible later crossover that needs direct validation.

VI. RESULTS FOR OTHER VALUES OF k

  • For k = 6 and 8, qudit QAOA beats the SDP baseline, but the heuristic achieves higher cut fractions at the tested depths up to p = 3.The result is reported for the Grover mixer.Source: §VI · p. 18, Figure 6 · p. 18
  • For k = 5 at p = 5 and k = 6 at p = 4, fitted depth trends suggest a finite threshold beyond which QAOA surpasses the heuristic.The optimal parameters were studied only to those simulated depths; claims beyond them rely on extrapolation and need direct validation with larger-depth circuit simulation and parameter optimization.Source: §VI · pp. 18–19, Figure 7 · p. 18
  • For k = 5 to 8, the heuristic outperforms Frieze–Jerrum SDP across tested degrees and attains cut fraction 1 for a broad range of degrees.The captioned comparison covers random regular graphs across node counts and degrees.Source: Figure 8 · p. 19, §VI · p. 19
  • The Frieze–Jerrum mean cut fraction varies little across tested girths at a fixed degree for the evaluated graph sizes.At n = 1000, generating high-degree, high-girth graphs becomes increasingly difficult because of the Moore bound.Source: Table IV · p. 19, §VI · p. 20

VII. HEURISTIC DSATUR ALGORITHM ON WEIGHTED GRAPHS

The section presents a weighted-graph DSatur heuristic that constructs and locally improves Max-k-Cut assignments. Its GSet comparison is identified, but the supplied table text does not provide readable results.

VII. HEURISTIC DSATUR ALGORITHM ON WEIGHTED GRAPHS

  • The implementation supports edge weights, defaults missing weights to 1, and uses a heap-based priority queue with NetworkX graph processing.The authors identify heapq and NetworkX as implementation components.Source: §VII · p. 20
  • The heuristic selects unassigned vertices by saturation and total incident weight, then assigns a label maximizing the weight of edges cut to already assigned vertices.Its priority counts the distinct labels among neighbors with positive accumulated weight, with total incident absolute weight as the secondary priority.Source: §VII · p. 20
  • An optional improvement pass changes a vertex’s label whenever doing so strictly increases its cut contribution against its neighbors.The code updates affected neighbors’ label-weight totals after each change and repeats passes until no change occurs.Source: §VII · p. 20
  • The section presents a Max-3-Cut comparison on the GSet benchmark, but the supplied table passages do not expose results that support a winner or numerical comparison.The caption names MOH, Rank-1, and Greedy comparison values and notes that time is in seconds; the visible table text provides only headings.Source: Table V · p. 21, §VII · p. 21

VIII. COMPUTATION OF QAOA EDGE EXPECTATION VALUES

This appendix proves the edge-expectation procedure by reducing high-girth graph QAOA to a depth-p tree neighborhood and expanding the expectation as a spin path integral. It derives tree-based evaluation and a simplified recurrence under regularity and uniform-cost assumptions.

VIII. COMPUTATION OF QAOA EDGE EXPECTATION VALUES

  • A high-girth graph edge expectation reduces to the same expectation on the edge’s depth-p tree neighborhood, which is labeled in shells around its endpoints.The derivation generalizes the method of Ref. from qubits to qudits and permits product-operator mixers beyond the transverse-field mixer.Source: §VIII · p. 22, Figure 9 · p. 22
  • The expectation is expanded as a spin path integral by inserting completeness relations before each QAOA layer and summing over computational-basis states.Positive and negative layer indices represent the bra and ket paths, respectively.Source: §VIII · pp. 22–23
  • For a general tree, the edge expectation becomes a two-body Gibbs partition function whose factors can be evaluated by belief propagation.The procedure splits the tree at the target edge and contracts subtrees into recursively defined tensors, proceeding from the outer shells inward.Source: §VIII · pp. 24–26
  • The general tree procedure supports diagonal observables and potentially non-uniform edge costs on trees of arbitrary geometry.The appendix states that the procedure evaluates an edge expectation under these conditions.Source: §VIII · p. 26
  • With uniform edge costs and a (d+1)-regular tree, the recursively defined tensors depend only on depth, reducing the stated complexity by replacing |V| = O(d^p) with p.The regular-tree specialization is identified as the special case treated in Ref..Source: §VIII · pp. 26–27

IX. MAX-k-CUT QAOA ON HIGH-GIRTH REGULAR GRAPHS

This section gives an efficient matrix-vector procedure for a structured matrix indexed by k-ary ditstrings. It uses Hadamard transforms and element-wise multiplication to reduce computation and memory requirements.

IX. MAX-k-CUT QAOA ON HIGH-GIRTH REGULAR GRAPHS

  • The method represents the matrix through its Hadamard transform, enabling the transform-based product procedure for vectors indexed by k-ary ditstrings.The lemma states the procedure for a matrix with entries indexed by ditstrings.Source: §IX · p. 28
  • The structured matrix-vector product can be computed in O(kn log(kn)) time and O(kn) memory using (inverse) Hadamard transforms and element-wise multiplication.The passage describes the vector as a complex-valued function indexed by ditstrings.Source: §IX · p. 28

Related papers

Loading 2602.05956v3…