Learning Stabilizers with Noise

Yihui Quek (MIT) https://simons.berkeley.edu/talks/yihui-quek-mit-2025-05-29 Quantum Algorithms, Complexity, and Fault Tolerance Reunion Random classical codes have good error correcting properties, and yet they are noto- riously hard to decode in practice. Despite many decades of extensive study, the fastest known algorithms still run in exponential time. The Learning Parity with Noise (LPN) prob- lem, which can be seen as the task of decoding a random linear code in the presence of noise, has thus emerged as a prominent hardness assumption with numerous applications in both cryptography and learning theory. Is there a natural quantum analog of the LPN problem? In this work, we introduce the Learning Stabilizers with Noise (LSN) problem, the task of decoding a random stabilizer code in the presence of local depolarizing noise. First, we show that LSN includes LPN as a special case, which suggests that it is at least as hard as its classical coun- terpart. We then provide concrete evidence that LSN is hard, ranging from low degree hardness to worst-to-average-case reductions.