Source-linked AI summary
Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
Sepehr Ebadi, Alexander Keesling, Madelyn Cain, Tout T. Wang, Harry Levine, Dolev Bluvstein, Giulia Semeghini, Ahmed Omran, Jinguo Liu, Rhine Samajdar, Xiu-Zhe Luo, Beatrice Nash, Xun Gao, Boaz Barak, Edward Farhi, Subir Sachdev, Nathan Gemelke, Leo Zhou, Soonwon Choi, Hannes Pichler, Shengtao Wang, Markus Greiner, Vladan Vuletic, Mikhail D. Lukin
TL;DR
The paper asks whether programmable Rydberg atom arrays can optimize computationally hard MIS instances and provide quantum speedup. It encodes MIS through Rydberg blockade, optimizes variational evolutions in a closed loop, and compares them with simulated annealing. The study relates hardness to degeneracy and local minima and reports a superlinear speedup for exact solutions on the hardest graphs.
Problem
The paper addresses whether quantum machines can accelerate practically relevant optimization of NP-hard Maximum Independent Set instances.
Method
The experiment encodes MIS in Rydberg atom arrays and compares optimized variational quantum evolution with classical simulated annealing.
Results
On the hardest graphs, the experiment observes a superlinear quantum speedup in finding exact solutions in the deep-circuit regime.
Takeaways & Limitations
Solution degeneracy and local-minimum structure provide supported indicators of optimization hardness, while delocalized quantum states can enable speedup over simulated annealing.
Takeaways & Limitations
QAOA performance is limited by parameter-optimization difficulty, finite measurement budgets, blockade violations, and leakage from the independent-set subspace.
Abstract
from arXiv · showhide
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.
Supplementary Materials
A planar graph with maximum degree 3 is transformed into a unit disk graph through grid embedding and even-length chain construction.
- The procedure embeds a maximum-degree-3 planar graph on a square grid without edge crossings.
- The embedded graph is reduced to a unit disk graph using a finer square lattice and unit disk radius 2a.
- Grid-chain deformations ensure that each chain connecting original vertices contains an even number of vertices.
1. NP-COMPLETENESS OF ENCODED GRAPHS
The encoded nearest- and next-nearest-neighbor graphs support NP-complete MIS decision problems through a reduction from planar maximum-degree-3 graphs.
- The MIS decision problem is NP-complete for graphs encoded on the simulator’s square lattice with nearest and diagonal edges.
- Diagonal connections are essential because removing them produces bipartite graphs for which MIS is not NP-complete.
- The reduction transforms a planar maximum-degree-3 graph G into a target graph G′ while preserving the existence of an independent set above a corresponding threshold.
- Each original edge is replaced by an even-length path of ancillary vertices placed on a finer square grid.
- The construction uses a finer grid with lattice spacing a = g/12 for placing ancillary vertices.
2. EXPERIMENTAL PLATFORM
The experiment encodes unit disk MIS instances in programmable two-dimensional Rydberg arrays, then uses readout post-processing and several figures of merit to evaluate solutions.
- Hardware-efficient encoding: Neutral ^87Rb atoms in optical-tweezer arrays are driven between ground and 70S1/2 Rydberg states for programmable quantum evolution.
- Hardware-efficient encoding: The evolution is controlled by time-varying Rabi frequency, phase, and detuning, with fixed long-range Rydberg interactions.
- Hardware-efficient encoding: The laser-parameter table relates two-photon couplings and intermediate detuning to the effective Rabi frequency and scattering timescale.
- Hardware-efficient encoding: A lattice constant of a = 4.5 µm gives Rb/a = 1.7 for the experimental blockade radius.
- Data post-processing: Readout detects Rydberg excitations through absent fluorescence, so atom loss and excitation can be indistinguishable.
- Data post-processing: Vertex reduction removes blockade violations, while vertex addition greedily extends valid independent sets to maximal ones.
- Data post-processing: The reported metrics include approximation ratio R, top-half ratio R0.5, exact-solution probability PMIS, and normalized Hamming distance.
- Data post-processing: Vertex addition produces a constant-factor improvement in approximation error and MIS probability with little effect on time-scaling.
3. CLOSED LOOP QUANTUM-CLASSICAL OPTIMIZATION
The experiment optimizes parameterized laser pulses in a closed quantum-classical loop, comparing classical optimizers and post-processing effects for QAOA-style searches.
- Closed-loop optimization: A classical optimizer selects time-varying laser pulses whose parameters implement QAOA or VQAA on a target graph.
- Closed-loop optimization: The optimization loop balances measurement-shot projection noise against the number of iterations available within the experimental time budget.
- Classical optimizers: Local gradient-based optimizers perform better when measurement resources are limited and the variational landscape becomes complex.
- Classical optimizers: Adam and AdaBound work best empirically, with AdaBound ultimately used for the reported closed-loop data.
- Post-processing: Post-selection on perfect rearrangement slightly improves performance, whereas limiting vertex reductions provides negligible additional benefit.
- QAOA optimization: QAOA depth p = 2 direct searches vary the second pulse phase and scan pulse times, while classical optimization achieves comparable results with fewer quantum-machine queries.
4. QUANTUM APPROXIMATE OPTIMIZATION ALGORITHM (QAOA)
The Rydberg-array QAOA replaces conventional single-qubit rotations with blockade-constrained many-body evolution and phase-based cost operations. Performance saturates beyond depth p = 4 because parameter optimization, blockade leakage, and pulse imperfections limit deeper circuits.
- QAOA formulation: QAOA uses p layers of evolution under non-commuting mixing and cost Hamiltonians with 2p variational parameters.The standard formulation uses parameters (γ1,...,γp) and (β1,...,βp).
- Rydberg implementation: In the Rydberg implementation, resonant laser pulses realize blockade-constrained mixing, while phase jumps implement global cost-function rotations.Pulse durations τi and phases φi serve as the variational parameters.
- Performance limitations: Higher-depth QAOA becomes difficult to optimize because the parameter count grows while experimental queries provide limited objective and gradient precision.The quasi-adiabatic algorithm is easier to optimize at longer effective depths because it uses fewer parameters.
- Performance limitations: Finite next-nearest-neighbor interactions cause blockade violations and leakage from the independent-set subspace, worsening QAOA performance relative to ideal blockade.The comparison is shown numerically for a small N = 24-vertex graph after vertex-reduction post-processing.
- Performance limitations: Acousto-optic-modulator phase changes can briefly reduce laser intensity, introducing pulse imperfections through phase–intensity cross-talk.The reported intensity reduction lasts approximately 10 ns.
5. VARIATIONAL QUANTUM ADIABATIC ALGORITHM (VQAA)
VQAA optimizes a quasi-adiabatic detuning path from a trivial initial ground state to a solution-encoding final Hamiltonian. A three-segment piecewise-linear sweep is generally nearly optimal, while additional manual optimization improves MIS probability on the hardest graphs.
- VQAA formulation: VQAA optimizes a detuning profile ∆(t) that interpolates from an initial trivial-ground-state Hamiltonian to a final solution Hamiltonian.The profile is piecewise linear and includes ramping and low-pass filtering parameters.
- Experimental parametrization: The piecewise-linear sweep is parameterized by segment durations, end detunings, initial detuning, filtering time, and coupling ramp times.The implementation uses 2f +3 variational parameters.
- Optimization: For f = 3 segments, optimization starts from a purely linear sweep and produces an optimized sweep at fixed duration T = 1.25 µs.The fixed-duration pulse corresponds to effective depth p̃ = 10 before rescaling.
- Performance: The same three-segment sweep gives nearly optimal approximation-error performance on most graphs.The optimized pulse shape is reused across graphs in the time-scaling experiments.
- Performance: Additional manual optimization increases PMIS for the hardest graphs studied.The supplementary cubic-spline family varies the inflection-point frequency while preserving starting and ending detunings and minimum slope.
- Graph characterization: Tensor networks are used to characterize the programmable graphs associated with the atom-array experiments.The graph is mapped to a tensor network whose indices and tensors encode connectivity.
6. CHARACTERIZING GRAPHS USING TENSOR NETWORK ALGORITHMS
Generic tensor-network contractions characterize graph structure by computing independent-set properties, including MIS size and degeneracies. Applied to randomly generated 80%-filled lattices, the method reaches N = 1095 and reveals broad, apparently exponential worst-case scaling.
- Method: The tensor-network method computes MIS size, MIS degeneracy, lower-size independent-set degeneracy, total independent sets, and the independence polynomial.These graph properties are obtained by adapting tensor-network contraction to different tensor element types.
- Independence polynomial: The independence polynomial’s coefficient Di gives the degeneracy of independent sets of size i, including D|MIS| and D|MIS|−1.Vertex tensors contribute x or 1, while edge tensors enforce the independence constraint through B11 = 0.
- Computational implementation: Contraction-order optimization enables efficient calculations on graphs with small tree width, while symbolic calculations are slower.Changing tensor element types can substantially accelerate selected computations.
- Computational implementation: Tropical algebra can replace ordinary tensor arithmetic when only the MIS size is required.The replacement uses max for addition and ordinary addition for multiplication.
- Scaling analysis: The method computes degeneracies for graphs up to N = 1095, corresponding to an 80%-filled 37 × 37 lattice.At each size, 1000 random graphs are generated for scaling analysis.
- Scaling analysis: For large N, worst-case MIS degeneracy and hardness parameter HP appear to scale exponentially, with wide instance-to-instance variation.The hardness parameter is HP = D|MIS|−1/(|MIS|D|MIS|).
7. SCALING OF QUANTUM APPROXIMATION ERROR
The scaling theory models MIS defects as conflicts between independently ordered domains whose correlation length grows with evolution time. It explains power-law error reduction and predicts that higher degeneracy density improves approximation and changes effective time-scaling.
- Basic formalism: The theory assumes correlated regions grow after the quantum critical point as R(t) ∼ t^µ.The growth exponent and prefactor reflect quantum Kibble–Zurek dynamics and coarsening processes.
- Basic formalism: Defects arise at boundaries where independently formed domains meet and their local orderings conflict.The number of domains is N(t) ≡ A/(πR^2(t)).
- Scaling prediction: The resulting approximation error decays as a power law with total sweep time, consistent with the experimental dependence.The proposed healing process involves long domain walls and bulk gapped quasiparticles.
- Degeneracy of MIS states: Degeneracy primarily originates from one-dimensional graph regions, including linear structures created by holes in an otherwise filled lattice.The average hole spacing is ζ = 2/√(πρ), used as the characteristic string length.
- Degeneracy of MIS states: When protodomains coalesce, strings crossing their interface multiply the available configurations, producing a degeneracy estimate that depends on interface length and regional degeneracies.The estimate is di,j ≃ (ζ)^γℓ δiδj.
- Scaling with degeneracy: Higher degeneracy provides more ways for independently seeded domains to merge without generating a domain wall, making such graphs generically easier to solve.This mechanism connects MIS degeneracy to the correction term in the defect-density scaling.
- Scaling with degeneracy: At fixed time, approximation error decreases linearly with degeneracy density ρ = (log D|MIS|)/N, while the slope becomes more negative with increasing T at short depths.For varying sweep times, the effective power-law exponent α increases with ρ.
- Classical comparison: A similar mechanism may apply to simulated annealing, but with different exponents.This extension is presented as a potential analogy rather than an established identity of mechanisms.
8. SIMULATED ANNEALING
The study benchmarks optimized simulated annealing variants for MIS, analyzing how update rules, energy penalties, temperature schedules, and graph structure affect performance.
- Markov-chain properties: The Markov chains are designed to be ergodic and satisfy detailed balance, yielding a unique stationary distribution and convergence at long times.At low temperature, the stationary distribution approaches a uniform mixture of MISs.
- Algorithm: SA initializes all vertices outside the independent set, proposes local updates, accepts them through Metropolis-Hastings, and gradually lowers the temperature.The algorithm depth pSA is the average number of attempted updates per spin.
- Algorithm: MIS SA uses vertex additions, removals, neighboring spin exchanges, and no-update proposals, with transition probabilities controlled by ϵ.The maximum degree is eight for the studied unit-disk graphs, ensuring non-negative no-update probability.
- Dynamics: The dynamics slow when both the edge penalty α and removal probability ϵ are large or small, while large α with small ϵ enables fast spin exchanges.Domain-wall propagation therefore depends jointly on energetic penalties and proposal probabilities.
- Hardness: α = 1 with intermediate or small ϵ exposes more low-energy non-MIS states, increasing local minima relative to global minima and making optimization harder.These states include configurations of sizes |MIS| and |MIS| −1 with limited blockade violations.
- Benchmarking: As degeneracy density decreases, both SA variants require increasingly long runtimes to reach a fixed approximation ratio compared with the experiment.This comparison covers 115 instances spanning N = 39–231, including randomly selected and hardest graphs.
9. SCALING OF QUANTUM AND CLASSICAL MIS PROBABILITY
Classical MIS search becomes hardness-limited through its Markov-chain gap and hitting time, whereas quantum scaling depends on adiabatic gaps and low-energy-state structure. The proposed quantum advantage requires sufficiently deep evolution and favorable delocalization.
- Classical scaling: The MIS SA spectral gap is bounded by O(poly(N)HP^-1), implying an expected hitting-time lower bound of Ω(HP).The bound assumes a stationary distribution polynomially close to the Gibbs distribution and applies to reversible, lazy, ergodic chains.
- Classical scaling: At low temperature, MIS SA converges toward a stationary distribution that becomes a uniform mixture of MISs, with spectral-gap-controlled convergence.The Markov-chain gap therefore directly controls the probability of finding an exact solution as depth increases.
- Quantum scaling: For a hard-blockade model, the inverse quantum gap correlates with HP, consistent with gap ∼1/HP, while removing longer-range interactions often enlarges the gap.The intermediate model retains nearest- and next-nearest-neighbor interactions but removes longer-range tails.
- Quantum scaling: A Grover-like quantum speedup would require a minimum gap scaling as O(poly(1/N)HP^-1/2), but the reported numerics do not establish this scaling.The proposed mechanism involves coherent coupling among delocalized low-energy independent-set states.
- Quantum scaling: The quantum gap can receive coherent enhancement when low-energy eigenstates are delocalized across MIS configurations and connected by the driver.The enhancement depends on overlaps between asymptotic Landau-Zener states and driver-accessible nonmaximal independent sets.