Homological product code

Homological product code[1,2]

Also known as Tensor product code.

Description

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

Given two classical codes, \(C_i=[n_i,k_i,d_i]\) with \(i\in\{1,2\}\), whose parity-check matrices \(H_i\) satisfy \(H_i^2 = 0\), their homological product yields two classical codes with \(C_{X,Z}\) with parity-check matrices \begin{align} H_X = H_Z^T = H_1 \otimes I + I \otimes H_2~, \tag*{(1)}\end{align} where \(I\) is the identity. These two codes then yield a homological product code via the CSS construction.

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 [3; 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. [2] is to show that the product code actually 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 [4].

Decoding

Union-find [5].

Fault Tolerance

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

Parent

Fiber-bundle code — Fiber-bundle code can be viewed as a homological product code with a twisted product.

Child

Hypergraph product (HGP) code — A homological product of chain complexes corresponding to two classical codes is a hypergraph product code [6].

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 [7].
Subsystem homological product code — SP codes reduce to homological product codes when there are no gauge qubits [8].
Distance-balanced code — Distance balancing relies on taking a homological product of chain complexes corresponding to a classical and a quantum code.

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]: S. Bravyi and M. B. Hastings, “Homological Product Codes”, (2013) arXiv:1311.0885
[3]: B. Audoux and A. Couvreur, “On tensor products of CSS Codes”, (2018) arXiv:1512.07081
[4]: T. Jochym-O’Connor, “Fault-tolerant gates via homological product codes”, Quantum 3, 120 (2019) arXiv:1807.09783 DOI
[5]: N. Delfosse and M. B. Hastings, “Union-Find Decoders For Homological Product Codes”, Quantum 5, 406 (2021) arXiv:2009.14226 DOI
[6]: M. B. Hastings, J. Haah, and R. O’Donnell, “Fiber bundle codes: breaking the n \({}^{\text{1/2}}\) polylog( n ) barrier for Quantum LDPC codes”, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021) arXiv:2009.03921 DOI
[7]: A. O. Quintavalle et al., “Single-Shot Error Correction of Three-Dimensional Homological Product Codes”, PRX Quantum 2, (2021) arXiv:2009.11790 DOI
[8]: 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/homological/balanced_product/homological_product.yml.