Quantum locally testable code (QLTC)[1]

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 of many of the code's local projectors.

The average-energy penalty 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 QLTC families as those for which the soundness is asymptotically constant. QLTC families that also have asymptotically constant distance, rate, and weight of local projectors are called \(c^3\)-QLTCs; none have been found so far.

More technically, a QLTC is a code \(\mathsf{C}\) defined as the ground-state space of a commuting-projector Hamiltonian \(H\) consisting of a sum of \(r\) local projectors, each of which acts on exactly \(u\) qubits (for some constant \(u\)). Such a code is a \((u,R)\)-QLTC with soundness function \(R(\delta)\in[0,1]\) if \begin{align} \label{eq:qltc} \forall \delta > 0,|\psi\rangle~:~\text{dist}(|\psi\rangle,C) \geq \delta n \Rightarrow \frac{1}{r}\langle\psi|H|\psi\rangle\geq R(\delta)~, \tag*{(1)}\end{align} where \(\text{dist}(|\psi\rangle,\mathsf{C})\) is a particular distance function between the state \(|\psi\rangle\) and the codespace \(\mathsf{C}\) [1; Def. 13]. The locality parameter \(u\) is called the query complexity of the code.

A qubit, modular-qudit, or Galois-qudit stabilizer code that is locally testable is called a stabilizer locally testable code (SLTC). In other words, the code admits a set of \(r\) \(u\)-local stabilizer generators \(S_i\) whose corresponding code Hamiltonian \(H=\frac{1}{2}\sum_{i=1}^r I-S_i\) satisfies the requirement of being QLTC.

For example, the \([[n=2L^2,k=2,d=L]]\) toric code on an \(L\times L\) lattice is not a QLTC because of the following argument. Let \(|\psi\rangle\) be a ground state that is excited by \(L/3\) Pauli strings, each of length \(L/2\). In order to fit on the lattice, such strings can, e.g., be horizontal and aligned next to each other in the vertical direction. The distance function \(\text{dist}(|\psi\rangle,\mathsf{C})\) is the weight of the smallest Pauli string that multiplies \(|\psi\rangle\) to yield a state in the codespace. In this case, that weight is the same as the weight of the perturbing string, i.e., \(L^2/6\), requiring \(\delta = 1/12\) to satisfy (1). There are \(2L/3\) violated Hamiltonian terms because each of the \(L/3\) strings violates only two stabilizer generators. However, there are \(r = 2(L^2-1)\) stabilizer generators, so the implication of (1) is not satisfied for nonzero soundness as \(L\to\infty\) because \(\frac{1}{r}\langle\psi|H|\psi\rangle = \frac{2L/3}{2(L^2-1)}\to 0\).