# Quantum Tanner code[1]

## Description

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.

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

## Protection

## Rate

## Decoding

## Realizations

## Notes

## Parents

- Generalized homological-product qubit CSS code
- Single-shot code — Quantum Tanner codes facilitate single-shot decoding [8].

## Child

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

## Cousins

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

## References

- [1]
- A. Leverrier and G. Zémor, “Quantum Tanner codes”, (2022) arXiv:2202.13641
- [2]
- A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
- [3]
- S. Gu, C. A. Pattison, and E. Tang, “An efficient decoder for a linear distance quantum LDPC code”, (2022) arXiv:2206.06557
- [4]
- 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
- [5]
- M. Hopkins and T.-C. Lin, “Explicit Lower Bounds Against \(Ω(n)\)-Rounds of Sum-of-Squares”, (2022) arXiv:2204.11469
- [6]
- 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
- [7]
- 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
- [8]
- S. Gu et al., “Single-shot decoding of good quantum LDPC codes”, (2023) arXiv:2306.12470
- [9]
- Nikolas P. Breuckmann, private communication, 2022
- [10]
- Anthony Leverrier, Mapping the toric code to the rotated toric code, 2022.
- [11]
- D. Ostrev et al., “Classical product code constructions for quantum Calderbank-Shor-Steane codes”, (2022) arXiv:2209.13474

## Page edit log

- Shouzhen (Bailey) Gu (2023-02-21) — most recent
- Victor V. Albert (2023-02-21)
- Victor V. Albert (2022-08-12)
- Victor V. Albert (2022-04-26)

## Cite as:

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