We study the quantum complexity of solving the subset sum problem, where the elements a_1, ..., a_n are randomly chosen from Z_{2^{l(n)}} and t = sum_i a_i in Z_{2^{l(n)}} is a sum of n/2 elements. In 2013, Bernstein, Jeffery, Lange and Meurer constructed a quantum subset sum algorithm with heuristic time complexity 2^{0.241n}, by enhancing the classical subset sum algorithm of Howgrave-Graham and Joux with a quantum random walk technique. We improve on this by defining a quantum random walk for the classical subset sum algorithm of Becker, Coron and Joux. The new algorithm only needs heuristic running time and memory 2^{0.226n}, for almost all random subset sum instances.
We study the quantum complexity of solving the subset sum problem, where the elements a_1, ..., a_n are randomly chosen from Z_{2^{l(n)}} and t = sum_i a_i in Z_{2^{l(n)}} is a sum of n/2 elements. In 2013, Bernstein, Jeffery, Lange and Meurer constructed a quantum subset sum algorithm with heuristic time complexity 2^{0.241n}, by enhancing the classical subset sum algorithm of Howgrave-Graham and Joux with a quantum random walk technique. We improve on this by defining a quantum random walk for the classical subset sum algorithm of Becker, Coron and Joux. The new algorithm only needs heuristic running time and memory 2^{0.226n}, for almost all random subset sum instances.
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∗(2n/2) (Horowitz and Sahni, 1974), whereas the best quantum upper bound is O∗(2n/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 O(n⌈k/2⌉), whereas the best quantum running time is O(nk/3) (Tani, 2009). For random instances, a quantum algorithm with running time O(nΦk) is known, where Φk=62k−⌊k/7⌋−⌊(k+3)/7⌋ (Schrottenloher, 2021). We present a new quantum algorithm solving worst-case k-SUM in time O(nΨk), where Ψk=Φk−9[k≡3mod7]−18[k≡6mod7]. 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∗(22n/7) quantum algorithm for Subset Sum, improving the previously known O∗(2n/3) algorithm.
Solving random subset sum instances plays an important role in constructing cryptographic systems. For the random subset sum problem, in 2013 Bernstein et al. proposed a quantum algorithm with heuristic time complexity O(20.241n), where the "O" symbol is used to omit poly(logn) factors. In 2018, Helm and May proposed another quantum algorithm that reduces the heuristic time and memory complexity to O(20.226n). In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity O(20.209n).
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.
Exponential quantum speedup for F3n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWE
We study vector subset sum over F3n: given m random vectors from F3n, find a nonempty subset that sums to zero; the smaller m, the more difficult it is to find such a subset. Chen, Liu, and Zhandry (EUROCRYPT'22) introduced an efficient quantum algorithm that solves this problem when m≈n2/2, where a naive classical algorithm would require exponential time. Subsequently, Kothari, O'Donnell, and Wu (STOC'2026) gave an efficient classical algorithm that only requires m≈n2/3 vectors, thus removing the hope for an exponential quantum advantage in this parameter regime.
Using the framework of Chen, Liu, and Zhandry, we give quantum algorithms that require much fewer input vectors, renewing the possibility of an exponential quantum speedup: for any fixed ε>0, our quantum algorithm solves F3-subset sum in polynomial time with m=ε⋅n2 vectors. More generally, we establish a full sample--time tradeoff that interpolates between exponential and polynomial runtime.
The main ingredient is a deterministic classical algorithm for the binary-error Learning-with-Errors problem, which is of independent cryptographic interest. For this, we rigorously establish a sample--time tradeoff that was predicted by earlier algebraic heuristics. For vector subset sums over larger fields, we also significantly improve classical algorithms in Kothari, O'Donnell, and Wu (STOC'2026).
Subset-Sum is an NP-complete problem where one must decide if a multiset of n integers contains a subset whose elements sum to a target value m. The best known classical and quantum algorithms run in time O~(2n/2) and O~(2n/3), respectively, based on the well-known meet-in-the-middle technique. Here we introduce a novel dynamic programming data structure with applications to Subset-Sum and a number of variants, including Equal-Sums (where one seeks two disjoint subsets with the same sum), 2-Subset-Sum (a relaxed version of Subset-Sum where each item in the input set can be used twice in the summation), and Shifted-Sums, a generalization of both of these variants, where one seeks two disjoint subsets whose sums differ by some specified value.
Given any modulus p, our data structure can be constructed in time O(np), after which queries can be made in time O(n) to the lists of subsets summing to a same value modulo p. We use this data structure to give new O~(2n/2) and O~(2n/3) classical and quantum algorithms for Subset-Sum, not based on the meet-in-the-middle method. We then use the data structure in combination with variable time amplitude amplification and a quantum pair finding algorithm, extending quantum element distinctness and claw finding algorithms to the multiple solutions case, to give an O(20.504n) quantum algorithm for Shifted-Sums, an improvement on the best known O(20.773n) classical running time. We also study Pigeonhole Equal-Sums and Pigeonhole Modular Equal-Sums, where the existence of a solution is guaranteed by the pigeonhole principle. For the former problem we give classical and quantum algorithms with running time O~(2n/2) and O~(22n/5), respectively. For the more general modular problem we give a classical algorithm which also runs in time O~(2n/2).