A Discrete Fourier Transform on Lattices with Quantum Applications

arXiv1703.02515MaRDI QIDQ6284022FDOQ6284022

Authors: Lior Eldar, Peter W. Shor 

Publication date: 7 March 2017

Abstract: In this work, we introduce a definition of the Discrete Fourier Transform (DFT) on Euclidean lattices in $R^n$, that generalizes the $n$-th fold DFT of the integer lattice $$ 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 cite{ES16}. 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 cite{GPV08} 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.

This page was built for publication: A Discrete Fourier Transform on Lattices with Quantum Applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6284022)