paulie.application.average_graph_complexity.average_graph_complexity#
- paulie.application.average_graph_complexity.average_graph_complexity(generators, p)#
Get the average graph complexity of a Pauli string with respect to the time evolution generated by a given generator set.
The average graph complexity \(G\) can be computed from the commutation graph as
\[\mathbb{E}_{U\sim \mu_G}G(U^{\dagger} p U) = \frac{1}{|C_p|}\sum_{q\in C_p}\ell(p,q)\]where \(C_p\) is the connected component of the commutation graph containing \(p\) and \(\ell(p,q)\) is the shortest path length between \(p\) and \(q\) in the commutation graph.
(arXiV:2502.16404)
- Parameters:
generators (PauliStringCollection) – Generating set of the time evolution.
p (PauliString) – Pauli string to compute the average graph complexity of.
- Returns:
Average graph complexity of p with respect to the time evolution generated by generators.
- Return type: