Improved Quantum Algorithms for Subset Sum and $k$-SUM

Abstract

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^{\ast }(2^{n/2})$ (Horowitz and Sahni, 1974), whereas the best quantum upper bound is $O^{\ast }(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 $\tilde{O}(n^{\lceil k/2\rceil })$, whereas the best quantum running time is $\tilde{O}(n^{k/3})$ (Tani, 2009). For random instances, a quantum algorithm with running time $\tilde{O}(n^{{\Phi }_k})$ is known, where $${\Phi }_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 $\tilde{O}(n^{{\Psi }_k})$, where $${\Psi }_k={\Phi }_k-\frac{[k\equiv 3\mathrm{mod}7]}{9}-\frac{[k\equiv 6\mathrm{mod}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^{\ast }(2^{2n/7})$ quantum algorithm for Subset Sum, improving the previously known $O^{\ast }(2^{n/3})$ algorithm.