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:NP-hardness of decoding quantum error correction c
odes - Min-Hsiu Hsieh (University of Cambridge)
DTSTART;TZID=Europe/London:20101202T141500
DTEND;TZID=Europe/London:20101202T151500
UID:TALK27842AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/27842
DESCRIPTION:Though the theory of quantum error correction is i
ntimately related 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 nec
essarily imply that the computational complexity\n
of decoding QECCs is the same as their classical c
ounterparts. Instead\, decoding QECCs can be\nvery
much different from decoding classical codes due
to the degeneracy property. Intuitively\, one\nexp
ect degeneracy would simplify the decoding since t
wo different errors might not and need not be dist
inguished in order to correct them. However\, we s
how that general quantum decoding problem is NP-ha
rd regardless of the quantum codes being degenerat
e or non-degenerate. This finding implies that no
considerably fast decoding algorithm exists for th
e 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
CONTACT:Ashley Montanaro
END:VEVENT
END:VCALENDAR