⚛️ quantum physics

Analog quantum approximate optimization algorithm for solving the weighted MaxCut problem on three-dimensional single-atom Rydberg array

This paper theoretically demonstrates that an analog quantum approximate optimization algorithm implemented on a 3D Rydberg atom array, utilizing a combined optimization strategy of discretized quantum annealing and graph neural network warm-start initialization, can outperform the classical Goemans-Williamson algorithm for solving weighted MaxCut problems even under realistic error models.

Original author: Junxi Chen, I. I. Beterov

Published 2026-11-11

📖 6 min read🧠 Deep dive

CC BY 4.0

Original author: Junxi Chen, I. I. Beterov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of computing, some problems are notoriously difficult to solve. They belong to a class known as NP-hard, where finding the perfect answer becomes exponentially harder as the problem grows, often taking longer than the age of the universe for even the most powerful supercomputers. One such puzzle is the weighted maximum cut problem. Imagine a network of points connected by lines, where each line has a specific value. The goal is to split the points into two groups so that the total value of the lines connecting the two groups is as high as possible. This task is not just a mathematical curiosity; it underpins real-world challenges like designing efficient computer chips, organizing data clusters, and planning network infrastructure. Because finding the perfect solution is so hard, scientists rely on clever shortcuts called approximation algorithms. For decades, a classical method developed by Goemans and Williamson has been the gold standard, guaranteeing a solution that is at least 87.8 percent as good as the perfect answer.

Recently, a new field has emerged that hopes to tackle these tough problems using the strange laws of quantum mechanics. Instead of using standard bits that are either zero or one, quantum computers use qubits, which can exist in a blend of states simultaneously. One promising approach is the Quantum Approximate Optimization Algorithm, or QAOA. While traditional quantum computers often try to solve problems by stringing together a long sequence of precise logic gates, a newer, "analog" version lets the quantum system evolve naturally under the influence of laser pulses. This paper explores a specific, advanced version of this analog approach using a three-dimensional grid of individual atoms trapped in a vacuum. These atoms are excited to a high-energy state known as a Rydberg state, where they interact strongly with one another. The researchers wanted to see if this physical setup could solve the weighted maximum cut problem better than the best classical methods, and if so, how it could be made to work reliably despite the noise and errors inherent in real-world quantum devices.

The researchers began by designing a simulation using twenty different random networks, each containing twelve points. They mapped these networks onto a physical grid of atoms, arranging the atoms in three-dimensional space so that the distance between any two atoms determined the strength of their interaction. By carefully placing the atoms, they encoded the specific values of the problem directly into the physical forces between the particles. If two points in the problem needed a strong connection, the corresponding atoms were placed close together; if they needed a weak connection, they were placed farther apart. This method allowed them to solve the problem without needing extra "helper" atoms or complex tricks, relying instead on the natural physics of the system. They then ran the quantum system through a sequence of laser pulses, testing two different strategies to guide the system toward the best solution.

The first strategy, known as a "cold start," began with all atoms in a neutral state and let the system evolve through a series of steps. The researchers discovered that the path the system took mattered immensely. If they simply let a computer optimizer choose the best settings layer by layer without guidance, the system would get stuck on a path that looked good at the beginning but failed to improve as the process continued. This path led to a solution that was only about 77 percent as good as the perfect answer. However, by adding a simple physical constraint—limiting how long certain parts of the laser pulse could last—they forced the system onto a different path. This new path behaved like a slow, careful cooling process, known as annealing. On this path, the quality of the solution kept improving as they added more layers, eventually reaching a score of 95.9 percent, surpassing the classical gold standard in most of their test cases.

The second strategy, called a "warm start," tried to give the quantum system a head start. Before the laser pulses began, the researchers used a classical computer program, specifically a type of artificial intelligence called a graph neural network, to guess a good starting arrangement. They then prepared the atoms in a state that matched this guess. This approach worked very well, but only if the initial guess was correct. When the network's guess was right, the quantum system refined it into a near-perfect solution very quickly. However, when the network's guess was wrong, the quantum system tended to get stuck near that wrong answer, unable to find the true best solution. This revealed a crucial insight: the two strategies failed in different situations. The cold-start method struggled when the physical arrangement of the atoms was imperfect, while the warm-start method struggled when the initial guess from the artificial intelligence was poor.

