[Jump to code hierarchy]

Quantum locally testable code (QLTC) [1,2]

Description

A local-projector Hamiltonian-based block quantum code which has a nonzero average-energy penalty for creating large errors. Informally, testing a randomly chosen local projector must reject states far from the codespace with probability bounded away from zero as \(n\) grows.

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 relative distance, rate, and weight of local projectors are called \(c^3\)-QLTCs. \(c^3\)-QLTCs were constructed concurrently in Refs. [3–5], all three being Reed-Solomon cubical sheaf codes.

More technically, a QLTC is a code \(\mathsf{C}\) defined as the ground-state space of a frustration-free Hamiltonian \(H\) consisting of a sum of \(r\) local projectors (where \(r\) typically scales linearly with \(n\)), each of which acts on at most \(u\) qubits or qudits (for some constant \(u\)). Such a code is a \((u,R)\)-QLTC with soundness function \(R(\delta)\in[0,1]\) if \begin{align} \forall \delta > 0,|\psi\rangle~:~dist(|\psi\rangle,C) \geq \delta n \Rightarrow \frac{1}{r}\langle\psi|H|\psi\rangle\geq R(\delta)~,\tag*{$(1)$} \end{align}where \(dist(|\psi\rangle,\mathsf{C})\) is a particular distance function between the state \(|\psi\rangle\) and the codespace \(\mathsf{C}\) [2; Def. 13]. The locality parameter \(u\) is called the query complexity of the code. For a frustration-free local Hamiltonian \(H=\sum_{i=1}^r h_i\) with \(0\leq h_i\leq I\), local testability can be expressed as the operator soundness inequality \(H/r\geq\sigma\Delta_{\mathsf{C}}/n\) with \(\sigma>0\) [6][7; Sec. 2.2]. Here, \(\Delta_{\mathsf{C}}=\sum_{j=0}^{n-1}(I-\Pi_{V_j})\), and \(\Pi_{V_j}\) projects onto the span of states obtained by applying errors of weight at most \(j\) to codewords.

In the linear-soundness formulation, \(R(\delta)=\rho\delta\), where \(\rho\) is the soundness parameter [8].

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=\sum_{i=1}^r (I-\Pi_i)\) satisfies the requirement of being a QLTC. Here, \(\Pi_i\) projects onto the \(+1\) eigenspace of \(S_i\), so \(I-\Pi_i=(I-S_i)/2\) for qubits.

For example, the \([[n=2L^2,k=2,d=L]]\) toric-code family on an \(L\times L\) lattice does not have constant linear soundness [2]. For even \(L\), applying a \(Z\)-type Pauli string along a straight segment of length \(L/2\) to a ground state produces a state \(|\psi\rangle\) at distance \(L/2\) from the codespace. Only the two stabilizer generators at the endpoints are violated. Using all \(r=2L^2\) star and plaquette checks gives \(\langle\psi|H|\psi\rangle/r=1/L^2\), while \(\delta=(L/2)/n=1/(4L)\). Thus, (1) with \(R(\delta)=\rho\delta\) requires \(\rho\leq 4/L\to0\).

Protection

