Combinatorial foundations for solvable chaotic local Euclidean quantum circuits in two dimensions

Abstract

We investigate a graph-theoretic problem motivated by questions in quantum computing concerning the propagation of information in quantum circuits. A graph $G$ is said to be a bounded extension of its subgraph $L$ if they share the same vertex set, and the graph distance $d_L(u,v)$ is uniformly bounded for edges $uv\in G$. Given vertices $u,v$ in $G$ and an integer $k$, the geodesic slice $S(u,v,k)$ denotes the subset of vertices $w$ lying on a geodesic in $G$ between $u$ and $v$ with $d_G(u,w)=k$. We say that $G$ has bounded geodesic slices if $|S(u,v,k)|$ is uniformly bounded over all $u,v,k$. We call a graph $L$ geodesically directable if it has a bounded extension $G$ with bounded geodesic slices. Contrary to previous expectations, we prove that ${\mathbb{Z}}^2$ is geodesically directable. Physically, this provides a setting in which one could devise exactly-solvable chaotic local quantum circuits with non-trivial correlation patterns on 2D Euclidean lattices. In fact, we show that any bounded extension of ${\mathbb{Z}}^2$ is geodesically directable. This further implies that all two-dimensional regular tilings are geodesically directable.