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α-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
AG 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
α∈(0,1]. We first establish the conditions under which the associated operator
ραAG 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
p3-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.