Learning Stabilizers with Noise

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.