Grid-Partitioned MWIS Solving with Neutral Atom Quantum Computing for QUBO Problems

• URL: http://arxiv.org/abs/2510.18540v2
• Date: Wed, 05 Nov 2025 03:51:29 GMT
• Title: Grid-Partitioned MWIS Solving with Neutral Atom Quantum Computing for QUBO Problems
• Authors: Soumyadip Das, Suman Kumar Roy, Rahul Rana, M Girish Chandra,
• Abstract summary: 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.
• Score: 0.6649512409446104
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Quantum Optimization in Loc(Q)ation Science: QUBO Formulations, Benchmark Problems, and a Computational Study [0.0]
  Quadratic Unconstrained Binary Optimization provides a unifying modeling framework for a broad class of $mathbfNP$-hard problems.<n>We develop QUBO formulations for several fundamental problems in location science, network design, and logistics.<n>These QUBO formulations serve as representative benchmark problems for assessing quantum algorithms and quantum hardware.
  arXiv  Detail & Related papers  (2026-02-11T15:39:26Z)
• An Introduction to the Quantum Approximate Optimization Algorithm [51.56484100374058]
  The tutorial begins by outlining variational quantum circuits and QUBO problems.<n>Next, it explores the QAOA in detail, covering its Hamiltonian formulation, gate decomposition, and example applications.<n>The tutorial extends these concepts to higher-order Hamiltonians and discussing the associated symmetries and circuit construction.
  arXiv  Detail & Related papers  (2025-11-23T09:54:20Z)
• Scalable Quantum Optimisation using HADOF: Hamiltonian Auto-Decomposition Optimisation Framework [0.0]
  Quantum Annealing (QA) and QAOA are promising quantum optimisation algorithms used for finding approximate solutions to problems on near-term NISQ systems.<n>We present the Hamiltonian Auto-Decomposition optimisation Framework (HADOF), which leverages an iterative strategy to automatically divide the Quadratic Unconstrained Binary optimisation (QUBO) Hamiltonian into sub-Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-03T11:54:41Z)
• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds.<n>We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Max-Cut graph-driven quantum circuit design for planar spin glasses [0.0]
  We present a graph-based approach for finding the ground state of spin glasses.<n>We employ a clustering strategy that organizes qubits into distinct groups based on the maximum cut technique.<n>Our results underscore the potential of hybrid quantum-classical methods in addressing complex optimization problems.
  arXiv  Detail & Related papers  (2025-04-16T14:00:32Z)
• 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)
• A Quantum Genetic Algorithm Framework for the MaxCut Problem [49.59986385400411]
  The proposed method introduces a Quantum Genetic Algorithm (QGA) using a Grover-based evolutionary framework and divide-and-conquer principles.<n>On complete graphs, the proposed method consistently achieves the true optimal MaxCut values, outperforming the Semidefinite Programming (SDP) approach.<n>On ErdHos-R'enyi random graphs, the QGA demonstrates competitive performance, achieving median solutions within 92-96% of the SDP results.
  arXiv  Detail & Related papers  (2025-01-02T05:06:16Z)
• Solving the Turbine Balancing Problem using Quantum Annealing [0.0]
  We describe how the Turbine Balancing Problem can be solved with quantum computing. Small yet relevant instances occur in industry, which makes the problem interesting for early quantum computing benchmarks.
  arXiv  Detail & Related papers  (2024-05-10T11:52:40Z)
• A Hybrid Quantum-Classical Approach to the Electric Mobility Problem [0.8796261172196743]
  We suggest a hybrid quantum-classical routine for the NP-hard Electric Vehicle Fleet Charging and Allocation Problem. We benchmark the performance of the decomposition technique with classical and quantum-inspired metaheuristics. The major advantage of the proposed approach is that it enables quantum-based methods for this realistic problem with many inequality constraints.
  arXiv  Detail & Related papers  (2023-10-04T12:14:56Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays [39.76254807200083]
  We experimentally investigate quantum algorithms for solving the Maximum Independent Set problem. We find the problem hardness is controlled by the solution degeneracy and number of local minima. On the hardest graphs, we observe a superlinear quantum speedup in finding exact solutions.
  arXiv  Detail & Related papers  (2022-02-18T19:00:01Z)
• 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)

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.