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 $\widetilde{O}(2^{0.241n})$, where the "$\widetilde{O}$" symbol is used to omit poly($\log n$) factors. In 2018, Helm and May proposed another quantum algorithm that reduces the heuristic time and memory complexity to $\widetilde{O}(2^{0.226n})$. In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity $\widetilde{O}(2^{0.209n})$.
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 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.
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 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).
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, a foundational NP-hard problem in theoretical computer science, serves as a critical building block for cryptographic constructions. This work introduces novel classical and quantum heuristic algorithms for the random subset-sum problem at density d=1, where exactly one solution is expected. Classically, we propose the first algorithm based on a ternary tree representation structure, inspired by recent advances in lattice-based cryptanalysis. Through numerical optimization, our method achieves a time complexity of 𝒪˜20.2400n and space complexity of 𝒪˜20.2221n, improving upon the previous best classical heuristic result of 𝒪˜20.2830n. In the quantum setting, we develop a corresponding algorithm by integrating the classical ternary representation technique with a quantum walk search framework. The optimized quantum algorithm attains a time and space complexity of 𝒪˜20.1843n, surpassing the prior state-of-the-art quantum heuristic of 𝒪˜20.2182n. Furthermore, we apply our algorithms to information set decoding in code-based cryptography. For half-distance decoding, our classical algorithm improves the time complexity to 𝒪˜20.0453n, surpassing the previous best of 𝒪˜20.0465n. For full-distance decoding, we achieve a quantum complexity of 𝒪˜20.058326n, advancing beyond the prior best quantum result of 𝒪˜20.058696n. These findings demonstrate the broad applicability and efficiency of our ternary representation technique across both classical and quantum computational models.