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

Protection

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

Rate

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

Decoding

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

Realizations

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

Notes

For details, see talk by A. Leverrier.

Parents

Child

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

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

References

[1]
A. Leverrier and G. Zémor, “Quantum Tanner codes”, (2022) arXiv:2202.13641
[2]
O. Å. Mostad, E. Rosnes, and H.-Y. Lin, “Generalizing Quantum Tanner Codes”, (2024) arXiv:2405.07980
[3]
A. Leverrier and G. Zémor, “Decoding quantum Tanner codes”, (2022) arXiv:2208.05537
[4]
S. Gu, C. A. Pattison, and E. Tang, “An efficient decoder for a linear distance quantum LDPC code”, (2022) arXiv:2206.06557
[5]
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
[6]
M. Hopkins and T.-C. Lin, “Explicit Lower Bounds Against \(Ω(n)\)-Rounds of Sum-of-Squares”, (2022) arXiv:2204.11469
[7]
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
[8]
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
[9]
S. Gu et al., “Single-Shot Decoding of Good Quantum LDPC Codes”, Communications in Mathematical Physics 405, (2024) arXiv:2306.12470 DOI
[10]
Nikolas P. Breuckmann, private communication, 2022
[11]
Anthony Leverrier, Mapping the toric code to the rotated toric code, 2022.
[12]
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
BibTeX:
@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:
https://errorcorrectionzoo.org/c/quantum_tanner

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.