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

arXiv:1601.07704 · Physical Review A

Bipartite separability and nonlocal quantum operations on graphs

Supriyo Dutta, Bibhas Adhikari, Subhashish Banerjee, R. Srikanth

Published Jul 5, 2016• 19 citations
arXivHTMLPDF

Abstract

In this paper we consider the separability problem for bipartite quantum states arising from graphs. Earlier it was proved that the degree criterion is the graph-theoretic counterpart of the familiar positive partial transpose criterion for separability, although there are entangled states with positive partial transpose for which the degree criterion fails. Here we introduce the concept of partially symmetric graphs and degree symmetric graphs by using the well-known concept of partial transposition of a graph and degree criteria, respectively. Thus, we provide classes of bipartite separable states of dimension $m\ifmmode\times\else\texttimes\fi{}n$ arising from partially symmetric graphs. We identify partially asymmetric graphs that lack the property of partial symmetry. We develop a combinatorial procedure to create a partially asymmetric graph from a given partially symmetric graph. We show that this combinatorial operation can act as an entanglement generator for mixed states arising from partially symmetric graphs.

DOI
10.1103/physreva.94.012306

Related papers

Complete family of separability criteria

Andrew C. Doherty, Pablo A. Parrilo, Federico M. Spedalieri

We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\rho} to a larger number of parties satisfying certain symmetry properties. It can be easily shown that all separable states have the required extensions, so the nonexistence of such an extension for a particular state implies that the state is entangled. One of the main advantages of this approach is that searching for the extension can be cast as a convex optimization problem known as a semidefinite program. Whenever an extension does not exist, the dual optimization constructs an explicit entanglement witness for the particular state. These separability tests can be ordered in a hierarchical structure whose first step corresponds to the well-known positive partial transpose (Peres-Horodecki) criterion, and each test in the hierarchy is at least as powerful as the preceding one. This hierarchy is complete, in the sense that any entangled state is guaranteed to fail a test at some finite point in the hierarchy, thus showing it is entangled. The entanglement witnesses corresponding to each step of the hierarchy have well-defined and very interesting algebraic properties that, in turn, allow for a characterization of the interior of the set of positive maps. Coupled with some recent results on the computational complexity of the separability problem, which has been shown to be NP hard, this hierarchy of tests gives a complete and also computationally and theoretically appealing characterization of mixed bipartite entangled states.

arXiv:quant-ph/0308032•Physical Review A•Feb 18, 2004•467 citations

A sufficient and necessary criterion for separability of bipartite quantum states

Hui Zhao, Xinyu Yu

A sufficient and necessary criterion for separability of bipartite quantum states is presented. We construct a class of mixed states in 2 ⊗ k quantum systems and in 3 ⊗ k quantum systems, respectively and show that these states are separable if and only if they are positive partial transpositions.

Chinese Physics B•Jul 31, 2014•0 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 structures in quantum correlation: A new perspective

Rohit kumar, Satyabrata Adhikari

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 $A_G$ 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 $α\in (0,1]$. We first establish the conditions under which the associated operator $ρ_α^{A_G}$ 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 $p_3$-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.

quant-pharXiv:2512.15686•Annals of Physics•Dec 18, 2025•0 citations

Separability criteria and bounds for entanglement measures

Heinz‐Peter Breuer

Employing a recently proposed separability criterion we develop analytical lower bounds for the concurrence and for the entanglement of formation of bipartite quantum systems. The separability criterion is based on a nondecomposable positive map which operates on state spaces with even dimension N >= 4, and leads to a class of nondecomposable optimal entanglement witnesses. It is shown that the bounds derived here complement and improve the existing bounds obtained from the criterion of positive partial transposition and from the realignment criterion.

arXiv:quant-ph/0606185•Journal of Physics A Mathematical and General•Sep 5, 2006•91 citations

Entanglement detection in triangle-free quantum states

Satvik Singh

