### Abstract

We settle the so-called degree conjecture for the separability of multipartite quantum states, which are normalized graph Laplacians, first given by Braunstein *et al.* [Phys. Rev. A73, 012320 (2006)]. The conjecture states that a multipartite quantum state is separable if and only if the degree matrix of the graph associated with the state is equal to the degree matrix of the partial transpose of this graph. We call this statement to be the strong form of the conjecture. In its weak version, the conjecture requires only the necessity, that is, if the state is separable, the corresponding degree matrices match. We prove the strong form of the conjecture for pure multipartite quantum states using the modified tensor product of graphs defined by Hassan and Joag [J. Phys. A40, 10251 (2007)], as both necessary and sufficient condition for separability. Based on this proof, we give a polynomial-time algorithm for completely factorizing any pure multipartite quantum state. By polynomial-time algorithm, we mean that the execution time of this algorithm increases as a polynomial in , where is the number of parts of the quantum system. We give a counterexample to show that the conjecture fails, in general, even in its weak form, for multipartite mixed states. Finally, we prove this conjecture, in its weak form, for a class of multipartite mixed states, giving only a necessary condition for separability.

Received 12 July 2007
Accepted 12 December 2007
Published online 23 January 2008

Acknowledgments:
We thank Dr. Guruprasad Kar and Professor R. Simon for encouragement. A.S.M.H. thanks the Government of Yemen for financial support. We thank Bhalachandra Pujari for his help with LaTex.

Article outline:

I. INTRODUCTION
II. THE SEPARABILITY CRITERION AND ITS PROOF
III. ALGORITHM
IV. A COUNTEREXAMPLE
V. PROOF OF DEGREE CRITERION FOR A CLASS OF MULTIPARTITE MIXED STATES

Commenting has been disabled for this content