text: 容錯學習問題 是一個機器學習領域中的懷疑難解問題。由 Oded Regev 在2005年提出，他因此贏得2018年哥德爾獎。這是一個極性學習問題的一般形式。Regev同時證明了LWE問題至少比幾個最壞情況下的格問題要難。這個問題在最近 被用作一種難度假設以建立後量子公鑰密碼系統，例如 Peikert 提出的容錯環學習金鑰交換。簡述.雖然來自機器學習領域，但是學習時出錯問題實際上是理論計算機科學中的計算複雜度問題。用簡單易懂的方式來說，問題如下。formula_1formula_2formula_3我提供類似的許多的線性多項式，讓你來求formula_4。這就是容錯學習問題。這一問題的關鍵就在於每個等式都是約等於，有一定誤差。這個誤差可以遵循一個離散隨機分佈，例如，有的時候左邊比右邊大1，有的時候左邊比右邊小1，還有的時候兩邊相等。如果假設所有式子都是直等，那這個問題就太簡單了。只要有足夠的式子，那麼使用常見的高斯消元法，在多項式時間內就能輕易求出formula_4。誤差的引入，導致如果你用高斯消元，那麼所有的式子加到一起之後誤差也加了起來，噪音過大，導致你無法從噪音中讀取任何資訊。這就是此問題的精華。密碼學上的應用.A是一個m x n矩陣，s是一個n維向量，e是一個m維向量。我們定義LWEA(s,e) := b := As + e。由此可以構造一個對稱加密演算法。加密演算法定義如下:這一演算法和傳統對稱金鑰加密演算法的區別的關鍵在於，加密方不將誤差資料e傳送給解密方，導致解密方所解得明文存在一個小的誤差。量子計算.2018年10月，斯坦福研究院的學生利用LWE問題作為基礎解決了經典計算機如何驗證量子計算機是否進行了量子計算這一問題。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 容錯學習問題
metadata: https://zh.wikipedia.org/wiki?curid=6322323