BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:NP-hardness of decoding quantum error correction codes - Min-Hsiu 
 Hsieh (University of Cambridge)
DTSTART:20101202T141500Z
DTEND:20101202T151500Z
UID:TALK27842@talks.cam.ac.uk
CONTACT:Ashley Montanaro
DESCRIPTION:Though the theory of quantum error correction is intimately re
 lated to the classical coding theory\,\nin particular\, one can construct 
 quantum error correction codes (QECCs) from classical codes with\nthe dual
  containing property\, this does not necessarily imply that the computatio
 nal complexity\nof decoding QECCs is the same as their classical counterpa
 rts. Instead\, decoding QECCs can be\nvery much different from decoding cl
 assical codes due to the degeneracy property. Intuitively\, one\nexpect de
 generacy would simplify the decoding since two different errors might not 
 and need not be distinguished in order to correct them. However\, we show 
 that general quantum decoding problem is NP-hard regardless of the quantum
  codes being degenerate or non-degenerate. This finding implies that no co
 nsiderably fast decoding algorithm exists for the general quantum decoding
  problems\, and suggests the existence of a quantum cryptosystem based on 
 the hardness of decoding QECCs.
LOCATION:MR4\, Centre for Mathematical Sciences
END:VEVENT
END:VCALENDAR