PaperlayerView exact revision on arXiv

Source-linked AI summary

Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach

Jordi R. Weggemans, Alexander Urech, Alexander Rausch, Robert Spreeuw, Richard Boucherie, Florian Schreck, Kareljan Schoutens, Jiří Minář, Florian Speelman

arXiv:2106.11672v3quant-phcond-mat.quant-gasphysics.atom-ph

TL;DR

This paper addresses how QAOA can be applied to correlation clustering, whose many possible clusters complicate qubit encodings. It develops a qudit-based, hardware-aware approach for neutral atoms and reports approximation ratios above the Swamy bound on the studied graphs at depths p ≥ 2.

  • Problem

    General QAOA analysis remains unavailable, while correlation clustering’s many possible clusters complicate qubit encodings.

    Source: §1 · pp. 1–2

  • Method

    The paper builds a full-stack QAOA approach for correlation clustering using qudits and a neutral-atom Rydberg implementation.

    Source: §1 · p. 2, §9 · p. 20

  • Results

    For complete and Erdős–Rényi graphs of up to 7 vertices and clusters, QAOA at p ≥ 2 exceeds the Swamy bound of 0.7666 in all studied cases.

    Source: §9 · p. 21

  • Takeaways & Limitations

    The identified strontium-87 level structure and designed gates provide a qudit processor approach with potential applications beyond QAOA.

    Source: §9 · pp. 20–21

    Including errors strongly limits scaling to large problem instances, and practical quantum advantage with QAOA remains a challenge.

    Source: §8 · p. 20, §9 · p. 21

Abstract

from arXiv · show

We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits, which constitute a natural platform for such non-binary problems. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering, including Hamiltonian formulation of the algorithm, analysis of its performance, identification of a suitable level structure for ${}^{87}{\rm Sr}$ and specific gate design. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count. For single layer QAOA, we also prove (conjecture) a lower bound of $0.6367$ ($0.6699$) for the approximation ratio on 3-regular graphs. Our numerical studies evaluate the algorithm's performance by considering complete and Erd\H{o}s-R\'enyi graphs of up to 7 vertices and clusters. We find that in all cases the QAOA surpasses the Swamy bound $0.7666$ for the approximation ratio for QAOA depths $p \geq 2$. Finally, by analysing the effect of errors when solving complete graphs we find that their inclusion severely limits the algorithm's performance.

1 Introduction

QAOA’s performance is difficult to analyze generally, and encoding correlation clustering’s many possible clusters with qubits complicates interactions. This work develops a qudit-based, hardware-aware approach and studies its algorithmic and physical implementation.

1 Introduction

  • Qudits encode cluster labels in states native to the problem, whereas encoding the many clusters with qubits complicates the required interactions.Earlier QAOA analysis is limited to specific instances, predominantly at low depth, leaving general analysis unresolved.Source: §1 · pp. 1–2
  • The paper develops a full-stack correlation-clustering approach, from a qudit QAOA formulation through Rydberg-system control and analysis.The implementation discussion focuses on fermionic strontium-87, with a similar derivation said to apply to related systems.Source: §1 · p. 2
  • The approach also analyzes noise using the random Pauli method and relates that error model to errors in Rydberg qudit systems.Source: §1 · p. 2
  • For single-layer QAOA on 3-regular graphs, the paper proves an approximation-ratio lower bound of 0.6367 and conjectures a tighter bound of 0.6699.The conjecture is based on numerical results from local optimization.Source: §1 · p. 2
  • Unlike related QAOA studies of multi-cut MAX-k-CUT and MAX k-VERTEX COVER, this work leaves the cluster count undetermined and optimizes a native-qudit, hardware-oriented formulation.The related studies are cited as and.Source: §1 · p. 3

2 Recap of QAOA

QAOA encodes a combinatorial objective and its feasible domain in a quantum circuit, then uses classical optimization to select circuit parameters. Its depth counts alternating applications of cost and mixing Hamiltonians.

2 Recap of QAOA

  • QAOA represents an optimization problem with a cost Hamiltonian, a mixing Hamiltonian, and an initial quantum state.The cost Hamiltonian is diagonal in the computational basis and represents the objective through its eigenvalues.Source: §2 · p. 3
  • The mixer depends on the feasible domain; for an unconstrained binary domain, it is usually the transverse-field Hamiltonian.Constraints can be incorporated into the mixer or added as a cost penalty.Source: §2 · p. 3
  • QAOA_p applies p alternating cost- and mixer-Hamiltonian evolutions to the initial state, with parameters γ and β.Source: §2 · p. 3
  • The expected cost is estimated by sampling the circuit state, and the achieved approximation ratio is evaluated from that expectation.Source: §2 · p. 3
  • A classical optimizer maximizes the expected cost over γ and β; the paper calls randomized initialization without additional strategies vanilla QAOA.Source: §2 · p. 3

