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

The Electronic Journal of Combinatorics

Separability of Density Matrices of Graphs for Multipartite Systems

Chen Xie, Hui Zhao, Zhi‐Xi Wang

Published Nov 22, 2013• 5 citations
Publisher

Abstract

We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of N graphs is N-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for N-partite entanglement in star graphs and propose a necessary and sufficient condition for separability of nearest point graphs.

DOI
10.37236/3092

Related papers

The Tripartite Separability of Density Matrices of Graphs

Zhen Wang, Zhi‐Xi Wang

The density matrix of a graph is the combinatorial laplacian matrix of a graph normalized to have unit trace. In this paper we generalize the entanglement properties of mixed density matrices from combinatorial laplacian matrices of graphs discussed in Braunstein et al. [Annals of Combinatorics, 10 (2006) 291] to tripartite states. Then we prove that the degree condition defined in Braunstein et al. [Phys. Rev. A, 73 (2006) 012320] is sufficient and necessary for the tripartite separability of the density matrix of a nearest point graph.

arXiv:0705.2561•The Electronic Journal of Combinatorics•May 23, 2007•7 citations

Multipartite Separability of Laplacian Matrices of Graphs

Chai Wah Wu

Recently, Braunstein et al. introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in Braunstein et al. Finally, we show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, lexicographical, etc.) is multipartite separable, extending analogous results for bipartite and tripartite separability.

arXiv:0809.0827•The Electronic Journal of Combinatorics•May 15, 2009•11 citations

Some families of density matrices for which separability is easily tested

Samuel L. Braunstein, Sibasish Ghosh A, Toufik Mansour +2 more

We reconsider density matrices of graphs as defined in quant-ph/0406165. The density matrix of a graph is the combinatorial Laplacian of the graph normalized to have unit trace. We describe a simple combinatorial condition (the ``degree condition'') to test the separability of density matrices of graphs. The condition is directly related to the Peres-Horodecki partial transposition condition. We prove that the degree condition is necessary for separability, and we conjecture that it is also sufficient. We prove special cases of the conjecture involving nearest-point graphs and perfect matchings. We observe that the degree condition appears to have a value beyond the density matrices of graphs. In fact, we point out that circulant density matrices and other matrices constructed from groups always satisfy the condition and indeed are separable with respect to any split. We isolate a number of problems and delineate further generalizations.

arXiv:quant-ph/0508020•Physical Review A•Jan 18, 2006•45 citations

Separability criterion for multipartite quantum states based on the Bloch representation of density matrices

Ali Saif M. Hassan, Pramod S. Joag

We give a new separability criterion, a necessary condition for separability of N-partite quantum states. The criterion is based on the Bloch representation of a N-partite quantum state and makes use of multilinear algebra, in particular, the matrization of tensors. Our criterion applies to arbitrary N-partite quantum states in $\mathcal{H}=\mathcal{H}^{d_1}\otimes \mathcal{H}^{d_2} \otimes \cdots \otimes \mathcal{H}^{d_N}.$ The criterion can test whether a N-partite state is entangled and can be applied to different partitions of the $N$-partite system. We provide examples that show the ability of this criterion to detect entanglement. We show that this criterion can detect bound entangled states. We prove a sufficiency condition for separability of a 3-partite state, straightforwardly generalizable to the case N > 3, under certain condition. We also give a necessary and sufficient condition for separability of a class of N-qubit states which includes N-qubit PPT states.

arXiv:0704.3942•Quantum Information and Computation•Sep 1, 2008•48 citations

A combinatorial approach to multipartite quantum systems: basic formulation

Ali Saif M. Hassan, Pramod S. Joag

In this paper we give a method to associate a graph with an arbitrary density matrix referred to a standard orthonormal basis in the Hilbert space of a finite dimensional quantum system. We study related issues such as classification of pure and mixed states, Von Neumann entropy, separability of multipartite quantum states and quantum operations in terms of the graphs associated with quantum states. In order to address the separability and entanglement questions using graphs, we introduce a modified tensor product of weighted graphs, and establish its algebraic properties. In particular, we show that Werner's definition (Werner 1989 Phys. Rev. A 40 4277) of a separable state can be written in terms of graphs, for the states in a real or complex Hilbert space. We generalize the separability criterion (degree criterion) due to Braunstein et al (2006 Phys. Rev. A 73 012320) to a class of weighted graphs with real weights. We have given some criteria for the Laplacian associated with a weighted graph to be positive semidefinite.

arXiv:quant-ph/0602053•Journal of Physics A Mathematical and Theoretical•Aug 1, 2007•13 citations

Combinatorial laplacians and positivity under partial transpose

Roland Hildebrand, Stefano Mancini, Simone Severini B

The density matrices of graphs are combinatorial laplacians normalised to have trace one (Braunsteinet al. 2006b). If the vertices of a graph are arranged as an array, its density matrix carries a block structure with respect to which properties such as separability can be considered. We prove that the so-called degree-criterion, which was conjectured to be necessary and sufficient for the separability of density matrices of graphs, is equivalent to the PPT-criterion. As such, it is not sufficient for testing the separability of density matrices of graphs (we provide an explicit example). Nonetheless, we prove the sufficiency when one of the array dimensions has length two (see Wu (2006) for an alternative proof). Finally, we derive a rational upper bound on the concurrence of density matrices of graphs and show that this bound is exact for graphs on four vertices.

