A Novel Solver for QUBO Problems: Performance Analysis and Comparative Study with State-of-the-Art Algorithms

• URL: http://arxiv.org/abs/2506.04596v1
• Date: Thu, 05 Jun 2025 03:22:48 GMT
• Title: A Novel Solver for QUBO Problems: Performance Analysis and Comparative Study with State-of-the-Art Algorithms
• Authors: Jiecheng Yang, Ding Wang, Xiang Zhao, Hairui Zhang, Ming Gao, Lin Yang,
• Abstract summary: We introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired strategies.<n>We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation.<n>Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances.
• Score: 18.408755407920744
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Quadratic Unconstrained Binary Optimization (QUBO) provides a versatile framework for representing NP-hard combinatorial problems, yet existing solvers often face trade-offs among speed, accuracy, and scalability. In this work, we introduce a quantum-inspired solver (QIS) that unites branch-and-bound pruning, continuous gradient-descent refinement, and quantum-inspired heuristics within a fully adaptive control architecture. We benchmark QIS3 against eight state-of-the-art solvers, including genetic algorithms, coherent Ising machines, simulated bifurcation, parallel tempering, simulated annealing, our prior QIS2 version, D-Wave's simulated-annealing (Neal), and Gurobi on three canonical QUBO problem classes: Max-Cut, NAE-3SAT, and Sherrington-Kirkpatrick spin glass problems. Under a uniform runtime budget, QIS3 attains the best solution on nearly all instances, achieving optimality in 94% of max-cut instances. These results establish QIS3 as a robust, high-performance solver that bridges classical exact strategies and quantum-inspired heuristics for scalable QUBO optimization.

Related papers

• 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)
• VeloxQ: A Fast and Efficient QUBO Solver [0.0]
  VeloxQ is a fast and efficient solver for Quadratic Unconstrained Binary Optimization problems.<n>We benchmark VeloxQ against the state-of-the-art QUBO solvers based on emerging technologies.
  arXiv  Detail & Related papers  (2025-01-31T15:27:50Z)
• Solving QUBOs with a quantum-amenable branch and bound method [0.3749861135832072]
  We describe and experimentally validate an exact classical branch and bound solver for quadratic unconstrained binary optimization problems. Our solver leverages cheap-to-implement bounds from the literature previously proposed for Ising models. We detail a variety of techniques from high-performance computing and operations research used to boost solver performance.
  arXiv  Detail & Related papers  (2024-07-29T17:13:01Z)
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA [1.5047640669285467]
  Quantum approximate optimization algorithm (QAOA) is one of the popular quantum algorithms that are used to solve optimization problems via approximations. However, performing QAOA on virtual quantum computers suffers from a slow simulation speed for solving optimization problems. We propose techniques to accelerate QCS for QAOA using mathematical optimizations to compress quantum operations.
  arXiv  Detail & Related papers  (2023-12-05T06:08:57Z)
• Polynomial-time Solver of Tridiagonal QUBO and QUDO problems with Tensor Networks [41.94295877935867]
  We present an algorithm for solving tridiagonal Quadratic Unconstrained Binary Optimization (QUBO) problems and Quadratic Unconstrained Discrete Optimization (QUDO) problems with one-neighbor interactions. Our method is based on the simulation of a quantum state to which we will apply an imaginary time evolution and perform a series of partial traces to obtain the state of maximum amplitude.
  arXiv  Detail & Related papers  (2023-09-19T10:45:15Z)
• Qubit efficient quantum algorithms for the vehicle routing problem on NISQ processors [48.68474702382697]
  Vehicle routing problem with time windows (VRPTW) is a common optimization problem faced within the logistics industry. In this work, we explore the use of a previously-introduced qubit encoding scheme to reduce the number of binary variables.
  arXiv  Detail & Related papers  (2023-06-14T13:44:35Z)
• Trainable Variational Quantum-Multiblock ADMM Algorithm for Generation Scheduling [0.0]
  This paper proposes a two-loop quantum solution algorithm for generation scheduling by quantum computing, machine learning, and distributed optimization. The aim is to facilitate noisy employing near-term quantum machines with a limited number of qubits to solve practical power system problems.
  arXiv  Detail & Related papers  (2023-03-28T21:31:39Z)
• 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)
• Q-FW: A Hybrid Classical-Quantum Frank-Wolfe for Quadratic Binary Optimization [44.96576908957141]
  We present a hybrid classical-quantum framework based on the Frank-Wolfe algorithm, Q-FW, for solving quadratic, linear iterations problems on quantum computers.
  arXiv  Detail & Related papers  (2022-03-23T18:00:03Z)
• 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)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Adiabatic Quantum Graph Matching with Permutation Matrix Constraints [75.88678895180189]
  Matching problems on 3D shapes and images are frequently formulated as quadratic assignment problems (QAPs) with permutation matrix constraints, which are NP-hard. We propose several reformulations of QAPs as unconstrained problems suitable for efficient execution on quantum hardware. The proposed algorithm has the potential to scale to higher dimensions on future quantum computing architectures.
  arXiv  Detail & Related papers  (2021-07-08T17:59: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.