Average graph complexity

Given a Hamiltonian, we can consider the Heisenberg evolution of an operator under it. Intuitively, if we start with a simple operator, over time it gets scrambled into a complex one. We can quantify this growth with the notion of “operator complexity”.

Consider the dynamical Lie algebra (DLA) generated by the generating set of a Hamiltonian. In “A graph-theoretic approach to chaos and complexity in quantum systems” [1], the authors introduce a notion of operator complexity termed “graph complexity”.

Specifically, given the Heisenberg evolution of an initial Pauli string \(p_t = e^{iHt}pe^{-iHt}=\sum_{q \in C_{p}}c_q(t)q\), the graph complexity is defined as

\[G(p_t) = \sum_{q \in C_{p}}l(p,q)|c_q(t)|^2\]

where \(l(p,q)\) is the shortest path length between the Pauli strings \(p\) and \(q\) in the commutator graph.

We can use paulie to compute the long time average of the graph complexity:

from paulie.application.graph_complexity import average_graph_complexity
from paulie.common.pauli_string_factory import get_identity, get_pauli_string
generators = get_pauli_string(["ZI", "IZ", "XX"])
i = get_identity(2)
for p in i.gen_all_pauli_strings():
    print(f'Graph complexity of {p} = {average_graph_complexity(generators, p)}')

which outputs:

Graph complexity of II = 0.0
Graph complexity of IZ = 2.0
Graph complexity of IX = 1.5
Graph complexity of IY = 1.0
Graph complexity of ZI = 2.0
Graph complexity of ZZ = 0.0
Graph complexity of ZX = 1.0
Graph complexity of ZY = 1.5
Graph complexity of XI = 1.5
Graph complexity of XZ = 1.0
Graph complexity of XX = 1.3333333333333333
Graph complexity of XY = 1.3333333333333333
Graph complexity of YI = 1.0
Graph complexity of YZ = 1.5
Graph complexity of YX = 1.3333333333333333
Graph complexity of YY = 1.3333333333333333

Note that the graph complexity of the commutants of the DLA is \(0\).