Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/323325 
Year of Publication: 
2025
Citation: 
[Journal:] Journal of Heuristics [ISSN:] 1572-9397 [Volume:] 31 [Issue:] 2 [Article No.:] 21 [Publisher:] Springer US [Place:] New York, NY [Year:] 2025
Publisher: 
Springer US, New York, NY
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).
Subjects: 
Number partitioning problem
Quantum optimization
Quantum annealing
Decomposition approach
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.