We present an alternative approach to unveil a different kind of entanglement in bipartite quantum states whose diagonal zero patterns in suitable matrix representations admit a nice description in terms of triangle-free graphs. Upon application of a local averaging operation, the separability of such states transforms into a simple matrix positivity condition, the violation of which implies the presence of entanglement. We completely characterize the class of triangle-free graphs, which allows for nontrivial entanglement detection using the above test. Moreover, we develop a recipe to construct a plethora of unique classes of positive partial transpose (PPT) entangled states in arbitrary dimensions. Finally, we link the task of entanglement detection in general states to the well-known graph-theoretic problem of finding triangle-free-induced subgraphs in a given graph.

arXiv:2010.11891•Physical Review A•Mar 29, 2021•9 citations
In this paper we consider the separability problem for bipartite quantum states arising from graphs. Earlier it was proved that the degree criterion is the graph-theoretic counterpart of the familiar positive partial transpose criterion for separability, although there are entangled states with positive partial transpose for which the degree criterion fails. Here we introduce the concept of partially symmetric graphs and degree symmetric graphs by using the well-known concept of partial transposition of a graph and degree criteria, respectively. Thus, we provide classes of bipartite separable states of dimension m\ifmmode×\else\texttimes\finm\ifmmode\times\else\texttimes\fi{}nm\ifmmode×\else\texttimes\fin arising from partially symmetric graphs. We identify partially asymmetric graphs that lack the property of partial symmetry. We develop a combinatorial procedure to create a partially asymmetric graph from a given partially symmetric graph. We show that this combinatorial operation can act as an entanglement generator for mixed states arising from partially symmetric graphs.
We introduce a family of separability criteria that are based on the existence of extensions of a bipartite quantum state \ensuremath{\rho} to a larger number of parties satisfying certain symmetry properties. It can be easily shown that all separable states have the required extensions, so the nonexistence of such an extension for a particular state implies that the state is entangled. One of the main advantages of this approach is that searching for the extension can be cast as a convex optimization problem known as a semidefinite program. Whenever an extension does not exist, the dual optimization constructs an explicit entanglement witness for the particular state. These separability tests can be ordered in a hierarchical structure whose first step corresponds to the well-known positive partial transpose (Peres-Horodecki) criterion, and each test in the hierarchy is at least as powerful as the preceding one. This hierarchy is complete, in the sense that any entangled state is guaranteed to fail a test at some finite point in the hierarchy, thus showing it is entangled. The entanglement witnesses corresponding to each step of the hierarchy have well-defined and very interesting algebraic properties that, in turn, allow for a characterization of the interior of the set of positive maps. Coupled with some recent results on the computational complexity of the separability problem, which has been shown to be NP hard, this hierarchy of tests gives a complete and also computationally and theoretically appealing characterization of mixed bipartite entangled 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.
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αA_αAα​-graph states, which are constructed from either unweighted or weighted graphs by taking the normalised convex combination of the degree matrix DDD and the adjacency matrix AGA_GAG​ of a graph GGG. 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]α\in (0,1]α∈(0,1]. We first establish the conditions under which the associated operator ραAGρ_α^{A_G}ραAG​​ is positive semidefinite and hence represents a valid quantum state. We then derive a positive partial transposition (PPT) condition for AαA_α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αA_α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 p3p_3p3​-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.
Employing a recently proposed separability criterion we develop analytical lower bounds for the concurrence and for the entanglement of formation of bipartite quantum systems. The separability criterion is based on a nondecomposable positive map which operates on state spaces with even dimension N >= 4, and leads to a class of nondecomposable optimal entanglement witnesses. It is shown that the bounds derived here complement and improve the existing bounds obtained from the criterion of positive partial transposition and from the realignment criterion.
We present an alternative approach to unveil a different kind of entanglement in bipartite quantum states whose diagonal zero patterns in suitable matrix representations admit a nice description in terms of triangle-free graphs. Upon application of a local averaging operation, the separability of such states transforms into a simple matrix positivity condition, the violation of which implies the presence of entanglement. We completely characterize the class of triangle-free graphs, which allows for nontrivial entanglement detection using the above test. Moreover, we develop a recipe to construct a plethora of unique classes of positive partial transpose (PPT) entangled states in arbitrary dimensions. Finally, we link the task of entanglement detection in general states to the well-known graph-theoretic problem of finding triangle-free-induced subgraphs in a given graph.