1
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – freshcoconut
    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$
    – Chris Pattison
    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$
    – freshcoconut
    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$
    – Chris Pattison
    Commented Jun 20 at 7:06

0

Reset to default

Browse other questions tagged or ask your own question.