Homological product code

Homological product code[1–3]

Alternative names: Tensor product code.

Description

CSS code formulated using the tensor product of two chain complexes of length one or greater (see Qubit CSS-to-homology correspondence).

Homological products and ordinary tensor products of chain complexes differ in a way that depends on whether the underlying code is defined by a general or a length-three chain complex [2; Sec. 3.4.3].

Protection

Given two codes \([[n_i, k_i, d_i, w_i]]\) for \(i\in\{1,2\}\), where \(w_i\) denotes the maximum hamming weight of all rows and columns of \(\partial_i\), the homological product code has parameter \([[n=n_1 n_2, k=k_1 k_2, d\leq d_1 d_2, w\leq w_1+w_2]]\). From this formula, and the fact that a randomly selected boundary operator \(\partial\) yields a CSS code that is good with high probability, we see that the product code has \(k=\Theta(n)\) and \(w=O(\sqrt{n})\) with high probability. The main result in Ref. [4] is to show that the product code has linear distance with high probability as well. To sum up, it is shown that we have a family of \([[n,k=c_1 n, d=c_2 n, w=c_3 \sqrt{n}]]\) codes given small enough \(c_1,c_2,c_3\).

Gates

Universal set of gates can be obtained by fault-tolerantly mapping between different encoded representations of a given logical state [5].Parallel Pauli product measurements via homomorphic CNOT gates [6].

Decoding

Union-find decoder [7].

Fault Tolerance

Universal set of gates can be obtained by fault-tolerantly mapping between different encoded representations of a given logical state [5].

Cousins

Random stabilizer code— Random homological codes are asymptotically good with high probability [1; Thm. 1].
Single-shot code— It is conjectured that a particular class of codes called three-dimensional product codes is single shot [8].
Subsystem homological product code— SP codes reduce to homological product codes when there are no gauge qubits [9].
Distance-balanced code— Distance balancing relies on taking a homological product of chain complexes corresponding to a classical and a quantum code.

Member of code lists

Primary Hierarchy

Quantum Domain

Qubit Kingdom

Qubit codeQECC Quantum

Union stabilizer (USt) codeQECC Quantum

Qubit stabilizer codeQubit Stabilizer Hamiltonian-based QECC Quantum

Coherent-parity-check (CPC) code

Qubit CSS codeCSS Stabilizer Hamiltonian-based QECC Quantum

Generalized homological-product qubit CSS codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum

Higher-dimensional homological product code

Parents

Higher-dimensional homological product code

Multi-dimensional homological products of two length-two chain complexes reduce to homological product codes.

Fiber-bundle codeQubit Generalized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum

A fiber-bundle code can be viewed as a homological product code with a twisted product.

Homological product code

Children

Hypergraph product (HGP) code

A homological-product code of length-one chain complexes reduce to an HGP code.

High-dimensional expander (HDX) code

Ramanujan codes result from a tensor product of a classical-code and a quantum-code chain complex.

Square homological product code

Square homological product codes are homological product codes whose boundary operators are square matrices [2; Sec. 3.4].

References

[1]: M. H. Freedman and M. B. Hastings, “Quantum Systems on Non-\(k\)-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs”, (2013) arXiv:1301.1363
[2]: B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
[3]: M. B. Hastings, “Weight Reduction for Quantum Codes”, (2016) arXiv:1611.03790
[4]: S. Bravyi and M. B. Hastings, “Homological Product Codes”, (2013) arXiv:1311.0885
[5]: T. Jochym-O’Connor, “Fault-tolerant gates via homological product codes”, Quantum 3, 120 (2019) arXiv:1807.09783 DOI
[6]: Q. Xu, H. Zhou, G. Zheng, D. Bluvstein, J. P. B. Ataides, M. D. Lukin, and L. Jiang, “Fast and Parallelizable Logical Computation with Homological Product Codes”, (2024) arXiv:2407.18490
[7]: N. Delfosse and M. B. Hastings, “Union-Find Decoders For Homological Product Codes”, Quantum 5, 406 (2021) arXiv:2009.14226 DOI
[8]: A. O. Quintavalle, M. Vasmer, J. Roffe, and E. T. Campbell, “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2, (2021) arXiv:2009.11790 DOI
[9]: W. Zeng and L. P. Pryadko, “Minimal distances for certain quantum product codes and tensor products of chain complexes”, Physical Review A 102, (2020) arXiv:2007.12152 DOI

Page edit log

Victor V. Albert (2022-11-22) — most recent
Victor V. Albert (2022-03-14)
Xinyuan Zheng (2021-12-15)
Victor V. Albert (2021-12-03)

Cite as:

“Homological product code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/homological_product

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/qldpc/balanced_product/tensor/singlesector/homological_product.yml.