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

Number Partitioning on a Quantum Computer

Hans A. De Raedt, Kristel F. L. Michielsen, Koen De Raedt, Seiji Miyashita

Published Oct 5, 2000• 6 citations
OpenAlex

Abstract

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.

Related papers

Quantum Algorithms of the Subset-Sum Problem on a Quantum Computer

Weng-Long Chang, Ting-Ting Ren, Mang Feng +3 more

In this paper, quantum algorithms for solving an instance of the subset-sum problem is proposed and a NMR experiment for the simplest subset-sum problem to test our theory is also performed.

WASE International Conference on Information Engineering•Jul 1, 2009•11 citations

Topologically protected Grover's oracle for the partition problem

Nikolai A. Sinitsyn, Bin Yan

The number partitioning problem (NPP) is one of the NP-complete (nondeterministic polynomial-time complete) computational problems. Its definite exact solution generally requires a check of all $N$ solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in $\sqrt{N}$ quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with $N$ only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time dependence of the physical parameters or the choice of the annealing protocol. We also argue that our approach can solve many other famous NP-complete computational problems in $\sqrt{N}$ steps.

arXiv:2304.10488•Physical Review A•Aug 14, 2023•4 citations

Quantum Algorithm for Polynomial Root Finding Problem

Guodong Sun, Shenghui Su, Maozhi Xu

Quantum computation is a new computing model based on fundamental quantum mechanical principle. Grover's algorithm finds the solution for a searching problem in the square root time of exhaustive search. Brassard, Hoyer, Tapp's algorithm counts the number of solutions for a searching problem. Through exploiting the two quantum algorithms, we propose a quantum algorithm for solving a new cryptography problem -- polynomial root finding problem, which could be used to design a cryptosystem. The algorithm will take O(rootM/t) steps for finding one of the t solutions to the problem, where M is the modular of the equation. The success rate of the algorithm is a constant and the cost of the algorithm depends on the calculations of modular exponentiation and the number of iterations.

International Conference on Computational Intelligence and Security (CIS)•Nov 1, 2014•14 citations

Seven combinatorial equations in quantum computation

AN Xue-mei

Seven combinatorial equations posed by a scientist in quantum combination are proved in this paper.

Journal of Southwest University•Jan 1, 2005•0 citations

Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem

Sean Hallgren

We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer d , Pell's equation is x 2 − dy 2 = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.

Journal of the ACM•Mar 1, 2007•147 citations

Quantum algorithms for the Hilbert's tenth problem

Tien D. Kieu

A quantum algorithm is presented for the classically non-computable Hilbert's tenth problem, which ultimately links to the Turing halting problem.

•Oct 24, 2001•5 citations
The number partitioning problem (NPP) is one of the NP-complete (nondeterministic polynomial-time complete) computational problems. Its definite exact solution generally requires a check of all NNN solution candidates, which is exponentially large. Here we describe a path to the fast solution of this problem in N\sqrt{N}N​ quasi-adiabatic quantum annealing steps. We argue that the errors due to the finite duration of the quantum annealing can be suppressed if the annealing time scales with NNN only logarithmically. Moreover, our adiabatic oracle is topologically protected, in the sense that it is robust against small uncertainty and slow time dependence of the physical parameters or the choice of the annealing protocol. We also argue that our approach can solve many other famous NP-complete computational problems in N\sqrt{N}N​ steps.
Quantum computation is a new computing model based on fundamental quantum mechanical principle. Grover's algorithm finds the solution for a searching problem in the square root time of exhaustive search. Brassard, Hoyer, Tapp's algorithm counts the number of solutions for a searching problem. Through exploiting the two quantum algorithms, we propose a quantum algorithm for solving a new cryptography problem -- polynomial root finding problem, which could be used to design a cryptosystem. The algorithm will take O(rootM/t) steps for finding one of the t solutions to the problem, where M is the modular of the equation. The success rate of the algorithm is a constant and the cost of the algorithm depends on the calculations of modular exponentiation and the number of iterations.
We give polynomial-time quantum algorithms for three problems from computational algebraic number theory. The first is Pell's equation. Given a positive nonsquare integer d , Pell's equation is x 2 − dy 2 = 1 and the goal is to find its integer solutions. Factoring integers reduces to finding integer solutions of Pell's equation, but a reduction in the other direction is not known and appears more difficult. The second problem we solve is the principal ideal problem in real quadratic number fields. This problem, which is at least as hard as solving Pell's equation, is the one-way function underlying the Buchmann--Williams key exchange system, which is therefore broken by our quantum algorithm. Finally, assuming the generalized Riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.