# Nilpotent adjacency matrices, random graphs, and quantum random variables

Nilpotent adjacency matrices, random graphs, and quantum random variables - Download this document for free, or read online. Document in PDF available to download.

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

Abstract : 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

Author: ** René Schott - Stacey Staples - **

Source: https://hal.archives-ouvertes.fr/