PaperlayerView exact revision on arXiv

Source-linked AI summary

Hybrid quantum-classical algorithms for approximate graph coloring

Sergey Bravyi, Alexander Kliesch, Robert Koenig, Eugene Tang

arXiv:2011.13420v2quant-phcond-mat.str-el

TL;DR

MAX-k-CUT raises the question of whether near-term hybrid quantum algorithms can compete with efficient classical methods despite short circuit-depth constraints. This paper adapts QAOA and RQAOA to the problem and develops classical simulations of their level-1 versions. The simulations find level-1 RQAOA competitive with a strong classical algorithm on the tested graphs, while standard constant-level QAOA is near random coloring on most large regular bipartite graphs.

  • Problem

    Near-term quantum devices are restricted to short-depth circuits, and whether hybrid algorithms can provide advantage over efficient classical algorithms remains unsettled.

    Source: §1 · p. 1

  • Method

    The paper adapts QAOA and recursive QAOA to MAX-k-CUT and constructs an efficient classical simulation for their level-1 versions.

    Source: §6 · p. 23

  • Results

    On tested generic k-colorable graphs, level-1 RQAOA significantly outperforms level-1 QAOA and is competitive with Newman’s classical MAX-3-CUT algorithm; for most large regular bipartite graphs, constant-level QAOA is barely better than random coloring.

    Source: §3 · p. 7, §6 · p. 23

  • Takeaways & Limitations

    The authors suggest RQAOA may be viable for NISQ devices with efficient classical computation, while higher levels may merit further study.

    Source: §6 · p. 23

    Local maxima and stationary points with negligible gradients often prevent gradient descent from finding the optimal solution in QAOA and RQAOA.

    Source: §5 · p. 16

Abstract

from arXiv · show

We show how to apply the recursive quantum approximate optimization algorithm (RQAOA) to MAX-$k$-CUT, the problem of finding an approximate $k$-vertex coloring of a graph. We compare this proposal to the best known classical and hybrid classical-quantum algorithms. First, we show that the standard (non-recursive) QAOA fails to solve this optimization problem for most regular bipartite graphs at any constant level $p$: the approximation ratio achieved by QAOA is hardly better than assigning colors to vertices at random. Second, we construct an efficient classical simulation algorithm which simulates level-$1$ QAOA and level-$1$ RQAOA for arbitrary graphs. In particular, these hybrid algorithms give rise to efficient classical algorithms, and no benefit arising from the use of quantum mechanics is to be expected. Nevertheless, they provide a suitable testbed for assessing the potential benefit of hybrid algorithm: We use the simulation algorithm to perform large-scale simulation of level-$1$ QAOA and RQAOA with up to $300$ qutrits applied to ensembles of randomly generated $3$-colorable constant-degree graphs. We find that level-$1$ RQAOA is surprisingly competitive: for the ensembles considered, its approximation ratios are often higher than those achieved by the best known generic classical algorithm based on rounding an SDP relaxation. This suggests the intriguing possibility that higher-level RQAOA may be a potentially useful algorithm for NISQ devices.

1 Introduction

Near-term quantum optimization must fit short-depth circuits while competing with mature classical algorithms, and whether hybrid methods offer practical advantage remains unsettled. This paper compares QAOA and RQAOA approximation ratios for MAX-k-CUT with k > 2 against classical methods.

1 Introduction

  • Near-term quantum devices are restricted to short-depth circuits, while hybrid algorithms must be compared with efficient classical probabilistic algorithms.The introduction notes that fault-tolerance limits circuit depth and that whether near-term hybrid algorithms provide computational advantage remains unsettled.Source: §1 · pp. 1–2
  • Earlier results found QAOA limitations for MAX-CUT, while RQAOA recursively applies constant-level QAOA to seek better approximation ratios.For MAX-CUT, numerical evidence indicated level-1 RQAOA improves on QAOA at the same level, though rigorous approximation guarantees remained open beyond special cases.Source: §1 · pp. 2–3
  • For k-colorable graphs, random coloring achieves ratio 1 − 1/k, while Cho, Raje, and Sarrafzadeh improve it when k is a power of two.Their stated ratio is 1 − 1/k(1 − 1/n)^log k; a deterministic algorithm [21] achieves the random-coloring ratio.Source: §1 · p. 3
  • For general graphs, Frieze and Jerrum achieve ratio 1 − 1/k + 2 log k/k^2, with stronger ratios ruled out unless P = NP.Their algorithm uses an SDP relaxation and randomized rounding; the passage states a hardness bound of 1 − 1/(34k) unless P = NP.Source: §1 · p. 3
  • For k = 3, Klerk et al. guarantee α3 ≥ 0.836008, and Newman [17] gives a simpler rounding procedure matching that bound.Goemans and Williamson independently match the k = 3 ratio using complex semidefinite programming.Source: §1 · p. 4
  • The paper studies QAOA and RQAOA approximation ratios for MAX-k-CUT with k > 2 against the best-known classical approximation algorithms.The introduction frames this comparison as an assessment of hybrid algorithms for a non-binary optimization problem.Source: §1 · p. 4

