Syndrome decoding is NP-complete problem [page 6 of this reference]. There are some special linear codes for which we know efficient classical decoding algorithms, such as Reed-Solomon, LDPC and etc.
Is there some linear codes for which we know there exists an efficient quantum decoding algorithm, but there is no known classical algorithm for it?
As far as we know, there isn’t any family of linear codes that can be decoded in polynomial time on a quantum computer but not on a classical one. For arbitrary linear codes, problems like syndrome decoding are NPhard on the classical side, and there’s no result showing that quantum computers can solve these kinds of NPhard problems efficiently (in polynomial time). The known quantum speedups are mostly of the Grover type, giving quadratic improvements so they make brute force faster, but they don’t reduce the problem to polynomial time.In practice, codes like Reed Solomon, BCH, LDPC, Polar, and Reed–Muller are already efficiently decodable classically, and there’s no special asymmetry known for quantum decoding. On the cryptography side, the McEliece line of code-based schemes relies on the hardness of decoding general linear codes, and it’s considered a strong candidate for post-quantum security. If there were a general decoding method that was efficient on quantum computers but not on classical ones, that whole approach would be seriously undermined.
