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. For certain choices of codes and complex, the resulting codes have asymptotically good parameters.

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 [2].


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 [3].Linear-time decoder [4].Logarithmic-time mismatch decomposition decoder [2].


Used to obtain explicit lower bounds in the sum-of-squares game [5].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 [6] of the No low-energy trivial states (NLTS) conjecture [7].


For details, see talk by A. Leverrier.



  • Rotated surface code — Specializing the quantum Tanner construction to the surface code yields the rotated surface code [9,10].


  • 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. [4] 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 [11] 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
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”, (2023) arXiv:2306.12470
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)

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/tree/main/codes/quantum/qubits/stabilizer/qldpc/quantum_tanner/quantum_tanner.yml.