Nilpotent adjacency matrices, random graphs, and quantum random variables

René Schott (1, 2) , Stacey Staples (3)

1 IECN - Institut Élie Cartan de Nancy
2 LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 Department of Mathematics and Statistics - Southern Illinois University

For fixed $n>0$, the space of finite graphs on $n$ vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the $2n$-particle fermion algebra. using the generators of the subalgebra, an algebraic probability space of "nilpotent adjacency matrices" associated with finite graphs is defined. Each nilpotent adjacency matrix is a quantum random variable whose $m^th$ moment corresponds to the number of $m$-cycles in the graph $G$. Each matrix admits a canonical "quantum decomposition" into a sum of three algebraic random variables: $a = a^\Delta+ a^\Upsilon+a^Lambda$, where $a^\Delta$ is classical while $a^\Upsilon and $a^\Lambda$ are quantum. Moreover, within the algebraic context, the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than $n^4$ multiplications within the algebra.

Mots clés: fermions; random graphs; cycles; paths; quantum computing

Domaines: Probabilités [math.PR]

René Schott, Stacey Staples. Nilpotent adjacency matrices, random graphs, and quantum random variables. Journal of Physics A: Mathematical and Theoretical, 2008, 41, pp.155-205. ⟨hal-00136290⟩