容錯學習問題
容錯學習問題（通常稱LWE 問題，是 Learning with errors 的縮寫）是一个機器學習領域的懷疑難解問題。由 Oded Regev 佇二空空五年提出，伊贏著二空一八年哥德爾獎。這是一个極性學習問題的一般形式。Regev 同時證明矣 LWE 問題至少比幾个上歹情形下的格問題難無。這个問題佇最近予人用做一種的難度假設以創建了後量子公鎖密碼系統，比如講 Peikert 提出的容錯環學習密鎖交換。
簡述
雖然來自機器學習領域，毋過學習的時陣出錯問題實際上是理論計算機科學中的計算複雜度問題。用簡單單捌的方式來講，問題如下。
$ 十四 \ cdot s _ { 一 } + 十五 \ cdot s _ { 二 } + 五 \ cdot s _ { 三 } + 二 \ cdot s _ { 四 } \ approx 八 { \ bmod { 一 } } 七 $ $ 十三 \ cdot s _ { 一 } + 十四 \ cdot s _ { 二 } + 十四 \ cdot s _ { 三 } + 六 \ cdot s _ { 四 } \ approx 十六 { \ bmod { 一 } } 七 $ $ 六 \ cdot s _ { 一 } + 十 \ cdot s _ { 二 } + 十三 \ cdot s _ { 三 } + 一 \ cdot s _ { 四 } \ approx 三 { \ bmod { 一 } } 七 $
我提供類似的真濟線性多項式，予你來求 $ s _ { 一 } \ cdots s _ { 四 } $。這就是容毋著學習問題。這一問題的關鍵就佇每一个等式攏是等於，有一定無差（咱所講的「脫箠」）。 這个誤差會當遵循一个離散隨機分佈，比如講，有的時陣倒爿比正爿較大嘛，有的時陣倒爿比正爿較細嘛，猶閣有當時仔兩爿相等。若假設所有的式攏是直等，按呢這个問題就傷簡單矣。只要有夠額的式，按呢使用捷見的高斯消元法，佇多項式時間內底就會當簡單共求出 $ s _ { 一 } \ cdots s _ { 四 } $。精差的引入，致使著你若用高斯的消元，遐爾仔所有的式座加甲做伙了後精差嘛加甲起來，噪音過大，致使你無法度對噪音內讀任何信息。這就是按呢問題的精華。
密碼學上的應用
A 是一个 m x n 矩陣，s 是一个 n 維向量，e 是一个 m 維向量。咱定義 LWEA ( s , e ) :=b :=As + e。由此會當構造一个對稱加密算法。加密算法定義如下 :
- s 做密鎖 k 使用；
- ( A , e ) 這一組數據佇加密時隨機生成；
- 由 s , A , e 所求的得的值 b 作為一改性密碼本的密鎖使用，密文 m 進行異或操作。
這一算法佮傳統對稱密鎖加密算法的區別的關鍵佇咧，加密方莫脫箠數據 e 傳送予解密方，致使解密方所解甲明文存在一个細的精差。
量仔計算
二空一八年十月，斯坦福研究院的學生利用 LWE 問題做基礎解決經典計算機欲按怎驗證量仔計算機會算機閣進行了量仔計算這一問題。