Learning-with-errors problem is easy with quantum samples

The learning-with-errors (LWE) problem is one of the fundamental problems in computational learning theory and has in the last years become the cornerstone of postquantum cryptography. In this work, we study the quantum sample complexity of learning with errors and show that there exists an efficient quantum learning algorithm (with polynomial sample and time complexity) for the learning-with-errors problem where the error distribution is the one used in cryptography. While our quantum learning algorithm does not break the LWE-based encryption schemes proposed in the cryptography literature, it does have some interesting implications for cryptography: if a quantum adversary has access to a particular superposition of quantum states, a LWE-based encryption scheme becomes insecure. In particular, if a quantum sample state could be created from classical samples, then it would be possible to break LWE-based schemes using our learning algorithm. Finally, we extend our results and show quantum learning algorithms for three related problems: learning parity with noise, learning with rounding, and short integer solution.