The Laplacian of a Graph as a Density Matrix: A Basic Combinatorial Approach to Separability of Mixed States

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 graphs on four vertices representing entangled states. It turns out that for these graphs the value of the concurrence is exactly fractional.

Authors and Affiliations

1. Department of Computer Science, University of York, Heslington, York, YO10 5DD, UK

   Samuel L. Braunstein & Sibasish Ghosh

2. Department of Mathematics and Department of Computer Science, University of York, Heslington, York, YO10 5DD, UK

   Simone Severini

Corresponding author

Correspondence to Samuel L. Braunstein.

Received July 28, 2004

Reprints and permissions