A promising quantum optimization strategy loses its edge when noise enters

Imagine dividing a network into two groups so that the connections crossing between them carry the largest possible total weight. That is weighted MaxCut, a mathematical optimization problem with applications including clustering and circuit design. Trying every division becomes impractical as networks grow, making it a useful testing ground for approximate algorithms.

In a November 10 arXiv preprint, Junxi Chen and I. I. Beterov investigate an analog quantum approximate optimization algorithm, or QAOA, for this task. Their results come from computer simulations, not an experiment. They test 20 randomly weighted networks with 12 vertices each, where every vertex has three connections. These instances are small enough that the exact answer can be checked by exhaustive search.

Writing a network into atom positions

The proposed processor uses individually trapped rubidium atoms excited to Rydberg states, in which they interact strongly. One atom represents each network vertex. Distances between atoms determine interaction strengths, allowing the geometry of a three-dimensional array to encode connection weights without additional auxiliary atoms.

That encoding is imperfect. Atoms representing unconnected vertices still interact, and fitting the geometry changes the intended weights. The researchers therefore evaluate solutions using the weights actually produced by their simulated atom placements. They also retain every pairwise interaction in the dynamics rather than ignoring unwanted ones. In three of the 20 instances, the lowest-energy state of the physical system does not correspond to the network's optimal cut. Even perfectly following that state would therefore miss the exact answer.

The algorithm alternates intervals that accumulate problem-dependent quantum phases with laser-driven intervals that mix possible assignments. Crucially, atomic interactions remain active during the mixing intervals. The hardware cannot simply switch the problem off while exploring alternatives.

Why a restriction helps

A straightforward optimizer tends to choose the strongest-performing first layer. But on many test instances, that choice leads into a family of pulse schedules that improves little as further layers are added.

The authors instead limit every problem-only interval to at most one microsecond. This keeps the search on a different path, which their analysis identifies as a discretized form of quantum annealing: a gradual progression toward low-energy states associated with good cuts.

At 20 layers, this constrained route reaches a mean approximation ratio of about 0.959. Here the ratio means the expected cut weight divided by the exact optimum; one would be perfect. The comparison method, Goemans–Williamson, averages about 0.948 for a single randomized rounding on the same instances. The quantum route exceeds that expectation on 15 of the 20 networks.

A second route starts from probabilities supplied by a graph neural network. This initial guess helps quickly, provided the mixing field is chosen consistently with the prepared quantum state. Most useful improvement arrives within three layers, taking about two microseconds of pulse time. But a poor network guess can leave the quantum state concentrated around a suboptimal answer.

Because the two routes fail on different instances, selecting whichever has the higher expected cut produces a mean ratio of 0.966, above the single-rounding classical benchmark on 19 instances.

The comparison is narrower than quantum advantage

Those numbers do not establish a speedup. Repeating Goemans–Williamson rounding is highly effective on these tiny networks: ten roundings already give an expected best-cut ratio of about 0.9993. The rounded neural-network output is also a strong classical reference, and the quantum portfolio does not significantly outperform it in mean cut ratio.

Reusing optimized pulse parameters from other instances substantially reduces the number of simulation evaluations needed. However, the reported target-instance counts exclude building the source parameter database. They are not an end-to-end demonstration of computational advantage.

Noise changes the preferred strategy

The researchers then simulate laser fluctuations, detuning errors, atom-position uncertainty, dephasing, decay and detection mistakes using an Aquila-based error model. With the unscaled model, the constrained route performs best at five layers rather than 20. Longer sequences accumulate more damage than useful improvement.

The short neural-network-assisted route becomes stronger, reaching a measured mean ratio of 0.826 versus 0.750 for the best constrained route. Neither reaches the classical benchmark. Reducing the model's error parameters tenfold brings the readout-corrected portfolio approximately level with that benchmark, not clearly beyond it.

This remains a proposal with demanding controls, including three-dimensional positioning and site-dependent detunings; the neural-network route additionally requires site-dependent drive amplitudes. The noise model was developed for two-dimensional arrays and applied here as an estimate, and schedules were not reoptimized under noise. The preprint's clearest contribution is therefore a lesson in algorithm design: a physically informed constraint can rescue optimization in an ideal model, while realistic errors determine whether that rescue is useful on hardware.