Learning with Errors is easy with quantum samples

Abstract

Learning with Errors is one of the fundamental problems in computational learning theory and has in the last years become the cornerstone of post-quantum 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: first, when building an LWE-based scheme, one needs to be careful about the access to the public-key generation algorithm that is given to the adversary; second, our algorithm shows a possible way for attacking LWE-based encryption by using classical samples to approximate the quantum sample state, since then using our quantum learning algorithm would solve LWE.

References in corpus (3)

• Improved Bounds on Quantum Learning Algorithms
• Quantum Algorithms for Learning and Testing Juntas
• A Survey of Quantum Learning Theory

Cited by in corpus (18)

• Quantum machine learning: a classical perspective
• On the Quantum versus Classical Learnability of Discrete Distributions
• Quantum statistical query learning
• Quantum advantage for differential equation analysis
• On the Hardness of PAC-learning Stabilizer States with Noise
• Statistical Limits of Supervised Quantum Learning
• Quantum Coupon Collector
• Binary Classification with Classical Instances and Quantum Labels
• Quantum solvability of noisy linear problems by divide-and-conquer strategy
• Quantum-Classical Hybrid Algorithm for Solving the Learning-With-Errors Problem on NISQ Devices
• Quantum Learning Boolean Linear Functions w.r.t. Product Distributions
• Quantum-classical reinforcement learning for decoding noisy classical parity information
• Polynomial T-depth Quantum Solvability of Noisy Binary Linear Problem: From Quantum-Sample Preparation to Main Computation
• Learning Quantum Processes with Quantum Statistical Queries
• Quantum Machine Learning For Classical Data
• Sample-size-reduction of quantum states for the noisy linear problem
• Assessing the feasibility of quantum learning algorithms for noisy linear problems
• Provable and Verifiable Quantum Advantage in Sample Complexity