Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
arXiv:2307.09442 · doi:10.1103/PhysRevResearch.5.043277
Abstract
Rydberg atom arrays are among the leading contenders for the demonstration of quantum speedups. Motivated by recent experiments with up to 289 qubits [Ebadi et al., Science 376, 1209 (2022)] we study the maximum independent set problem on unit-disk graphs with a broader range of classical solvers beyond the scope of the original paper. We carry out extensive numerical studies and assess problem hardness, using both exact and heuristic algorithms. We find that quasi-planar instances with Union-Jack-like connectivity can be solved to optimality for up to thousands of nodes within minutes, with both custom and generic commercial solvers on commodity hardware, without any instance-specific fine-tuning. We also perform a scaling analysis, showing that by relaxing the constraints on the classical simulated annealing algorithms considered in Ebadi et al., our implementation is competitive with the quantum algorithms. Conversely, instances with larger connectivity or less structure are shown to display a time-to-solution potentially orders of magnitudes larger. Based on these results we propose protocols to systematically tune problem hardness, motivating experiments with Rydberg atom arrays on instances orders of magnitude harder (for established classical solvers) than previously studied.
Manuscript: 9 pages, 9 figures. Appendix: 2 pages, 4 figures
References in corpus (23)
- Quantum information with Rydberg atoms
- Probing many-body dynamics on a 51-atom quantum simulator
- Dipole Blockade and Quantum Information Processing in Mesoscopic Atomic Ensembles
- Parallel Tempering: Theory, Applications, and New Perspectives
- Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
- Realizing quantum Ising models in tunable two-dimensional arrays of single Rydberg atoms
- Entanglement of two individual neutral atoms using Rydberg blockade
- Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
- Quantum computing with atomic qubits and Rydberg interactions: Progress and challenges
- Parallel implementation of high-fidelity multi-qubit gates with neutral atoms
- Synthetic three-dimensional atomic structures assembled atom by atom
- High-fidelity parallel entangling gates on a neutral atom quantum computer
- Quantum computing with neutral atoms
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
- Rydberg atom quantum technologies
- Observing the space- and time-dependent growth of correlations in dynamically tuned synthetic Ising antiferromagnets
- Quantum optimization with arbitrary connectivity using Rydberg atom arrays
- Strengths and weaknesses of weak-strong cluster problems: A detailed overview of state-of-the-art classical heuristics vs quantum approaches
- Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
- Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
- Computing solution space properties of combinatorial optimization problems via generic tensor networks
- Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks
Cited by in corpus (12)
- Challenges and Opportunities in Quantum Optimization
- Scaling Advantage in Approximate Optimization with Quantum Annealing
- Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
- Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
- Low-depth Clifford circuits approximately solve MaxCut
- Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
- Approximating maximum independent set on Rydberg atom arrays using local detunings
- Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
- 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
- Quantum imaginary time evolution and UD-MIS problem
- A quantum wire approach to weighted combinatorial graph optimisation problems