NP-hardness of decoding quantum error-correction codes

Abstract

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 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 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 QECCs.

5 pages, no figure. Final version for publication

References in corpus (1)

• Correcting Quantum Errors with Entanglement

Cited by in corpus (33)

• The Future of Quantum Computing with Superconducting Qubits
• Quantum Computation vs. Firewalls
• Machine-learning-assisted correction of correlated qubit errors in a topological code
• Triangular color codes on trivalent graphs with flag qubits
• Tensor Networks and Quantum Error Correction
• Advantages of versatile neural-network decoding for topological codes
• Cellular-automaton decoders with provable thresholds for topological codes
• General framework for constructing fast and near-optimal machine-learning-based decoder of the topological stabilizer codes
• Tensor-network codes
• Quantum Computation with Topological Codes: from qubit to topological fault-tolerance
• New Quantum Codes from CSS Codes
• A Scalable Decoder Micro-architecture for Fault-Tolerant Quantum Computing
• Local tensor-network codes
• Asymmetric Quantum Concatenated and Tensor Product Codes with Large Z-Distances
• Ising model formulation for highly accurate topological color codes decoding
• On the Hardness of the Minimum Distance Problem of Quantum Codes
• Improved Belief Propagation Decoding Algorithms for Surface Codes
• Efficient diagnostics for quantum error correction
• Good Gottesman-Kitaev-Preskill codes from the NTRU cryptosystem
• The Encoding and Decoding Complexities of Entanglement-Assisted Quantum Stabilizer Codes
• Partially Concatenated Calderbank-Shor-Steane Codes Achieving the Quantum Gilbert-Varshamov Bound Asymptotically
• Decoherence and Quantum Error Correction for Quantum Computing and Communications
• Constant Overhead Entanglement Distillation via Scrambling
• Error Correction for Reliable Quantum Computing
• Syndrome decoding by quantum approximate optimization
• Hardness of decoding quantum stabilizer codes
• Layer codes as partially self-correcting quantum memories
• Quantum Error Source and Channel Coding
• Hardness results for decoding the surface code with Pauli noise
• qSIEVE: Efficient qLDPC Memory via Systolic Movement in Atom Arrays
• Optimizing short stabilizer codes for asymmetric channels
• Overflow-Safe Polylog-Time Parallel Minimum-Weight Perfect Matching Decoder: Toward Experimental Demonstration
• Protecting Information Against Computational Errors and Quantum Erasures via Concatenation