# Quantum locally testable code (QLTC)[1]

## Description

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

## Notes

## Parents

- Block quantum code
- Hamiltonian-based code — Quantum LTC codespaces are ground-state spaces of \(u\)-local Hamiltonians.

## Child

- Quantum check-product code — Quantum check-product constructions yield a sLTC code with constant soundness \(2\rho\) from a classical LTC code with soundness \(\rho\). While these are the first bona-fide QLTC code family because they admit asymptotically constant soundess, they are not practical because their distance is two.

## Cousins

- Quantum low-density parity-check (QLDPC) code — Stabilizer LTCs are QLDPC. More general QLTCs are not defined using Pauli strings, but the codespace is the ground-state subspace of a local Hamiltonian. In this sense, QLTCs are QLDPC codes.
- Self-correcting quantum code — The notion of an energy barrier in a self-correcting memory is intimately related to the soundness of a QLTC.
- Locally testable code (LTC)
- Hemicubic code — A hemicubic code family has asymptotically diminishing soundness that scales as order \(\Omega(1/\log n)\).
- Hypersphere product code — The hypersphere product code family has asymptotically diminishing soundness that scales as order \(O(1/(\log n)^2)\), locality of stabilizer generators scaling as order \(O(\log n)\), and distance \(\Theta(\sqrt{n})\).

## References

- [1]
- D. Aharonov and L. Eldar, “Quantum Locally Testable Codes”, (2013) arXiv:1310.5664
- [2]
- L. Eldar and A. W. Harrow, “Local Hamiltonians Whose Ground States Are Hard to Approximate”, 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) (2017) DOI
- [3]
- 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

## Page edit log

- Victor V. Albert (2022-09-28) — most recent

## Cite as:

“Quantum locally testable code (QLTC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/qltc