The robustness \(\rho(\delta)\) of an SLTC whose qudits each lie in \(D\) generators is the largest \(\rho\) such that every Pauli error of weight \(\delta n\), taken modulo the centralizer, violates at least \(\rho D\delta n\) generators [1; Def. 9]. For \(u\)-local generators on \(q\)-dimensional qudits, distance at least two, and no nontrivial stabilizer of weight below \(u\), \(\rho(\delta)\leq 1-1/(q^2-1)\) for \(\delta\leq 1/(u^3D)\) [1; Fact 4]. If also \(u\geq 4\) and the distance is at least \(u\), then \(\rho(\delta')\leq(1-1/(q^2-1))(1-\gamma)\) with \(\gamma\geq\min\{10^{-3},0.01/u\}\), for some \(\delta'\) within \(1\%\) of any sufficiently small constant \(\delta\) [1; Thm. 4]. If the distance is at least two and every set \(S\) of at most \(u\) qudits lies in at least \((1-\epsilon)D|S|\) generators with \(\epsilon<1/2\), then \(\rho(\delta)\leq 2\epsilon\) for all \(\delta<\min\{1/(u^3D),\delta_C/2\}\), where \(\delta_C\) is the relative distance [1; Thm. 3].

Distance balancing and weight reduction are useful for constructing QLTCs. For CSS QLTC families satisfying \(d_Z=\omega(w_Zw_X)\), a slightly modified version of the weight-reduction procedure of Ref. [9] yields QLTCs of constant locality [10; Lemma 3.8]. If the numbers of \(X\)- and \(Z\)-checks are both \(\Theta(n)\) and the input soundness parameters are \(O(1)\), the soundness losses are polynomial in \(w_X,w_Z,q_X,q_Z\). These losses are at most polylogarithmic when \(w_X,w_Z,q_X,q_Z=O(\log n)\). The effect of generalized distance balancing [11] on soundness is established in [12; Thm. 1.1].

Soundness amplification can be used to obtain a constant-soundness (i.e., \(\rho = \Omega(1)\)) QLTC family from a CSS family with sub-constant soundness \(\rho\) [13; Prop. 1][10; Thm. 1.2]. The construction of Ref. [10; Thm. 1.2] multiplies the locality by at most a polynomial in \(1/\rho\).

AEL distance amplification [14,15] can be used to convert an \([[n,k,d,w]]\) soundness-\(\rho\) CSS LTC family into one with the same dimension, linear distance, and block length differing by at most a constant factor, with \(w\) and \(\rho\) differing by at most a polynomial factor in \(w\) and \(n/d\) [10; Thm. 1.3].

Notes

It was shown in Ref. [8] that existence of a QLTC with constant parameters would imply resolution of the No low-energy trivial states (NLTS) conjecture [16] (see also [17]). QLTCs are believed to also be useful for solving the quantum PCP conjecture [18].Families of frustration-free local Hamiltonians whose codes have linear distance, constant operator soundness, and a dimension with a prime divisor tending to infinity have no low-energy trivial magic (NLTM) [7; Thm. 3]. For every fixed bound on qudit dimensions, their states with energy density below a constant require circuits of depth of order \(\Omega(\log n)\) to prepare from qudit stabilizer states [7; Thm. 3].

Cousins

  • Commuting-projector Hamiltonian code— Stabilizer QLTCs admit commuting-projector tests. The general QLTC definition does not require the test projectors to commute [2; Def. 14].
  • QLDPC code— Stabilizer LTCs with bounded site degree are QLDPC codes. General QLTCs need not be stabilizer 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— If a qubit CSS code defined by \(H_{Z}\) and \(H_{X}\) is locally testable with soundness \(\rho\), then the constituent codes \(\ker H_{Z}\) and \(\ker H_{X}\) are locally testable with soundness at least \(\rho/2\). Conversely, constituent codes with soundness \(\rho\) yield a CSS code with soundness \(\rho\) [8; Fact 17].
  • Distance-balanced code— Distance balancing and weight reduction are useful for constructing QLTCs [10,12,19].
  • Locally testable code (LTC)— QLTCs are quantum analogues of LTCs.
  • Good QLDPC code— Stabilizer \(c^3\)-QLTCs, i.e., stabilizer QLTC families with constant rate, linear distance, constant soundness, and bounded locality, are good QLDPC codes.
  • Gauged sheaf QLTC— Gauged sheaf QLTCs have linear distance, and their frustration-free Hamiltonians satisfy the operator-soundness form of local testability with constant soundness [7; Thm. 4].
  • Dinur-Lin-Vidick (DLV) code— DLV codes with Abelian-lift complexes have linear dimension and inverse poly-logarithmic relative distance and soundness [20]. Applying distance amplification and soundness amplification yields asymptotically constant soundness, order \(\Theta(n)\) distance, order \(\Theta(n)\) dimension, but poly-logarithmic locality [10; Table 4].
  • Hemicubic code— The hemicubic code family has a soundness lower bound of order \(\Omega(1/\log n)\), locality of stabilizer generators scaling as order \(O(\log n)\), and distance of order \(\Theta(\sqrt{n})\). Soundness amplification and AEL distance amplification [14,15] can also yield improvements in various parameters [10; Table 3]. Application of generalized distance balancing [11] to hemicubic codes using an asymptotically good classical code of length \(t\) yields \(\Omega( 1/(\log(n) t^2) )\) soundness and order \(\Theta(\sqrt{n}t)\) distance while maintaining locality scaling and increasing the dimension to order \(\Theta(t^2)\) [12].
  • 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 of order \(\Theta(\sqrt{n})\). Applying Hastings’ weight-reduction construction yields QLDPC families with distance \(\Theta^*(\sqrt{n})\) and inverse-polylogarithmic soundness [19]. Application of generalized distance balancing [11] to hypersphere product codes using an asymptotically good classical code of length \(t\) yields \(O( 1/(\log(n)^2 t^2) )\) soundness and order \(\Theta(\sqrt{n}t)\) distance while maintaining locality scaling and at the expense of a dimension scaling as order \(\Theta(t^2)\) [12].

Primary Hierarchy

Parents
Quantum LTC codespaces are ground-state spaces of \(u\)-local frustration-free Hamiltonians.
Quantum locally testable code (QLTC)
Children
Quantum check-product constructions yield an SLTC code with constant soundness \(2\rho\) from a classical LTC code with soundness \(\rho\) [21]. These form the first bona-fide QLTC family because they admit asymptotically constant soundness, but they are not practical because their distance is two.
Reed-Solomon cubical sheaf codes are binary QLTCs with linear distance, and suitable local-code dimensions make them \(c^3\)-QLTC families [4][3; Thm. 6.2].

References

  1. [1]

    D. Aharonov and L. Eldar, “Commuting Local Hamiltonians on Expanders, Locally Testable Quantum codes, and the qPCP conjecture”, (2013) arXiv:1301.3407

  2. [2]

    D. Aharonov and L. Eldar, “Quantum Locally Testable Codes”, (2013) arXiv:1310.5664

  3. [3]

    Y. Chen, M. M.-Y. Huang, Y. Liu, and E.-C. Tang, “Cubical Sheaf Complexes with Constant Expansion with Applications to Asymptotically Good qLTCs”, (2026) arXiv:2609.28028

  4. [4]

    W. Gay and F. G. Jeronimo, “Asymptotically Good Quantum Locally Testable Codes”, (2026) arXiv:2609.20780

  5. [5]

    M. Bafna, A. Li, and Q. T. Nguyen, “Good Quantum Locally Testable Codes from Product Expansion”, (2026) arXiv:2609.26735

  6. [6]

    A. Leverrier, V. Londe, and G. Zémor, “Towards local testability for quantum coding”, Quantum 6, 661 (2022) arXiv:1911.03069 DOI

  7. [7]

    F. Wei, Z. Han, Z. Li, and Z.-W. Liu, “NLTM Hamiltonians from gauged sheaf quantum locally testable codes”, (2026) arXiv:2609.40220

  8. [8]

    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) 427 (2017) arXiv:1510.02082 DOI

  9. [9]

    M. B. Hastings, “On Quantum Weight Reduction”, (2023) arXiv:2102.10030

  10. [10]

    A. Wills, T.-C. Lin, and M.-H. Hsieh, “Tradeoff Constructions for Quantum Locally Testable Codes”, (2024) arXiv:2309.05541

  11. [11]

    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

  12. [12]

    A. Wills, T.-C. Lin, and M.-H. Hsieh, “General Distance Balancing for Quantum Locally Testable Codes”, (2023) arXiv:2305.00689

  13. [13]

    L. Eldar, “Robust Quantum Entanglement at (nearly) Room Temperature”, (2020) arXiv:1911.04461

  14. [14]

    N. Alon, J. Edmonds, and M. Luby, “Linear time erasure codes with nearly optimal recovery”, Proceedings of IEEE 36th Annual Foundations of Computer Science 512 DOI

  15. [15]

    N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery”, IEEE Transactions on Information Theory 42, 1732 (1996) DOI

  16. [16]

    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

  17. [17]

    L. Golowich and T. Kaufman, “NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes”, (2023) arXiv:2311.09503

  18. [18]

    D. Aharonov, I. Arad, and T. Vidick, “The Quantum PCP Conjecture”, (2013) arXiv:1309.7495

  19. [19]

    M. B. Hastings, “Weight Reduction for Quantum Codes”, (2016) arXiv:1611.03790

  20. [20]

    I. Dinur, T.-C. Lin, and T. Vidick, “Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes”, (2025) arXiv:2402.07476

  21. [21]

    A. Cross, Z. He, A. Natarajan, M. Szegedy, and G. Zhu, “Quantum Locally Testable Code with Constant Soundness”, Quantum 8, 1501 (2024) arXiv:2209.11405 DOI

Page edit log

Your contribution is welcome!

on github.com (edit & pull request)

— see instructions

Zoo Code ID: qltc

Cite as:
“Quantum locally testable code (QLTC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/qltc, arXiv:2606.11484
BibTeX:
@incollection{eczoo_qltc,
title={Quantum locally testable code (QLTC)},
booktitle={The Error Correction Zoo},
year={2026},
editor={Albert, Victor V. and Faist, Philippe},
eprint={2606.11484},
doi={10.48550/arXiv.2606.11484},
url={https://errorcorrectionzoo.org/c/qltc}
}
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/qltc

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/properties/hamiltonian/qltc.yml.