Weighted Graph Optimisation with Neutral Atom Arrays

Neutral atoms have emerged as a powerful and scalable platform for quantum computing, offering the ability to generate large numbers of identical and high quality qubits in reconfigurable arrays. By coupling atom to highly excited Rydberg states with strong, long-range dipole-dipole interactions it is possible to perform high-fidelity two and multi-qubit gate operations, or to natively implement classical graph optimisation problems, highlighting the versatility for performing both analogue and digital quantum computing.

Here we present, and experimentally demonstrate, an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture [1]. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform weighted-graph annealing on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes building on results from [2]. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.

[1] A.G. de Oliveira et al., arXiv:2503.17115 (2025).

[2] A.G. de Oliveira et al., PRX Quantum 6, 010301 (2025).