IMPROVED CLASSICAL AND QUANTUM ALGORITHMS FOR THE SHORTEST VECTOR PROBLEM VIA BOUNDED DISTANCE DECODING

作     者：Aggarwal, Divesh Chen, Yanlin Kumar, Rajendra Shen, Yixin 

作者机构：Ctr Quantum Technol Singapore 117543 Singapore Natl Univ Singapore Singapore 117543 Singapore QuSoft Amsterdam Netherlands CWI Amsterdam Netherlands Indian Inst Technol Delhi New Delhi 110016 India Univ Rennes Inria CNRS IRISA F-35040 Rennes France 

出 版 物：《SIAM JOURNAL ON COMPUTING》 (SIAM J Comput)

年 卷 期：2025年第54卷第2期

页      面：233-278页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：Singapore Ministry of Education [MOE2019-T2-1-145] National Research Foundation [R-710-000-012-135] National Research Foundation Singapore award [AISG-RP-2018-005] Engineering and Physical Sciences Research Council [EP/W02778X/2] French Agence Nationale de la Recherche through the France [ANR-22-PETQ-0008 PQ-TLS] 

主　　题：lattices shortest vector problem discrete Gaussian sampling time-space tradeoff quantum computation bounded distance decoding 

摘      要：The most important computational problem on lattices is the shortest vector problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results: (1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 \leq q \leq root n, our algorithm takes q13n+o(n) time and requires poly(n) \cdot q16n/q2 memory. This tradeoff, which ranges from enumeration (q = root n) to sieving (q constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In a quantum random access memory (QRAM) model, this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733--742] that has a time and space complexity 2n+o(n). (3) A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285--306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n), and our quantum algorithm in a QRA