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

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

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})$ (Horo…