Distance Verification for Classical and Quantum LDPC Codes
Authors:
Open Access
- 31 March 2017
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (7) , 4675-4686
Abstract
The techniques of distance verification known for general linear codes are first applied to the quantum stabilizer codes. Then, these techniques are considered for classical and quantum (stabilizer) low-density-parity-check (LDPC) codes. New complexity bounds for distance verification with provable performance are derived using the average weight spectra of the ensembles of LDPC codes. These bounds are expressed in terms of the erasure-correcting capacity of the corresponding ensemble. We also present a new irreducible-cluster technique that can be applied to any LDPC code and takes advantage of parity-checks' sparsity for both the classical and quantum LDPC codes. This technique reduces complexity exponents of all existing deterministic techniques designed for generic stabilizer codes with small relative distances, which also include all known families of the quantum stabilizer LDPC codes.Keywords
All Related Versions
Funding Information
- NSF (PHY-1415600)
- U.S. Army Research Office (W911NF-14-1-0272)
- NSF (PHY-1416578)
This publication has 48 references indexed in Scilit:
- A method for finding codewords of small weight2005
- On Decoding of Low-Density Parity-Check Codes Over the Binary Erasure ChannelIEEE Transactions on Information Theory, 2004
- Hardness of approximating the minimum distance of a linear codeIEEE Transactions on Information Theory, 2003
- Fault-tolerant quantum computation by anyonsAnnals of Physics, 2003
- Topological quantum memoryJournal of Mathematical Physics, 2002
- The capacity of low-density parity-check codes under message-passing decodingIEEE Transactions on Information Theory, 2001
- Efficient erasure correcting codesIEEE Transactions on Information Theory, 2001
- Soft-decision decoding using punctured codesIEEE Transactions on Information Theory, 2001
- The complexity of information set decodingIEEE Transactions on Information Theory, 1990
- Low-density parity-check codesIEEE Transactions on Information Theory, 1962