Here is a list of codes related to locally testable codes.
Code | Description |
---|---|
Balanced code | An even-length-\(n\) \(q\)-ary code whose nonzero codewords all have a Hamming weight of \(n/2\). A code is \(\epsilon\)-balanced if the relative weight (i.e., weight divided by \(n\)) of all nonzero codewords lies in the interval \([\frac{1-\epsilon}{2},\frac{1+\epsilon}{2}]\). A code is \(\gamma\)-unbiased if the relative weight lies in the interval \((\frac{1}{2}-\frac{1}{n^{\gamma}},\frac{1}{2}+\frac{1}{n^{\gamma}})\). |
Ben-Sasson-Goldreich-Harsha-Sudan-Vadhan (BGHSV) code | Locally testable \([n,k,d]\) code with \(n = k^{1+\epsilon}\) and query complexity of order \(O(1/\epsilon)\) for any \(\epsilon > 0\). |
Ben-Sasson-Sudan code | Locally testable \([n,k/2,d]_{2^m}\) code with \(k\) a power of two, \(n = k \log^{c} k\), and query complexity \(\log^{c}k\) for some universal constant \(c\). |
Ben-Sasson-Sudan-Vadhan-Wigderson (BSVW) code | Locally testable \([n,k,d]\) code with \(n = k \cdot 2^{\tilde{O}(\sqrt{\log k})}\) and asymptotically constant query complexity. |
Binary linear LTC | A binary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). |
Bose–Chaudhuri–Hocquenghem (BCH) code | Cyclic \(q\)-ary code, with \(n\) and \(q\) relatively prime, whose zeroes are consecutive powers of a primitive \(n\)th root of unity \(\alpha\). More precisely, the generator polynomial of a BCH code of designed distance \(\delta\geq 1\) is the lowest-degree monic polynomial with zeroes \(\{\alpha^b,\alpha^{b+1},\cdots,\alpha^{b+\delta-2}\}\) for some \(b\geq 0\). BCH codes are called narrow-sense when \(b=1\), and are called primitive when \(n=q^r-1\) for some \(r\geq 2\). More general BCH codes can be defined for zeroes are powers of the form \(\{b,b+s,b+2s,\cdots,b+(\delta-2)s\}\) where gcd\((s,n)=1\). |
Classical Goppa code | Let \( G(x) \) be a polynomial describing a projective-plane curve with coefficients from \( GF(q^m) \) for some fixed integer \(m\). Let \( L \) be a finite subset of the extension field \( GF(q^m) \) where \(q\) is prime, meaning \( L = \{\alpha_1, \cdots, \alpha_n\} \) is a subset of nonzero elements of \( GF(q^m) \). A Goppa code \( \Gamma(L,G) \) is an \([n,k,d]_q\) linear code consisting of all vectors \(a = a_1, \cdots, a_n\) such that \( R_a(x) =0 \) modulo \(G(x)\), where \( R_a(x) = \sum_{i=1}^n \frac{a_i}{z - \alpha_i} \). |
Cyclic linear \(q\)-ary code | A \(q\)-ary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=q^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
Cyclic linear binary code | A binary code of length \(n\) is cyclic if, for each codeword \(c_1 c_2 \cdots c_n\), the cyclically shifted string \(c_n c_1 \cdots c_{n-1}\) is also a codeword. A cyclic code is called primitive when \(n=2^r-1\) for some \(r\geq 2\). A shortened cyclic code is obtained from a cyclic code by taking only codewords with the first \(j\) zero entries, and deleting those zeroes. |
Dinur code | Member of infinite family of locally testable \([n,n/\text{polylog}(n),d]\) codes with vanishing rate. Code construction relies on a construction utilizing tensor-product codes [1]. |
Expander LP code | Family of \(G\)-lifted product codes constructed using two random classical Tanner codes defined on expander graphs [2]. For certain parameters, this construction yields the first asymptotically good QLDPC codes. Classical codes resulting from this construction are one of the first two families of \(c^3\)-LTCs. |
Generalized RM (GRM) code | Reed-Muller code GRM\(_q(r,m)\) of length \(n=q^m\) over \(GF(q)\) with \(0\leq r\leq m(q-1)\). Its codewords are evaluations of the set of all degree-\(\leq r\) polynomials in \(m\) variables at the points of \(GF(q)\). |
Goldreich-Sudan code | Locally testable \([n,k,d]\) code with \(n = k^{1+O(1/u)}\) and distance \(\Omega(n)\) for query complexity \(u\). The same work also presented a probabilistic construction of codes of size \(k^{1+o(1)}\). |
Hadamard code | An \([2^m,m,2^{m-1}]\) balanced binary code. The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)). |
Hypergraph product (HGP) code | A member of a family of CSS codes whose stabilizer generator matrix is obtained from a hypergraph product of two classical linear codes. Codes from hypergraph products in higher dimension are called higher-dimensional HGP codes [3]. |
Kopparty-Meir-Ron-Zewi-Saraf (KMRS) code | Member of a family of locally testable binary linear codes with constant rate, constant relative distance, and subpolynomial query complexity \(u = (\log n)^{O(\log \log n)}\)). Later work by Gopi, Kopparty, Oliveira, Ron-Zewi, and Saraf [4] showed that related concatenated codes achieve the GV bound. |
La-cross code | Code constructed using the hypergraph product of two copies of a cyclic LDPC code. The construction uses cyclic LDPC codes with generating polynomials \(1+x+x^k\) for some \(k\). Using a length-\(n\) seed code yields an \([[2n^2,2k^2]]\) family for periodic boundary conditions and an \([[(n-k)^2+n^2,k^2]]\) family for open boundary conditions. |
Left-right Cayley complex code | Binary code constructed on a left-right Cayley complex using a pair of base codes \(C_A,C_B\) and an expander graph [2] such that codewords for a fixed graph vertex are codewords of the tensor code \(C_A \otimes C_B\). A family of such codes is one of the first \(c^3\)-LTCs. |
Linear binary code | An \((n,2^k,d)\) linear code is denoted as \([n,k]\) or \([n,k,d]\), where \(d\) is the code's distance. Its codewords form a linear subspace, i.e., for any codewords \(x,y\), \(x+y\) is also a codeword. A code that is not linear is called nonlinear. |
Locally correctable code (LCC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LCC is a block code for which one can recover any coordinate of a codeword from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). |
Locally decodable code (LDC) | Recall that a block code encodes a length-\(k\) message into a length-\(n\) codeword, which is then sent through a noise channel to yield an error word. Informally, an LDC is a block code for which one can recover any coordinate of the message from at most \(r\) coordinates of the error word (assuming the error word is within some tolerated corruption rate \(\delta\)). Efficiency of the correction is quantified by the code's query complexity \(r\), and correction is performed by sampling subsets of \(r\) bits. |
Locally testable code (LTC) | Code for which one can efficiently check whether a given string is a codeword or is far from a codeword. Efficiency of the verification is quantified by the code's query complexity \(u\), while effectiveness is quantified by the code's soundness \(R\). |
Long code | Locally testable \([2^{2^k},k,d]\) code. The encoder maps a \(k\)-bit string into a codeword that consists of the values of all Boolean functions on the \(k\)-bit string. The code is not practical, but is useful for certain probabilistically checkable proof (PCP) constructions [5]. |
Long-range enhanced surface code (LRESC) | Code constructed using the hypergraph product of two copies of a concatenated LDPC-repetition seed code. This family interpolates between surface codes and hypergraph codes since the hypergraph product of two repetition codes yields the planar surface code. The construction uses small \([3,2,2]\) and \([6,2,4]\) LDPC codes concatenated with \([4,1,4]\) and \([2,1,2]\) repetition codes, respectively. An example using a \([5,2,3]\) code is also presented. |
Lossless expander balanced-product code | QLDPC code constructed by taking the balanced product of lossless expander graphs. Using one part of a quantum-code chain complex constructed with one-sided loss expanders [6] yields a \(c^3\)-LTC [7]. Using two-sided expanders, which are only conjectured to exist, yields an asymptotically good QLDPC code family [8]. |
Meir code | Locally testable \([n,k,d]_q\) code with query complexity \(\text{poly}(\log k)\) and rejection ratio \(R/n = 1/\text{poly}(\log k)\). Code construction is probabilistic and combinatorial. |
Multiplicity code | A generalization of an \(m\)-variate polynomial evaluation code based on evaluating polynomials and \(s\) of their derivatives at all points in \(GF(q)^m\). Originally proposed for coding using the Rosenbloom-Tsfasman metric [9]. Univariate (\(m=1\)) [9,10] and multivariante (\(m>1\)) [11] codes have been proposed. |
Quantum expander code | CSS codes constructed from a hypergraph product of bipartite expander graphs [2] with bounded left and right vertex degrees. For every bipartite graph there is an associated matrix (the parity check matrix) with columns indexed by the left vertices, rows indexed by the right vertices, and 1 entries whenever a left and right vertex are connected. This matrix can serve as the parity check matrix of a classical code. Two bipartite expander graphs can be used to construct a quantum CSS code (the quantum expander code) by using the parity check matrix of one as \(X\) checks, and the parity check matrix of the other as \(Z\) checks. |
Quantum locally testable code (QLTC) | A local commuting-projector Hamiltonian-based block quantum code which has a nonzero average-energy penalty for creating large errors. Informally, QLTC error states that are far away from the codespace have to be excited states by a number of the code's local projectors that scales linearly with \(n\). |
Reed-Muller (RM) code | Member of the RM\((r,m)\) family of linear binary codes derived from multivariate polynomials. The code parameters are \([2^m,\sum_{j=0}^{r} {m \choose j},2^{m-r}]\), where \(r\) is the order of the code satisfying \(0\leq r\leq m\). First-order RM codes are also called biorthogonal codes, while \(m\)th order RM codes are also called universe codes. Punctured RM codes RM\(^*(r,m)\) are obtained from RM codes by deleting one coordinate from each codeword. |
Reed-Solomon (RS) code | An \([n,k,n-k+1]_q\) linear code based on polynomials over \(GF(q)\). |
Sierpinsky fractal spin-liquid (SFSL) code | A fractal type-I fracton CSS code defined on a cubic lattice [12; Eq. (D22)]. The code admits an excitation-moving operator shaped like a Sierpinski triangle [12; Fig. 2]. |
Tanner code | A linear \(q\)-ary code defined on a bipartite graph similar to a Tanner graph. This generalized Tanner graph consists of variable nodes and constraint nodes, with the generalization being that the constraint nodes of degree \(r\) now represent a linear codes of length \(r\). |
Toric code | Version of the Kitaev surface code on the two-dimensional torus, encoding two logical qubits. Being the first manifestation of the surface code, "toric code" is often an alternative name for the general construction. Twisted toric code [13; Fig. 8] refers to the construction on a torus with twisted (a.k.a. shifted) boundary conditions. |
\([[4,2,2]]\) Four-qubit code | Four-qubit CSS stabilizer code is the smallest qubit stabilizer code to detect a single-qubit error. |
\(q\)-ary linear LTC | A \(q\)-ary linear code \(C\) of length \(n\) that is a \((u,R)\)-LTC with query complexity \(u\) and soundness \(R>0\). More technically, the code is a \((u,R)\)-LTC if the rows of its parity-check matrix \(H\in GF(q)^{r\times n}\) have weight at most \(u\) and if \begin{align} \frac{1}{r}|H x| \geq \frac{R}{n} D(x,C) \tag*{(1)}\end{align} holds for any \(q\)-ary string \(x\), where \(D(x,C)\) is the \(q\)-ary Hamming distance between \(x\) and the closest codeword to \(x\) [14; Def. 11]. A code satisfying the above constraint without the weight-\(u\) restriction is called an \(R\)-testable code [15]. |
References
- [1]
- E. Ben-Sasson and M. Sudan, “Robust Locally Testable Codes and Products of Codes”, (2004) arXiv:cs/0408066
- [2]
- S. Hoory, N. Linial, and A. Wigderson, “Expander graphs and their applications”, Bulletin of the American Mathematical Society 43, 439 (2006) DOI
- [3]
- W. Zeng and L. P. Pryadko, “Higher-Dimensional Quantum Hypergraph-Product Codes with Finite Rates”, Physical Review Letters 122, (2019) arXiv:1810.01519 DOI
- [4]
- S. Gopi et al., “Locally Testable and Locally Correctable Codes approaching the Gilbert-Varshamov Bound”, IEEE Transactions on Information Theory 64, 5813 (2018) DOI
- [5]
- P. Harsha et al., “Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)”, (2010) arXiv:1002.3864
- [6]
- M. Capalbo et al., “Randomness conductors and constant-degree lossless expanders”, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing (2002) DOI
- [7]
- T.-C. Lin and M.-H. Hsieh, “\(c^3\)-Locally Testable Codes from Lossless Expanders”, (2022) arXiv:2201.11369
- [8]
- T.-C. Lin and M.-H. Hsieh, “Good quantum LDPC codes with linear time decoder from lossless expanders”, (2022) arXiv:2203.03581
- [9]
- M. Yu. Rosenbloom, M. A. Tsfasman, “Codes for the m-Metric”, Probl. Peredachi Inf., 33:1 (1997), 55–63; Problems Inform. Transmission, 33:1 (1997), 45–52
- [10]
- Rasmus R. Nielsen. List decoding of linear block codes. PhD thesis, Technical University of Denmark, 2001
- [11]
- S. Kopparty, S. Saraf, and S. Yekhanin, “High-rate codes with sublinear-time decoding”, Journal of the ACM 61, 1 (2014) DOI
- [12]
- A. Dua et al., “Sorting topological stabilizer models in three dimensions”, Physical Review B 100, (2019) arXiv:1908.08049 DOI
- [13]
- N. P. Breuckmann and J. N. Eberhardt, “Balanced Product Quantum Codes”, IEEE Transactions on Information Theory 67, 6653 (2021) arXiv:2012.09271 DOI
- [14]
- A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI
- [15]
- M. Chapman, T. Vidick, and H. Yuen, “Efficiently stable presentations from error-correcting codes”, (2023) arXiv:2311.04681