A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
12 Pith papers cite this work. Polarity classification is still indexing.
12
Pith papers citing it
abstract
We describe and analyze an architecture for quantum optimization to solve maximum independent set (MIS) problems using neutral atom arrays trapped in optical tweezers. Optimizing independent sets is one of the paradigmatic, NP-hard problems in computer science. Our approach is based on coherent manipulation of atom arrays via the excitation into Rydberg atomic states. Specifically, we show that solutions of MIS problems can be efficiently encoded in the ground state of interacting atoms in 2D arrays by utilizing the Rydberg blockade mechanism. By studying the performance of leading classical algorithms, we identify parameter regimes, where computationally hard instances can be tested using near-term experimental systems. Practical implementations of both quantum annealing and variational quantum optimization algorithms beyond the adiabatic principle are discussed.
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
A graph-theoretic method systematically constructs quantum many-body scars in frustrated Rydberg lattices via type-I and type-II mechanisms, with numerical demonstration of an exponential family of scarred trajectories on the hexagonal lattice.
A harness for AI agents enabled construction of a Rust library with 100+ problem types and 200+ reduction rules for NP-hard problems in three months.
Engineered local Hamiltonian controls in Rydberg arrays accelerate adiabatic convergence to MIS solutions, raise success probabilities over global controls, and cut fidelity decay rate by 25% as graphs harden.
Demonstrates a quantum wire encoding using Rydberg atom chains to solve MWIS and QUBO problems on neutral atom arrays with reduced ancilla overhead and experimental validation.
A compact xor_1 gadget enforces exactly-one constraints on Rydberg arrays via fixed-detuning blockade, cutting detuning range by up to 99% and atom/connectivity overhead by up to 54% versus QUBO for gate assignment and N-queens.
A Möbius-inversion compiler that preserves native multiqubit controlled-phase gates improves estimated success rates for diagonal circuits on neutral-atom hardware.
Hybrid quantum-classical framework uses neutral-atom devices as independent set samplers to solve minimum dominating set instances up to 100 nodes for emergency hub placement.
The paper proposes identifying quantum advantage with the existence of a polynomial-in-n upper bound on the minimal time to achieve operator controllability for bilinear quantum control systems on SU(N).
Literary texts are turned into graphs for neutral-atom quantum processors, with a new rigidity metric distinguishing structural uniqueness and a QOuLiPo corpus of engineered texts created to match hardware-native graphs.
Classical kernelisation fully reduces many small and sparse unit-disk graphs for MIS and MWIS native to Rydberg arrays, but dense graphs retain finite irreducible kernels, with vertex weights increasing reducibility and extended interaction ranges suppressing it.
Defines an entanglement-structure factor from Fourier analysis of site concurrences and compares it to local-density order parameters for Z_n transitions in Rydberg chains.
citing papers explorer
-
A Machine-Verified Proof of a Quantum-Optimization Conjecture
A Lean 4 machine-verified proof establishes that depth-p QAOA on the ring of disagrees attains approximation ratio (2p+1)/(2p+2) exactly.
-
Systematic construction of quantum many-body scars in frustrated Rydberg arrays
A graph-theoretic method systematically constructs quantum many-body scars in frustrated Rydberg lattices via type-I and type-II mechanisms, with numerical demonstration of an exponential family of scarred trajectories on the hexagonal lattice.
-
Problem Reductions at Scale: Agentic Integration of Computationally Hard Problems
A harness for AI agents enabled construction of a Rust library with 100+ problem types and 200+ reduction rules for NP-hard problems in three months.
-
Efficient Hamiltonian Engineering for Adiabatic MIS Algorithms
Engineered local Hamiltonian controls in Rydberg arrays accelerate adiabatic convergence to MIS solutions, raise success probabilities over global controls, and cut fidelity decay rate by 25% as graphs harden.
-
A quantum wire approach to weighted combinatorial graph optimisation problems
Demonstrates a quantum wire encoding using Rydberg atom chains to solve MWIS and QUBO problems on neutral atom arrays with reduced ancilla overhead and experimental validation.
-
Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms
A compact xor_1 gadget enforces exactly-one constraints on Rydberg arrays via fixed-detuning blockade, cutting detuning range by up to 99% and atom/connectivity overhead by up to 54% versus QUBO for gate assignment and N-queens.
-
M\"obius-Guided Diagonal-Gate Compilation with Native Multiqubit Controlled-Phase Gates on Neutral-Atom Processors
A Möbius-inversion compiler that preserves native multiqubit controlled-phase gates improves estimated success rates for diagonal circuits on neutral-atom hardware.
-
Emergency hub placement with a neutral-atom quantum computer
Hybrid quantum-classical framework uses neutral-atom devices as independent set samplers to solve minimum dominating set instances up to 100 nodes for emergency hub placement.
-
Towards a Control interpretation of Quantum Advantage
The paper proposes identifying quantum advantage with the existence of a polynomial-in-n upper bound on the minimal time to achieve operator controllability for bilinear quantum control systems on SU(N).
-
QOuLiPo: What a quantum computer sees when it reads a book
Literary texts are turned into graphs for neutral-atom quantum processors, with a new rigidity metric distinguishing structural uniqueness and a QOuLiPo corpus of engineered texts created to match hardware-native graphs.
-
Reducibility of native weighted graphs on Rydberg Arrays
Classical kernelisation fully reduces many small and sparse unit-disk graphs for MIS and MWIS native to Rydberg arrays, but dense graphs retain finite irreducible kernels, with vertex weights increasing reducibility and extended interaction ranges suppressing it.
-
Entanglement Structure Across $\mathbb{Z}_n$ Phase Transitions in 1D Rydberg Atom Arrays
Defines an entanglement-structure factor from Fourier analysis of site concurrences and compares it to local-density order parameters for Z_n transitions in Rydberg chains.