<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume10 Issue3" %>
The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed States
Samuel L. Braunstein1, Sibasish Ghosh1, and Simone Severini2
1Department of Computer Science, University of York, Heslington, York YO10 5DD, United Kingdom
{schmuel, sibasish}@cs.york.ac.uk
2Department of Mathematics and Department of Computer Science, University of York, Heslington, York YO10 5DD, United Kingdom
Annals of Combinatorics 10 (3) p. 291-317 September, 2006
AMS Subject Classification: 05C50, 81P68
We study entanglement properties of mixed density matrices obtained from combinatorial Laplacians. This is done by introducing the notion of the density matrix of a graph. We characterize the graphs with pure density matrices and show that the density matrix of a graph can be always written as a uniform mixture of pure density matrices of graphs. We consider the von Neumann entropy of these matrices and we characterize the graphs for which the minimum and maximum values are attained. We then discuss the problem of separability by pointing out that separability of density matrices of graphs does not always depend on the labelling of the vertices. We consider graphs with a tensor product structure and simple cases for which combinatorial properties are linked to the entanglement of the state. We calculate the concurrence of all graph on four vertices representing entangled states. It turns out that for some of these graphs the value of the concurrence is exactly fractional.
Keywords: graph laplacian, density matrix, entanglement


1. J. Batle, M. Casas, A.R. Plastino, and A. Plastino, Entanglement, mixedness, and q-entropies, Phys. Lett. A 296 (6) (2002) 251–258.

2. C. Godsil and G. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, Vol. 207, Springer-Verlag, New York, 2001.

3. M. Horodecki, P. Horodecki, and R. Horodecki, Separability of mixed states: necessary and sufficient conditions, Phys. Lett. A 223 (1-2) (1996) 1–8.

4. M. Horodecki, P. Horodecki, and R. Horodecki, Mixed-state entanglement and distillation: Is there a “bound” entanglement in nature? Phys. Rev. Lett. 80 (24) (1998) 5239–5242.

5. W. Imrich and S. Klavžar, Product Graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.

6. J.P. Keating, J. Marklof, and B. Winn, Value distribution of the eigenfunctions and spectral determinants of quantum star graphs, Comm. Math. Phys. 241 (2-3) (2003) 421–452.

7. B. Mohar, The Laplacian spectrum of graphs, In: Graph Theory, Combinatorics, and Applications, Vol. 2, Wiley-Intersci. Publ., Wiley, New York, (1991) pp. 871–898.

8. A Peres, Quantum Theory: Concepts and Methods, Fundamental Theories of Physics, Vol. 57, Kluwer Academic Publishers Group, Dordrecht, 1993.

9. A. Peres, Separability criterion for density matrices, Phys. Rev. Lett. 77 (8) (1996) 1413– 1415.

10. E. Prisner, Graph Dynamics, Pitman Research Notes in Mathematics Series, Vol. 338, Longman, Harlow, 1995.

11. J.-L. Shu, Y. Hong, and W.-R. Kai, A sharp upper bound on the largest eigenvalue of the Laplacian matrix of a graph, Linear Algebra Appl. 347 (2002) 123–129.

12. W.K. Wootters, Entanglement of formation and concurrence, Quantum Inform. Comput. 1 (1) (2001) 27–44.