arXiv:cs/0607036•Mathematical Structures in Computer Science•Feb 1, 2008•22 citations
We investigate separability of Laplacian matrices of graphs when seen as density matrices. This is a family of quantum states with many combinatorial properties. We firstly show that the well-known matrix realignment criterion can be used to test separability of this type of quantum states. The criterion can be interpreted as novel graph-theoretic idea. Then, we prove that the density matrix of the tensor product of N graphs is N-separable. However, the converse is not necessarily true. Additionally, we derive a sufficient condition for N-partite entanglement in star graphs and propose a necessary and sufficient condition for separability of nearest point graphs.
The density matrix of a graph is the combinatorial laplacian matrix of a graph normalized to have unit trace. In this paper we generalize the entanglement properties of mixed density matrices from combinatorial laplacian matrices of graphs discussed in Braunstein et al. [Annals of Combinatorics, 10 (2006) 291] to tripartite states. Then we prove that the degree condition defined in Braunstein et al. [Phys. Rev. A, 73 (2006) 012320] is sufficient and necessary for the tripartite separability of the density matrix of a nearest point graph.
Recently, Braunstein et al. introduced normalized Laplacian matrices of graphs as density matrices in quantum mechanics and studied the relationships between quantum physical properties and graph theoretical properties of the underlying graphs. We provide further results on the multipartite separability of Laplacian matrices of graphs. In particular, we identify complete bipartite graphs whose normalized Laplacian matrix is multipartite entangled under any vertex labeling. Furthermore, we give conditions on the vertex degrees such that there is a vertex labeling under which the normalized Laplacian matrix is entangled. These results address an open question raised in Braunstein et al. Finally, we show that the Laplacian matrix of any product of graphs (strong, Cartesian, tensor, lexicographical, etc.) is multipartite separable, extending analogous results for bipartite and tripartite separability.
We reconsider density matrices of graphs as defined in quant-ph/0406165. The density matrix of a graph is the combinatorial Laplacian of the graph normalized to have unit trace. We describe a simple combinatorial condition (the ``degree condition'') to test the separability of density matrices of graphs. The condition is directly related to the Peres-Horodecki partial transposition condition. We prove that the degree condition is necessary for separability, and we conjecture that it is also sufficient. We prove special cases of the conjecture involving nearest-point graphs and perfect matchings. We observe that the degree condition appears to have a value beyond the density matrices of graphs. In fact, we point out that circulant density matrices and other matrices constructed from groups always satisfy the condition and indeed are separable with respect to any split. We isolate a number of problems and delineate further generalizations.
We give a new separability criterion, a necessary condition for separability of N-partite quantum states. The criterion is based on the Bloch representation of a N-partite quantum state and makes use of multilinear algebra, in particular, the matrization of tensors. Our criterion applies to arbitrary N-partite quantum states in H=Hd1⊗Hd2⊗⋯⊗HdN.\mathcal{H}=\mathcal{H}^{d_1}\otimes \mathcal{H}^{d_2} \otimes \cdots \otimes \mathcal{H}^{d_N}.H=Hd1​⊗Hd2​⊗⋯⊗HdN​. The criterion can test whether a N-partite state is entangled and can be applied to different partitions of the NNN-partite system. We provide examples that show the ability of this criterion to detect entanglement. We show that this criterion can detect bound entangled states. We prove a sufficiency condition for separability of a 3-partite state, straightforwardly generalizable to the case N > 3, under certain condition. We also give a necessary and sufficient condition for separability of a class of N-qubit states which includes N-qubit PPT states.
In this paper we give a method to associate a graph with an arbitrary density matrix referred to a standard orthonormal basis in the Hilbert space of a finite dimensional quantum system. We study related issues such as classification of pure and mixed states, Von Neumann entropy, separability of multipartite quantum states and quantum operations in terms of the graphs associated with quantum states. In order to address the separability and entanglement questions using graphs, we introduce a modified tensor product of weighted graphs, and establish its algebraic properties. In particular, we show that Werner's definition (Werner 1989 Phys. Rev. A 40 4277) of a separable state can be written in terms of graphs, for the states in a real or complex Hilbert space. We generalize the separability criterion (degree criterion) due to Braunstein et al (2006 Phys. Rev. A 73 012320) to a class of weighted graphs with real weights. We have given some criteria for the Laplacian associated with a weighted graph to be positive semidefinite.
The density matrices of graphs are combinatorial laplacians normalised to have trace one (Braunsteinet al. 2006b). If the vertices of a graph are arranged as an array, its density matrix carries a block structure with respect to which properties such as separability can be considered. We prove that the so-called degree-criterion, which was conjectured to be necessary and sufficient for the separability of density matrices of graphs, is equivalent to the PPT-criterion. As such, it is not sufficient for testing the separability of density matrices of graphs (we provide an explicit example). Nonetheless, we prove the sufficiency when one of the array dimensions has length two (see Wu (2006) for an alternative proof). Finally, we derive a rational upper bound on the concurrence of density matrices of graphs and show that this bound is exact for graphs on four vertices.