Improved quantum algorithm for the random subset sum problem
This work addresses a critical problem in cryptography for constructing secure systems, but it is incremental as it builds on existing quantum algorithms with modest improvements.
The paper tackles the random subset sum problem, a key challenge in cryptography, by proposing a new quantum algorithm that achieves heuristic time and memory complexity of O(2^{0.209n}), improving upon previous results of O(2^{0.241n}) and O(2^{0.226n}).
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 $\widetilde{O}(2^{0.241n})$, where the "$\widetilde{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 $\widetilde{O}(2^{0.226n})$. In this paper, a new quantum algorithm is proposed, with heuristic time and memory complexity $\widetilde{O}(2^{0.209n})$.