2017/03/07 by Eldar, Lior, Shor, Peter
#FOS: Physical sciences #Mathematical Physics (math-ph) #Quantum Physics (quant-ph)
paper · doi:10.48550/arxiv.1703.02515
In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in \Rn, that generalizes the n-th fold DFT of the integer lattice \Zn to arbitrary lattices. This definition is not applicable for every lattice, but can be defined on lattices known as Systematic Normal Form (SysNF) introduced in \citeES16. Systematic Normal Form lattices are sets of integer vectors that satisfy a single homogeneous modular equation, which itself satisfies a certain number-theoretic property. Such lattices form a dense set in the space of n-dimensional lattices, and can be used to approximate efficiently any lattice. This implies that for every lattice L a DFT can be computed efficiently on a lattice near L. Our proof of the statement above uses arguments from quantum computing, and as an application of our definition we show a quantum algorithm for sampling from discrete distributions on lattices, that extends our ability to sample efficiently from the discrete Gaussian distribution \citeGPV08 to any distribution that is sufficiently "smooth". We conjecture that studying the eigenvectors of the newly-defined lattice DFT may provide new insights into the structure of lattices, especially regarding hard computational problems, like the shortest vector problem.