A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem
arXiv:2312.08940 · doi:10.1007/s10732-025-09556-3
Abstract
Current quantum computers can only solve optimization problems of a very limited size. For larger problems, decomposition methods are required in which the original problem is broken down into several smaller sub-problems. These are then solved on the quantum computer and their solutions are merged into a final solution for the original problem. Often, these decomposition methods do not take the specific problem structure into account. In this paper, we present a tailored method using a divide-and-conquer strategy to solve the number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which can be solved on a quantum computer, and then recombine the results into another small auxiliary NPP. Solving this auxiliary problem yields an approximate solution of the original larger problem. We experimentally verify that our method allows to solve NPPs with over a thousand variables using a D-Wave quantum annealer.
arXiv comment12 pages, 3 figures, 1 table
References in corpus (13)
- Quantum Computing in the NISQ era and beyond
- Adiabatic Quantum Computing
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
- A practical heuristic for finding graph minors
- Quantum Annealing: An Overview
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Hybrid quantum annealing for larger-than-QPU lattice-structured problems
- Solving large Maximum Clique problems on a quantum annealer
- Analysis of the Karmarkar-Karp Differencing Algorithm
- Low Rank Non-Negative Matrix Factorization with D-Wave 2000Q
- Decomposition algorithms for solving NP-hard problems on a quantum annealer
- Quantum Annealing Algorithms for Boolean Tensor Networks
- A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem