The Power of Few Qubits and Collisions - Subset Sum below Grover's Bound

Abstract

Let a1, . . . an, t be a solvable subset sum instance, i.e. there exists a subset of the ai that sums to t. Such a subset can be found with Grover search in time 2 n 2 , the square root of the search space, using only 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 . Using the Schroeppel-Shamir list construction technique, we further improve downto run time 2 0.43n . The price that we have to pay for beating the square root bound is that as opposed to Grover search our algorithms require classical memory, but no QRAM, i.e. we get a time/memory/qubit tradeoff. Thus, our algorithms have to be compared to purely classical time/memory subset sum trade-offs such as those of Howgrave-Graham and Joux. Our quantum algorithms improve on these purely classical algorithms for all memory complexities M < 2 0.2n . As an example, for memory 2 0.1n we obtain run time 2 0.47n as opposed to 2 0.63n for the best classical algorithm.