A quantum wire approach to weighted combinatorial graph optimisation problems

Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems [1]. 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 [2]. 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 [3]. 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] J. Wurtz et al., arXiv:2205.08500 (2022).

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

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