Lifted-product code
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
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
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
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
References
- ↑ 1.0 1.1 Panteleev, Pavel; Kalachev, Gleb (2022). "Quantum LDPC Codes With Almost Linear Minimum Distance". IEEE Transactions on Information Theory 68 (1): 213–229. doi:10.1109/TIT.2021.3119384.
- ↑ 2.0 2.1 2.2 2.3 Breuckmann, Nikolas P.; Eberhardt, Jens Niklas (2021). "Quantum Low-Density Parity-Check Codes". PRX Quantum 2. doi:10.1103/PRXQuantum.2.040101.
- ↑ Panteleev, Pavel; Kalachev, Gleb (2022). "Asymptotically Good Quantum and Locally Testable Classical LDPC Codes". pp. 375–388. 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. doi:10.1145/3663763.
 |  |
