  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 $\Z^n$ 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.
