Solving optimization problems with local light shift encoding on Rydberg quantum annealers
arXiv:2308.07798 · doi:10.1103/PhysRevResearch.6.023031
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.
arXiv comment18 pages, 6 figures, 1 table
References in corpus (36)
- SciPy 1.0--Fundamental Algorithms for Scientific Computing in Python
- Quantum Computing in the NISQ era and beyond
- Quantum information with Rydberg atoms
- Ising formulations of many NP problems
- QuTiP: An open-source Python framework for the dynamics of open quantum systems
- Noisy intermediate-scale quantum (NISQ) algorithms
- Trapped-Ion Quantum Computing: Progress and Challenges
- Characterizing Quantum Supremacy in Near-Term Devices
- Many-Body Physics with Individually-Controlled Rydberg Atoms
- Observation of Rydberg blockade between two atoms
- A Theory of Fault-Tolerant Quantum Computation
- Observation of collective excitation of two individual atoms in the Rydberg blockade regime
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- Demonstration of multi-qubit entanglement and algorithms on a programmable neutral atom quantum computer
- ARC: An open-source library for calculating properties of alkali Rydberg atoms
- Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Training variational quantum algorithms is NP-hard
- Chopped random-basis quantum optimization
- Many-body interferometry of a Rydberg-dressed spin lattice
- High fidelity spin entanglement using optimal control
- Rydberg mediated entanglement in a two-dimensional neutral atom qubit array
- Hybrid Quantum-Classical Approach to Quantum Optimal Control
- Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
- Optimal quantum control using randomized benchmarking
- An experimental and theoretical guide to strongly interacting Rydberg gases
- Erasure conversion for fault-tolerant quantum computing in alkaline earth Rydberg atom arrays
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Fault-tolerant quantum computation
- Programmable Quantum Annealing Architectures with Ising Quantum Wires
- Robust and efficient in situ quantum control
- Bayesian optimal control of GHZ states in Rydberg lattices
- Rydberg blockade based parity quantum optimization
- Optimal quantum control with poor statistics
- Long-term drifts of stray electric fields in a Paul trap
- Preparation of ordered states in ultra-cold gases using Bayesian optimization
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