2 Hybrid algorithms for MAX-k-CUT

The section adapts QAOA and RQAOA to MAX-k-CUT using qudits and a cost Hamiltonian for color assignments. RQAOA repeatedly fixes color relations and reduces the problem before a classical final solve.

2 Hybrid algorithms for MAX-k-CUT

  • The section formulates QAOA and RQAOA for MAX-k-CUT for any k ≥ 2.The MAX-k-CUT formulation uses one color variable per graph vertex and maximizes the number of edges whose endpoints have different colors.Source: §2 · p. 4

2.1 QAOA to MAX-k-CUT

  • Level-p QAOA uses n qudits of dimension k, with a cost Hamiltonian encoding the graph’s cut objective and a generalized qudit ansatz.The Hamiltonian’s edge coefficients implement MAX-k-CUT, and it commutes with the generalized Pauli-X symmetry operator.Source: §2.1 · pp. 4–5

2.2 Adapting RQAOA to MAX-k-CUT

  • RQAOA deterministically rounds correlations, selecting a vertex pair and color offset with largest-magnitude M_i,j(b) and imposing that relation.On the initial MAX-k-CUT Hamiltonian, M_i,j(b) depends only on whether b is nonzero; after eliminations this need not remain true.Source: §2.2 · pp. 6–7
  • The imposed relation lets the algorithm substitute one vertex into the Hamiltonian, identify the pair, and remove a qudit while preserving the constrained maximum.The resulting Hamiltonian acts on one fewer variable and is defined on a graph formed by identifying the two vertices.Source: §2.2 · p. 6
  • RQAOA repeats eliminations to a predefined cutoff, solves the remaining problem classically, then reconstructs eliminated colors recursively.The remaining Hamiltonian depends on n_c variables; brute-force search is one example of a classical final solver.Source: §2.2 · pp. 6–7

3 Limitations of QAOAp applied to MAX-k-CUT

For most random d-regular bipartite graphs, QAOA must have a level growing at least logarithmically with n to do more than marginally better than random coloring. The analysis uses local structure and bounds on typical maximum k-cut sizes to establish this limitation.

3 Limitations of QAOAp applied to MAX-k-CUT

  • For most random d-regular bipartite graphs, QAOA cannot be more than marginally better than random coloring unless its level grows at least logarithmically with n.The bound applies to almost all graphs in the considered ensemble, rather than only bounding performance averaged over the ensemble.Source: §3 · pp. 7–8
  • Because QAOA is local and uniform, its edge terms depend on p-local neighborhoods, which are tree-like for almost all edges in typical random regular graphs.The reference neighborhood is T_p,d, a tree whose non-leaf vertices are d-regular.Source: §3 · pp. 8–9
  • All T-typical graphs with the same n and d have nearly identical optimal QAOA values, and angles optimal for one are nearly optimal for the others.The local-term function for a typical neighborhood depends only on p and d.Source: §3 · p. 9
  • The analysis bounds typical maximum k-cut sizes, then converts that bound into an approximation-ratio bound using d-regular bipartite graphs with optimum nd/2.The maximum k-cut size is nd/2 for every d-regular bipartite graph.Source: §3 · pp. 7, 9, 10, 11

4 Classical simulation of level-1 RQAOA

The section develops a classical procedure for computing level-1 QAOA expectation values and specializes it to MAX-k-CUT. It also shows that level-1 RQAOA can be simulated classically in its entirety.

4 Classical simulation of level-1 RQAOA

  • For constant k, level-1 QAOA expectation values ⟨ψ|Z_rZ_v|ψ⟩ take O(k^5(d_r+d_v)) time, making them at most linear in n and constant-time on constant-degree graphs.The resulting classical simulation covers level-1 RQAOA in its entirety because its recursive version does not use a final quantum measurement.Source: §4 · pp. 11–12
  • The variational energy and its angle-search intermediates can be computed classically, and level-1 RQAOA needs no quantum device for its final recursive procedure.The expectation values form the variational energy; the method can also compute partial derivatives, and the recursive algorithm does not use a final measurement.Source: §4 · pp. 11–12

4.1 General algorithm for level-1 QAOA-type expectation values

  • For generalized QAOA-type states, the method computes a two-qudit observable’s expectation by forming the reduced state of the qudit pair.The framework assumes pairwise-commuting interactions on different qudit pairs and applies when the cost Hamiltonian is 2-local.Source: §4.1 · p. 12
  • The reduced state is built by coupling the target pair to interacting qudits through channels; restricting to their neighbors reduces the steps to fewer than d_u+d_v.In general, the construction uses n−2 channel applications; only qudits interacting with either target qudit need be included.Source: §4.1 · pp. 12–13

