Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Journal of Physics A Mathematical and Theoretical

Nilpotent adjacency matrices, random graphs and quantum random variables

René Schott, G. Stacey Staples

Published Apr 2, 2008• 18 citations
Publisher

Abstract

While a number of researchers have previously investigated the relationship between graph theory and quantum probability, the current work explores a new perspective. The approach of this paper is to begin with an arbitrary graph having no previously established relationship to quantum probability and to use that graph to construct a quantum probability space in which moments of quantum random variables reveal information about the graph's structure. Given an arbitrary finite graph and arbitrary odd integer m ⩾ 3, fermion annihilation operators are used to construct a family of quantum random variables whose m th moments correspond to the graph's m -cycles. The approach is then generalized to recover a graph's m -cycles for any integer m ⩾ 3 by defining nilpotent adjacency operators in terms of null-square generators of an infinite-dimensional Abelian algebra. It is shown that ordering the vertices of a simple graph induces a canonical decomposition Ψ = Ψ + + Ψ − on any nilpotent adjacency operator Ψ. The work concludes with applications to Markov chains and random graphs.

DOI
10.1088/1751-8113/41/15/155205

Related papers

CLIFFORD ALGEBRAS, RANDOM GRAPHS, AND QUANTUM RANDOM VARIABLES

René Schott, G. Stacey Staples

For fixed n > 0, the space of finite graphs on n vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the Clifford algebra which is canonically isomorphic to the 2n-particle fermion algebra. Using the generators of the subalgebra, an algebraic probability space of “Clifford adjacency matrices” associated with finite graphs is defined. Each Clifford 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 Δ + a ϒ + a Λ , where a Δ is classical while a ϒ and a Λ are quantum. Moreover, within the Clifford algebra context the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than n 4 Clifford (geo-metric) multiplications within the algebra.

Quantum Stochastics and Information•Aug 1, 2008•1 citation

Combinatorial structures in quantum correlation: A new perspective

Rohit kumar, Satyabrata Adhikari

Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called $A_α$-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix $D$ and the adjacency matrix $A_G$ of a graph $G$. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter $α\in (0,1]$. We first establish the conditions under which the associated operator $ρ_α^{A_G}$ is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for $A_α$-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter $α$ for which the $A_α$-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed $p_3$-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.

quant-pharXiv:2512.15686•Annals of Physics•Dec 18, 2025•0 citations

QUANTUM DECOMPOSITION AND QUANTUM CENTRAL LIMIT THEOREM

Akihito Hora, Nobuaki Obata

On the basis of the canonical relation between an interacting Fock space and a system of orthogonal polynomials we introduce the notion of quantum decomposition of a real random variable in an algebraic probability space. To understand prototypes we review some basic examples appearing from the Boson, Fermion, and free Fock spaces. We then prove quantum central limit theorems for the quantum components of the adjacency matrices (combinatorial Laplacians) of a growing family of regular connected graphs. As a corollary, asymptotic properties of the adjacency matrix are obtained. Concrete examples include lattices, homogeneous trees, Cayley graphs of the Coxeter groups, Hamming graphs and Johnson graphs. In particular, asymptotic spectral distribution of the adjacency matrix of a Johnson graph is described by an interacting Fock space corresponding to the Meixner polynomials which are one-parameter deformation of the Laguerre polynomials.

•Feb 1, 2003•15 citations

Characterizing the Relationship Between Unitary Quantum Walks and Non-Homogeneous Random Walks

Matheus Guedes de Andrade, Franklin de Lima Marquezino, Daniel R. Figueiredo

Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.

•Jun 29, 2021•0 citations

Information theoretic parameters for graphs and operator systems

Gareth Boreland

This thesis explores connections between information theory and graph theory. We prove a number of seemingly new results on graph entropy, a classical information theoretic quantity introduced by Korner. Our work includes the determination of the graph entropy of the odd cycles and their complements under certain probability distributions. We develop a theory of convex corners in finite dimensional spaces of matrices appropriate for applications in quantum information, and discuss the concept of entropy over a convex corner. We recall the definition of a non-commutative graph from the work of Duan, Severini and Winter, and with a given non-commutative graph we associate a number of convex corners, before proving a "quantum sandwich theorem". We define several new parameters for non-commutative graphs, and show them to be generalisations of the corresponding graph parameters. This includes two quantum versions of the Lovasz number, one of which is seen to be an upper bound on the Shannon capacity of an associated quantum channel. Finally we return to examine graph entropy in the case of a non-i.i.d. classical source, and attempt to generalise the Kolmogorov-Sinai entropy of a dynamical system to this setting.

