A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866909596179759104 |
|---|---|
| author | Li, Zongji Seidel, Tobias Bortz, Michael Heese, Raoul |
| author_facet | Li, Zongji Seidel, Tobias Bortz, Michael Heese, Raoul |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_08940 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem Li, Zongji Seidel, Tobias Bortz, Michael Heese, Raoul Optimization and Control Discrete Mathematics 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. |
| title | A Decomposition Method for the Hybrid Quantum-Classical Solution of the Number Partitioning Problem |
| topic | Optimization and Control Discrete Mathematics |
| url | https://arxiv.org/abs/2312.08940 |