Operator growth bounds from graph theory

Let $A$ and $B$ be local operators in Hamiltonian quantum systems with $N$ degrees of freedom and finite-dimensional Hilbert space. We prove that the commutator norm $\parallel [A(t),B]\parallel$ is upper bounded by a topological combinatorial problem: counting irreducible weighted paths between two points on the Hamiltonian’s factor graph. Our bounds sharpen existing Lieb-Robinson bounds by removing extraneous growth. In quantum systems drawn from zero-mean random ensembles with few-body interactions, we prove stronger bounds on the ensemble-averaged out-of-time-ordered correlator $$\mathbb{E}$\left[ \lVert [A(t),B]\rVert_F^2\right]$. In such quantum systems on Erd"os-R'enyi factor graphs, we prove that the scrambling time $t_{\mathrm{s}}$, at which $\lvert [A(t),B]\rVert_F=$\mathrm{\Theta }$(1)$,isalmostsurely$t_{$\mathrm{s}$}=$\mathrm{\Omega }$(\sqrt{\log N})$;wefurtherprove$t_{$\mathrm{s}$}=$\mathrm{\Omega }$(\log N) $ to high order in perturbation theory in $1\mathrm{/}N$. We constrain infinite temperature quantum chaos in the $q$-local Sachdev-Ye-Kitaev model at any order in $1\mathrm{/}N$; at leading order, our upper bound on the Lyapunov exponent is within a factor of 2 of the known result at any $q>2$. We also speculate on the implications of our theorems for conjectured holographic descriptions of quantum gravity.