  We present a quantum augmented variant of the dual lattice attack on the
Learning with Errors (LWE) problem, using classical memory with quantum random
access (QRACM). Applying our results to lattice parameters from the literature,
we find that our algorithm outperforms previous algorithms, assuming unit cost
access to a QRACM. On a technical level, we show how to obtain a quantum
speedup on the search for Fast Fourier Transform (FFT) coefficients above a
given threshold by leveraging the relative sparseness of the FFT and using
quantum amplitude estimation. We also discuss the applicability of the Quantum
Fourier Transform in this context. Furthermore, we give a more rigorous
analysis of the classical and quantum expected complexity of guessing part of
the secret vector where coefficients follow a discrete Gaussian (mod \(q\)).
