On the hardnesses of several quantum decoding problems

DOI10.1007/S11128-020-02622-8MaRDI QIDQ2677282zbMATH OpenOpenAlexFDO

Authors Kao-Yueh Kuo, Chung-Chin Lu

Publication date 13 January 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.5173

zbMATH Keywords

computational complexitydecoding hardnessdegeneracy propertyquantum cryptographyquantum error correction codesquantum stabilizer codes

Mathematics Subject Classification ID

Computational stability and error-correcting codes for quantum computation and communication processing (81P73) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Recommendations

• The hardness of decoding linear codes with preprocessing
• Maximum-likelihood decoding of Reed-Solomon codes is NP-hard
• On the Hardness of Decoding the Gale–Berlekamp Code
• Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
• Hard Problems of Algebraic Geometry Codes

Cites work

• Algebraic function fields and codes
• Concatenated Quantum Codes Constructible in Polynomial Time: Efficient Decoding and Error Correction
• Faster integer multiplication
• scientific article; zbMATH DE number 1579275 (Why is no real title available?)
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• scientific article; zbMATH DE number 4055695 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1104924 (Why is no real title available?)
• scientific article; zbMATH DE number 854560 (Why is no real title available?)
• Introduction to post-quantum cryptography
• On binary constructions of quantum codes
• On the inherent intractability of certain coding problems (Corresp.)
• On the iterative deconding of sparse quantum codes
• Quantum Error Correction and Orthogonal Geometry
• Quantum error correction via codes over GF(4)
• Quantum information theory
• Quantum McEliece public-key cryptosystem
• Wild McEliece

Cited in

(9)

• Quasi-cyclic constructions of asymmetric quantum error-correcting codes
• On the equivalence of two post-quantum cryptographic families
• A family of Hermitian dual-containing constacyclic codes and related quantum codes
• Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians
• Quantum Hardcore Functions by Complexity-Theoretical Quantum List Decoding
• Quantum hardcore functions by complexity-theoretical quantum list decoding
• On the Hardnesses of Several Quantum Decoding Problems
• Syndrome decoding by quantum approximate optimization
• On the maximum-likelihood decoding problem

Describes a project that uses

Uses Software

• McEliece

This page was built for publication: On the hardnesses of several quantum decoding problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2677282)