3 Correlation clustering

Correlation clustering groups graph nodes using positive or negative pairwise relationships, without fixing the number of clusters in advance. The paper encodes this task in qudits and formulates cost and mixing Hamiltonians for QAOA.

3 Correlation clustering

  • Correlation clustering represents elements as graph nodes and similarities as edge weights; its cluster count is not specified in advance.A pose-estimation application models body-part candidates as nodes and pairwise relations as edge weights to separate people in an image.Source: §3 · p. 4
  • MAXAGREE counts positive edges within clusters and negative edges across clusters, while MINDISAGREE minimizes the opposite disagreements.For general graphs, MAXAGREE is APX-hard, and the best classical algorithm has approximation ratio 0.7666 via SDP with rounding.Source: §3 · p. 4

3.1 Hamiltonian formulation for qudit systems

  • For unweighted instances, each qudit represents a node’s cluster label, and the cost Hamiltonian sums edge-weighted interactions that score same-cluster versus different-cluster assignments.The encoding minimizes the Hamiltonian, which the paper states is equivalent to maximizing the classical cost function.Source: §3.1 · p. 5
  • The single-qudit mixer has a connectivity parameter r, with r = 1 giving the ring mixer and r = d − 1 the fully connected mixer.The simulations use r = 1 for their low-depth studies.Source: §3.1 · p. 5
  • The mixer starts in a superposition of computational-basis states, and the qudit dimension d can be varied to choose the maximum number of available clusters.The formulation’s approximation ratio is related to MAXAGREE because each edge is either an agreement or a disagreement.Source: §3.1 · p. 6
  • The numerical implementation uses generalized Hadamard operations for the initial state and treats cost and mixing unitaries as native elementary operations.Simulations use Cirq with custom gate operations matching the formulation.Source: §3.1 · p. 6

4 Improvement strategies

The paper tests several ways to improve vanilla QAOA, including optimizer choice, restarts, parameter initialization, and varying the cluster limit. Across the tested instances, varying the cluster limit contributes most to improvement.

4 Improvement strategies

  • BOBYQA gave the best performance in a small optimizer study using off-the-shelf settings.The full optimizer comparison is reported in Appendix A.Source: §4 · p. 6
  • The study uses five restarts because local optimizers can depend on initialization and can include stochasticity from optimization, sampling, or gate errors.Source: §4 · p. 6
  • The improvement comparison plots mean approximation ratios over 50 N = 4 complete-graph instances, with shaded error in the mean.COBYLA is used as the classical optimizer in the figure.Source: Figure 2 · p. 7
  • The algorithm loops over d = 1,…,N and keeps the best result, addressing weaker vanilla-QAOA performance when the optimal clustering uses few clusters.Source: §4 · p. 7
  • Looping over cluster numbers contributes most to improvement on 50 complete-graph instances with randomly assigned ±1 edge weights.The reported comparison also finds optimized initial points beneficial, particularly for intermediate depths 2 ≤ p ≤ 4.Source: §4 · p. 7, Figure 2 · p. 7

5 Performance

Across the tested complete and Erdős–Rényi data sets, QAOA at p = 2 exceeds the Swamy approximation-ratio bound on every instance. The study also reports a 3-regular-graph lower bound, while noting that its numerical scalability analysis is limited to graphs with at most 7 vertices.

5 Performance

  • At p = 2, QAOA exceeds the Swamy bound of 0.7666 on all tested complete- and Erdős–Rényi-graph instances.Average performance is comparable across graph types, while worst-case performance is slightly better for complete graphs.Source: §5 · p. 8
  • As p increases, the most difficult N = 7 complete-graph instances appear to have optimal cluster counts between the singleton and all-different extremes.At low p, instances requiring few clusters are most difficult, except the trivial singleton-cluster case.Source: §5 · p. 8
  • For 3-regular graphs, QAOA1 has a proved approximation-ratio lower bound of 0.6367 and a conjectured tighter bound of 0.6699.The numerical scalability study covers only graphs up to N = 7 and does not establish optimal parameters; the bound's dependence on graph degree is unclear.Source: §5 · p. 8

6 Experimental building blocks

