Emergency hub placement with a neutral-atom quantum computer

• URL: http://arxiv.org/abs/2606.19589v1
• Date: Wed, 17 Jun 2026 20:45:17 GMT
• Title: Emergency hub placement with a neutral-atom quantum computer
• Abstract summary: We study the problem of emergency operation center placement in disaster response.<n>A minimal number of hubs must be selected to ensure timely coverage of all affected locations.<n>We propose a hybrid quantum-classical approximation framework that leverages neutral-atom quantum computers as independent set samplers.
• Score: 7.106206192312008
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Iterative Optimization with Partial Convergence Guarantees on Neutral Atom Quantum Computers [0.0]
  Lp-Quts is a hybrid quantum-classical framework that integrates an NAQC sampler into a classical cutting-plane algorithm.<n>We show how Lp-Quts can be effectively embedded within classical optimization frameworks to deliver near-optimal solutions with reduced quantum resources.
  arXiv  Detail & Related papers  (2026-03-30T19:12:21Z)
• A Scalable Distributed Quantum Optimization Framework via Factor Graph Paradigm [46.08923284345648]
  We introduce a structure-aware framework for distributed quantum optimization.<n>We find that for a search space of size $N$, our framework achieves $O(sqrtN)$ query complexity up to processors and separator dependent factors.<n>We show that structure-aware decomposition delivers a practical path to scalable distributed quantum optimization on quantum networks.
  arXiv  Detail & Related papers  (2026-03-08T15:15:52Z)
• A quantum feasibility preserving modeling for the min cut problem [1.3701366534590498]
  We study the minimum cut problem in weighted undirected graphs using variational quantum algorithms.<n>We employ a ring structured XY mixer that restricts the quantum evolution to the subspace of valid cut configurations.
  arXiv  Detail & Related papers  (2026-02-26T12:34:59Z)
• Drone delivery packing problem on a neutral-atom quantum computer [7.106206192312008]
  We address the Drone Delivery Packing Problem via a hybrid quantum-classical framework leveraging a neutral-atom quantum processing unit (QPU)<n>We reformulate the optimization task as a graph-partitioning problem based on the independent sets (ISs) of a scheduling graph that encodes delivery incompatibilities.<n>While the ISs represent time-feasible schedules, battery-duration constraints are enforced through a classical post-processing routine.
  arXiv  Detail & Related papers  (2026-02-17T10:52:10Z)
• Grid-Partitioned MWIS Solving with Neutral Atom Quantum Computing for QUBO Problems [0.6649512409446104]
  We propose a hybrid quantum-classical framework to address Quadratic Unconstrained Binary Optimization problems.<n>Our framework offers a promising path toward solving large-scale optimization problems efficiently.
  arXiv  Detail & Related papers  (2025-10-21T11:36:13Z)
• A quantum wire approach to weighted combinatorial graph optimisation problems [0.0]
  We present and experimentally demonstrate an efficient encoding scheme based on chains of Rydberg-blockaded atoms.<n>We embed maximum weighted independent set (MWIS) and quadratic unconstrained binary optimization (QUBO) problems on a neutral atom architecture.
  arXiv  Detail & Related papers  (2025-03-21T13:00:51Z)
• Optimizing random local Hamiltonians by dissipation [44.99833362998488]
  We prove that a simplified quantum Gibbs sampling algorithm achieves a $Omega(frac1k)$-fraction approximation of the optimum. Our results suggest that finding low-energy states for sparsified (quasi)local spin and fermionic models is quantumly easy but classically nontrivial.
  arXiv  Detail & Related papers  (2024-11-04T20:21:16Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• Industry applications of neutral-atom quantum computing solving independent set problems [39.58317527488534]
  We show how to encode independent set problems in Rydberg Hamiltonians. We outline the major classes of independent set problems and include associated example applications with industry and social relevance. We determine a wide range of sectors that could benefit from efficient solutions of independent set problems.
  arXiv  Detail & Related papers  (2022-05-17T17:13:20Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• A Hybrid Quantum-Classical Algorithm for Robust Fitting [47.42391857319388]
  We propose a hybrid quantum-classical algorithm for robust fitting. Our core contribution is a novel robust fitting formulation that solves a sequence of integer programs. We present results obtained using an actual quantum computer.
  arXiv  Detail & Related papers  (2022-01-25T05:59:24Z)
• Quantum Robust Fitting [43.28199403216451]
  Many computer vision applications need to recover structure from imperfect measurements of the real world. The task is often solved by robustly fitting a geometric model onto noisy and outlier-contaminated data. In this paper, we explore the usage of quantum computers for robust fitting.
  arXiv  Detail & Related papers  (2020-06-12T08:00:55Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.