Lifted-product code
 | This article is an orphan, as no other articles link to it. Please introduce links to this page from related articles. (September 2026) |
A lifted-product code is a quantum error-correcting code constructed by a generalization of the tensor product or Kronecker product to matrices over a commutative algebra. Lifted products were introduced by Pavel Panteleev and Gleb Kalachev and are used to construct quantum low-density parity-check (qLDPC) codes with large minimum distance.[1]
Construction
[edit]The ordinary hypergraph-product construction starts from two classical parity-check matrices over a finite field. The lifted-product construction instead permits matrix entries to lie in a commutative subalgebra of square matrices. Equivalently, its inputs can be viewed as block matrices whose blocks commute. A tensor-like product is first formed over this algebra and the resulting blocks are then interpreted over the base field.[2]
For cyclic lifts, the algebra can be generated by a cyclic permutation matrix. The construction then collapses a symmetry present in an ordinary tensor product: compared with the unreduced product, the number of physical qubits can be smaller by the degree of the lift.[2] This relation connects lifted products with quasi-cyclic classical codes, graph covers, chain complexes and hypergraph-product quantum codes.
Distance results
[edit]Panteleev and Kalachev used lifted products of expander-based codes to construct qLDPC-code families with minimum distance almost linear in block length. One family has dimension proportional to and distance proportional to , where is the number of physical qubits.[1] These results exceeded the previously long-standing square-root-type distance barrier for known qLDPC constructions.[2]
In subsequent work, Panteleev and Kalachev used lifted products over non-abelian groups to construct asymptotically good qLDPC codes—families whose encoding rate and relative distance are both bounded away from zero.[3] This established the existence claimed by the quantum-LDPC conjecture.
Decoding
[edit]Decoders for lifted-product codes include iterative message-passing methods combined with ordered-statistics decoding, as well as provable decoders for expander-based constructions.[2][4]
See also
[edit]References
[edit]- 1 2 Panteleev, Pavel; Kalachev, Gleb (2022). "Quantum LDPC Codes With Almost Linear Minimum Distance". IEEE Transactions on Information Theory. 68 (1): 213–229. arXiv:2012.04068. doi:10.1109/TIT.2021.3119384.
- 1 2 3 4 Breuckmann, Nikolas P.; Eberhardt, Jens Niklas (2021). "Quantum Low-Density Parity-Check Codes". PRX Quantum. 2 040101. arXiv:2103.06309. doi:10.1103/PRXQuantum.2.040101.
- ↑ Panteleev, Pavel; Kalachev, Gleb (2022). "Asymptotically Good Quantum and Locally Testable Classical LDPC Codes". Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. pp. 375–388. arXiv:2111.03654. doi:10.1145/3519935.3520017.
- ↑ Leverrier, Anthony; Zémor, Gilles (2024). "Efficient Decoding up to a Constant Fraction of the Code Length for Asymptotically Good Quantum Codes". ACM Transactions on Algorithms. arXiv:2206.07571. doi:10.1145/3663763.