Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers

• URL: http://arxiv.org/abs/2502.16212v1
• Date: Sat, 22 Feb 2025 12:29:52 GMT
• Title: Clustering-Based Sub-QUBO Extraction for Hybrid QUBO Solvers
• Authors: Wending Zhao, Gaoxiang Tang,
• Abstract summary: Quantum Approximate Optimization Algorithm (QAOA) can be used to solve quadratic unconstrained binary optimization (QUBO) problems.<n>To leverage noisy intermediate-scale quantum (NISQ) devices to solve large-scale QUBO problems, one possible way is to decompose the full problem into multiple sub-problems.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Quantum Approximate Optimization Algorithm (QAOA) can be used to solve quadratic unconstrained binary optimization (QUBO) problems. However, the size of the solvable problem is limited by the number of qubits. To leverage noisy intermediate-scale quantum (NISQ) devices to solve large-scale QUBO problems, one possible way is to decompose the full problem into multiple sub-problems, which we refer to as the Sub-QUBO Formalism. In this work, we enhance this formalism by proposing a sub-QUBO extraction protocol. To do so, we define a measure to quantify correlations between variables and use it to build a correlation matrix. This matrix serves as the input for clustering algorithms to group variables. Variables belonging to the same group form sub-QUBOs and are subsequently solved using QAOA. Our numerical analysis on several classes of randomly generated QUBO problems demonstrates that this grouping method outperforms previous approaches in terms of objective function values, while maintaining a comparable number of quantum subroutine calls. This method offers wide applicability for solving QUBO problems on NISQ devices.

Related papers

• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• 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)
• Characterizing QUBO Reformulations of the Max-k-Cut Problem for Quantum Computing [0.0]
  Quantum computing offers significant potential for solving NP-hardweighted (optimization) problems that are beyond the reach of classical computers.<n>One way to tap into this potential is by reformulating problems as a quadratic unconstrained binary optimization (QUBO) problem.<n>We present closed-form characterizations of tight penalty coefficients for two distinct QUBO reformulations of the max $k$-cut problem.
  arXiv  Detail & Related papers  (2025-11-02T22:49:59Z)
• Auxiliary-Qubit-Free Quantum Approximate Optimization Algorithm for the Minimum Dominating Set Problem [6.467872637658972]
  We present an auxiliary-qubit-free Quantum Approximate Optimization Algorithm (QAOA) for the Minimum Dominating Set (MDS) problem.<n>Our algorithm achieves comparable performance to the existing best QAOA for this problem while using fewer qubits.<n>An ablation study based on multi-angle QAOA reveals that the solution quality of the algorithm can be further improved by replacing shared circuit parameters with independent ones.
  arXiv  Detail & Related papers  (2025-09-20T12:01:57Z)
• Reducing QUBO Density by Factoring Out Semi-Symmetries [4.581191399651181]
  We introduce the concept of textitsemi-symmetries in QUBO matrices.<n>We show that our algorithm reduces the number of couplings and circuit depth by up to $45%.
  arXiv  Detail & Related papers  (2024-12-18T12:05:18Z)
• Evaluating Quantum Optimization for Dynamic Self-Reliant Community Detection [3.6021182997326022]
  We formulate a Quadratic Unconstrained Binary Optimization (QUBO) problem suitable for solving using quantum computationcolorblue. The formulation aims to find communities with maximal self-sufficiency and minimal power flowing between them. We benchmark the solution quality for multiple approaches: D-Wave's hybrid quantum-classical solvers, classicals, and a branch-and-bound solver.
  arXiv  Detail & Related papers  (2024-07-09T11:44:58Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• Mixed Integer Linear Programming Solver Using Benders Decomposition Assisted by Neutral Atom Quantum Processor [0.0]
  This paper presents a new hybrid classical-quantum approach to solve Mixed Linear Programming (MILP) We apply Benders decomposition (BD) to segment MILPs into a master problem (MP) and a subproblem (SP) Our MILP to QUBO conversion tightens the upper bounds of the involved continuous variables, positively impacting the required qubit count, and the convergence of the algorithm.
  arXiv  Detail & Related papers  (2024-02-08T15:33:09Z)
• Variational Amplitude Amplification for Solving QUBO Problems [0.0]
  This study focuses on QUBO (quadratic unconstrained binary optimization) problems, which are well-suited for qubit superposition states. We demonstrate circuit designs which encode QUBOs as cost oracle' operations $U_textrmC$, which when combined with the standard Grover diffusion operator $U_textrms$ lead to high probabilities of measurement for states corresponding to the optimal and near optimal solutions.
  arXiv  Detail & Related papers  (2023-01-31T14:33:40Z)
• 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)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• 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)
• Hybrid Quantum-Classical Unit Commitment [0.0]
  This paper proposes a hybrid quantum-classical algorithm to solve a fundamental power system problem called unit commitment (UC) Using Qiskit on the IBM Q system as the simulation environment, simulation results demonstrate the validity of the proposed algorithm to solve the UC problem.
  arXiv  Detail & Related papers  (2022-01-07T01:48:58Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• QROSS: QUBO Relaxation Parameter Optimisation via Learning Solver Surrogates [14.905085636501438]
  We build surrogate models of QUBO solvers via learning from solver data on a collection of instances of a problem. In this way, we are able capture the common structure of the instances and their interactions with the solver, and produce good choices of penalty parameters. QROSS is shown to generalise well to out-of-distribution datasets and different types of QUBO solvers.
  arXiv  Detail & Related papers  (2021-03-19T09:06:12Z)
• Low-Rank Sinkhorn Factorization [45.87981728307819]
  We introduce an explicit factorization of low rank couplings as a product of textitsub-coupling factors linked by a common marginal. We prove the non-asymptotic stationary convergence of this algorithm and illustrate its efficiency on benchmark experiments.
  arXiv  Detail & Related papers  (2021-03-08T13:18:45Z)

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.