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

Protection

Distance balancing and weight reduction are useful for constructing QLTCs. Scaling of the soundness of a given code family is proven in [2; Lemma 7] for the original distance balancing scheme and in [3; Thm. 1.1] for a generalized scheme [4]. Weight reduction can be used to construct codes of constant locality out of CSS QLTCs [5; Thm. 1.1].

Soundness amplification [5; Thm. 1.2] can be used to obtain a constant-soundness (i.e., \(R = O(1)\)) QLTC family from a CSS family with a sub-constant value, with the former's locality being at most polynomial in \(1/R\).

AEL distance amplification [6,7] can be used to convert an \([[n^{\prime},k,d,w]]\) soundness-\(R\) CSS LTC family into an \([[n=n^{\prime}+O(1),k,d=O(n)]]\) family with \(w\) and \(R\) differing by a factor at most polynomial in \(w\) and \(n/d\) [5; Thm. 1.3].

Notes

It was shown in Ref. [8] that existence of a QLTC with constant parameters would implies resolution of the No low-energy trivial states (NLTS) conjecture [9] (see also [10]). QLTCs are believed to also be useful for solving the quantum PCP conjecture [11].

Parents

Child

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

Cousins

  • Quantum LDPC (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 [13; Fact 17].
  • Distance-balanced code — Distance balancing and weight reduction are useful for constructing QLTCs [2,3,5].
  • 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 [14]. Applying distance amplification and soundness amplification yields asymptotically constant soundness, order \(\Theta(n)\) distance, order \(\Theta(n)\) dimension, but poly-logarithmic locality [5; Table 4].
  • Hemicubic code — The hemicubic 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 of order \(\Theta(\sqrt{n})\). Soundness amplification and AEL distance amplification [6,7] can also yield improvements in various parameters [5; Table 3]. Application of generalized distance balancing [4] to hemicubic codes using an asymptotically good classical code of length \(t\) yields \(O(1/(\log(n) 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)\) [3].
  • 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 order \(\Theta(\sqrt{n})\). Application of generalized distance balancing [4] to hemicubic 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)\) [3].

References

[1]
D. Aharonov and L. Eldar, “Quantum Locally Testable Codes”, (2013) arXiv:1310.5664
[2]
M. B. Hastings, “Weight Reduction for Quantum Codes”, (2016) arXiv:1611.03790
[3]
A. Wills, T.-C. Lin, and M.-H. Hsieh, “General Distance Balancing for Quantum Locally Testable Codes”, (2023) arXiv:2305.00689
[4]
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
[5]
A. Wills, T.-C. Lin, and M.-H. Hsieh, “Tradeoff Constructions for Quantum Locally Testable Codes”, (2024) arXiv:2309.05541
[6]
N. Alon, J. Edmonds, and M. Luby, “Linear time erasure codes with nearly optimal recovery”, Proceedings of IEEE 36th Annual Foundations of Computer Science DOI
[7]
N. Alon and M. Luby, “A linear time erasure-resilient code with nearly optimal recovery”, IEEE Transactions on Information Theory 42, 1732 (1996) DOI
[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) DOI
[9]
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
[10]
L. Golowich and T. Kaufman, “NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes”, (2023) arXiv:2311.09503
[11]
D. Aharonov, I. Arad, and T. Vidick, “The Quantum PCP Conjecture”, (2013) arXiv:1309.7495
[12]
A. Cross et al., “Quantum Locally Testable Code with Constant Soundness”, Quantum 8, 1501 (2024) arXiv:2209.11405 DOI
[13]
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
[14]
I. Dinur, T.-C. Lin, and T. Vidick, “Expansion of higher-dimensional cubical complexes with application to quantum locally testable codes”, (2024) arXiv:2402.07476
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: qltc

Cite as:
“Quantum locally testable code (QLTC)”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/qltc
BibTeX:
@incollection{eczoo_qltc, title={Quantum locally testable code (QLTC)}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, 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.), 2023. https://errorcorrectionzoo.org/c/qltc

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