To get the best of both worlds, the researchers combined the two approaches into a single portfolio. For each problem, they ran both the cold-start and warm-start versions and simply chose the better result. This combined strategy outperformed the classical gold standard in nineteen out of the twenty test cases in a perfect, noiseless simulation. However, when tested against a realistic error model based on an existing quantum processor called Aquila, the results changed. In this noisy environment, the advantage of running a long, complex sequence disappeared. The deep, annealing-based path that worked so well in the simulation became too fragile, and the system could not maintain its quality as the sequence grew longer. The best performance under these noisy conditions came from the short, warm-start approach, which required only a few steps and a very brief laser pulse. However, even this short version did not beat the classical gold standard in the noisy simulation; it yielded an optimal cut in only 16% of the shots, less than half as often as a single Goemans–Williamson rounding.

The study concludes that while the analog quantum approach holds great promise for outperforming classical algorithms, the path to realizing this potential is not straightforward. The deep, annealing-like sequences that offer the highest theoretical performance are currently too sensitive to the errors found in today's hardware. The most effective immediate strategy appears to be a hybrid one: using short, smart initial guesses to guide the system, or running multiple strategies in parallel and picking the winner. The researchers found that to make the deep, high-performance sequences viable, the error rates in quantum processors would need to be reduced by roughly an order of magnitude. Until then, the most practical way to use these machines is to combine different approaches, leveraging the speed of short sequences and the power of multiple strategies to navigate the complex landscape of difficult problems.

Technical Summary: Analog Quantum Approximate Optimization Algorithm for Weighted MaxCut on 3D Rydberg Arrays

Problem Statement
This work addresses the weighted Maximum Cut (MaxCut) problem, a fundamental NP-hard combinatorial optimization problem with applications in VLSI design, data clustering, and network infrastructure. The problem involves partitioning the vertices of a graph $G=(V, E, w)$ into two disjoint sets to maximize the total weight of edges connecting the two sets. The authors focus on solving this problem using an analog implementation of the Quantum Approximate Optimization Algorithm (QAOA) on a three-dimensional (3D) array of individually trapped Rydberg atoms. Unlike previous approaches that often rely on planar lattices or auxiliary "gadget" constructions to embed arbitrary graphs, this study utilizes the natural 3D geometry of the atomic array to directly encode edge weights.

Methodology
The proposed protocol utilizes a 3D array of $N=12$ ultracold $^{87}$ Rb atoms, excited to Rydberg states ( $|70S_{1/2}\rangle$ ). The system is governed by a Hamiltonian where the van der Waals interaction ( $V_{ij} \propto 1/r_{ij}^6$ ) provides programmable two-body Ising couplings.

Graph Embedding: The authors map the weighted MaxCut problem directly onto the physical system. Edge weights $w_{ij}$ are encoded by positioning atoms at specific distances $r_{ij}$ such that the interaction energy $V_{ij}/4$ corresponds to the desired weight. Non-adjacent atoms also interact, but these "non-edge" couplings are treated as part of the system dynamics rather than being eliminated.
Hamiltonian and Pulse Sequence: The system evolves under a time-dependent Hamiltonian $H(t) = \sum_i \frac{\Omega_i(t)}{2}(e^{i\phi}|g\rangle\langle r| + h.c.) - \sum_i \Delta_i(t) n_i + \sum_{i<j} V_{ij} n_i n_j$ $H (t) = \sum_{i} \frac{Ω _{i} ( t )}{2} (e^{i ϕ} ∣ g ⟩ ⟨ r ∣ + h . c .) - \sum_{i} Δ_{i} (t) n_{i} + \sum_{i < j} V_{ij} n_{i} n_{j}$ .
- Preparation: A global pulse prepares an initial state (either $|+\rangle^{\otimes N}$ for cold start or a specific product state for warm start).
- Cost Segments: Periods where the drive is off ( $\Omega=0$ ), evolving under the cost Hamiltonian $H_C$ (Ising model with site-dependent detunings $\Delta_i$ used to cancel single-site terms arising from the van der Waals interaction).
- Mixer Segments: Periods where global or site-resolved drives are active, providing a transverse field component.
Optimization Strategies: The study compares two approaches for optimizing the pulse parameters (durations $\gamma_k$ $γ_{k}$ and $\beta_k$ $β_{k}$ ):
- Cold Start: Initialization from the uniform superposition state $|+\rangle^{\otimes N}$ .
- Warm Start: Initialization using a product state derived from a Graph Neural Network (GNN) that predicts vertex marginals. This requires site-resolved Rabi frequencies and specific detuning shifts to ensure the initial state is an eigenstate of the mixer.
Simulation and Validation: The authors simulate the system using a Krylov propagation method (Arnoldi) and a quantum trajectory solver to emulate the "Aquila" neutral-atom quantum processor. This error model includes quasi-static laser noise, atom position fluctuations, dephasing, spontaneous decay, and detection errors.