4.2 Simulating QAOA1 for MAX-k-CUT

  • For MAX-k-CUT, commutativity cancels gates on non-target qudits and groups the remaining gates into paired interactions with each external qudit.The specialization uses a diagonal 2-local Hamiltonian commuting with X^⊗n; simulating each channel takes O(k^5), yielding fewer than O(k^5(d_u+d_v)) steps for the reduced state.Source: §4.2 · pp. 13–15

5 Comparison of QAOA, RQAOA and classical algorithms

The experiments compare level-1 QAOA and RQAOA with Newman’s classical algorithm on randomly generated 3-colorable regular graphs. RQAOA1 outperforms QAOA1 and is competitive with Newman, with its relative performance depending on Newman’s variance.

Choice of parameters

  • The experiments use connected, 3-colorable d-regular graphs built from three equal vertex sets, and compare QAOA1 and RQAOA1 with Newman’s algorithm.The graph construction rejects triangles and disconnected graphs; the study generated 20 graphs for each (n, d) pair.Source: §5 · pp. 16–17

Details for implementation

  • Local maxima and stationary points often hinder gradient descent from finding optimal QAOA and RQAOA solutions; the authors identify this as a barren-plateau phenomenon.They note that strategies for alleviating the problem have been explored previously.Source: §5 · p. 16
  • For MAX-3-CUT, fixing γ lets the authors optimize β efficiently, reducing the search to a one-dimensional grid over γ.For fixed γ, the β optimization uses roots of a degree-4 polynomial and binary search on the unit circle; the search is restricted to γ ∈ [0, π).Source: §5 · pp. 16–17

Numerical results

  • RQAOA1 significantly outperforms QAOA1, and both methods’ performance deteriorates as degree increases, though RQAOA1 is less susceptible.The authors caution that their asymptotic no-go theorem does not immediately apply to these numerical examples.Source: §5 · p. 17
  • Newman’s approximation-ratio variance increases with degree and decreases with graph size; its empirical average appears close to its theoretical guarantee of 0.836008.When variance is large, the best of 100 trials typically yields an essentially optimal solution.Source: §5 · pp. 17–18
  • When Newman’s results are concentrated, RQAOA1 outperforms virtually all its runs, including on large graphs; with high variance, it beats Newman’s mean but not its best result.The comparisons include graphs with n = 30 and n = 300 vertices.Source: §5 · p. 18, Figure 2 · p. 19, Figure 5 · p. 22

6 Discussion and Outlook

The paper studies a qudit version of QAOA and efficient classical simulation of its level-1 QAOA and RQAOA variants. Although these variants are classically simulable, experiments find RQAOA1 competitive with Newman’s algorithm, motivating further study of higher levels.

Discussion and Outlook

  • A qudit version of QAOA applies to non-binary optimization, and its performance on random d-regular k-colorable graphs approaches random guessing as d grows.The stated regime is d = o(√n).Source: §6 · p. 23
  • We give an efficient classical simulation algorithm for level-1 QAOA that extends to problem Hamiltonians with pairwise-commuting 2-local terms and can also simulate level-1 recursive QAOA (RQAOA).Source: §6 · p. 23
  • On tested generic k-colorable graphs, RQAOA1 significantly outperforms QAOA1 and is competitive with Newman’s classical algorithm in MAX-3-CUT experiments up to 300 vertices.The paper states that efficient simulability rules out a quantum advantage over the best efficient classical algorithm.Source: §6 · p. 23
  • The authors suggest RQAOA may be useful for NISQ devices and that higher levels may improve approximation ratios, while noting that exploring p > 1 may require new ideas or quantum devices.They identify establishing performance guarantees and finding additional graph classes with achievability results as future work.Source: §6 · p. 23

A MAX-3-CUT angle optimization without gradient descent

The appendix reduces level-1 MAX-3-CUT angle optimization by first optimizing β for fixed γ. A change of variables then turns the remaining optimization into a search over the unit circle.

Angle optimization

  • For fixed γ, the authors consider maximizing the level-1 QAOA energy E(β, γ) over β, with the cost Hamiltonian C specified for k = 3.Source: A MAX-3-CUT angle optimization without… · p. 24
  • Setting θ_a = 3β_a − β̄ makes θ_0 + θ_1 + θ_2 = 0, reducing the β optimization to maximizing F′′ over the unit circle.For a fixed candidate value, roots of a degree-4 polynomial test whether F′′ reaches that value on the unit circle, enabling binary search.Source: A MAX-3-CUT angle optimization without… · p. 25
  • After finding the maximizing angle, the authors derive the remaining θ values and solve a linear system to recover β_0, β_1, and β_2.The procedure sets θ_1 = −arg z_0 and θ_2 = −θ_0 − θ_1 before solving for the β values.Source: A MAX-3-CUT angle optimization without… · p. 25
Loading 2011.13420v2…