COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > CQIF Seminar > NP-hardness of decoding quantum error correction codes

## NP-hardness of decoding quantum error correction codesAdd to your list(s) Download to your calendar using vCal - Min-Hsiu Hsieh (University of Cambridge)
- Thursday 02 December 2010, 14:15-15:15
- MR4, Centre for Mathematical Sciences.
If you have a question about this talk, please contact Ashley Montanaro. Though the theory of quantum error correction is intimately related to the classical coding theory, in particular, one can construct quantum error correction codes (QECCs) from classical codes with the dual containing property, this does not necessarily imply that the computational complexity of decoding QEC Cs is the same as their classical counterparts. Instead, decoding QEC Cs can be very much different from decoding classical codes due to the degeneracy property. Intuitively, one expect degeneracy 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 considerably fast decoding algorithm exists for the general quantum decoding problems, and suggests the existence of a quantum cryptosystem based on the hardness of decoding QEC Cs. 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
- MR4, Centre for Mathematical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsReading Group on Principles of Neural Design Education, Equality and Development (EED) Group Seminars Cambridge Climate Coalition## Other talksBeyond truth-as-correspondence: realism for realistic people Ethics for the working mathematician, seminar 10: Mathematicians being leaders. Sir Richard Stone Annual Lecture: The Emergence of Weak, Despotic and Inclusive States Constructing datasets for multi-hop reading comprehension across documents Cafe Synthetique- AI and Automation: Revolutionising Biology Polynomial approximation of high-dimensional functions on irregular domains |