LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling

In this paper, we show new algorithms, hardness results and applications for sfS|LWErangle and sfC|LWErangle with real Gaussian, Gaussian with linear or quadratic phase terms, and other related amplitudes. Let n be the dimension of LWE samples. Our main results are 1. There is a 2^tildeO(√n)-time algorithm for sfS|LWErangle with Gaussian amplitude with known phase, given 2^tildeO(√n) many quantum samples. The algorithm is modified from Kuperberg's sieve, and in fact works for more general amplitudes as long as the amplitudes and phases are completely known. 2. There is a polynomial time quantum algorithm for solving sfS|LWErangle and sfC|LWErangle for Gaussian with quadratic phase amplitudes, where the sample complexity is as small as tildeO(n). As an application, we give a quantum oblivious LWE sampler where the core quantum sampler requires only quasi-linear sample complexity. This improves upon the previous oblivious LWE sampler given by Debris-Alazard, Fallahpour, Stehl'e [STOC 2024], whose core quantum sampler requires tildeO(nr) sample complexity, where r is the standard deviation of the error. 3. There exist polynomial time quantum reductions from standard LWE or worst-case GapSVP to sfS|LWErangle with Gaussian amplitude with small unknown phase, and arbitrarily many samples. Compared to the first two items, the appearance of the unknown phase term places a barrier in designing efficient quantum algorithm for solving standard LWE via sfS|LWErangle.