The proposed neutral-atom implementation uses fermionic 87Sr, whose ground-state manifold provides up to 10 qudit levels. The paper outlines the level structure and mixer-driving approach for single-qudit operations.

6 Experimental building blocks

  • 87Sr provides a ground-state manifold with up to 10 hyperfine states for qudit encoding; the analysis can also be adapted to 173Yb, whose maximum manifold dimension is 6.The 87Sr nuclear spin is I = 9/2, and its ground-state hyperfine states are insensitive to electric and magnetic field fluctuations.Source: §6 · p. 9

6.1 1-gates

  • Single-qudit gates couple selected qudit levels with laser fields, and the proposed mixer implementation considers coupling ranges r = 1 and r = 2.The paper also comments on r > 2; the r = 1 implementation uses a sequence of pulses beginning with the levels in the S-manifold.Source: §6.1 · p. 10, §6.1.1 · p. 10

6.1.1 Implementation of hardware mixers

  • For the r = 1 mixer, a pulse sequence with adjusted nearest-neighbor Rabi frequencies realizes the mixing unitary.The paper proposes resonant and off-resonant Raman coupling for mixer ranges r = 1 and r = 2, respectively.Source: §6.1.1 · p. 10

1. Apply

The section translates QAOA operations into qudit hardware procedures, including mixer pulses, controlled-phase gates, and state preparation and measurement. Hardware-specific mixers perform similarly to the standard mixer in the tested N = 4 complete-graph instances.

1. Apply

  • The r = 1 mixer is implemented by driving neighboring qudit levels with adjusted Rabi frequencies so the pulse sequence realizes the mixing unitary.The idealized mixer includes periodic wraparound coupling between levels 0 and d − 1, unlike the open-boundary hardware coupling; r = 2 adds a second diagonal through off-resonant coupling.Source: §1 · p. 11
  • Mixers beyond r = 2 are nontrivial with the specified coupling Hamiltonian, which reaches only next-to-nearest qudit levels.For large d near 10, equalized couplings may also require slow operations or increase decoherence from off-resonant scattering; stepwise Givens rotations are suggested.Source: §1 · p. 11

6.1.2 Performance of hardware mixers

  • On the tested N = 4 complete-graph instances, hardware mixers show at most about 4% performance difference from the standard mixer; the r = 2 hardware mixer performs best on average.The standard r = 1 mixer outperforms the hardware r = 1 mixer, and replacing the standard mixer is not expected to cause a significant performance decrease.Source: §6.1.2 · p. 11, Figure 7 · p. 12

6.1.3 Unitaries beyond mixers

  • Resonant two-level and Λ-scheme evolutions provide single-qudit unitaries, with the Λ-scheme coupling two qudit levels through a common Rydberg state and ending with no Rydberg population.These unitaries are used for operations beyond mixers and for controlled operations.Source: §6.1.3 · pp. 11–12

6.2 2-gates

  • The edge-wise commuting cost unitary is implemented as a controlled-phase gate, with Rydberg-mediated operations used in its construction.For distant graph vertices, the implementation can use qudit SWAP gates; parallel application of phase pulses contributes to the qudit SWAP construction.Source: §6.2 · pp. 12–14

6.3 Initialisation and measurement

  • The initial state is prepared by optical pumping into |0⟩ followed by d − 1 single-qudit unitaries; measurement detects levels sequentially through state transfer and imaging.The proposed resonance-fluorescence imaging can detect all qudit states within the expected optical-tweezer lifetime of more than 10 seconds.Source: §6.3 · p. 14

7 Processor design and gate count

The section compares qudit and binary-qubit gate costs for complete-graph instances across selected processor geometries, finding lower counts for qudits in every considered case. It also limits its analysis to nearest-neighbour two-gates.

7 Processor design and gate count

  • The gate-count comparison uses CX gates as its cost unit and depends on graph topology, processor topology, and the qubit encoding scheme.For complete graphs, the authors consider an open 1D chain and a 2D triangular lattice.Source: §7 · p. 14, §7.1 · p. 17
  • The analysis counts nearest-neighbour two-gates, leaving optimization that exploits longer-range connectivity for future work.Although Rydberg interactions can provide higher connectivity, the paper notes that longer-range gates take more time because of the blockade constraint.Source: §7 · p. 15

