# 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 by a number of the code's local projectors that scales linearly with \(n\).

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 (where \(r\) typically scales linearly with \(n\)), 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
- Commuting-projector code — Quantum LTC codespaces are ground-state spaces of \(u\)-local commuting-projector 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.
- Qubit CSS code — A qubit CSS code defined by \(H_{Z}\) and \(H_{X}\) is glocally testable with some soundness iff the constituent codes \(\ker H_{Z}\) and \(\ker H_{X}\) are locally testable with the same soundness [6; Fact 17].
- Distance-balanced code — Distance balancing is useful for constructing QLTCs. Scaling of the soundness of a given code family is proven in [7; Lemma 7] for the original distance balancing scheme and in [8; Thm. 1.1] for the generalized scheme [9].
- Locally testable code (LTC)
- Dinur-Lin-Vidick (DLV) code — DLV codes have linear dimension and inverse poly-logarithmic relative distance and soundness, assuming a conjecture about random linear maps.
- Hemicubic code — The hypersphere product code family has asymptotically diminishing soundness that scales as order \(\Omega(1/\log n)\), locality of stabilizer generators scaling as order \(O(\log n)\), and distance \(\Theta(\sqrt{n})\). Application of the generalized distance balancing scheme [9] using an asymptotically good classical code of length \(t\) yields \(O(1/(\log(n) t^2))\) soundness and \(\Theta(\sqrt{n}t)\) distance while maintaining locality scaling and at the expense of a dimension scaling as \(\Theta(t^2)\) [8].
- 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/ \log\log n)\), and distance \(\Theta(\sqrt{n})\). Application of the generalized distance balancing scheme [9] using an asymptotically good classical code of length \(t\) yields \(O(1/(\log(n)^2 t^2))\) soundness and \(\Theta(\sqrt{n}t)\) distance while maintaining locality scaling and at the expense of a dimension scaling as \(\Theta(t^2)\) [8].

## 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
- [4]
- L. Golowich and T. Kaufman, “NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes”, (2023) arXiv:2311.09503
- [5]
- D. Aharonov, I. Arad, and T. Vidick, “The Quantum PCP Conjecture”, (2013) arXiv:1309.7495
- [6]
- 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) arXiv:1510.02082 DOI
- [7]
- M. B. Hastings, “Weight Reduction for Quantum Codes”, (2016) arXiv:1611.03790
- [8]
- A. Wills, T.-C. Lin, and M.-H. Hsieh, “General Distance Balancing for Quantum Locally Testable Codes”, (2023) arXiv:2305.00689
- [9]
- S. Evra, T. Kaufman, and G. Zémor, “Decodable quantum LDPC codes beyond the \(\sqrt{n}\) distance barrier using high dimensional expanders”, (2020) arXiv:2004.07935

## Page edit log

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

## Cite as:

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