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.
Quantum Optimization for Maximum Independent Set Using Rydberg Atom Arrays
7 Pith papers cite this work. Polarity classification is still indexing.
7
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
verdicts
UNVERDICTED 7roles
background 1polarities
background 1representative citing papers
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.
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.
citing papers explorer
-
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.
-
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.