Sparse Graph Optimization using Weighted Quantum Wires in Rydberg Atom Arrays

Nov 5, 2025

Overview

Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. In this work 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. 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. 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. For more details see arXiv:2503.17115.

Weighted Quantum Wires

Rydberg atom arrays provide easy access to low degree unit-disk embeddings (UDG) whereby each atom is coupled to it’s neighbours, which has been used to implement weighted graph optimisation of MWIS problems using local addressing [1]. In general however, target graph problems may not be natively UDG requiring a mapping process such as the gadget approach in [2] which incurs an overhead of physical atoms of approximately 4n^2 when encoding a graph with n vertices. In many cases however, the underlying graph problem combines short-range UDG edges with a sparse subset of longer range connections. In these cases, we have developed a weighted quantum wire approach that allows chains of ancillary atoms to be used to create longer range couplings that can link either pairs of atoms or even cliques of 3 or 4 atoms using a single wire. Where wires need to cross, the gadget from [2] can be adapted as shown in the figure below. This approach provides a significant reduction in the overhead compared to the more general gadget case, making it easier to find real-world problem instances that can efficiently map to near-term hardware.

Maximum Weighted Independent Set Problems (MWIS)

To demonstrate the quantum wire approach the image below shows an example graph problem which has been mapped onto a UDG-MWIS using two quantum wires, one connecting three vertices and a second connecting four vertices. This mapping takes the n=10 vertex problem onto only 20 physical atoms, compared to several hundred as required using the gadget based encoding of Ref [2]. We show experimentally these wire encodings can be used to perform closed-loop feedback for finding MWIS solutions.

Solving non-UDG MWIS problems using quantum wire encoding: (a) A non-unit disk graph instance of the maximum weighted independent set problem is first rearranged, and quantum wires are inserted to transform it into a UDG. (b) The resulting UDG can be natively implemented on a neutral atom array. In this example, two weighted quantum wires are added to realize the connections highlighted in red. The MWIS solution is indicated by dashed lines around Rydberg excited nodes in the logical and embedded graphs. (c) Ground state probability versus average MWIS cost observed during annealing parameter optimization. Classical post-processing of the measured configurations enhances the anti-correlation between these quantities. — **Solving non-UDG MWIS problems using quantum wire encoding:** (a) A non-unit disk graph instance of the maximum weighted independent set problem is first rearranged, and quantum wires are inserted to transform it into a UDG. (b) The resulting UDG can be natively implemented on a neutral atom array. In this example, two weighted quantum wires are added to realize the connections highlighted in red. The MWIS solution is indicated by dashed lines around Rydberg excited nodes in the logical and embedded graphs. (c) Ground state probability versus average MWIS cost observed during annealing parameter optimization. Classical post-processing of the measured configurations enhances the anti-correlation between these quantities.

Quadratic Unconstrained Binary Optimization (QUBO)

The quantum wire approach can be extended to enable encoding of QUBO problems whereby in addition to a weight on each vertex, a coupling strength is assigned to each edge. These weighted connections can be implemented using wires with weights equal to the coupling, providing a native embedding on the Rydberg platform. Below we show an example for a 4-qubit all-to-all QUBO mapped to an MWIS problem using quantum wires.

QUBO Embedding: A QUBO instance with 4 nodes and all-to-all connectivity is shown. (b) This problem is mapped to a UDG-MWIS using quantum wires and a modified crossing gadget. The resulting system exhibits six degenerate ground states with distinct wire configurations but identical QUBO solutions. — **QUBO Embedding:** A QUBO instance with 4 nodes and all-to-all connectivity is shown. (b) This problem is mapped to a UDG-MWIS using quantum wires and a modified crossing gadget. The resulting system exhibits six degenerate ground states with distinct wire configurations but identical QUBO solutions.

References

[1] A. de Oliveira et al., Demonstration of Weighted-Graph Optimization on a Rydberg-Atom Array Using Local Light Shifts, PRX Quantum 6, 010301 (2025)
[1] M.-T. Nguyen et al., Quantum optimization with arbitrary connectivity using Rydberg atom arrays, PRX Quantum 5, 010316 (2023)