A quantum wire approach to weighted combinatorial graph optimisation problems

Abstract

Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. 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. 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 annealing of weighted graphs 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.

16 pages, 14 figures

References in corpus (29)

• A variational eigenvalue solver on a quantum processor
• The density-matrix renormalization group in the age of matrix product states
• Variational Quantum Algorithms
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Ising formulations of many NP problems
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Perspectives of quantum annealing: Methods and implementations
• Quantum computing with neutral atoms
• ARC: An open-source library for calculating properties of alkali Rydberg atoms
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Quantum chemistry calculations on a trapped-ion quantum simulator
• Quantum simulation and computing with Rydberg-interacting qubits
• Challenges and Opportunities in Quantum Optimization
• Quantum Annealing: An Overview
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Large-Scale Uniform Optical Focus Array Generation with a Phase Spatial Light Modulator
• Quantum simulation of Ising spins on Platonic graphs
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Rydberg blockade based parity quantum optimization
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Accurate holographic light potentials using pixel crosstalk modelling
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• A Rydberg-atom approach to the integer factorization problem
• Programming higher-order interactions of Rydberg atoms