Solving optimization problems with local light shift encoding on Rydberg quantum annealers

Abstract

We provide a non-unit disk framework to solve combinatorial optimization problems such as Maximum Cut (Max-Cut) and Maximum Independent Set (MIS) on a Rydberg quantum annealer. Our setup consists of a many-body interacting Rydberg system where locally controllable light shifts are applied to individual qubits in order to map the graph problem onto the Ising spin model. Exploiting the flexibility that optical tweezers offer in terms of spatial arrangement, our numerical simulations implement the local-detuning protocol while globally driving the Rydberg annealer to the desired many-body ground state, which is also the solution to the optimization problem. Using optimal control methods, these solutions are obtained for prototype graphs with varying sizes at time scales well within the system lifetime and with approximation ratios close to one. The non-blockade approach facilitates the encoding of graph problems with specific topologies that can be realized in two-dimensional Rydberg configurations and is applicable to both unweighted as well as weighted graphs. A comparative analysis with fast simulated annealing is provided which highlights the advantages of our scheme in terms of system size, hardness of the graph, and the number of iterations required to converge to the solution.

18 pages, 6 figures, 1 table

References in corpus (4)

• Many-Body Physics with Individually-Controlled Rydberg Atoms
• Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
• An experimental and theoretical guide to strongly interacting Rydberg gases
• Robust and efficient in situ quantum control

Cited by in corpus (16)

• Enhancing a Many-body Dipolar Rydberg Tweezer Array with Arbitrary Local Controls
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Universal quantum processors in spin systems via robust local pulse sequences
• Towards Arbitrary QUBO Optimization: Analysis of Classical and Quantum-Activated Feedforward Neural Networks
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Spin-glass quantum phase transition in amorphous arrays of Rydberg atoms
• Atom Cavity Encoding for NP-Complete Problems
• Integer Programming Using A Single Atom
• 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
• Engineering the non-Hermitian Su-Schrieffer-Heeger model with skin effects in Rydberg atom arrays
• Explicitly Quantum-parallel Computation by Displacements
• Resource-Efficient Quantum Optimization via Higher-Order Encoding