Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays

Abstract

Realizing quantum speedup for practically relevant, computationally hard problems is a central challenge in quantum information science. Using Rydberg atom arrays with up to 289 qubits in two spatial dimensions, we experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We use a hardware-efficient encoding associated with Rydberg blockade, realize closed-loop optimization to test several variational algorithms, and subsequently apply them to systematically explore a class of graphs with programmable connectivity. We find the problem hardness is controlled by the solution degeneracy and number of local minima, and experimentally benchmark the quantum algorithm's performance against classical simulated annealing. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions in the deep circuit regime and analyze its origins.

10 pages, 5 figures, Supplementary materials at the end

References in corpus (16)

• The density-matrix renormalization group in the age of matrix product states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Probing Topological Spin Liquids on a Programmable Quantum Simulator
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Universal adiabatic dynamics across a quantum critical point
• From density-matrix renormalization group to matrix product states
• Quantum Simulations of Classical Annealing Processes
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Defect formation beyond Kibble-Zurek mechanism and holography
• The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs
• The Overlap Gap Property: a Geometric Barrier to Optimizing over Random Structures
• Monte Carlo simulations of 2d hard core lattice gases
• Tropical Tensor Network for Ground States of Spin Glasses
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Distribution of Kinks in an Ising Ferromagnet After Annealing and the Generalized Kibble-Zurek Mechanism

Cited by in corpus (232)

