Noisy decoding by shallow circuit with parities: classical and quantum

Add to your list(s) Download to your calendar using vCal

• Davi Silva (QuSoft)
• Friday 20 October 2023, 13:00-14:30
• MR9.

If you have a question about this talk, please contact Sergii Strelchuk.

How well can simple circuits decode corrupted error-correcting codes? We consider this problem for the class of constant-depth circuits with parities (i.e. NC^0[+] circuits) in both 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. By contrast, we give a simple quantum circuit that correctly decodes the Hadamard code with optimal probability 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 under biased input-distributions. This is proved using a structure-versus-randomness strategy based on a new notion of rank for 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.

This talk is based on joint work with Jop Briët, Harry Buhrman and Niels Neumann.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR9
• bld31

Note that ex-directory lists are not shown.