Noisy decoding by shallow circuits with parities: classical and quantum
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911763323158528 |
|---|---|
| author | Briët, Jop Buhrman, Harry Castro-Silva, Davi Neumann, Niels M. P. |
| author_facet | Briët, Jop Buhrman, Harry Castro-Silva, Davi Neumann, Niels M. P. |
| contents | We consider the problem of decoding corrupted error correcting codes with NC$^0[\oplus]$ 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 large 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 $Ω(\varepsilon^2)$ even if a $(1/2 - \varepsilon)$-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_02870 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Noisy decoding by shallow circuits with parities: classical and quantum Briët, Jop Buhrman, Harry Castro-Silva, Davi Neumann, Niels M. P. Computational Complexity Combinatorics Quantum Physics 15A69, 11B30, 68R05 F.2.0; E.4 We consider the problem of decoding corrupted error correcting codes with NC$^0[\oplus]$ 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 large 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 $Ω(\varepsilon^2)$ even if a $(1/2 - \varepsilon)$-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. |
| title | Noisy decoding by shallow circuits with parities: classical and quantum |
| topic | Computational Complexity Combinatorics Quantum Physics 15A69, 11B30, 68R05 F.2.0; E.4 |
| url | https://arxiv.org/abs/2302.02870 |