BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Noisy decoding by shallow circuit with parities: classical and qua
 ntum - Davi Silva (QuSoft)
DTSTART:20231020T120000Z
DTEND:20231020T133000Z
UID:TALK207544@talks.cam.ac.uk
CONTACT:Sergii Strelchuk
DESCRIPTION: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 se
 ttings. 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 prob
 ability even if a (1/2−ε)-fraction of a codeword is adversarially corru
 pted.\n\nOur classical hardness result is based on an equidistribution phe
 nomenon for multivariate polynomials under biased input-distributions. Thi
 s is proved using a structure-versus-randomness strategy based on a new no
 tion of rank for polynomial maps that may be of independent interest. Our 
 quantum circuit is inspired by a non-local version of the Bernstein-Vazira
 ni problem\, a technique to generate "poor man's cat states" by Watts et a
 l.\, and a constant-depth quantum circuit for the OR function by Takahashi
  and Tani.\n\nThis talk is based on joint work with Jop Briët\, Harry Buh
 rman and Niels Neumann.
LOCATION:MR9
END:VEVENT
END:VCALENDAR