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.
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.
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. 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. These results exceeded the previously long-standing square-root-type distance barrier for known qLDPC constructions.
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. 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.
See also Quantum error correction Low-density parity-check code Expander graph
References