Average-Case Complexity of Quantum Stabilizer Decoding

Andrey Boris Khesin, Jonathan Z. Lu, Alexander Poremba +2

Random classical linear codes are widely believed to be hard to decode. While slightly sub-exponential time algorithms exist when the coding rate vanishes sufficiently rapidly, all…