Locally testable code (LTC)[1][2][3][4]

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\).

Typically, one looks at how \(R\) scales with increasing code size for infinite families of codes, defining LTC families as those for which the soundness is asymptotically constant. Such LTC families with asymptotically constant distance, rate, and query complexity are called \(c^3\)-LTCs. The first two such families are classical codes arising from the expander lifted-product quantum code construction and left-right Cayley complex codes.

A technical definition for codes over binary alphabets is provided as follows; for general alphabets, see Ref. [5]. The idea behind LTCs is to be able to reliably test whether a given bit-string \(x\) is in the code by only sampling subsets of \(u\) bits. To have something to check against, we first have to define a collection of length-\(u\) subsets \(S\) of bit locations that are called allowed local views. A code is LTC if the following two conditions are satisfied [6; Thm. 1.1].

First, if \(x\) is a codeword, then all of its restrictions \(x|_S\) to the subsets \(S\) are allowed local views, \begin{align} x\in C \Rightarrow x|_S \in \{\text{allowed local views}\}~. \tag*{(1)}\end{align} This guarantees that codewords can indeed be determined from this limited sampling procedure.

Second, the probability that a given restriction is not an allowed local view is lower-bounded by the relative distance to the code, \begin{align} \text{Pr}_S (x|_S\text{ not allowed local view}) \geq \frac{R}{n} D(x,C)~, \tag*{(2)}\end{align} where \(D(x,C)\) is the Hamming distance between \(x\) and the closest codeword to \(x\). This condition ensures that strings \(x\) can be deemed to be not in the codespace with high probability, i.e., with probability increasing as \(x\) gets farther from the code.