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

WASE International Conference on Information Engineering

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

Weng-Long Chang, Ting-Ting Ren, Mang Feng, Lai Chin Lu, Kawuu W. Lin, Minyi Guo

Published Jul 1, 2009• 12 citations
Publisher

Abstract

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.
DOI
10.1109/icie.2009.15

Related papers

Towards An Implementation of the Subset-sum Problem on the IBM Quantum Experience

David Gunter, Toks Adedoyin

In seeking out an algorithm to test out the capability of the IBM Quantum Experience quantum computer, we were given a review paper covering various algorithms for solving the subset-sum problem, including both classical and quantum algorithms. The paper went on to present a novel algorithm that beat the previous best algorithm known at the time. The complex nature of the algorithm made it difficult to see a path for implementation on the Quantum Experience machine and the exponential cost - only slightly better than the best classical algorithm - left us looking for a different approach for solving this problem. We present here a new quantum algorithm for solving the subset-sum problem that for many cases should lead to O(poly(n))-time to solution. The work is reminiscent of the verification procedure used in a polynomial-time algorithm for the quantum Arthur-Merlin games presented elsewhere, where the use of a quantum binary search to find a maximum eigenvalue in the final output stage has been adapted to the subset-sum problem as in another paper.

arXiv:1912.03254•Dec 4, 2019•1 citation

The Subset Sum Problem: Reducing Time Complexity of NP-Completeness with Quantum Search

Bo Moon

The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.

Undergraduate Journal of Mathematical Modeling One + Two•May 1, 2013•3 citations

Improved Quantum Algorithms for Subset Sum and kkk-SUM

Nikolai Chukhin, Alexander S. Kulikov, Maksim Levitskii +1 more

The Subset Sum problem asks whether, given $n$ integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is $O^*(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^*(2^{n/3})$ (Bernstein, Jeffery, Lange, and Meurer, 2013). The $k$-SUM problem is a parameterized version of Subset Sum asking whether there are $k$ integers that sum to the target. The best classical upper bound for it is $\widetilde O(n^{\lceil k/2\rceil})$, whereas the best quantum running time is $\widetilde O(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\widetilde O(n^{Φ_k})$ is known, where $$ Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} $$ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case $k$-SUM in time $\widetilde O(n^{Ψ_k})$, where $$ Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. $$ The algorithm is not only faster for all $k$ congruent to $3$ or $6$ modulo $7$, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for $7$-SUM with the standard block reduction technique yields an $O^*(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^*(2^{n/3})$ algorithm.

arXiv:2608.07309•Aug 7, 2026•1 citation

Quantum Algorithms for the Subset-Sum Problem

Daniel J. Bernstein, Stacey Jeffery, Tanja Lange +1 more

Lecture notes in computer science•Jan 1, 2013•83 citations

Quantum algorithm and experimental demonstration for the subset sum problem

Qilin Zheng, Pingyu Zhu, Shichuan Xue +8 more

Science China Information Sciences•Dec 13, 2021•11 citations

A Quantum Approach to Subset-Sum and Similar Problems

Ammar Daskin

In this paper, we study the subset-sum problem by using a quantum heuristic approach similar to the verification circuit of quantum Arthur-Merlin games. Under described certain assumptions, we show that the exact solution of the subset sum problem my be obtained in polynomial time and the exponential speed-up over the classical algorithms may be possible. We give a numerical example and discuss the complexity of the approach and its further application to the knapsack problem.

arXiv:1707.08730•Jul 27, 2017•9 citations
In seeking out an algorithm to test out the capability of the IBM Quantum Experience quantum computer, we were given a review paper covering various algorithms for solving the subset-sum problem, including both classical and quantum algorithms. The paper went on to present a novel algorithm that beat the previous best algorithm known at the time. The complex nature of the algorithm made it difficult to see a path for implementation on the Quantum Experience machine and the exponential cost - only slightly better than the best classical algorithm - left us looking for a different approach for solving this problem. We present here a new quantum algorithm for solving the subset-sum problem that for many cases should lead to O(poly(n))-time to solution. The work is reminiscent of the verification procedure used in a polynomial-time algorithm for the quantum Arthur-Merlin games presented elsewhere, where the use of a quantum binary search to find a maximum eigenvalue in the final output stage has been adapted to the subset-sum problem as in another paper.
The Subset Sum Problem is a member of the NP-complete class, so no known polynomial time algorithm exists for it. Although there are polynomial time approximations and heuristics, these are not always acceptable, yet exact-solution algorithms are unfeasible for large input. Quantum computation offers new insights for not only the Subset Sum Problem but also the entire NP-complete class; most notably, Grover's quantum algorithm for an unstructured database search can be tailored to identify solutions to problems within mathematics and computer science. This paper discusses the physical and conceptual feasibility of quantum computation and demonstrates the utility of quantum search by analyzing the time complexities of the classical dynamic programming algorithm and Grover's algorithm in solving the Subset Sum Problem, evincing the implications this has on the NP-complete class in general.
The Subset Sum problem asks whether, given nnn integers and a target, some subset of the integers sums to the target. Its best known worst-case running time is O∗(2n/2)O^*(2^{n/2})O∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/3)O^*(2^{n/3})O∗(2n/3) (Bernstein, Jeffery, Lange, and Meurer, 2013). The kkk-SUM problem is a parameterized version of Subset Sum asking whether there are kkk integers that sum to the target. The best classical upper bound for it is O~(n⌈k/2⌉)\widetilde O(n^{\lceil k/2\rceil})O(n⌈k/2⌉), whereas the best quantum running time is O~(nk/3)\widetilde O(n^{k/3})O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O~(nΦk)\widetilde O(n^{Φ_k})O(nΦk​) is known, where Φk=2k−⌊k/7⌋−⌊(k+3)/7⌋6 Φ_k=\frac{2k-\lfloor k/7\rfloor-\lfloor (k+3)/7\rfloor}{6} Φk​=62k−⌊k/7⌋−⌊(k+3)/7⌋​ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case kkk-SUM in time O~(nΨk)\widetilde O(n^{Ψ_k})O(nΨk​), where Ψk=Φk−[k≡3 mod 7]9−[k≡6 mod 7]18. Ψ_k=Φ_k-\frac{[k\equiv 3\bmod 7]}{9}-\frac{[k\equiv 6\bmod 7]}{18}. Ψk​=Φk​−9[k≡3mod7]​−18[k≡6mod7]​. The algorithm is not only faster for all kkk congruent to 333 or 666 modulo 777, but also gives a worst-case guarantee rather than a guarantee restricted to single-solution random instances. Combining our algorithm for 777-SUM with the standard block reduction technique yields an O∗(22n/7)O^*(2^{2n/7})O∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3)O^*(2^{n/3})O∗(2n/3) algorithm.