Key Results
The study evaluates twenty randomly generated 3-regular graphs with 12 vertices.

Optimization Landscapes: The authors identify two distinct branches in the optimization landscape. A standard layer-by-layer optimizer often gets trapped in a "non-adiabatic branch" (Basin B), where the approximation ratio ( $R_a$ ) saturates around 0.77. By imposing a physical constraint limiting cost-segment durations ( $\gamma_k \leq 1 \mu s$ ), the optimizer is guided to an "annealing branch" (Basin A). On this branch, $R_a$ increases monotonically with depth, reaching $0.959$ at $p=20$ .
Comparison with Classical Algorithms:
- In the noiseless regime, the optimized annealing branch ( $p \geq 16$ ) outperforms the Goemans-Williamson (GW) rounding algorithm in terms of expected cut value for the majority of instances.
- The GNN warm-start protocol, however, is statistically indistinguishable from GW (e.g., at $p=10$ , the mean difference is $-0.006$ with $P=0.76$ ).
- A portfolio strategy, which selects the better result between the cold-start annealing branch and the warm-start protocol for each instance, achieves an average $R_a$ of $0.966$, surpassing GW in 19 out of 20 instances. However, the portfolio's mean difference relative to GW is not statistically significant ( $P=0.45$ ), and the portfolio is not significantly better than the GNN rounding itself. The GNN rounding serves as a strong classical reference, often outperforming the quantum protocols in expectation values, particularly in instances where the network's initial guess is optimal.
- The GNN warm start is highly effective when the network's initial guess is close to optimal but can fail (concentrate on suboptimal strings) when the GNN prediction is poor. Conversely, the cold-start annealing branch is robust to GNN failures but requires deeper circuits.
Noise Analysis: When emulated with the realistic error model of the Aquila processor:
- The advantage of deep circuits diminishes; the optimal depth for the annealing branch drops from $p=20$ to $p=5$ .
- The warm-start protocol at shallow depth ( $p=3$ ) becomes the most robust single protocol, outperforming the noisy annealing branch.
- Crucially, the portfolio strategy loses its value as noise levels increase. At noise scaling factors $\lambda \geq 1$ (representing current hardware capabilities), the warm start is the better member on every instance, effectively reducing the portfolio to the warm start alone. The portfolio only retains its complementary value at significantly lower noise levels ( $\lambda \approx 0.1$ ).
Sampling Statistics: While the expected values improve, the probability of measuring the exact optimal cut ( $P_{opt}$ ) in a single shot remains lower than that of repeated GW rounding for small depths. However, the quantum protocols show promise in finding high-quality cuts with fewer shots compared to classical sampling in specific regimes.

Significance and Claims
The paper modestly claims to demonstrate the potential of analog Rydberg-based QAOA for weighted MaxCut without the overhead of gadget-based embeddings. The primary contributions are:

Direct 3D Embedding: Demonstrating that 3D atomic arrays can natively encode arbitrary weighted graphs by tuning interatomic distances, avoiding the need for auxiliary qubits.
Landscape Analysis: Identifying that the "greedy" choice of the best local minimum at depth $p=1$ can lead to suboptimal global performance (non-adiabatic branch), and that a simple physical constraint on pulse duration can guide the optimizer toward a superior, adiabatic-like trajectory.
Hybrid Strategy: Showing that combining a classical heuristic (GNN) for warm-starting with a quantum annealing branch creates a portfolio that is more robust than either method alone in the noiseless limit, effectively covering the weaknesses of each. However, this advantage is conditional on low noise levels; under current hardware noise, the portfolio collapses to the warm-start protocol.
Noise Resilience: Providing a realistic assessment that while current hardware noise limits the depth advantage and the efficacy of the portfolio strategy, shallow-depth warm-start protocols can still outperform classical baselines in expectation values, provided error rates are managed.

The authors conclude that while current noise levels prevent the realization of the full potential of deep annealing branches and the portfolio approach, the observed performance in the noiseless limit and the robustness of the warm-start protocol suggest a viable path forward as hardware fidelity improves.

Technical Summary: Analog Quantum Approximate Optimization Algorithm for Weighted MaxCut on 3D Rydberg Arrays

More like this