•Oct 1, 2026•4 citations

THE QUANTUM DECOMPOSITION OF RANDOM VARIABLES WITHOUT MOMENTS

Luigi Accardi, Habib Rebei, Anis Riahi

The quantum decomposition of a classical random variable is one of the deep results of quantum probability: it shows that any classical random variable or stochastic process has a built-in non-commutative structure which is intrinsic and canonical, and not artificially put by hands. Up to now the technique to deduce the quantum decomposition has been based on the theory of interacting Fock spaces and on Jacobi's tri-diagonal relation for orthogonal polynomials. Therefore it requires the existence of moments of any order and cannot be applied to random variables without this property. The problem to find an analogue of the quantum decomposition for random variables without finite moments of any order remained open for about fifteen years and nobody had any idea of how such a decomposition could look like. In the present paper we prove that any infinitely divisible random variable has a quantum decomposition canonically associated to its Lévy–Khintchin triple. The analytical formulation of this result is based on Kolmogorov representation of these triples in terms of 1–cocycles (helices) in Hilbert spaces and on the Araki–Woods–Parthasarathy–Schmidt characterization of these representation in terms of Fock spaces. It distinguishes three classes of random variables: (i) with finite second moment; (ii) with finite first moment only; (iii) without any moment. The third class involves a new type of renormalization based on the associated Lévy–Khinchin function.

