Homological product code[1]
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. [3] 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 [4].Parallel Pauli product measurements via homomorphic CNOT gates [5].Decoding
Union-find [6].Fault Tolerance
Universal set of gates can be obtained by fault-tolerantly mapping between different encoded representations of a given logical state [4].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.
Primary Hierarchy
Generalized homological-product qubit CSS codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum
Fiber-bundle codeGeneralized homological-product QLDPC CSS Stabilizer Hamiltonian-based QECC Quantum
Parents
Fiber-bundle code can be viewed as a homological product code with a twisted product.
Homological product code
Children
A homological product of chain complexes corresponding to two linear binary codes is a hypergraph product code [9]. Homological product codes constructed with diagonal boundary operators admit very different properties than those with rectangular boundary operators.
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]
- S. Bravyi and M. B. Hastings, “Homological Product Codes”, (2013) arXiv:1311.0885
- [4]
- T. Jochym-O’Connor, “Fault-tolerant gates via homological product codes”, Quantum 3, 120 (2019) arXiv:1807.09783 DOI
- [5]
- 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
- [6]
- N. Delfosse and M. B. Hastings, “Union-Find Decoders For Homological Product Codes”, Quantum 5, 406 (2021) arXiv:2009.14226 DOI
- [7]
- 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
- [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
- [9]
- 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 1276 (2021) arXiv:2009.03921 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