7.1 Gate count and comparison to qubits

  • The binary encoding represents a qudit as an effective qudit in qubits, with q = log2 d as its best-case comparison and a binary controlled-phase gate cost.The paper also notes that the proposed e-dit tilings are not necessarily unique.Source: §7.1 · pp. 17–18
  • Qudit encoding has a lower total gate count than binary-qubit encoding in every considered case, including the binary encoding’s best-case q = log2 d.The comparison covers 1D and 2D processor geometries; for complete graphs, the dominant qudit contribution scales with the number of edges, O(N^2).Source: Table 2 · p. 17, §7.1 · p. 19

8 Errors

The section evaluates a two-qudit random-unitary error model on complete-graph instances using noise-free optimized parameters. Performance is little affected at small error probabilities, but degrades as noise increases; the resulting error limits scaling to large instances.

8 Errors

  • The error model applies a random two-qudit unitary after each cost unitary, with probability p2, and uses noise-free optimized QAOA parameters for the noisy simulations.It is motivated by errors dominated by two-gate operations and is related to errors in Rydberg qudit systems.Source: §8 · p. 19
  • For p2 ≲ 10^-3, noise hardly affects performance; at higher p2 it degrades toward the randomized-state performance.The threshold p2,Th is defined as the noise level where QAOA loses half its performance over random guessing, averaged over instances.Source: §8 · p. 19, Figure 8 · p. 20
  • The threshold gate count gTh is compatible with a linear dependence on 1/p2 across the tested QAOA depths.The threshold values are obtained from the complete-graph results for N = 3, 4, and 5.Source: §8 · p. 19, Figure 8 · p. 20
  • For d = 8, p2 = (10^-2, 10^-3, 10^-4) corresponds to pCX ≈ (10^-3, 10^-4, 10^-5) and estimated N ≈ 13, 41, 130.The authors describe these achievable system sizes as estimates because the formula was verified when the number of clusters saturates the number of vertices.Source: §8 · p. 20
  • Including errors strongly limits scaling to large problem instances, even for the complete-graph setting considered.The paper notes that robustness to errors is directly related to graph topology.Source: §8 · p. 20

9 Conclusions and outlook

The paper presents a QAOA approach to correlation clustering on a Rydberg qudit processor and evaluates it numerically. In the studied graph cases, depth p ≥ 2 exceeds the Swamy bound, while the authors caution that errors make outperforming classical algorithms challenging for near-term noisy devices.

9 Conclusions and outlook

  • The authors identify a suitable 87Sr level structure and design gates for implementing QAOA on a neutral-atom Rydberg processor.They note that the discussed qudit gates can also be used for MAX-k-CUT and MAX k-VERTEX COVER.Source: §9 · pp. 20–21
  • For complete and Erdős-Rényi graphs up to 7 vertices and clusters, QAOA with depth p ≥ 2 exceeds the Swamy bound 0.7666 in all studied cases.The comparison is to the best-known classical strategy based on SDP with performance guarantees for MAXAGREE.Source: §9 · p. 21
  • Including errors makes outperforming classical algorithms challenging for QAOA on near-term noisy devices, at least for complete graphs.Source: §9 · p. 21
  • The authors leave systematic study of the proposed scenarios for future work and note that practical quantum advantage with QAOA remains a challenge.They also describe qudit processors as useful for applications beyond QAOA, including condensed-matter models.Source: §9 · p. 21

A Results optimizer study

For p = 1, optimized parameter points cluster in a small region across related correlation-clustering instances. For 3-regular graphs, the analysis proves a 0.6367 approximation bound and conjectures 0.6699, using local subgraph environments and linear-program relaxations.

B Initial points study for p = 1

  • 0.2% of the parameter space contains the optimal points across 50 dataset instances initialized from all-negative-weight graphs.The all-negative graph’s initial point lies at the boundary of the collection, suggesting other graphs may provide more suitable initial points.Source: B Initial points study for p = 1 · p. 32
  • 0.2% of the parameter space contains the optimal points for one instance across the examined N and d values, with d = 2 somewhat outside the pattern.The points still fall within a single rectangle of that size.Source: B Initial points study for p = 1 · p. 32

C Approximation ratio bound on 3-regular graphs

  • For QAOA that loops over clusters, an approximation ratio greater than 0.6699 is achievable even without the classical optimization loop, and LP relaxation proves a bound of at least 0.6367.Source: C Approximation ratio bound on… · p. 33

C.1 Problem setup and a lower bound for the energy

  • At p = 1, each edge’s environment is induced by neighboring edges, yielding three possible subgraph structures with five edges each.Symmetry reduces the weighted subgraphs considered for the energy bound.Source: §C.1 · pp. 33–34

