Junxi Chen of the Rzhanov Institute of Semiconductor Physics SB RAS and colleagues benchmarked a quantum optimization algorithm using twenty randomly weighted 3-regular graphs, each containing 12 vertices. The work theoretically investigates an analog implementation of the quantum approximate optimization algorithm (QAOA) for the weighted maximum cut problem, using a three-dimensional array of Rydberg atoms and globally addressed laser pulses.

Researchers compared discretized quantum annealing with warm-start initialization using a graph neural network, achieving performance that surpasses the Goemans-Williamson rounding in most noiseless instances. The optimized schedules were then emulated using a realistic error model of the Aquila neutral-atom quantum processor.

QAOA for Weighted MaxCut on Rydberg Atom Arrays

The study directly encoded problem weights into the physical arrangement of atoms, a method differing from approaches that rely on “gadgets” to represent graph connections. This direct placement avoids the overhead and potential interpretability issues associated with using additional elements to simulate complex graph structures, as Bauer et al. previously demonstrated with local detunings and Rydberg excitation. Two distinct strategies were employed to optimize the parameters governing the quantum approximate optimization algorithm (QAOA) implementation.

The GNN-based warm-start method aims to provide a strong initial guess for the optimization process, potentially accelerating convergence and improving solution quality. The researchers evaluated both approaches based on sampling statistics and the total pulse-time cost, seeking to identify the most efficient pathway to solving the weighted MaxCut problem on their chosen hardware.

The team acknowledges that further improvements are needed, specifically focusing on reducing per-shot coherence and detection fidelity, before deeper annealing branches can be effectively tested. The combined optimization strategy creates a portfolio that outperforms the Goemans–Williamson (GW) rounding almost in all instances in the noiseless case.

The error budget highlights the critical need to enhance both coherence and detection fidelity to allow the full potential of this approach to be realized. This focus on error mitigation highlights the challenges inherent in building practical quantum optimization algorithms, even with promising hardware platforms like Rydberg atom arrays.

Three-Dimensional Rydberg Array for Problem Encoding

Encoding of any set of positive weights is enabled by the design of the quantum system, provided the three-dimensional atomic arrangement can physically realize the inverse sixth root of those weights as interatomic distances. This geometric constraint limits the range of attainable weights; in the benchmarks used, the largest and smallest edge weights differed by a factor of approximately three.

This careful consideration of physical realizability is important for translating theoretical optimization algorithms into practical implementations. Junxi Chen and I. I.

While the combined approach of warm start and a short annealing circuit yielded the best results for small shot budgets, the team acknowledges that re-optimizing the laser pulse schedules under realistic noise conditions remains a key area for improvement. This indicates that addressing these practical limitations is essential for achieving higher performance and reliability. The ability to accurately model and mitigate errors is paramount for scaling up quantum optimization algorithms and achieving meaningful computational advantages.

The geometry admits a three-dimensional placement in which every non-edge pair of atoms is farther apart than every edge pair, a critical requirement for accurate problem encoding. This work demonstrates the potential of three-dimensional Rydberg atom arrays for analog quantum optimization, while also emphasising the challenges associated with building and controlling complex quantum systems. The combination of theoretical investigation and emulation on a realistic quantum processor represents a step toward realizing practical quantum solutions for challenging optimization problems.

Weighted MaxCut Problem Definition and Approximation

This approach allowed for direct comparison with the Goemans-Williamson (GW) algorithm, a classical reference for solving the weighted MaxCut problem, and its performance on the same graphs. The GW algorithm, based on the unique games conjecture, offers a worst-case approximation ratio of 0.878, but often performs better in practice, necessitating a comparison based on actual results rather than theoretical guarantees.

Embedding graphs into the geometric constraints of a quantum system often requires the use of “gadgets,” intermediary components that translate the problem’s structure, but these can introduce overhead and complexity. Instead, the researchers directly positioned atoms in three dimensions to encode the edge weights of the MaxCut problem, mirroring the interatomic coupling energies. The team’s work focused on establishing a direct correspondence between atom positions and the weights assigned to each edge in the graph, simplifying the translation of the problem to the quantum realm.

Goemans-Williamson Algorithm as a Benchmark

This outperformance is particularly notable given that the GW algorithm, a classical approach to the MaxCut problem, possesses a guaranteed approximation ratio of 0.878, and often achieves better results in practice. Researchers directly compared the performance of their quantum approximate optimization algorithm (QAOA) implementation against the actual cut ratios obtained by the GW algorithm on the same graph instances, rather than solely against the theoretical guarantee. These findings demonstrate the potential for QAOA to offer a competitive advantage over traditional algorithms for solving the MaxCut problem, particularly as the optimization depth increases.

This detailed analysis provides a robust framework for evaluating the effectiveness of the QAOA implementation and contextualizes its performance relative to a well-established classical algorithm. “For any alternative algorithm, a fair comparison must be made with what GW actually achieves on the same graphs, both for a single rounding and for repeated sampling,” the authors state, highlighting the importance of a direct, empirical comparison.

The total pulse-time cost of both the discretized quantum annealing and warm-start initialization approaches were also analyzed, providing a comprehensive assessment of the computational resources required for each strategy. This consideration of both performance and efficiency is important for evaluating the practical feasibility of implementing QAOA on near-term quantum devices. Specifically, the team encoded weights by selecting three-dimensional coordinates for each atom, establishing a direct relationship between spatial arrangement and the resulting van der Waals interactions.

Performance Emulation on the Aquila Processor

revealed a surprising shift in optimal quantum annealing depth under realistic noise conditions. With the Aquila model, representing the parameters of the neutral-atom quantum processor, the most effective depth of the annealing branch dropped from 20 to just 5, indicating a significant erosion of benefits from increasing algorithmic complexity in the presence of errors. This finding contrasts sharply with noiseless simulations where deeper annealing branches typically yield improved results, demonstrating the critical impact of hardware-specific noise characteristics.

This data highlights the trade-off between computational depth and performance degradation due to noise, as the initial gains from increased depth are ultimately outweighed by error accumulation. A graph neural network (GNN)-based warm start approach proved most effective at a depth of 3, achieving a measured $R_{a}$ of 0.826, outperforming the annealing branch at all depths and yielding an optimal cut in 16% of the shots. “Warm start at p = 3 becomes the best protocol in all 20 instances,” the study reports, emphasizing the practical advantage of this combined strategy.

👉 More information
🗞 Analog quantum approximate optimization algorithm for solving the weighted MaxCut problem on three-dimensional single-atom Rydberg array
✍️ Junxi Chen and I. I. Beterov (Rzhanov Institute of Semiconductor Physics SB RAS, Novosibirsk, Russia)
🧠 ArXiv: https://arxiv.org/abs/2611.13796v1

More like this