Graph algorithms with neutral atom quantum processors

Constantin Dalyac, Lucas Leclerc, Louis Vignoli, Mehdi Djellabi, Wesley da Silva Coelho, Bruno Ximenez, Alexandre Dareau, Davide Dreon, Vincent E. Elfving, Adrien Signoles, Louis-Paul Henry, Loïc Henriet

TL;DR

Neutral atom quantum processors are emerging as a powerhouse for graph-based problems because they allow researchers to physically "draw" a graph using qubits. By leveraging the Rydberg blockade effect and reconfigurable 3D geometries, these processors can natively embed complex optimization and machine learning tasks directly into hardware, offering a path toward quadratic speedups and novel quantum feature maps.

What Problem Does This Paper Address?

In traditional quantum computing (like superconducting loops or trapped ions), the connectivity between qubits is often fixed or limited by the physical wiring of the chip. Mapping a complex graph problem—like finding the most efficient delivery route or predicting molecular toxicity—onto such hardware requires significant overhead and "swap" operations that eat into the limited coherence time of the qubits.

This paper reviews how neutral atom technology bypasses this "connectivity tax." By using optical tweezers to move individual atoms into arbitrary 2D or 3D configurations, the hardware itself becomes a physical representation of the graph. The authors explore how this "geometry-as-code" approach can tackle NP-hard optimization problems and enhance graph machine learning (GML).

Methods

The paper details several core techniques that make neutral atom QPUs (Quantum Processing Units) unique:

  • Hamiltonian Engineering: Researchers use two primary interaction types:
  • Ising Model: Uses the "Rydberg blockade," where an excited atom prevents its neighbors within a certain radius ($r_b$) from being excited. This naturally maps to the Maximum Independent Set (MIS) problem.
  • XY Model: Facilitates "spin-exchange" interactions, allowing excitations to hop between atoms. This is used to implement quantum walks, which are essential for graph machine learning.
  • Geometric Programming & Gadgets: To solve problems beyond simple "unit-disk" graphs (where edges only exist between nearby neighbors), the authors describe using "gadgets"—small clusters of ancillary atoms that act as wires or crossings—to mediate interactions between distant qubits.
  • Hybrid Workflows: The paper emphasizes "Quantum-Classical" hybrids. For example, using a QPU to solve a difficult sub-problem (like "pricing" in Column Generation) while a classical computer handles the overall optimization logic.
  • Quantum Feature Maps: For machine learning, the QPU evolves a quantum state based on the graph's topology. Measuring this state creates a "fingerprint" (feature map) of the graph that classical neural networks can then use for classification.

Datasets

While primarily a review paper, it cites specific benchmarks used in the field:

  • Biochemistry Dataset: A standard dataset of 286 molecules (sizes 2 to 32 nodes) used for toxicity screening.
  • Synthetic Graphs: Non-isomorphic strongly regular graphs used to test the "expressiveness" of quantum walks compared to classical algorithms.
  • Industrial Use-Cases: References to molecular structures and logistics/routing graphs used in "Extremal Learning" scenarios.

Key Insights and Ideas

  • The Geometry is the Algorithm: The most striking insight is that the physical distance between atoms is the edge of the graph. By moving atoms, you are literally programming the interaction matrix.
  • Breaking the Plane: While many quantum platforms are 2D, neutral atoms can be arranged in 3D. This is crucial for embedding non-planar graphs (graphs that can't be drawn on paper without edges crossing) without needing massive amounts of error-prone overhead.
  • Quantum Walks vs. Weisfeiler-Leman: The paper notes that 2-particle quantum walks on these QPUs can distinguish certain complex graphs that standard classical "WL-tests" (the gold standard for graph isomorphism) fail to separate.
  • Equivariance by Design: Because the quantum evolution happens on the physical layout of the graph, the resulting data naturally respects the symmetries of the graph (permutation equivariance), a property that is hard-won in classical GML.

Key Results

  • Quadratic Speedup: Experimental setups with over 280 atoms have demonstrated a quadratic quantum speedup over classical simulated annealing for hard MIS graph problems.
  • Competitive Accuracy: In toxicity screening tasks, neutral atom QPUs achieved classification accuracies on par with state-of-the-art classical kernels, even when using limited "global" controls.
  • Scalability Path: The paper highlights the jump from few-qubit prototypes to systems supporting hundreds of atoms, with a clear engineering roadmap toward the 1,000+ qubit regime.

Limitations and Future Work

Despite the promise, several hurdles remain:

  • The "Tail" Problem: Interactions follow a $1/r^6$ or $1/r^3$ decay. While the "blockade" is strong, the long-range "tails" of these interactions can introduce unsought terms (noise) in the graph embedding.
  • Low Repetition Rates: Currently, these machines operate at a few Hz because they have to physically reload and rearrange atoms for every "shot." The authors suggest "atom reservoirs" and faster imaging to push this into the kHz range.
  • Addressability: Most current results use "global" pulses (shining light on all atoms at once). True "geometric programming" requires high-speed local control over every single atom, which is an ongoing hardware challenge involving complex optical modulators (LCoS-SLM).

In summary, the paper argues that neutral atom QPUs aren't just another way to build a gate-based computer; they are a native language for the world's most complex networked data.

Summary updated

Abstract

Neutral atom technology has steadily demonstrated significant theoretical and experimental advancements, positioning itself as a front-runner platform for running quantum algorithms. One unique advantage of this technology lies in the ability to reconfigure the geometry of the qubit register, from shot to shot. This unique feature makes possible the native embedding of graph-structured problems at the hardware level, with profound consequences for the resolution of complex optimization and machine learning tasks. By driving qubits, one can generate processed quantum states which retain graph complex properties. These states can then be leveraged to offer direct solutions to problems or as resources in hybrid quantum-classical schemes. In this paper, we review the advancements in quantum algorithms for graph problems running on neutral atom Quantum Processing Units (QPUs), and discuss recently introduced embedding and problem-solving techniques. In addition, we clarify ongoing advancements in hardware, with an emphasis on enhancing the scalability, controllability and computation repetition rate of neutral atom QPUs.
BibTeX
@article{dalyac2024graph,
  author = {Constantin Dalyac and Lucas Leclerc and Louis Vignoli and Mehdi Djellabi and Wesley da Silva Coelho and Bruno Ximenez and Alexandre Dareau and Davide Dreon and Vincent E. Elfving and Adrien Signoles and Louis-Paul Henry and Loïc Henriet},
  title = {{Graph algorithms with neutral atom quantum processors}},
  journal = {The European Physical Journal A},
  year = {2024},
  doi = {10.1140/epja/s10050-024-01385-5},
}

Loading related content...

Figure