容错学习问题

简述

虽然来自机器学习领域，但是学习时出错问题实际上是理论计算机科学中的计算复杂度问题。用简单易懂的方式来说，问题如下。
我提供类似的许多的线性多项式，让你来求。这就是容错学习问题。这一问题的关键就在于每个等式都是约等于，有一定误差（所谓的“出错”）。这个误差可以遵循一个离散随机分布，例如，有的时候左边比右边大1，有的时候左边比右边小1，还有的时候两边相等。如果假设所有式子都是直等，那这个问题就太简单了。只要有足够的式子，那么使用常见的高斯消元法，在多项式时间内就能轻易求出。误差的引入，导致如果你用高斯消元，那么所有的式子加到一起之后误差也加了起来，噪音过大，导致你无法从噪音中读取任何信息。这就是此问题的精华。

量子计算

2018年10月，斯坦福研究院的学生利用LWE问题作为基础解决了经典计算机如何验证量子计算机是否进行了量子计算这一问题。