Lifted-product code
This article coincides in timing and pattern with contributions by the same user which have been determined to be AI-generated, and has no significant contributions by other editors. It is presumed to have also been AI-generated, and may be assumed to violate Wikipedia's policies and guidelines. If no editor takes responsibility for it within a five-day grace period, this article may be deleted. To object to proposed deletion, an editor may take responsibility for the content and assume the onus to achieve consensus for its inclusion. Assuming responsibility requires that all content and its sources be closely reviewed and reworked as needed to ensure that they comply with policies and guidelines. This may involve checking that the cited sources support the content and are reliable, determining whether the content is due for inclusion, and rewriting the content to revise any tone issues and resolve possible copyright violations. Once this has been done, this template may be removed. The nominator also gave the following reason for this proposed deletion:
Find sources: "Lifted-product code" – news · newspapers · books · scholar · JSTOR Reviewer tools: guideline project (talk • log) The article may be deleted if this message remains in place for five days, i.e., after 22:56, 14 November 2026 (UTC). Nominator: Please consider notifying the author if active: {{subst:prodwarningLLM|Lifted-product code|concern=[[WP:LLMPRV|Presumptive removal of LLM-generated content]]. Please do not remove this tag without following [[WP:LLMPRVOBJ|the procedures for disputing presumptive removal of LLM-generated content]].}} ~~~~ |
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
References
- 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.