C.2 Upper bound on the number of agreements

  • Brute-force subgraph optima bound the global optimum from above, because overlapping edge environments may require incompatible clusterings.The subgraphs have at most 64 feasible solutions.Source: §C.2 · p. 34

C.3 Constructing the hardest graph

  • The hardest-graph search relaxes integer subgraph counts and uses two LP bounds: one sets every cλ to 1, while the other retains only perfect-clustering subgraphs.The relaxations bound the approximation ratio from below and above, respectively.Source: §C.3 · pp. 34–35

C.4 Iterative procedure for determining the bound

An iterative search over parameters and hardest graphs establishes the 0.6367 p = 1 bound and supports a 0.6699 conjecture, but the paper does not extend these bounds to p > 1. It also derives qudit controlled-phase gates from driven-level dynamics and controlled-X operations.

C.4 Iterative procedure for determining the bound

  • 0.6367 is proven and 0.6699 is conjectured as a p = 1 approximation bound for 3-regular graphs, with the conjecture based on local optimization.The theorem and conjecture apply to graphs other than the complete N = 4 graph; classical optimization only slightly improves the result for the hardest graph found.Source: §C.4 · p. 36

C.5 Performance bounds for p > 1?

  • For p > 1, the authors do not determine bounds because subgraph enumeration and energy calculations are computationally expensive.A back-of-the-envelope estimate without symmetry reduction is about 10 million computing hours.Source: §C.5 · p. 37

D.1 Dynamics of a driven three-level system

  • A driven three-level scheme couples two qudit states to a Rydberg state, whose energy shifts when a nearby atom is also excited.The dynamics are described in the rotating-wave approximation and can be evaluated on resonance.Source: §D.1 · pp. 37–38

D.2 Derivation of the qudit controlled-phase gates

  • The paper systematically constructs the qudit controlled-phase gates in Eqs. (26) and (27) from available unitaries.For gate (27), controlled-X operations move equal-state elements to |0ℓ⟩, a phase is applied, and the operations are reversed.Source: §D.2 · p. 38, §D.2.2 · p. 40

D.2.1 On qudit controlled-phase gate Eq. (26)

  • For d = 2, gate (26) costs 4 = 2d, twice the cost 2 = d of gate (64).The symmetric construction for gate (26) also generalizes to higher d.Source: §D.2.1 · pp. 38–39

D.2.2 On qudit controlled-phase gate Eq. (27)

  • For qutrits, controlled-X gates map equal-state elements to |0ℓ⟩ so a phase can be applied, then reverse to form gate (27).The scheme also applies to higher d.Source: §D.2.2 · pp. 39–40

E Simulating complete graphs using only nearest-neighbour interactions

The paper gives a swap sequence for simulating all-to-all interactions on a line of qudits, along with counting-based lower bounds on the required swaps and layers.

E Simulating complete graphs using only nearest-neighbour interactions

  • A sequence of swaps simulates a complete graph on a line in n − 2 layers, using (n − 1)(n − 2) swaps.Alternating two sets of swaps ensures every qudit pair becomes nearest neighbors during the sequence.Source: E Simulating complete graphs using… · p. 40
  • A counting argument gives lower bounds on the SWAP count and number of layers needed to enable all-to-all interactions on a line.The authors describe their construction as close to optimal by this counting argument.Source: E Simulating complete graphs using… · p. 40

F On experimental errors

The error analysis focuses on spontaneous decay during two-qudit gates, simplifying decay outside the qudit manifold with an auxiliary level. The unitary error model captures fidelity loss qualitatively but misses dynamics outside that manifold.

F On experimental errors

  • The analysis considers only two-gate errors, focusing on spontaneous decay from Rydberg levels because two-gate errors dominate one-gate errors.Other error sources include background-gas collisions, laser noise, scattering, fluctuating fields, and atom motion.Source: F On experimental errors · p. 41
  • Approximately 0.4 of Rydberg decays return to the qudit manifold, while at least 0.6 decay outside it; an auxiliary level models the latter.The returned population need not be in the same qudit state.Source: F On experimental errors · pp. 41–42
  • Under open dynamics, the qudit-subspace density matrix is approximately the ideal matrix rescaled by e^(-ΓtCP).The authors report this relation holds to good accuracy.Source: F On experimental errors · p. 42
  • The unitary error model qualitatively captures decreasing state fidelity but cannot represent dynamics outside the qudit subspace.The authors call for more rigorous analysis of errors in the QAOA setting.Source: F On experimental errors · p. 42

Related papers

Loading 2106.11672v3…