I am studying CSS quantum LDPC codes and I am curious as to whether the Tanner Graph structure necessarily must have long-range connections in order to be a non-local qLDPC code. This is because the surface code has a Tanner Graph structure that is local and has no long-range edges on a torus.

On the other hand, the Tanner Graph says nothing about the locality of each X and Z stabilizer, they could be supported on a set of large diameter. So I am under the impression that just because the Tanner Graph can be written locally, does not imply that the actual code is a geometrically local code. So I am wondering if anyone is aware of a concrete example of a qLDPC code that produces this property, that its Tanner Graph can be written as a local graph structure on a torus, for instance. Or maybe this statement is wrong.

  • $\begingroup$ the tanner graph itself is the same no matter where you embed it. I would think locality and other geometric properties depend on where you embed it (plane vs torus vs ...) $\endgroup$
    – unknown
    Commented Jun 19 at 15:42
  • $\begingroup$ @unknown are you aware of an example where we have a code family that beats the Bravyi-Poulin-Terhal bound whilst having the same Tanner Graph structure as the toric code? $\endgroup$ Commented Jun 19 at 16:52
  • 1
    $\begingroup$ The checks are completely specified by the Tanner graph, so specifying the Tanner graph specifies a code. In general, if there exists an embedding of the Tanner graph into a euclidean space $\mathbb{R}^D$ with unit density such that any two vertices connected by an edge are within distance $r$, then that same embedding gives an assignment of qubits of the code to $\mathbb{R}^D$ such that the support of any check is contained within a ball of radius $r$. Are you perhaps asking about codes for which you can implement their syndrome extraction circuits using geometrically local gates? $\endgroup$ Commented Jun 20 at 4:05
  • $\begingroup$ @ChrisPattison, I was not aware of this. Thank you for the clarification! Do you have any resource that discusses this, or is this just a known fact in the community? $\endgroup$ Commented Jun 20 at 5:51
  • 2
    $\begingroup$ This follows from the definition of the Tanner graph. As a reminder, the Tanner graph associated with the (classical) check matrix $H\in \mathbb{F}_2^{r\times n}$ is a bipartite graph on the vertex set $V = [r] \sqcup [n]$ where an $(u,v) \in [r] \times [n]$ share an edge iff the entry $H[u,v]=1$. E.g. see arxiv.org/abs/2109.14599). Now, if there is an embedding of $V$ into $\mathbb{R}^D$ satisfying the previously mentioned properties, then there is an embedding of bits $[n]$. The balls are centered on each of these vertices. Everything here carries over to the CSS code case. $\endgroup$ Commented Jun 20 at 7:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.