• A Review on Quantum Approximate Optimization Algorithm and its Variants
• Quantum Annealing for Industry Applications: Introduction and Review
• Quantum critical dynamics in a 5000-qubit programmable spin glass
• Challenges and Opportunities in Quantum Optimization
• Erasure conversion in a high-fidelity Rydberg quantum simulator
• Quantum optimization with arbitrary connectivity using Rydberg atom arrays
• Noisy intermediate-scale quantum computers
• Beyond-classical computation in quantum simulation
• Neutral Atom Quantum Computing Hardware: Performance and End-User Perspective
• Quantum Dynamics in Krylov Space: Methods and Applications
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Towards provably efficient quantum algorithms for large-scale machine-learning models
• NISQ Computers: A Path to Quantum Supremacy
• Constrained Quantum Optimization for Extractive Summarization on a Trapped-ion Quantum Computer
• Pulser: An open-source package for the design of pulse sequences in programmable neutral-atom arrays
• Demonstration of algorithmic quantum speedup
• Rydberg superatoms: An artificial quantum system for quantum information processing and quantum optics
• Emergent ${\mathbb{Z}}_2$ gauge theories and topological excitations in Rydberg atom arrays
• Quantum coarsening and collective dynamics on a programmable simulator
• In-situ equalization of single-atom loading in large-scale optical tweezers arrays
• Realizing quantum gates with optically-addressable ${}^{171}$Yb${}^{+}$ ion qudits
• Towards large-scale quantum optimization solvers with few qubits
• Emergent glassy behavior in a kagome Rydberg atom array
• Compiling Quantum Circuits for Dynamically Field-Programmable Neutral Atoms Array Processors
• Majorana Loop Models for Measurement-Only Quantum Circuits
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Quantum-Informed Recursive Optimization Algorithms
• Quantum Feature Maps for Graph Machine Learning on a Neutral Atom Quantum Processor
• Quantum-Enhanced Greedy Combinatorial Optimization Solver
• An entanglement perspective on the quantum approximate optimization algorithm
• Long-Lived Circular Rydberg Qubits of Alkaline-Earth Atoms in Optical Tweezers
• Optimal compression of quantum many-body time evolution operators into brickwall circuits
• Universal Quantum Computation in Globally Driven Rydberg Atom Arrays
• Rydberg blockade based parity quantum optimization
• Protocols for Rydberg entangling gates featuring robustness against quasi-static errors
• Randomized Benchmarking using Non-Destructive Readout in a 2D Atom Array
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Computational Capabilities and Compiler Development for Neutral Atom Quantum Processors: Connecting Tool Developers and Hardware Experts
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Number Partitioning with Grover's Algorithm in Central Spin Systems
• High-fidelity interconversion between Greenberger-Horne-Zeilinger and $W$ states through Floquet-Lindblad engineering in Rydberg atom arrays
• Hardness of the Maximum Independent Set Problem on Unit-Disk Graphs and Prospects for Quantum Speedups
• Comprehensive characterization of three-qubit Grover search algorithm on IBM's 127-qubit superconducting quantum computers
• Fault-tolerant quantum computation using large spin cat-codes
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Benchmarking digital quantum simulations above hundreds of qubits using quantum critical dynamics
• Quantum Computing Techniques for Multi-Knapsack Problems
• Designing Quantum Annealing Schedules using Bayesian Optimization
• An Empirical Comparison of Optimizers for Quantum Machine Learning with SPSA-based Gradients
• Scaling Advantage in Approximate Optimization with Quantum Annealing
• Analytical Framework for Quantum Alternating Operator Ansätze
• Trimer states with ${\mathbb{Z}}_3$ topological order in Rydberg atom arrays
• Accelerating the assembly of defect-free atomic arrays with maximum parallelisms
• Approaches to Constrained Quantum Approximate Optimization
• Demonstration of weighted graph optimization on a Rydberg atom array using local light-shifts
• Neutral atom entanglement using adiabatic Rydberg dressing
• Information processing at the speed of light
• Modular Parity Quantum Approximate Optimization
• Trimer quantum spin liquid in a honeycomb array of Rydberg atoms
• Circumventing superexponential runtimes for hard instances of quantum adiabatic optimization
• Quantum Computing Dataset of Maximum Independent Set Problem on King's Lattice of over Hundred Rydberg Atoms
• Preparation of Metrological States in Dipolar-Interacting Spin Systems
• Quantum pricing-based column-generation framework for hard combinatorial problems
• Extending relax-and-round combinatorial optimization solvers with quantum correlations
• Solving optimization problems with local light shift encoding on Rydberg quantum annealers
• Generalized Toffoli gate decomposition using ququints: Towards realizing Grover's algorithm with qudits
• Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms
• Solution of SAT Problems with the Adaptive-Bias Quantum Approximate Optimization Algorithm
• Enhancing variational Monte Carlo using a programmable quantum simulator
• Volume-entangled exact scar states in the PXP and related models in any dimension
• Quantum Programming of the Satisfiability Problem with Rydberg Atom Graphs
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Colloquium: Synthetic quantum matter in non-standard geometries
• Rydberg-atom graphs for quadratic unconstrained binary optimization problems
• Quantum slush state in Rydberg atom arrays
• Quantum Sampling Algorithms, Phase Transitions, and Computational Complexity
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Universal Quantum Optimization with Cold Atoms in an Optical Cavity
• SimuQ: A Framework for Programming Quantum Hamiltonian Simulation with Analog Compilation
• A blueprint for a Digital-Analog Variational Quantum Eigensolver using Rydberg atom arrays
• Parity Quantum Optimization: Encoding Constraints
• Functional completeness of planar Rydberg blockade structures
• Entangling quantum logic gates in neutral atoms via the microwave-driven spin-flip blockade
• Exploring Quantum Annealing Architectures: A Spin Glass Perspective
• An Optimization Case Study for solving a Transport Robot Scheduling Problem on Quantum-Hybrid and Quantum-Inspired Hardware
• Gauge theory description of Rydberg atom arrays with a tunable blockade radius
• Quantum dimer models with Rydberg gadgets
• Quantum adiabatic optimization with Rydberg arrays: localization phenomena and encoding strategies
• Evidence that PUBO outperforms QUBO when solving continuous optimization problems with the QAOA
• Opportunities and challenges of quantum computing for climate modelling
• Interspecies Förster resonances of Rb-Cs Rydberg $d$-states for enhanced multi-qubit gate fidelities
• Estimating the randomness of quantum circuit ensembles up to 50 qubits
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints
• Low-depth Clifford circuits approximately solve MaxCut
• Protocols for classically training quantum generative models on probability distributions
• Localized Virtual Purification
• Realization of programmable Ising models in a trapped-ion quantum simulator
• Leveraging Analog Quantum Computing with Neutral Atoms for Solvent Configuration Prediction in Drug Discovery
• Qudit Machine Learning
• Bias-field digitized counterdiabatic quantum optimization
• Quantum optimization within lattice gauge theory model on a quantum simulator
• Beyond Energy: Teleporting Current, Charge, and More
• Strong-to-weak Symmetry Breaking and Entanglement Transitions
• Finite-time scaling beyond the Kibble-Zurek prerequisite in Dirac systems
• Quantum-inspired optimization for wavelength assignment
• Improving the performance of quantum approximate optimization for preparing non-trivial quantum states without translational symmetry
• Digital-analog quantum convolutional neural networks for image classification
• Highly Efficient Encoding for Job-Shop Scheduling Problems and its Application on Quantum Computers
• The Coming Decades of Quantum Simulation
• Digital-analog quantum learning on Rydberg atom arrays
• A renewal approach to configurational entropy in one dimension
• A fiber array architecture for atom quantum computing
• Quantum Computing for Discrete Optimization: A Highlight of Three Technologies
• Equilibrium dynamics of infinite-range quantum spin glasses in a field
• Comparing the hardness of MAX 2-SAT problem instances for quantum and classical algorithms
• Two-qubit gate in neutral atoms using transitionless quantum driving
• A Rydberg-atom approach to the integer factorization problem
• Quantized Thouless pumps protected by interactions in dimerized Rydberg tweezer arrays
• Benchmarking Quantum Optimization for the Maximum-Cut Problem on a Superconducting Quantum Computer
• Exploring the neighborhood of 1-layer QAOA with Instantaneous Quantum Polynomial circuits
• Demonstration of Algorithmic Quantum Speedup for an Abelian Hidden Subgroup Problem
• Approaching Collateral Optimization for NISQ and Quantum-Inspired Computing
• Counterdiabatic Driving with Performance Guarantees
• Simulation of a feedback-based algorithm for quantum optimization for a realistic neutral atom system with an optimized small-angle controlled-phase gate
• Parameter-Parallel Distributed Variational Quantum Algorithm
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Symmetric quantum states: a review of recent progress
• Single-beam grating-chip 3D and 1D optical lattices
• Recurrent neural network wave functions for Rydberg atom arrays on kagome lattice
• Long-lived oscillations of metastable states in neutral atom systems
• Quantum gates between distant atoms mediated by a Rydberg excitation antiferromagnet
• Quantum tomography of Rydberg atom graphs by configurable ancillas
• Optimized QUBO formulation methods for quantum computing
• Quantum circuit compilation with quantum computers
• A numerical approach for calculating exact non-adiabatic terms in quantum dynamics
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• Long-range $CC\Phi$ gates via radio-frequency-induced Förster resonances
• Efficient and quantum-adaptive machine learning with fermion neural networks
• Quantum Natural Gradient optimizer on noisy platforms: QAOA as a case study
• Improving Quantum Approximate Optimization by Noise-Directed Adaptive Remapping
• Modelling noise in global Molmer-Sorensen interactions applied to quantum approximate optimization
• Nonequilibrium Critical Dynamics with Emergent Supersymmetry
• Alleviating the quantum Big-$M$ problem
• Two-photon Interface of Nuclear Spins Based on the Opto-Nuclear Quadrupolar Effect
• Multiphoton dressed Rydberg excitations in a microwave cavity with ultracold Rb atoms
• Compressed quantum error mitigation
• Robust Quantum Reservoir Computing for Molecular Property Prediction
• Observation of average topological phase in disordered Rydberg atom array
• Scheme to Detect the Strong-to-weak Symmetry Breaking via Randomized Measurements
• Relaxation Control of Open Quantum Systems
• Quantum Optimization on Rydberg Atom Arrays with Arbitrary Connectivity: Gadgets Limitations and a Heuristic Approach
• Universal quantum processors in spin systems via robust local pulse sequences
• Virtual mitigation of coherent non-adiabatic transitions by echo verification
• Implementing transferable annealing protocols for combinatorial optimisation on neutral atom quantum processors: a case study on smart-charging of electric vehicles
• Pitfalls of the sublinear QAOA-based factorization algorithm
• Maximum-Likelihood-Estimate Hamiltonian learning via efficient and robust quantum likelihood gradient
• The Role of Quantum Computing in Advancing Scientific High-Performance Computing: A perspective from the ADAC Institute
• Imaginary Hamiltonian variational ansatz for combinatorial optimization problems
• Scalable Parity Architecture With a Shuttling-Based Spin Qubit Processor
• Quantum dynamics of a fully-blockaded Rydberg atom ensemble
• Quantum annealing of Cayley-tree Ising spins at small scales
• Warm Start Adaptive-Bias Quantum Approximate Optimization Algorithm
• Learning topological states from randomized measurements using variational tensor network tomography
• Driven Critical Dynamics in Tricitical Point
• Hamilton-Jacobi-Bellman equations for Rydberg-blockade processes
• Approximating maximum independent set on Rydberg atom arrays using local detunings
• Optimal compression of constrained quantum time evolution
• Quantum Annealing with chaotic driver Hamiltonians
• Quantum ergodicity and scrambling in quantum annealers
• Quantum Scar States in Coupled Random Graph Models
• Optimization via Quantum Preconditioning
• Quantum eigenstate broadcasting assisted by a coherent link
• Spin-glass quantum phase transition in amorphous arrays of Rydberg atoms
• Microscopic dynamics and an effective Landau-Zener transition in the quasi-adiabatic preparation of spatially ordered states of Rydberg excitations
• Optimisation of ultrafast singlet fission in 1D rings towards unit efficiency
• Decoherence of a tunable capacitively shunted flux qubit
• Constraint-Aware Quantum Optimization via Hamming Weight Operators
• Expanding Hardware-Efficiently Manipulable Hilbert Space via Hamiltonian Embedding
• Approximate combinatorial optimization with Rydberg atoms: the barrier of interpretability
• Efimov Effect in Long-range Quantum Spin Chains
• Krylov Spread Complexity of Quantum-Walks
• Topological order in symmetric blockade structures
• Quantum Optimization Benchmarking Library - The Intractable Decathlon
• Random displacements in critical Rydberg atom arrays
• Supervised binary classification of small-scale digit images and weighted graphs with a trapped-ion quantum processor
• Engineering quantum states with neutral atoms
• Hardness-dependent quantum adiabatic schedules for the maximum-independent-set problem
• Escaping Local Minima with Quantum Coherent Cooling
• Macroproperties vs. Microstates in the Classical Simulation of Critical Phenomena in Quench Dynamics of 1D Ising Models
• Geometric phase and multipartite entanglement of Rydberg atom chains
• Generation of quantum phases of matter and finding a maximum-weight independent set of unit-disk graphs using Rydberg atoms
• Quantum Hamiltonian Algorithms for Maximum Independent Sets
• Dynamical transition in controllable quantum neural networks with large depth
• Simulating dynamics of the two-dimensional transverse-field Ising model: a comparative study of large-scale classical numerics
• Bulk and Boundary Quantum Phase Transitions in a Square Rydberg Atom Array
• Quantum Annealing Algorithms for Estimating Ising Partition Functions
• Spatiotemporal Quenches in Long-Range Hamiltonians
• Hamiltonian formulations of centroid-based clustering
• Qualifying quantum approaches for hard industrial optimization problems. A case study in the field of smart-charging of electric vehicles
• Consensus-based qubit configuration optimization for variational algorithms on neutral atom quantum systems
• Scaling corrections in driven critical dynamics: Application to a two-dimensional dimerized quantum Heisenberg model
• Graph Coloring via Quantum Optimization on a Rydberg-Qudit Atom Array
• Anti-crossings occurrence as exponentially closing gaps in Quantum Annealing
• Sub-universal variational circuits for combinatorial optimization problems
• Qubits on programmable geometries with a trapped-ion quantum processor
• Quantum-data-driven dynamical transition in quantum learning
• Continuous-wave quantum light control via engineered Rydberg-induced dephasing
• Continuous-wave all-optical single-photon transistor based on a Rydberg-atom ensemble
• Learning quantum symmetries with interactive quantum-classical variational algorithms
• Scalable Heteronuclear Architecture of Neutral Atoms Based on EIT
• A short review on the maximum clique problem algorithms with classical, AI, and quantum methods
• Effects of Topological Boundary Conditions on Bell Nonlocality
• Benchmarking a heuristic Floquet adiabatic algorithm for the Max-Cut problem
• Universal Relations in Long-range Quantum Spin Chains
• Resource-Efficient Quantum Optimization via Higher-Order Encoding
• Autonomously Designed Pulses for Precise, Site-Selective Control of Atomic Qubits
• Quantum imaginary time evolution and UD-MIS problem
• Doped resonating-valence-bond states: Robustness of the spin-ice phases in three-dimensional Rydberg arrays
• Solving the Turbine Balancing Problem using Quantum Annealing
• Engineering the non-Hermitian Su-Schrieffer-Heeger model with skin effects in Rydberg atom arrays
• Quantum combinatorial optimization beyond the variational paradigm: simple schedules for hard problems
• Q-CHOP: Quantum constrained Hamiltonian optimization
• All-to-all connectivity of Rydberg-atom-based quantum processors with messenger qubits
• Qubit-efficient quantum combinatorial optimization solver
• Transfer of quantum-enhanced information through a many-body system
• Quantum community detection via deterministic elimination
• Photon-Number Conserved Universal Quantum Logic Employing Continuous-Time Quantum Walk on Dual-Rail Qubit Arrays
• A quantum wire approach to weighted combinatorial graph optimisation problems
• Leveraging Analog Neutral Atom Quantum Computers for Diversified Pricing in Hybrid Column Generation Frameworks
• Symmetric $C_Z$ gate for ultracold neutral atoms based on counterdiabatic driving at Rydberg excitation
• Structural encoding with classical codes for computational-basis bit-flip correction in the early fault-tolerant regime
• Distinct many-body scars and emergent quantum phases driven by competing interactions in two-species Rydberg arrays