Abstract
Solving random subset sum instances plays an important role in constructing cryptographic systems. For the random subset sum problem, in 2013 Bernstein et al. proposed a quantum algorithm with heuristic time complexity O(2^0.241n), where the "O" symbol is used to omit poly(log n) factors. In 2018, Helm and May proposed another quantum algorithm that reduces the heuristic time and memory complexity to O(2^0.226n). In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity O(2^0.209n).