Publication
Improved Quantum Algorithms for Subset Sum and k-SUM
ECCC TR26-135, 2026. PDF ยท Official record
Abstract
The Subset Sum problem asks whether, given \(n\) integers and a target, some subset sums to the target. Its best known worst-case classical running time is \(O^*(2^{n/2})\), while the previous best quantum upper bound was \(O^*(2^{n/3})\). The \(k\)-SUM problem asks whether one can select entries from \(k\) lists that sum to a target.
We present a new quantum algorithm for worst-case \(k\)-SUM that improves the best known exponent for all \(k\) congruent to \(3\) or \(6\) modulo \(7\). Unlike the preceding bound, it gives a worst-case guarantee rather than one restricted to single-solution random instances. Combining our algorithm for 7-SUM with the standard block reduction yields an \(O^*(2^{2n/7})\) quantum algorithm for Subset Sum, improving the previous \(O^*(2^{n/3})\) bound.