Infinite Dimensional Analysis Quantum Probability and Related Topics•Jun 1, 2013•15 citations
While a number of researchers have previously investigated the relationship between graph theory and quantum probability, the current work explores a new perspective. The approach of this paper is to begin with an arbitrary graph having no previously established relationship to quantum probability and to use that graph to construct a quantum probability space in which moments of quantum random variables reveal information about the graph's structure. Given an arbitrary finite graph and arbitrary odd integer m ⩾ 3, fermion annihilation operators are used to construct a family of quantum random variables whose m th moments correspond to the graph's m -cycles. The approach is then generalized to recover a graph's m -cycles for any integer m ⩾ 3 by defining nilpotent adjacency operators in terms of null-square generators of an infinite-dimensional Abelian algebra. It is shown that ordering the vertices of a simple graph induces a canonical decomposition Ψ = Ψ + + Ψ − on any nilpotent adjacency operator Ψ. The work concludes with applications to Markov chains and random graphs.
For fixed n > 0, the space of finite graphs on n vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the Clifford algebra which is canonically isomorphic to the 2n-particle fermion algebra. Using the generators of the subalgebra, an algebraic probability space of “Clifford adjacency matrices” associated with finite graphs is defined. Each Clifford 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 Δ + a ϒ + a Λ , where a Δ is classical while a ϒ and a Λ are quantum. Moreover, within the Clifford algebra context the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than n 4 Clifford (geo-metric) multiplications within the algebra.
Graph-theoretic structures play a central role in the description and analysis of quantum systems. In this work, we introduce a new class of quantum states, called AαA_αAα​-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix DDD and the adjacency matrix AGA_GAG​ of a graph GGG. The constructed states are different from the standard graph states arising from stabiliser formalism. Our approach is also different from the approach used by Braunstein et al. This class of states depend on a tunable mixing parameter α∈(0,1]α\in (0,1]α∈(0,1]. We first establish the conditions under which the associated operator ραAGρ_α^{A_G}ραAG​​ is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for AαA_αAα​-graph states in terms of graph parameters. This PPT condition involves only the Frobenius norm of the adjacency matrix of the graph, the degrees of the vertices and the total number of vertices. For simple graphs, we obtain the range of the parameter ααα for which the AαA_αAα​-graph states represent a class of entangled states. We then develop a graph-theoretic formulation of a moments-based entanglement detection criterion, focusing on the recently proposed p3p_3p3​-PPT criterion, which relies on the second and third moments of the partial transposition. Since the estimation of these moments is experimentally accessible via randomised measurements, swap operations, and machine-learning-based protocols, our approach provides a physically relevant framework for detecting entanglement in structured quantum states derived from graphs. This work bridges graph theory and moments-based entanglement detection, offering a new perspective on the role of combinatorial structures in quantum correlations.
On the basis of the canonical relation between an interacting Fock space and a system of orthogonal polynomials we introduce the notion of quantum decomposition of a real random variable in an algebraic probability space. To understand prototypes we review some basic examples appearing from the Boson, Fermion, and free Fock spaces. We then prove quantum central limit theorems for the quantum components of the adjacency matrices (combinatorial Laplacians) of a growing family of regular connected graphs. As a corollary, asymptotic properties of the adjacency matrix are obtained. Concrete examples include lattices, homogeneous trees, Cayley graphs of the Coxeter groups, Hamming graphs and Johnson graphs. In particular, asymptotic spectral distribution of the adjacency matrix of a Johnson graph is described by an interacting Fock space corresponding to the Meixner polynomials which are one-parameter deformation of the Laguerre polynomials.
Quantum walks on graphs are ubiquitous in quantum computing finding a myriad of applications. Likewise, random walks on graphs are a fundamental building block for a large number of algorithms with diverse applications. While the relationship between quantum and random walks has been recently discussed in specific scenarios, this work establishes a formal equivalence between the two processes on arbitrary finite graphs and general conditions for shift and coin operators. It requires empowering random walks with time heterogeneity, where the transition probability of the walker is non-uniform and time dependent. The equivalence is obtained by equating the probability of measuring the quantum walk on a given node of the graph and the probability that the random walk is at that same node, for all nodes and time steps. The first result establishes procedure for a stochastic matrix sequence to induce a random walk that yields the exact same vertex probability distribution sequence of any given quantum walk, including the scenario with multiple interfering walkers. The second result establishes a similar procedure in the opposite direction. Given any random walk, a time-dependent quantum walk with the exact same vertex probability distribution is constructed. Interestingly, the matrices constructed by the first procedure allows for a different simulation approach for quantum walks where node samples respect neighbor locality and convergence is guaranteed by the law of large numbers, enabling efficient (polynomial-time) sampling of quantum graph trajectories. Furthermore, the complexity of constructing this sequence of matrices is discussed in the general case.
This thesis explores connections between information theory and graph theory. We prove a number of seemingly new results on graph entropy, a classical information theoretic quantity introduced by Korner. Our work includes the determination of the graph entropy of the odd cycles and their complements under certain probability distributions. We develop a theory of convex corners in finite dimensional spaces of matrices appropriate for applications in quantum information, and discuss the concept of entropy over a convex corner. We recall the definition of a non-commutative graph from the work of Duan, Severini and Winter, and with a given non-commutative graph we associate a number of convex corners, before proving a "quantum sandwich theorem". We define several new parameters for non-commutative graphs, and show them to be generalisations of the corresponding graph parameters. This includes two quantum versions of the Lovasz number, one of which is seen to be an upper bound on the Shannon capacity of an associated quantum channel. Finally we return to examine graph entropy in the case of a non-i.i.d. classical source, and attempt to generalise the Kolmogorov-Sinai entropy of a dynamical system to this setting.
The quantum decomposition of a classical random variable is one of the deep results of quantum probability: it shows that any classical random variable or stochastic process has a built-in non-commutative structure which is intrinsic and canonical, and not artificially put by hands. Up to now the technique to deduce the quantum decomposition has been based on the theory of interacting Fock spaces and on Jacobi's tri-diagonal relation for orthogonal polynomials. Therefore it requires the existence of moments of any order and cannot be applied to random variables without this property. The problem to find an analogue of the quantum decomposition for random variables without finite moments of any order remained open for about fifteen years and nobody had any idea of how such a decomposition could look like. In the present paper we prove that any infinitely divisible random variable has a quantum decomposition canonically associated to its Lévy–Khintchin triple. The analytical formulation of this result is based on Kolmogorov representation of these triples in terms of 1–cocycles (helices) in Hilbert spaces and on the Araki–Woods–Parthasarathy–Schmidt characterization of these representation in terms of Fock spaces. It distinguishes three classes of random variables: (i) with finite second moment; (ii) with finite first moment only; (iii) without any moment. The third class involves a new type of renormalization based on the associated Lévy–Khinchin function.