Quantum optimization with arbitrary connectivity using Rydberg atom arrays
arXiv:2209.03965 · doi:10.1103/PRXQuantum.4.010316
Abstract
Programmable quantum systems based on Rydberg atom arrays have recently been used for hardware-efficient tests of quantum optimization algorithms [Ebadi et al., Science, 376, 1209 (2022)] with hundreds of qubits. In particular, the maximum independent set problem on so-called unit-disk graphs, was shown to be efficiently encodable in such a quantum system. Here, we extend the classes of problems that can be efficiently encoded in Rydberg arrays by constructing explicit mappings from a wide class of problems to maximum weighted independent set problems on unit-disk graphs, with at most a quadratic overhead in the number of qubits. We analyze several examples, including: maximum weighted independent set on graphs with arbitrary connectivity, quadratic unconstrained binary optimization problems with arbitrary or restricted connectivity, and integer factorization. Numerical simulations on small system sizes indicate that the adiabatic time scale for solving the mapped problems is strongly correlated with that of the original problems. Our work provides a blueprint for using Rydberg atom arrays to solve a wide range of combinatorial optimization problems with arbitrary connectivity, beyond the restrictions imposed by the hardware geometry.
19 pages, 12 figures, including Appendices
References in corpus (4)
Cited by in corpus (62)
- Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
- Quantum Feature Maps for Graph Machine Learning on a Neutral Atom Quantum Processor
- Rydberg blockade based parity quantum optimization
- Randomized Benchmarking using Non-Destructive Readout in a 2D Atom Array
- Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
- Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
- Open Hardware Solutions in Quantum Technology
- Trimer quantum spin liquid in a honeycomb array of Rydberg atoms
- Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
- Extending relax-and-round combinatorial optimization solvers with quantum correlations
- Solving optimization problems with local light shift encoding on Rydberg quantum annealers
- Enhancing variational Monte Carlo using a programmable quantum simulator
- Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
- Rydberg-atom graphs for quadratic unconstrained binary optimization problems
- Universal Quantum Optimization with Cold Atoms in an Optical Cavity
- Entangling quantum logic gates in neutral atoms via the microwave-driven spin-flip blockade
- Functional completeness of planar Rydberg blockade structures
- Interspecies Förster resonances of Rb-Cs Rydberg -states for enhanced multi-qubit gate fidelities
- Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor
- Quantum dimer models with Rydberg gadgets
- Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
- Digital-analog quantum learning on Rydberg atom arrays
- Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
- A Rydberg-atom approach to the integer factorization problem
- A renewal approach to configurational entropy in one dimension
- Equilibrium dynamics of infinite-range quantum spin glasses in a field
- Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
- Long-lived oscillations of metastable states in neutral atom systems
- Long-range gates via radio-frequency-induced Förster resonances
- Optimized QUBO formulation methods for quantum computing
- Recurrent neural network wave functions for Rydberg atom arrays on kagome lattice
- BBQ-mIS: a parallel quantum algorithm for graph coloring problems
- Universal quantum processors in spin systems via robust local pulse sequences
- 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
- Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
- Probing fractional statistics in quantum simulators of spin liquid Hamiltonians
- Going Beyond Gadgets: The Importance of Scalability for Analogue Quantum Simulators
- Replica symmetry breaking in spin glasses in the replica-free Keldysh formalism
- Approximating maximum independent set on Rydberg atom arrays using local detunings
- Spin-glass quantum phase transition in amorphous arrays of Rydberg atoms
- Multi-Qubit Parity Gates for Rydberg Atoms in Various Configurations
- Quantum Scar States in Coupled Random Graph Models
- Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
- Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
- Engineering quantum states with neutral atoms
- Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
- Topological order in symmetric blockade structures
- Constraint-Aware Quantum Optimization via Hamming Weight Operators
- Atom Cavity Encoding for NP-Complete Problems
- A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
- Hamiltonian formulations of centroid-based clustering
- Consensus-based qubit configuration optimization for variational algorithms on neutral atom quantum systems
- Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
- Scalable Heteronuclear Architecture of Neutral Atoms Based on EIT
- Signatures of quantum chaos and complexity in the Ising model on random graphs
- Transfer of quantum-enhanced information through a many-body system
- Non-destructive optical read-out and manipulation of circular Rydberg atoms
- Engineering the non-Hermitian Su-Schrieffer-Heeger model with skin effects in Rydberg atom arrays
- Improving success probability in the LHZ parity embedding by computing with quantum walks
- All-to-all connectivity of Rydberg-atom-based quantum processors with messenger qubits
- A quantum wire approach to weighted combinatorial graph optimisation problems