Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0010018 · Physics Letters A

Number partitioning on a quantum computer

Hans A. De Raedt, K Michielsen, K De Raedt, S Miyashita

Published Nov 1, 2001• 10 citations
arXivHTMLPDF
DOI
10.1016/s0375-9601(01)00680-6

Related papers

Number Partitioning on a Quantum Computer

Hans A. De Raedt, Kristel F. L. Michielsen, Koen De Raedt +1 more

We present a quantum algorithm to compute the number of solutions of the (constrained) number partitioning problem. We show that on a quantum computer this algorithm solves the number partitioning problem in polynomial time and space.

•Oct 5, 2000•6 citations

The set partitioning problem in a quantum context

Rafael Cação, Lucas R. C. T. Cortez, Jackson Forner +3 more

Optimization Letters•Jun 23, 2023•3 citations

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

Zongji Li, Tobias Seidel, Dominik Leib +2 more

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).

arXiv:2312.08940•Journal of Heuristics•Apr 17, 2025•4 citations

QUANTUM COMPUTING AND NUMBER THEORY

Yoshitaka Sasaki

•Sep 27, 2012•1 citation

Multi-level probabilistic computing: application to the multiway number partitioning problems

Ki-Hyuk Han, G.S. Park, Jeong Ung Ahn +7 more

Probabilistic computing, a class of physics-based computing, bridges the gap between quantum computing and the classical von Neumann architecture. This approach provides more efficient means of addressing NP problems, which are challenging for classical computers. In this work, we analyze the core concept of probabilistic computing which is based on the Ising model framework-including bit fluctuations and energy trends. In addition, we extend the traditional binary (two-level) system into a multi-level probabilistic framework, i.e. number partitioning problem to multiway number partitioning problem, as a case study.

Scientific Reports•Aug 7, 2025•0 citations

Algorithms for Quantum Computers

Jamie Smith, Michele Mosca

arXiv:1001.0767•Springer eBooks•Jan 1, 2012•23 citations
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).
Probabilistic computing, a class of physics-based computing, bridges the gap between quantum computing and the classical von Neumann architecture. This approach provides more efficient means of addressing NP problems, which are challenging for classical computers. In this work, we analyze the core concept of probabilistic computing which is based on the Ising model framework-including bit fluctuations and energy trends. In addition, we extend the traditional binary (two-level) system into a multi-level probabilistic framework, i.e. number partitioning problem to multiway number partitioning problem, as a case study.