Noisy decoding by shallow circuits with parities: classical and quantum (extended abstract)
conference paper
We consider the problem of decoding corrupted error correcting codes with NC0 [⊕] circuits in the classical and quantum settings. We show that any such classical circuit can correctly recover only a vanishingly small fraction of messages, if the codewords are sent over a noisy channel with positive error rate. Previously this was known only for linear codes with non-trivial dual distance, whereas our result applies to any code. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with probability Ω(ε 2 ) even if a (1/2 − ε)-fraction of a codeword is adversarially corrupted. Our classical hardness result is based on an equidistribution phenomenon for multivariate polynomials over a finite field under biased input distributions. This is proved using a structure-versus-randomness strategy based on a new notion of rank for high-dimensional polynomial maps that may be of independent interest. Our quantum circuit is inspired by a non-local version of the Bernstein-Vazirani problem, a technique to generate “poor man’s cat states” by Watts et al., and a constant-depth quantum circuit for the OR function by Takahashi and Tani.
Topics
TNO Identifier
992246
Source title
15th Innovations in Theoretical Computer Science Conference (ITCS 2024).
Files
To receive the publication files, please send an e-mail request to TNO Repository.