Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10\% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees.
Neutral atom quantum computers (NAQCs) have emerged as a promising platform for solving the maximum weighted independent set (MWIS) problem. However, analog quantum approaches face two key limitations: constraints of the atomic layout on realizable graph geometries and the absence of performance guarantees. We introduce Lp-Quts, a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm. At each iteration, a relaxed linear program (RLP) bounds the MWIS and induces a reduced graph from which independent sets are sampled using an analog quantum sampler. A novel sample-informed separation problem guides odd-cycle cut selection and accelerates convergence. For t-perfect graphs, Lp-Quts inherits polynomial-time convergence guarantees from the classical theory of cutting planes. We evaluate our approach on instances with up to 300 vertices -- a scale that exceeds the capabilities of current NAQC hardware. In this regime, Lp-Quts reaches solutions within 5--10% of optimality, outperforming direct analog quantum protocols and greedy baselines under equal sampling budgets. As expected, simulated annealing remains the strongest sample-based solver at this scale. These results demonstrate how quantum samplers can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources while preserving formal guarantees.
Quadratic Unconstrained Binary Optimization (QUBO) problems are prevalent in real-world applications, such as portfolio optimization, but pose significant computational challenges for large-scale instances. We propose a hybrid quantum-classical framework that leverages neutral atom quantum computing to address QUBO problems by mapping them to the Maximum Weighted Independent Set (MWIS) problem on unit disk graphs. Our approach employs spatial grid partitioning to decompose the problem into manageable subgraphs, solves each subgraph using Analog Hamiltonian Simulation (AHS), and merges solutions greedily to approximate the global optimum. We evaluate the framework on a 50-asset portfolio optimization problem using historical S&P 500 data, benchmarking against classical simulated annealing. Results demonstrate competitive performance, highlighting the scalability and practical potential of our method in the Noisy Intermediate-Scale Quantum (NISQ) era. As neutral atom quantum hardware advances, our framework offers a promising path toward solving large-scale optimization problems efficiently.
We study the problem of emergency operation center placement in disaster response, where a minimal number of hubs must be selected to ensure timely coverage of all affected locations. This task can be formulated as a minimum dominating set problem on a graph encoding reachability within a target response time. We propose a hybrid quantum-classical approximation framework that leverages neutral-atom quantum computers as independent set samplers. Candidate dominating sets are constructed from both small maximal independent sets and complements of large independent sets, and are subsequently refined via a lightweight classical procedure. We benchmark the approach on synthetic instances and realistic case studies, and implement it on the Fresnel quantum processor by Pasqal, solving instances of up to 100 nodes. Our results show that quantum-generated samples, despite hardware noise, enable near-optimal solutions of the placement problem. Overall, our results demonstrate that neutral-atom devices operating in analog mode can already be used to tackle graph optimization problems for real-world applications.
In this work, we develop new pulse designs and embedding strategies to improve the analog quantum subroutines of hybrid column generation (CG) algorithms based on neutral-atoms quantum computers (NAQCs). These strategies are designed to improve the quality and diversity of the samples generated. We apply these to an important combinatorial optimization (CO) problem in logistics, namely the fleet assignment. Depending on the instance tested, our quantum protocol has a performance that is either comparable or worse than the best classical method tested, both in terms of the number of iterations and final objective value. We identify the cause of these suboptimal solutions as a result of our quantum protocol often generating high-quality but degenerate samples. We address this limitation by introducing a greedy post-processing technique, Make\_Diff, which applies bit-wise modifications to degenerate samples in order to return a non-degenerate set. With this modification, our quantum protocol becomes competitive with an exact solver for the subproblem, all the while being resilient to state preparation and measurements (SPAM) errors. We also compare our CG scheme with a Gurobi solver and find that it performs better on over 50\% of our synthetic instances and that, despite Gurobi having a more extensive runtime. These improvements and benchmarks herald the potential of deploying hybrid CG schemes on NISQ devices for industrially relevant CO problems.
Over the past decades, the operations research community has developed numerous effective optimization algorithms, yet quantum computing is emerging as a new computational paradigm with the potential to approach optimization problems more efficiently. Grover's algorithm offers a provable speedup for combinatorial optimization, but its circuit depth places it beyond current noisy intermediate-scale quantum (NISQ) devices. A more accessible alternative is to reformulate the optimization problem as a quadratic unconstrained binary optimization (QUBO) problem and apply quantum annealing; however, practical problem instances remain out of reach for existing hardware. We introduce AtomTreeSearch, a hybrid classical-quantum algorithm that integrates a quantum subroutine natively implementable on neutral-atom quantum computers within a Monte Carlo Tree Search framework. At each expansion step, a maximal weighted independent set of candidate actions provided by the quantum processor is selected, and these collective actions are performed to obtain a child node. We benchmark our method on the Traveling Salesman Problem, with instances of up to 60 cities on random Euclidean instances and up to 100 cities on TSPLIB instances. Our hybrid algorithm generally matches or outperforms both OR-Tools and simulated annealing on these instances, and we find that the quantum subroutine produces more diverse and higher-quality branches compared to classical alternate subroutines. These results suggest that carefully scoped quantum subroutines embedded in classical search frameworks represent a promising path toward near-term quantum utility in combinatorial optimization.
Neutral atom arrays provide a versatile platform to implement coherent quantum annealing as an approach to solving hard combinatorial optimization problems. Here we present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms, which we call quantum wires, to natively embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture. For graphs with quasi-unit-disk connectivity, in which only a few long-range edges are required, our approach requires a significantly lower overhead in the number of ancilla qubits than previous proposals, facilitating the implementation on currently available hardware. To demonstrate the approach, we perform annealing of weighted graphs on a programmable atom array using local light shifts to encode problem-specific weights across graphs of varying sizes. This approach successfully identifies the solutions to the original MWIS and QUBO graph instances. Our work expands the operational toolkit of near-term neutral atom arrays, enhancing their potential for scalable quantum optimization.
Neutral atom quantum computers (NAQC) are emerging as a promising, scalable quantum computing platform because of their long qubit coherence, flexible qubit arrangement, and multiqubit gate capabilities. However, circuit execution often requires physically moving qubits, making compilation a critical optimization challenge. We propose a circuit independent mathematical framework built on graph-theoretic combinatorial optimization that determines the minimal number of required qubit transfers. This model captures spatial constraints specific to NAQC platforms with zone-limited gate operations and multi-qubit gates. From this framework, we encode the qubit mapping problem as a nonlinear integer program and solve it using a genetic algorithm, enabling trade-offs between minimizing the total traveled distance and the number of parallel transfer operations. Compared to the state-of-the-art scalable compiler for zoned architectures, our approach consistently finds fewer transfers. Depending on the optimization focus, our method produces shorter traveled distances or fewer parallel transfer operations. This work provides both theoretical guaranties and a practical tool for efficient, architecture-aware quantum circuit compilation. As a result, practitioners can generate hardware-aware mappings that reduce movement-induced errors and better exploit atom transfer parallelism, directly improving execution efficiency on NAQC devices.