Improved Low-qubit Hidden Shift Algorithms
This work addresses quantum security assessment for cryptography, but it is incremental as it builds on an existing algorithm.
The authors tackled the hidden shift problem relevant to quantum cryptography by improving a 2010 polynomial quantum memory algorithm, using subset-sum algorithms to reduce complexity and proposing new tradeoffs between quantum queries, classical time, and classical memory.
Hidden shift problems are relevant to assess the quantum security of various cryptographic constructs. Multiple quantum subexponential time algorithms have been proposed. In this paper, we propose some improvements on a polynomial quantum memory algorithm proposed by Childs, Jao and Soukharev in 2010. We use subset-sum algorithms to significantly reduce its complexity. We also propose new tradeoffs between quantum queries, classical time and classical memory to solve this problem.