2019/01/31 by Xavier Bonnetain, Bonnetain, Xavier
Computer Science · #Coding theory and cryptography #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1901.11428
openalex publication_date 2019/01/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.