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.

arXiv comment10 pages, 5 figures, Supplementary materials at the end

References in corpus (36)

• The density-matrix renormalization group in the age of matrix product states
• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Dipole Blockade and Quantum Information Processing in Mesoscopic Atomic Ensembles
• Adiabatic Quantum Computing
• Quantum Phases of Matter on a 256-Atom Programmable Quantum Simulator
• Probing Topological Spin Liquids on a Programmable Quantum Simulator
• Dynamics of a Quantum Phase Transition
• Programmable quantum simulation of 2D antiferromagnets with hundreds of Rydberg atoms
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Spin-lattice coupling in frustrated antiferromagnets
• Quantum Search by Local Adiabatic Evolution
• Defining and detecting quantum speedup
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• Efficient Z-Gates for Quantum Computing
• Universal adiabatic dynamics across a quantum critical point
• Simulating quantum computation by contracting tensor networks
• Quantum Approximate Optimization of Non-Planar Graph Problems on a Planar Superconducting Processor
• From density-matrix renormalization group to matrix product states
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Quantum Simulations of Classical Annealing Processes
• First order phase transition in the Quantum Adiabatic Algorithm
• 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
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Training A Quantum Optimizer
• Kibble-Zurek mechanism and infinitely slow annealing through critical points
• Tropical Tensor Network for Ground States of Spin Glasses
• Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
• Quantum Sampling Algorithms for Near-Term Devices
• Distribution of Kinks in an Ising Ferromagnet After Annealing and the Generalized Kibble-Zurek Mechanism
• Kibble-Zurek Scaling and String-Net Coarsening in Topologically Ordered Systems

Cited by in corpus (235)

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