Efficient solution of the number partitioning problem on a quantum annealer: a hybrid quantum-classical decomposition approach

Zongji Li, Tobias Seidel (), Dominik Leib, Michael Bortz and Raoul Heese
Additional contact information
Zongji Li: Fraunhofer Institute for Industrial Mathematics ITWM
Tobias Seidel: Fraunhofer Institute for Industrial Mathematics ITWM
Dominik Leib: Fraunhofer Institute for Industrial Mathematics ITWM
Michael Bortz: Fraunhofer Institute for Industrial Mathematics ITWM
Raoul Heese: Fraunhofer Institute for Industrial Mathematics ITWM

Journal of Heuristics, 2025, vol. 31, issue 2, No 4, 20 pages

Abstract: 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 recombined 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 2-way Number partitioning problem (NPP) with a large number of variables. The idea is to perform a specialized decomposition into smaller NPPs, which are 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 the D-Wave Advantage quantum annealer (Advantage_system6.4).

Keywords: Number partitioning problem; Quantum optimization; Quantum annealing; Decomposition approach (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10732-025-09556-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joheur:v:31:y:2025:i:2:d:10.1007_s10732-025-09556-3

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10732

DOI: 10.1007/s10732-025-09556-3

Access Statistics for this article

Journal of Heuristics is currently edited by Manuel Laguna

More articles in Journal of Heuristics from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().