Solving optimization problems with Rydberg analog quantum computers: Realistic requirements for quantum advantage using noisy simulation and classical benchmarks

Abstract

Platforms of Rydberg atoms have been proposed as promising candidates to solve some combinatorial optimization problems. Here, we compute quantitative requirements on the system sizes and noise levels that these platforms must fulfill to reach quantum advantage in approximately solving the Unit-Disk Maximum Independent Set problem. Using noisy simulations of Rydberg platforms of up to 26 atoms interacting through realistic van der Waals interactions, we compute the average approximation ratio that can be attained with a simple quantum annealing-based heuristic within a fixed temporal computational budget. Based on estimates of the correlation lengths measured in the engineered quantum state, we extrapolate the results to large atom numbers and compare them to a simple classical approximation heuristic. We find that approximation ratios of at least $\approx 0.84$ are within reach for near-future noise levels. Not taking into account further classical and quantum algorithmic improvements, we estimate that quantum advantage could be reached by attaining a number of controlled atoms of $\sim 8,000$ for a time budget of 2 seconds, and $\sim 1,000-1,200$ for a time budget of 0.2 seconds, provided the coherence levels of the system can be improved by a factor 10 while maintaining a constant repetition rate.

References in corpus (10)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• QuTiP 2: A Python framework for the dynamics of open quantum systems
• Many-Body Physics with Individually-Controlled Rydberg Atoms
• 14-qubit entanglement: creation and coherence
• An atom-by-atom assembler of defect-free arbitrary 2d atomic arrays
• Quantum computing with neutral atoms
• High-Fidelity Entanglement and Detection of Alkaline-Earth Rydberg Atoms
• Unsupervised Machine Learning on a Hybrid Quantum Computer
• Robustness to spontaneous emission of a variational quantum algorithm
• Fermionic Hamiltonians for quantum simulations: a general reduction scheme

Cited by in corpus (20)

• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Quantum logic and entanglement by neutral Rydberg atoms: methods and fidelity
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Functional completeness of planar Rydberg blockade structures
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• Fast and High-Yield Loading of a D${}_2$ MOT of Potassium from a Cryogenic Buffer Gas Beam
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Quantum tomography of Rydberg atom graphs by configurable ancillas
• BBQ-mIS: a parallel quantum algorithm for graph coloring problems
• Quantum annealing of Cayley-tree Ising spins at small scales
• Neural-powered unit disk graph embedding: qubits connectivity for some QUBO problems
• Neural optimization for quantum architectures: graph embedding problems with Distance Encoder Networks
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Topological order in symmetric blockade structures
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
• Quantum imaginary time evolution and UD-MIS problem