The Power of Few Qubits and Collisions – Subset Sum Below Grover’s Bound

Let \(a_1, \ldots a_n, t\) be a solvable subset sum instance, i.e. there exists a subset of the \(a_i\) that sums to t. Such a subset can be found with Grover search in time \(2^{\frac{n}{2}}\), the square root of the search space, using only \(\mathcal {O}(n)\) qubits. The only quantum algorithms that beat Grover’s square root bound – such as the Left-Right-Split algorithm of Brassard, Hoyer, Tapp – either use an exponential amount of qubits or an exponential amount of expensive classical memory with quantum random access (QRAM). We propose the first subset sum quantum algorithms that breaks the square root Grover bound with linear many qubits and without QRAM. Building on the representation technique and the quantum collision finding algorithm from Chailloux, Naya-Plasencia and Schrottenloher (CNS), we obtain a quantum algorithm with time \(2^{0.48n}\).