Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays

Abstract

We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.

6 pages+7 pages Supplementary Material

Cited by in corpus (19)

• Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Variational spin-squeezing algorithms on programmable quantum sensors
• Variational Thermal Quantum Simulation via Thermofield Double States
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Complex density wave orders and quantum phase transitions in a model of square-lattice Rydberg atom arrays
• Quantum logic and entanglement by neutral Rydberg atoms: methods and fidelity
• Network Community Detection On Small Quantum Computers
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Floquet-engineered quantum state manipulation in a noisy qubit
• Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• Quantum Sampling Algorithms for Near-Term Devices
• Analytical Framework for Quantum Alternating Operator Ansätze
• Approaches to Constrained Quantum Approximate Optimization
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Robustness to spontaneous emission of a variational quantum algorithm
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Learning quantum symmetries with interactive quantum-classical variational algorithms