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

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.

Introduction: Bypassing the Connectivity Tax

In the landscape of quantum computing, traditional architectures such as superconducting loops or trapped ions often face a "connectivity tax." In these systems, the physical layout of qubits is typically fixed or limited by the hardware's wiring. Mapping a complex, real-world graph problem—such as logistics optimization or molecular property prediction—onto these fixed grids requires significant overhead. This often involves numerous "swap" operations, which consume precious coherence time and introduce noise, limiting the complexity of problems that can be solved.

Neutral atom technology offers a paradigm shift by allowing researchers to physically "draw" the problem graph using qubits. By utilizing optical tweezers to manipulate individual atoms into arbitrary 2D or 3D configurations, the hardware itself becomes a direct physical representation of the graph. This "geometry-as-code" approach eliminates the need for complex mapping layers and allows for the native execution of graph-based algorithms.

Native Graph Embedding and Hamiltonian Engineering

The core of neutral atom quantum processing lies in the ability to engineer specific Hamiltonians that govern the interactions between qubits. Two primary interaction models are utilized:

  1. The Ising Model and Rydberg Blockade: By exciting atoms to high-energy Rydberg states, a "blockade" effect is created. An excited atom prevents its neighbors within a specific radius ($r_b$) from being excited. This physical constraint naturally maps to the Maximum Independent Set (MIS) problem, where one seeks the largest set of nodes in a graph such that no two nodes are connected.
  2. The XY Model and Spin-Exchange: This model facilitates spin-exchange interactions, allowing excitations to "hop" between atoms within a radius ($r_e$). This is the fundamental mechanism for implementing quantum walks, which serve as a powerful tool for graph machine learning (GML) and graph isomorphism testing.
Overview of Hamiltonian engineering and the graph embedding workflow on neutral atom QPUs.

The embedding process involves mapping a logical graph $\mathcal{G}$ to a set of atomic positions $r_{\mathcal{G}}$. The physical distance between atoms determines the strength and presence of edges in the resulting interaction matrix $U(r_{\mathcal{G}})$. For non-planar graphs or those requiring complex connectivity, "gadgets"—small clusters of ancillary atoms—can be used to mediate interactions between distant qubits or facilitate edge crossings.

Applications in Optimization and Machine Learning

The ability to natively embed graphs has direct implications for both combinatorial optimization and machine learning.

Combinatorial Optimization

Neutral atom QPUs are particularly well-suited for solving NP-hard problems like MIS. Beyond direct mapping, hybrid quantum-classical workflows are being developed. In these schemes, the QPU handles computationally intensive sub-problems, such as the "pricing" step in Column Generation for large-scale logistics, while a classical optimizer manages the global problem logic.

Graph Machine Learning (GML)

For machine learning tasks, the QPU can be used to generate "quantum feature maps." By evolving a quantum state according to the graph's topology, the system creates a high-dimensional "fingerprint" of the graph. These quantum-generated features can then be fed into classical neural networks for classification or regression. A key advantage here is "equivariance by design": because the quantum evolution occurs on the physical layout of the graph, the resulting data naturally respects the graph's inherent symmetries, such as permutation invariance.

Key Results and Scalability

Recent experimental milestones have validated the potential of this platform. In optimization tasks, setups with over 280 atoms have demonstrated a quadratic quantum speedup over classical simulated annealing for challenging MIS instances. In the realm of biochemistry, neutral atom QPUs have achieved classification accuracies on molecular toxicity datasets that are competitive with state-of-the-art classical graph kernels.

Furthermore, the platform shows a clear path toward scalability. Current systems are transitioning from few-qubit prototypes to processors supporting hundreds of atoms, with a roadmap targeting the 1,000+ qubit regime. The ability to utilize 3D geometries further enhances this scalability, allowing for the embedding of highly connected graphs that would be impossible to represent efficiently in 2D.

Challenges and Future Directions

Despite significant progress, several technical hurdles remain. The "tail" problem refers to the $1/r^6$ or $1/r^3$ decay of interactions; while the blockade is strong, long-range tails can introduce unwanted noise into the graph embedding. Additionally, current repetition rates are limited to a few Hertz due to the time required to physically reload and rearrange atoms. Future hardware improvements, such as "atom reservoirs" and faster imaging techniques, aim to push these rates into the kilohertz range. Finally, achieving high-speed local control over every individual atom remains a major engineering challenge, requiring advanced optical modulators like LCoS-SLMs.

Conclusion

Neutral atom quantum processors represent more than just a different hardware substrate; they provide a native language for processing complex networked data. By merging geometry with computation, this platform offers a unique and powerful pathway toward solving some of the most difficult problems in optimization and machine learning.

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},
}
Figure