A more efficient quantum algorithm for solving the shortest vector problem
Date Issued
2016
Date
2016
Author(s)
Chen, Yanlin
Abstract
SVP is a well known NP hard problem both for classical and quantum. The best algorithm for SVP takes O(2^n) in classical and quantum computing does not helps. In this paper we demonstrate a quantum algorithm which solves SVP in time O(3^{n/2}) and in space O(2^{n/2}). Our main contribution includes two parts: we first tighten the inequality of smoothing parameter and λ1 such that we have a better oracle for bounded decoding distance(BDD) problem. Then we apply Grover search on the Enumeration algorithm by Paul to solve SVP in time O(3^{n/2}). To date, the best quantum algorithm for SVP still costs O(2^{1.79n}) in time, we provide an almost square better result for it.
Subjects
lattice
cryptography
decryption
quantum
computing
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-105-R03921034-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):eb32119eddd868717d68ec0e52ad58a6