BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Noisy decoding by shallow circuit with parities: c
lassical and quantum - Davi Silva (QuSoft)
DTSTART;TZID=Europe/London:20231020T130000
DTEND;TZID=Europe/London:20231020T143000
UID:TALK207544AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/207544
DESCRIPTION:How well can simple circuits decode corrupted erro
r-correcting codes? We consider this problem for t
he 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 s
mall fraction of messages\, if the codewords are s
ent over a noisy channel with positive error rate.
By contrast\, we give a simple quantum circuit th
at correctly decodes the Hadamard code with optima
l probability even if a (1/2−ε)-fraction of a code
word is adversarially corrupted.\n\nOur classical
hardness result is based on an equidistribution ph
enomenon for multivariate polynomials under biased
input-distributions. This is proved using a struc
ture-versus-randomness strategy based on a new not
ion of rank for polynomial maps that may be of ind
ependent 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 qua
ntum circuit for the OR function by Takahashi and
Tani.\n\nThis talk is based on joint work with Jop
Briët\, Harry Buhrman and Niels Neumann.
LOCATION:MR9
CONTACT:Sergii Strelchuk
END:VEVENT
END:VCALENDAR