NP-hardness of decoding quantum error-correction codes
- Publication Type:
- Journal Article
- Citation:
- Physical Review A - Atomic, Molecular, and Optical Physics, 2011, 83 (5)
- Issue Date:
- 2011-05-31
Closed Access
| Filename | Description | Size | |||
|---|---|---|---|---|---|
 | 2012004729OK.pdf | 93.41 kB |
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Although the theory of quantum error correction is intimately related to classical coding theory and, 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 QECCs is the same as their classical counterparts. Instead, decoding QECCs can be very much different from decoding classical codes due to the degeneracy property. Intuitively, one expects 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 nondegenerate. 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 QECCs. © 2011 American Physical Society.
Please use this identifier to cite or link to this item: