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" <https://arxiv.org/abs/2502.16404>`_ [1], the authors introduce a notion of operator complexity termed "graph complexity".

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

.. math::

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

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

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

.. code-block:: python

    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:

.. code-block:: bash

    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 :math:`0`.