Rydberg-atom graphs for quadratic unconstrained binary optimization problems

Abstract

There is a growing interest in harnessing the potential of the Rydberg-atom system to address complex combinatorial optimization challenges. Here we present an experimental demonstration of how the quadratic unconstrained binary optimization (QUBO) problem can be effectively addressed using Rydberg-atom graphs. The Rydberg-atom graphs are configurations of neutral atoms organized into mathematical graphs, facilitated by programmable optical tweezers, and designed to exhibit many-body ground states that correspond to the maximum independent set (MIS) of their respective graphs. We have developed four elementary Rydberg-atom subgraph components, not only to eliminate the need of local control but also to be robust against interatomic distance errors, while serving as the building blocks sufficient for formulating generic QUBO graphs. To validate the feasibility of our approach, we have conducted a series of Rydberg-atom experiments selected to demonstrate proof-of-concept operations of these building blocks. These experiments illustrate how these components can be used to programmatically encode the QUBO problems to Rydberg-atom graphs and, by measuring their many-body ground states, how their QUBO solutions are determined subsequently.

arXiv comment13 pages, 6 figures

References in corpus (30)

• Quantum information with Rydberg atoms
• Probing many-body dynamics on a 51-atom quantum simulator
• Ising formulations of many NP problems
• Adiabatic Quantum Computing
• Fast quantum gates for neutral atoms
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• Observation of Rydberg blockade between two atoms
• An atom-by-atom assembler of defect-free arbitrary 2d atomic arrays
• Observation of collective excitation of two individual atoms in the Rydberg blockade regime
• Generation and manipulation of Schrödinger cat states in Rydberg atom arrays
• Synthetic three-dimensional atomic structures assembled atom by atom
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
• Direct measurement of the van der Waals interaction between two Rydberg atoms
• In situ single-atom array synthesis by dynamic holographic optical tweezers
• Analysis of imperfections in the coherent optical excitation of single atoms to Rydberg states
• Coherent dipole-dipole coupling between two single atoms at a Förster resonance
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Ultrafast energy exchange between two single Rydberg atoms on the nanosecond timescale
• A Coherent Quantum Annealer with Rydberg Atoms
• Single-Atom Addressing in Microtraps for Quantum-State Engineering using Rydberg Atoms
• Detecting Multiple Communities Using Quantum Annealing on the D-Wave System
• Adiabatic quantum computation with Rydberg-dressed atoms
• Rydberg atom entanglements in the weak coupling regime
• Quantum simulation of Ising spins on Platonic graphs
• Programmable Quantum Annealing Architectures with Ising Quantum Wires
• Rydberg blockade based parity quantum optimization
• Quantum-Ising Hamiltonian programming in trio, quartet, and sextet qubit systems
• Functional completeness of planar Rydberg blockade structures
• Lossy compression of statistical data using quantum annealer

Cited by in corpus (9)

• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
• Programming higher-order interactions of Rydberg atoms
• Topological order in symmetric blockade structures
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• A quantum wire approach to weighted combinatorial graph optimisation problems