Quantum Tanner code[1] 


Member of a family of QLDPC codes based on two compatible classical Tanner codes defined on a two-dimensional Cayley complex, a complex constructed from Cayley graphs of groups. For certain choices of codes and complex, the resulting codes have asymptotically good parameters. This construction has been generalized to Schreier graphs [2].

The underlying geometric complex of the code is a left-right Cayley complex \(\operatorname{Cay}_2(A,G,B)\), where \(G\) is a finite group and \(A=A^{-1}\), \(B=B^{-1}\) are two symmetric generating sets satisfying the total no-conjugacy condition: \(ag\ne gb\) for any \(g\in G\), \(a\in A\), and \(b\in B\). The vertices of the complex are group elements, i.e., \(V=G\). If necessary, the double cover of the graph should be taken so that the graph is bipartite, \(V=V_0\sqcup V_1\).

There are two types of edges in the resulting complex, \begin{align} \begin{split} E_A &= \{(g,ag): g\in G, a\in A\}\\ E_B &= \{(g,gb): g\in G, b\in B\}~. \end{split} \tag*{(1)}\end{align} The faces are squares defined by quadruples, \begin{align} Q = \{(g,ag,gb,agb): g\in G, a\in A, b\in B\}~. \tag*{(2)}\end{align} Two additional graphs can be obtained from \(\operatorname{Cay}_2(A,G,B)\) by taking the diagonals of the squares as edges, \(\mathcal G_0^\square = (V_0, Q)\) and \(\mathcal G_1^\square = (V_1, Q)\).

In the quantum Tanner construction, qubits are placed on the squares of the left-right Cayley complex. Two classical codes \(C_A\) and \(C_B\) of blocklengths \(|A|\) and \(|B|\), respectively, are chosen, yielding local codes \(C_0 = C_A\otimes C_B\) and \(C_1 = C_A^\perp\otimes C_B^\perp\). The quantum Tanner code is a CSS code defined by the classical Tanner codes \(C_Z = T(\mathcal G_0^\square, C_0^\perp)\) and \(C_X = T(\mathcal G_1^\square, C_1^\perp)\). The figure below depicts an example of a stabilizer generator.

Figure I: An example of a \(Z\) generator on a \(V_0\) local view when \(C_A = \{000\}\) and \(C_B=\{110, 011\}\). The faces incident to a \(V_0\) vertex are in bijection with the set \(A\times B\), and a codeword of \(C_0 = C_A\otimes C_B\) can be described using this set.

To achieve asymptotically good parameters, fixed classical local codes are chosen so that their dual tensor codes are sufficiently robust, and the left-right Cayley complexes are chosen to be sufficiently expanding. The family is defined using a family of groups \(G\) of increasing size but constant-size generating sets \(A\), \(B\).


For correctly chosen complexes and local codes, the distance scales as \(d=\Theta(n)\). Minimum distance bound obtained using robustness of dual tensor-product codes [3].


Asymptotically good QLDPC codes. When \(C_A\) and \(C_B\) are chosen to have rates not equal to a half, the number of encoded qubits scales as \(k=\Theta(n)\).


Linear-time potetial-based decoder similar to the small-set-flip decoder for quantum expander codes [4].Linear-time decoder [5].Logarithmic-time mismatch decomposition decoder [3].

Code Capacity Threshold

Independent \(X,Z\) noise: lower bound under potetial-based decoder [4; Corr. 15].


Used to obtain explicit lower bounds in the sum-of-squares game [6].States that, on average, achieve small violations of check operators for quantum Tanner codes require a circuit of non-constant depth to make. They are used in the proof [7] of the No low-energy trivial states (NLTS) conjecture [8].


For details, see talk by A. Leverrier.



  • Rotated surface code — Applying the quantum Tanner transformation to the surface code yields the rotated surface code [10,11].


  • Good QLDPC code — Quantum Tanner code construction yields asymptotically good QLDPC codes.
  • Regular binary Tanner code — Regular binary Tanner codes are used in constructing quantum Tanner codes.
  • Tensor-product code — Tensor codes are used in constructing quantum Tanner codes.
  • Expander LP code — Quantum Tanner codes are an attempt to construct asymptotically good QLDPC codes that are similar to but simpler than expander lifted-product codes; see Ref. [5] for connection between the codes.
  • Left-right Cayley complex code — Applying the CSS construction to two left-right Cayley complex codes yields quantum Tanner codes, and one can simultaneously prove a linear distance for the quantum code and local testability for one of its constituent classical codes [1].
  • Classical-product code — A \([[512,174,8]]\) classical-product code performed well [12] against erasure and depolarizing noise when compared to a member of an asymptotically good quantum Tanner code family.


A. Leverrier and G. Zémor, “Quantum Tanner codes”, (2022) arXiv:2202.13641
O. Å. Mostad, E. Rosnes, and H.-Y. Lin, “Generalizing Quantum Tanner Codes”, (2024) arXiv:2405.07980
A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
S. Gu, C. A. Pattison, and E. Tang, “An efficient decoder for a linear distance quantum LDPC code”, (2022) arXiv:2206.06557
A. Leverrier and G. Zémor, “Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes”, (2022) arXiv:2206.07571
M. Hopkins and T.-C. Lin, “Explicit Lower Bounds Against \(Ω(n)\)-Rounds of Sum-of-Squares”, (2022) arXiv:2204.11469
A. Anshu, N. P. Breuckmann, and C. Nirkhe, “NLTS Hamiltonians from Good Quantum Codes”, Proceedings of the 55th Annual ACM Symposium on Theory of Computing (2023) arXiv:2206.13228 DOI
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
S. Gu et al., “Single-Shot Decoding of Good Quantum LDPC Codes”, Communications in Mathematical Physics 405, (2024) arXiv:2306.12470 DOI
Nikolas P. Breuckmann, private communication, 2022
Anthony Leverrier, Mapping the toric code to the rotated toric code, 2022.
D. Ostrev et al., “Classical product code constructions for quantum Calderbank-Shor-Steane codes”, (2022) arXiv:2209.13474
Page edit log

Your contribution is welcome!

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

edit on this site

Zoo Code ID: quantum_tanner

Cite as:
“Quantum Tanner code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/quantum_tanner
@incollection{eczoo_quantum_tanner, title={Quantum Tanner code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/quantum_tanner} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:

Cite as:

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

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/quantum/qubits/stabilizer/qldpc/homological/quantum_tanner/quantum_tanner.yml.