Laplacian matrices of weighted digraphs represented as quantum states

Abstract

Representing graphs as quantum states is becoming an increasingly important approach to study entanglement of mixed states, alternate to the standard linear algebraic density matrix-based approach of study. In this paper, we propose a general weighted directed graph framework for investigating properties of a large class of quantum states which are defined by three types of Laplacian matrices associated with such graphs. We generalize the standard framework of defining density matrices from simple connected graphs to density matrices using both combinatorial and signless Laplacian matrices associated with weighted directed graphs with complex edge weights and with/without self-loops. We also introduce a new notion of Laplacian matrix, which we call signed Laplacian matrix associated with such graphs. We produce necessary and/or sufficient conditions for such graphs to correspond to pure and mixed quantum states. Using these criteria, we finally determine the graphs whose corresponding density matrices represent entangled pure states which are well known and important for quantum computation applications. We observe that all these entangled pure states share a common combinatorial structure.

1 Introduction

Quantum mechanics deals with states living in the Hilbert space, allowing for linear superpositions to be built up, a facility of immense importance for harnessing the power of quantum mechanics but at the same time making it computationally a formidable task. This can be most easily appreciated by considering entanglement [1,2,3] in higher dimensions as well as in multipartite systems [4], all mathematically and computationally very formidable tasks. Any tool that would aid in this regard would be very welcome.

In combinatorics, a graph is a combination of vertices and edges. We draw a vertex by a bold or labelled point in a paper. Edges are directed or undirected curves joining these vertices. A digraph is a graph consisting directed edges. A loop is an edge that joins a vertex with itself. Edge weight is a complex number assigned to an edge. A graph with weighted edges is called a weighted graph. The theory of graphs is a well-developed mathematical theory that has found many applications in diverse areas, such as the spectrum of a discrete Schr$\ddot{o}$dinger operator in a uniform, periodic magnetic field [5]. Graphs have, by their very construction, the inbuilt feature of visualization. A pertinent question to ask is whether quantum representation of graphs can be made? This would enable the incorporation of the mathematical machinery of graphs into the problems of quantum mechanics and at the same time bring in the attractive feature of visualization of quantum states.

Attempts have been made in this direction by defining a density matrix associated with a graph. In this case, the graph is called the graph representation of such a quantum state. This idea was first introduced in [6] by considering a combinatorial Laplacian matrix associated with an unweighted undirected graph (simple graph). It was further extended in [7] for weighted graphs. Combinatorial and signless Laplacian matrices of a graph are positive semi-definite and Hermitian matrices, defined later.

A criteria of separability of multipartite states represented by the Laplacian of simple graphs have also developed in [8]. Recently, local unitary transformations on a density matrix obtained by signless Laplacian matrix associated with a simple graph have been established as a combinatorial operation which is known as switching of a graph in [9]. A combinatorial operation has also been introduced for density matrices defined by Laplacian matrices associated with simple graphs in [10] that act as an entanglement generator for mixed states arising from partially symmetric graphs.

In this paper, we use both combinatorial and signless Laplacian matrix to define density matrices associated with a weighted digraph having complex edge weights and with or without loops. We also introduce a matrix, which we call signed Laplacian matrix associated with a weighted digraph having loops with both positive and negative weights. In order to relate the topological structure of a weighted digraph and properties of the density matrices defined by these Laplacian matrices, we investigate the rank, zero eigenvalues and positive definiteness of these matrices associated with such graphs. This leads to a classification of graphs which always provide density matrices representing pure quantum states and those which determine mixed quantum states.

Indeed, since pure states comprise a zero-measure subset of mixed states, emphasis is given on identifying graphs which can produce important classes of pure states. We also provide graphs which identify a number of well-known entangled pure states by using the Laplacian matrices associated with such graphs.

A state vector of an entangled state cannot be expressed as a tensor product of other state vectors. These states play an important role in different tasks of quantum information theory. We observe that if a graph represents a pure entangled state, then all the weighted edges are clustered in a subgraph which forms a completely connected graph and the weight of the self-loops attached to each of the vertices is $-(m-2)$ where m is the number of vertices involved in the complete subgraph. This should be of interest to the quantum information community.

The plan of the paper is as follows. In Sect. 2, we define the required terminologies of graph theory, and in particular, we investigate the Laplacian matrices and Laplacian spectra associated with a weighted digraph with or without loops. In Sect. 3, we define the density matrix associated with a weighted digraph and classify the graphs which represent pure and mixed states. Finally, we provide graphs which define density matrices of entangled pure states.

2 Weighted digraphs with/without loops and its Laplacian spectra

Let $G=(V, E)$ be a graph with the vertex set $V = \{1, 2, \ldots , n\}$ and edge set $E \subseteq V\times V.$ A directed graph or digraph G is a graph with a function assigning to each edge an ordered pair of vertices. The first vertex of the ordered pair is called the initial vertex of the edge, and the second is the terminal vertex; together, they are the endpoints. Thus, each edge of a digraph is directed and an undirected edge can be considered as two-way directed. A weighted graph G is a graph with a function $w: E\rightarrow {\mathbb C},$ defined by $w(i,j) = w_{ij}, 1\le i, j \le n,$ where ${\mathbb C}$ is the set of all complex numbers. If $|w_{ij}|=1$ for all $(i,j)\in E$, such a graph is called a gain graph [11]. The function w is called an edge-weight function, and $w_{ij}$ is called the weight of $(i,j)\in E.$ An unweighted graph can be considered as an edge-weighted graph with weight function $w_{ij} =1$ if $w_{ij}\ne 0$. A weighted digraph is a graph which is both weighted and directed. Thus, from now on a graph always is a weighted digraph unless otherwise mentioned.

2.1 Weighted digraphs with or without loops having nonnegative weights

First, we consider weighted digraphs having loops (at least one loop and maximum one loop at a vertex) with nonnegative real weights. The adjacency matrix $A(G)=(a_{ij})$ associated with G is defined as

$$\begin{aligned} a_{ij} = \left\{ \begin{array}{ll} w_{ij}, &{} \hbox { if } (i, j)\in E; \\ \overline{w}_{ij}, &{} \hbox { if } (j, i)\in E; \\ r_i , &{} \hbox { if } (i, i)\in E; \\ 0, &{} \hbox { otherwise } \end{array} \right. \end{aligned}$$

where $0\le r_i\in {\mathbb R}$ is the weight of the loop at ith vertex and $w_{ij}\in {\mathbb C}$. Note that $r_i=0$ if ith vertex does not have a loop. The weighted degree $d_i$ of a vertex $i\in V$ is given by $d_i =\sum _{j=1}^n |a_{ij}|.$ The Laplacian and the signless Laplacian matrices are defined by

$$\begin{aligned} L(G)= & {} \text{ diag }\left( \{d_i\}_{i=1}^n\right) - A(G),\end{aligned}$$

(1)

$$\begin{aligned} Q(G)= & {} \text{ diag }\left( \{d_i\}_{i=1}^n\right) + A(G), \end{aligned}$$

(2)

respectively [12,13,14]. Notice that loops, even though apparent in the adjacency matrix A(G), do not appear in the Laplacian matrix L(G). The above constructions of L(G) and Q(G) will lead to diagonally dominant matrices, i.e. a matrix M where $|M_{i,i}| \ge \sum _{j \ne i}|M_{i,j}|$.

For a weighted edge from vertex i to j with weight $w_{ij}\in {\mathbb C},$ we assume $w_{ij}=r_{ij}e^{i\theta _{ij}}, r_{ij}>0, 0\le \theta \le \pi .$ We consider $\overline{w_{ij}}= r_{ij} e^{-i\theta _{ij}}$ and $-\pi \le \theta _{ij}\le 0$, so that, $\sqrt{w_{ij}}=\sqrt{r_{ij}}e^{i\theta _{ij}/2}, \sqrt{\overline{w_{ij}}}=\sqrt{r_{ij}}e^{-i\theta _{ij}/2}.$ Thus, $(\sqrt{w_{ij}})^2=w_{ij}$ and $\sqrt{w_{ij}} \sqrt{\overline{w_{ij}}}=r_{ij}.$

Theorem 1

Let $G=(V,E)$ be a weighted directed graph without loops. Then L(G) and Q(G) are Hermitian and positive semi-definite matrices.

Proof: Assume that $w_{ij}\in {\mathbb C}$ is the weight of an edge (i, j). Then define

$$\begin{aligned}&(M^{-})_{v,e} \\&=\left\{ \begin{array}{ll} \sqrt{w}_{ij}, &{} \hbox { if } w_{ij}\in {\mathbb C}\setminus {\mathbb R}\hbox { and } v \hbox { is initial vertex of nonloop edge e } \\ -\sqrt{\overline{w}}_{ij}, &{} \hbox { if } w_{ij}\in {\mathbb C}\setminus {\mathbb R}\hbox { and } v \hbox { is terminal vertex of nonloop edge e } \\ \sqrt{|w_{ij}|}, &{} \hbox { if } 0 > w_{ij}\in {\mathbb R}\hbox { and } v \hbox { is initial or terminal vertex of nonloop edge e } \\ -\sqrt{|w_{ij}|}, &{} \hbox { if } 0< w_{ij}\in {\mathbb R}and v \hbox { is initial vertex of nonloop edge e } \\ \sqrt{|w_{ij}|}, &{} \hbox { if } 0 < w_{ij}\in {\mathbb R}\hbox { and } v \hbox { is terminal vertex of nonloop edge e } \\ 0, &{} \hbox { otherwise } \end{array} \right. \end{aligned}$$

and

$$\begin{aligned}&(M^{+})_{v,e}\\&=\left\{ \begin{array}{ll} \sqrt{w}_{ij}, &{} \hbox { if } w_{ij}\in {\mathbb C}\setminus {\mathbb R}\hbox { and } v \hbox { is initial vertex of nonloop edge e } \\ \sqrt{\overline{w}}_{ij}, &{} \hbox { if } w_{ij}\in {\mathbb C}\setminus {\mathbb R}\hbox { and } v \hbox { is terminal vertex of nonloop edge e } \\ \sqrt{|w_{ij}|}, &{} \hbox { if } 0 < w_{ij}\in {\mathbb R}\hbox { and } v \hbox { is initial or terminal vertex of nonloop edge e } \\ -\sqrt{|w_{ij}|}, &{} \hbox { if } 0> w_{ij}\in {\mathbb R}\hbox { and } v \hbox { is initial vertex of nonloop edge e } \\ \sqrt{|w_{ij}|}, &{} \hbox { if } 0 > w_{ij}\in {\mathbb R}\hbox { and } v \hbox { is terminal vertex of nonloop edge e } \\ 0, &{} \hbox { otherwise } \end{array} \right. \end{aligned}$$

for any $v\in V$ and $e\in E.$ Then it is easy to verify that $L(G)=M^{-}(M^{-})^\dagger$ and $Q(G)=M^{+}(M^{+})^\dagger$ where $^\dagger$ denotes conjugate transpose. Therefore, the result follows. $\square$

From the construction of $M^+$ and $M^-$ in Theorem 1, it follows that

$$\begin{aligned} x^\dagger L(G)x= & {} \sum _{i\ne j, (i, j)\in E, 0< w_{ij}\in {\mathbb R}} |w_{ij}||x_i -x_j|^2 + \sum _{i\ne j, (i, j)\in E, 0> w_{ij}\in {\mathbb R}} |w_{ij}||x_i +x_j|^2 \nonumber \\&+ \sum _{i\ne j, (i, j)\in E, w_{ij}\in {\mathbb C}\setminus {\mathbb R}} |\sqrt{\overline{w_{ij}}}x_i - \sqrt{w_{ij}} x_j|^2 \end{aligned}$$

(3)

$$\begin{aligned} x^\dagger Q(G)x= & {} \sum _{i\ne j, (i, j)\in E, 0< w_{ij}\in {\mathbb R}} |w_{ij}||x_i +x_j|^2 + \sum _{i\ne j, (i, j)\in E, 0> w_{ij}\in {\mathbb R}} |w_{ij}||x_i -x_j|^2 \nonumber \\&+ \sum _{i\ne j, (i, j)\in E, w_{ij}\in {\mathbb C}\setminus {\mathbb R}} |\sqrt{\overline{w_{ij}}}x_i + \sqrt{w_{ij}} x_j|^2 \end{aligned}$$

(4)

In the following theorem, we provide a necessary and sufficient condition for a connected loopless weighted digraph having a signless Laplacian eigenvalue zero. Recall that, a digraph is said to be connected if it is connected without considering the directions of the edges.

Theorem 2

Let G be a connected weighted digraph without self-loops. The least eigenvalue of the signless Laplacian matrix of G is 0 if and only if

$$\begin{aligned} (-1)^{p_+ + |P|}\prod _{(i,j)\in P, w_{ij}\in {\mathbb C}\setminus {\mathbb R}}\frac{w_{ij}}{|w_{ij}|} \end{aligned}$$

is directed path invariant for any two fixed vertices in G, where $p_+$ and |P| denotes the number of edges having positive real weights and the number of edges having nonreal weights in a directed path P between the fixed vertices.

Proof: Assume that the least eigenvalue of the signless Laplacian Q(G) of G has an eigenvalue zero, that is, $x^HQ(G)x=0$ for some nonzero vector x. From (4), it is obvious that for such $x, x_i=-x_j$ if $0< w_{ij}\in {\mathbb R}; x_i=x_j$ if $0> w_{ij}\in {\mathbb R}; x_i=-\frac{w_{ij}}{|w_{ij}|}x_j$ if $w_{ij}\in {\mathbb C}\setminus {\mathbb R}.$ Let $P\equiv (u=i_1, i_2, \ldots , i_{k_1}=v)$ and $P'\equiv (u=i'_1, i'_2,i'_3, \ldots , i'_{k_2}=v)$ be two distinct directed paths from the vertex u to the vertex v. Then, for the path P, 

$$\begin{aligned} x_u=(-1)^{p_+ + |P|}\prod _{(i,j)\in P, w_{ij}\in {\mathbb C}\setminus {\mathbb R}}\frac{w_{ij}}{|w_{ij}|} \,\, x_v; \end{aligned}$$

and for the path $P',$

$$\begin{aligned} x_u=(-1)^{p'_+ + |P'|}\prod _{(ij)\in P', w_{ij}\in {\mathbb C}\setminus {\mathbb R}}\frac{w_{ij}}{|w_{ij}|} \,\, x_v. \end{aligned}$$

Further, $x_u\ne 0$ and $x_v\ne 0$ since otherwise $x=0$ follows from (4) as the graph is connected. Hence, the desired result follows.

Conversely, if the given condition is true for any two different directed paths for any pair of vertices in G,  a vector x defined by $x_i=-x_j$ if $0< w_{ij}\in {\mathbb R}; x_i=x_j$ if $0> w_{ij}\in {\mathbb R}; x_i=-\frac{w_{ij}}{|w_{ij}|}x_j$ if $w_{ij}\in {\mathbb C}\setminus {\mathbb R}$ will satisfy $x^\dagger Q(G)x=0.$ Hence, the proof. $\square$

Corollary 1

The least eigenvalue of the signless Laplacian matrix of a loopless connected weighted digraph G having complex unit weights is equal to 0 if and only if $(-1)^p W(P)$ is directed path invariant for any two fixed vertices in G, where p and W(P) denote the length and the product of the weights of the edges of a directed path P between the fixed vertices in G. In particular, 0 is a simple eigenvalue.

Corollary 2

Let G be a weighted digraph without loops with $n (>2)$ vertices. Assume that 0 is a signless Laplacian eigenvalue of G. Then the multiplicity of 0 as a signless Laplacian eigenvalue of G is k if and only if the graph is disconnected with k connected components.

It is shown in [14] that for a unweighted undirected connected graph G without loops, the least eigenvalue of the signless Laplacian of G is equal to 0 if and only if the graph is bipartite and 0 is a simple eigenvalue. We mention that the condition provided in Corollary 2 for existence of zero eigenvalue of weighted directed graph is a generalized version of the condition obtained for unweighted undirected graph in [14]. That is, the condition in Corollary 2 is satisfied for an unweighted undirected connected graph if and only if the graph is bipartite.

The following corollary provides a necessary and sufficient condition for existence of zero Laplacian eigenvalue of a weighted connected digraph.

Corollary 3

The least eigenvalue of the combinatorial Laplacian matrix of a loopless connected weighted digraph G is equal to 0 if and only if

$$\begin{aligned} (-1)^{p_-}\prod _{(i,j)\in P, w_{ij}\in {\mathbb C}\setminus {\mathbb R}}\frac{w_{ij}}{|w_{ij}|} \end{aligned}$$

is directed path invariant for any two fixed vertices in G, where $p_-$ denotes the number of links with negative real weights of a directed path P between the fixed vertices.

Proof: The proof is similar to the proof of Theorem 2. $\square$

Corollary 4

The least eigenvalue of the combinatorial Laplacian of a loopless connected weighted digraph G having complex unit weights is equal to 0 if and only if W(P) is directed path invariant for any two fixed vertices in G. In particular, 0 is a simple eigenvalue.

An alternative proof of the above corollary also can be found in [13].

Corollary 5

Let G be a weighted digraph without loops with $n (>2)$ vertices. Assume that 0 is a combinatorial Laplacian eigenvalue of G. Then the multiplicity of 0 as a combinatorial Laplacian eigenvalue of G is k if and only if the graph is disconnected with k connected components.

As we mentioned above, loops with nonnegative weights have no effect on the combinatorial Laplacian matrix. Thus, we only consider signless Laplacian matrix when an weighted digraph contains at least one loop with positive real weight. It is easy to verify that, given an weighted digraph G with at least one loop having positive real weight, we have

$$\begin{aligned} x^\dagger Q(G)x=x^\dagger Q(\widehat{G})x + \sum _{(i,i)\in E} r_i|x_i|^2 \end{aligned}$$

(5)

where $\widehat{G}$ is the subgraph of G without considering loops. This also shows that Q(G) is Hermitian and positive semi-definite.

Theorem 3

Zero can never be a signless Laplacian eigenvalue of a connected weighted digraph G with loops (at least one vertex contains a loop) having positive weights.

Proof: Consider a connected weighted digraph G with loops (at least one vertex contains a loop) having positive weights. If 0 is a signless Laplacian eigenvalue of G,  from (5) we know that there exists an $0\ne x\in {\mathbb C}^n$ such that

$$\begin{aligned} x^\dagger Q(G)x=x^\dagger Q\left( \widehat{G}\right) x + \sum _{(i,i)\in E} r_i|x_i|^2=0 \end{aligned}$$

where $\widehat{G}$ is the subgraph of G without loops. Assume that the k-th vertex contains the loop. For $x^\dagger Q_Gx$ to be zero, $x_k$ has to be zero since $r_k$ is positive. Further, since the graph is connected, kth vertex is linked with m (say) vertices $k_1, k_2, \ldots , k_m$ for some m which implies $x_{k_j}=0$ for $j=1,\ldots , m$ which further implies that $x_j=0$ for all $j=1, \ldots , n$ since $k_j$ vertices are linked with other vertices and $x^\dagger Q(\widehat{G})x=0$ for all $(i,j)\in E.$ $\square$

2.2 Weighted digraphs with loops having at least one loop with negative weight

Recall the definitions of Laplacian and signless Laplacian matrices associated with a weighted digraph. Observe that loops, even though apparent in the adjacency matrix A(G), do not reflect in Laplacian matrix when the loops have positive weights, and in signless Laplacian matrices when the loops have negative weights. Thus, for weighted digraphs with both nonnegative and negative weighted loops (at least one of the loops has negative weight), we introduce a new matrix, which we call signed Laplacian, denoted by $L_-(G)$ and $L_{\pm }(G)$ when G has all the loops with nonpositive weights, and when G contains loops with positive weights as well as negative weights, respectively, by

$$\begin{aligned} L_-(G)&= R_-(G) + Q(\widehat{G}),\nonumber \\ \text{ and }~ L_{\pm }(G)&= R_{\pm }(G) + Q(\widehat{G}), \end{aligned}$$

(6)

where $R_-(G)=R_{\pm }(G)=\mathrm {diag}\{r_1, r_2, \ldots , r_n\}, r_j\in {\mathbb R}$ denotes the weight of the loop at jth vertex, $j=1,\ldots , n$ and $Q(\widehat{G})$ is the signless Laplacian matrix of the graph $\widehat{G}$ constructed from G without considering the loops. Obviously, $L_-(G)$ and $L_{\pm }(G)$ are Hermitian matrices. In order to simplify the notation, we denote $R(G)=R_-(G)=R_{\pm }(G).$

Theorem 4

Given a weighted digraph G with nonpositive loops, $L_-(G)$ is semi-definite if

$$\begin{aligned} \max _i |r_i| \le \lambda _{\min }Q(\widehat{G}) \end{aligned}$$

where $r_i\le 0, i=1:n$ are the weights of the loops present in the graph and $\lambda _{min}Q(\widehat{G})$ denotes the minimum eigenvalue of $Q(\widehat{G}).$

Proof: For any unit vector $0\ne x\in {\mathbb C}^n,$ we have

$$\begin{aligned}&-x^{\dagger }R(G)x \le \max _i|r_i|, \nonumber \\ \text{ and }~&x^{\dagger }Q(\widehat{G})x \ge \lambda _{\min }(Q(\widehat{G})). \end{aligned}$$

(7)

In order to show that $L_-(G)$ is positive semi-definite, for any nonzero unit vector $x\in {\mathbb C}^n,$ we must have $x^{\dagger }L_-(G)x=x^{\dagger }R(G)x+x^{\dagger }Q(\widehat{G})x \ge 0.$ If the given condition is satisfied, the proof follows from (7). $\square$

Given a weighted digraph, the theorem declares that if the maximum of the modulus of weights of the loops do not exceed the minimum signless Laplacian eigenvalue of the graph without considering the loops, then the signed Laplacian corresponding to the given graph will be positive semi-definite.

Example 1

• 1. Consider the graph given in Fig. 1. The signed Laplacian matrix with negative loops associated with G is given by

  $$\begin{aligned} L_-(G)= & {} \left[ \begin{matrix} 1 &{}1 &{} 1 &{} -1\\ 1 &{} 1 &{} 1 &{} -1\\ 1 &{} 1 &{} 1 &{} -1 \\ -1 &{} -1 &{} -1 &{} 1 \end{matrix} \right] \\= & {} \left[ \begin{matrix} -2 &{} 0 &{} 0 &{} 0 \\ 0 &{} -2 &{} 0 &{} 0\\ 0 &{} 0 &{} -2 &{} 0\\ 0 &{} 0 &{} 0&{} -2 \end{matrix} \right] + \left[ \begin{matrix} 3 &{}1 &{} 1 &{} -1\\ 1 &{} 3 &{} 1 &{} -1\\ 1 &{} 1 &{} 3 &{} -1 \\ -1 &{} -1 &{} -1 &{} 3 \end{matrix} \right] \\= & {} R(G) + Q(\widehat{G}). \end{aligned}$$

  Note that, eigenvalues of $Q(\widehat{G})$ are 2, 2, 2, 6.

• 2. Consider the weighted digraph given in Fig. 2. The eigenvalues of $L_-(G)$ are given by 0.0679, 1.8000, 3.5321.

Theorem 5

Let G be a weighted digraph with loops having nonpositive weights. If the subgraph $\widehat{G}$ obtained from G by removing the loops has signless Laplacian eigenvalue zero, then $L_-(G)$ is not positive semi-definite.

Proof: Let x be the unit eigenvector corresponding to the zero Laplacian eigenvalue of $\widehat{G}.$ Then $x^{\dagger }L_-(G)x=x^{\dagger }R(G)x <0$ since R contains at least one loop with negative weight. $\square$

Theorem 6

Let G be a connected weighted digraph with nonpositive loop weights and n number of vertices. Let $\lambda$ be a signless Laplacian eigenvalue of $\widehat{G}$ of algebraic multiplicity k. Then the number of zero eigenvalues of $L_-(G)$ is k if $|r_i|=\lambda$ for all $i\in V(G).$

Proof: Consider $L_-(G)=R(G)+Q(\widehat{G}).$ We know that 0 is an eigenvalue of $L_-(G)$ if an only if there exists a unit vector $x\in {\mathbb C}^n$ such that $x^{\dagger }L_-(G)x=0,$ which implies $x^{\dagger }R(G)x=x^{\dagger }Q(\widehat{G})x.$ Assume that $\lambda$ is an eigenvalue of $Q(\widehat{G})$ with algebraic multiplicity k. Since $Q(\widehat{G})$ is Hermitian, there exists unit orthogonal vectors $x_1, x_2, \ldots , x_k$ such that $x_i^{\dagger }Q(\widehat{G})x_i=\lambda , i=1, \ldots , k.$ Set $R(G)=-\lambda I_n,$ where $I_n$ is the identity matrix of order n. Then $x_i^{\dagger }L_-(G)x_i=0$ for all i. Since $x_i$s are orthonormal vectors, algebraic multiplicity of eigenvalue 0 of $L_-(G)$ is k. $\square$

Remark 1

Note that, a connected weighted digraph with all negative weighted loops can have zero signed Laplacian eigenvalues of multiplicity more than one. In particular, consider any connected weighted complete digraph G where all the loops are present having weights equal to one of the eigenvalues of $Q(\widehat{G}).$ For example, consider Fig. 1.

Fig. 1

Graph with negative weighted loops

Fig. 2

Graph with negative weighted loops

Now we consider weighted digraphs with loops having both positive and negative weights. Then we have the following theorem.

Theorem 7

Let G be a weighted digraph with loops having at least one negative and at least one positive weighted loops. Assume that G has n vertices, k are having positive loop weights, l are having negative loop weights such that $k+l\le n.$ Let $r_1^+, \ldots , r_k^+$ be the positive weights and $r_{k+1}^-, \ldots , r_l^-$ the negative weights such that $r_j^{\pm }=r_j-d_j,$ for some $r_j\in {\mathbb R}, j=1,\ldots ,k,k+1,\ldots ,l,\ldots , n$ where $d_j$ is the degree of jth vertex of $\widehat{G}$. Then $L_{\pm }(G)$ is positive semi-definite if and only if

$$\begin{aligned} \mathrm {diag}\{r_1, r_2, \ldots , r_n\} + A(\widehat{G}) \end{aligned}$$

is positive semi-definite.

Proof: Without loss of generality, assume that the first k vertices are having loops with positive weights, second l vertices are having loops with negative weights, and the remaining (if any) vertices have no loops. For any nonzero $x\in {\mathbb C}^n,$

$$\begin{aligned} x^{\dagger }L_{\pm }(G)x= & {} x^{\dagger }\left[ \begin{matrix} R_+ &{} 0 &{} 0 \\ 0 &{} R_- &{} 0 \\ 0 &{} 0 &{} R_0 \end{matrix} \right] x + x^{\dagger }Q(\widehat{G})x \\= & {} x^{\dagger }(\mathrm {diag}\{r_1, r_2, \ldots , r_n\} + A(\widehat{G}))x \end{aligned}$$

where $R_+=\mathrm {diag}\{r_1^+,\ldots ,r_k^+\}, R_-=\mathrm {diag}\{r_1^-,\ldots , r_l^-\}$ and $R_0=\mathrm {diag}\{r_{l+1}, \ldots , r_n\}.$ Hence, the result follows. $\square$

Theorem 8

Let G be a weighted digraph with loops having both positive and negative weighted loops. The number of zero eigenvalues of $L_{\pm }(G)$ is equal to the number of zero eigenvalues of $\mathrm {diag}\{r_1, r_2, \ldots , r_n\} + A(\widehat{G})$ where $r_j^{\pm }=r_j-d_j, j=1,\ldots , n$ and $r_j^{\pm }$ is the weight of the loop at jth vertex.

Proof: The proof follows by Theorem 7. $\square$

Example 2

Consider the weighted digraph in Fig. 3.The signed Laplacian is

$$\begin{aligned} L_{\pm }(G)=\left[ \begin{matrix} 1 &{} 0 &{} 0 &{} -2 \\ 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 0\\ -2 &{} 0 &{} 0 &{} 4 \end{matrix} \right] =\left[ \begin{matrix} -1 &{} 0 &{} 0 &{} 0 \\ 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 2 \end{matrix} \right] + \left[ \begin{matrix} 2 &{} 0 &{} 0 &{} -2 \\ 0 &{} 0 &{} 0 &{} 0\\ 0 &{} 0 &{} 0 &{} 0\\ -2 &{} 0 &{} 0 &{} 2 \end{matrix} \right] . \end{aligned}$$

Fig. 3

Graph G with negative and positive weighted loops

Note that if the number of zero eigenvalues of a Laplacian matrix is more than one, the corresponding graph represents a mixed state. We use this in the next section to determine graphs which represent pure states, that is, the graphs whose Laplacian eigenvalues are all zeros, except one.

3 Graph structure for pure and mixed states

The approach of identifying the density matrix representations of quantum states by density matrices of unweighted undirected graphs was introduced in [6] and extended in [7] for weighted graphs. However, the recent development of signless Laplacian matrix associated with a graph has not been gainfully used in both [6] and [7] to define density matrix associated with the graph. Thus, the results in [7] could not capture interesting connections between the properties of density matrices defined by a graph and topology of the graph. In this section, we use the Laplacian matrices defined in the last section to define density matrix associated with a weighted digraph. Further, we describe how the topological structure of the graph dictates whether the corresponding density matrices represent pure or mixed states.

3.1 Pure states and mixed states

Recall that density matrix representation of a quantum state is a Hermitian positive semi-definite matrix with unit trace. The density matrix $\sigma$ corresponding to a state is called pure if $\mathrm {Tr}(\sigma ^2)=1$ and mixed if $\mathrm {Tr}(\sigma ^2)<1.$ A quantum state, in general, can also be represented as

$$\begin{aligned} \sigma = \sum _{i} p_i |\psi _i\rangle \langle \psi _i|, \end{aligned}$$

(8)

where $0\ne |\psi _i\rangle \in {\mathbb C}^2$ with norm one and $\sum _i p_i =1, 0\le p_i \le 1$. Thus $\sigma$ is a convex combination of rank one matrices, in particular, rank one projections. If $\sigma$ is just a projection with rank one then $\sigma$ is a pure state, otherwise, a mixed state.

We define density matrices associated with a weighted digraph. We denote an weighted complete bipartite digraph without loops of order n by $K_n.$

Definition 1

The density matrix $\sigma _G$ associated with an weighted digraph G is given by

$$\begin{aligned} \sigma _G := \frac{1}{\mathrm {Tr}(K(G))} K(G) \end{aligned}$$

(9)

where

• $K(G)=L(G)$ when G is without a loop

• $K(G)=Q(G)$ when either G is without a loop or having loops with nonnegative weights

• $K(G)=L_-(G)$ when G is with loops having nonpositive weights and $L_-(G)$ is positive semi-definite

• $K(G)=L_{\pm }(G)$ when G contains loops with positive weights, negative weights and $L_{\pm }(G)$ is positive semi-definite.

Recall that, an isolated vertex in a graph is a vertex, not adjacent to any other vertex.

Theorem 9

The density matrix defined by Laplacian or signless Laplacian matrix of a weighted digraph G without loops has rank one if and only if the graph is $K_ 2$ or $\widehat{K}_2 := K_2 \sqcup v_1 \sqcup v_2 \sqcup \ldots v_{n-2}.$, where $v_1, v_2, \ldots , v_{n-2}$ are isolated vertices.

Proof: Assume that $\sigma _G$ has rank one and G contains n vertices. Then $\sigma _G$ has eigenvalue 1 with multiplicity one (since trace of $\sigma _G =1$) and 0 is an eigenvalue of multiplicity $n-1.$ If $n=2$ then obviously $G=K_2.$ If $n\ne 2$ then by Corollary 5, G contains $n-1$ connected components. Thus, $G = \widehat{K}_2.$

Conversely, suppose $G = K_2$ or $\widehat{K}_2.$ Then the eigenvalues of $\sigma _G$ are 0 with multiplicity $n-1$ for $G=\widehat{K}_2$ and multiplicity 1 for $G=K_2$, and 1 with multiplicity one. Hence, the result follows. $\square$

Remark 2

We mention that the same result has been obtained in [6] for unweighted undirected graphs.

Corollary 6

Let G be a weighted digraph without loops isomorphic to $K_2$ or $\widehat{K}_2.$ Then $\sigma _G$ constructed by L(G) or Q(G) represents a pure state.

Proof: The density matrix $\sigma _G$ has a simple eigenvalue 1, and other eigenvalues are zeros. Since trace of any matrix is sum of the eigenvalues of the matrix, we have $\mathrm {Tr}(\sigma _G)=1$ and $\mathrm {Tr}(\sigma _G^2) = 1.$ Thus, the result follows. $\square$

Corollary 7

Let G be a weighted digraph without loops of order n that is not isomorphic to $K_2$ and $\widehat{K}_2.$ Then $\sigma _G$ constructed by L(G) or Q(G) represents a mixed state.

Proof: Let the eigenvalues of $\sigma (G)$ be $\lambda _1\le \lambda _2\le \ldots \le \lambda _n.$ By the definition of $\sigma _G$, we have $\mathrm {Tr}(\sigma _G)=1$ as $\sum _{i=1}^n \frac{\lambda _i}{d(G)} =1$ where $d(G)=\sum _{i=1}^n \lambda _i.$ Then the eigenvalues of $\sigma _G^2$ are $\frac{\lambda _1^2}{d(G)^2}, \frac{\lambda _2^2}{d(G)^2}, \ldots , \frac{\lambda _n^2}{d(G)^2}.$ Thus

$$\begin{aligned} \mathrm {Tr}(\sigma _G^2)= & {} \frac{\sum _{i=1}^n \lambda _i^2}{d(G)^2} = \frac{d(G)^2 - 2\sum _{i\ne j, i,j=1}^n \lambda _i\lambda _j}{d(G)^2} < 1. \end{aligned}$$

Hence, G represents a mixed state. $\square$

Fig. 4

Pure state given by $K_2$ along with 4 isolated nodes

Fig. 5

Mixed state with 6 vertices

Fig. 6

Pure state given by $O_1$ along with a single loop

Example 3

• 1. Consider the graph in Fig. 4 which represents a pure state.

• 2. Consider the graph in Fig. 5 which represents a mixed state. The digraph $O_1$, Fig. 6, denotes a digraph with one vertex, and the vertex contains a directed weighted loop.

Theorem 10

The density matrix of order n defined by signless Laplacian matrix associated with a weighted digraph G with loops having nonnegative weights has rank one if and only if the graph is $\widehat{O}_1 := O_1 \sqcup v_1 \sqcup v_2 \sqcup \ldots v_{n-1}$, where $v_1, v_2, \ldots , v_{n-1}$ are isolated vertices without loops.

Proof: Assume that the density matrix $\sigma _G$ of G constructed by the signless Laplacian of the graph and G contains n vertices with at least one vertex contains a directed loop. Obviously, the matrix $\sigma _G$ has rank 1 if and only if any submatrix of $\sigma _G$ of order $\ge 2$ is singular. Without loss of generality, assume that the first vertex $v_1$ is attached with a directed loop. Then the following cases arise.

Case-I: The vertex $v_1$ is linked by a directed edge with another vertex say the second vertex $v_2.$ In this case, if we consider the $2\times 2$ submatrix of $\sigma _G$ constructed by the intersection of the 1st row, 2nd row, 1st column and 2nd column of $\sigma _G$ then this is a matrix with nonzero determinant. Hence, rank of $\sigma _G$ is at least 2.

Case-II: Any two vertices without loops say $v_i$ and $v_j$ are linked by a directed edge. In this case, if we consider the $2\times 2$ submatrix of $\sigma _G$ constructed by the intersection of the 1st row, ith row, 1st column and ith column of $\sigma _G$ then this is a matrix with nonzero determinant. Hence, rank of $\sigma _G$ is at least 2.

Case-III: All the vertices are isolated without loops except two vertices say the 1st and the 2nd vertex. Then, if we consider the $2\times 2$ submatrix of $\sigma _G$ constructed by the intersection of the 1st row, 2nd row, 1st column and 2nd column of $\sigma _G$ then this is a matrix with nonzero determinant. Hence, rank of $\sigma _G$ is at least 2.

Case-IV: All the vertices are isolated without loops except the 1st vertex. Then the density matrix $\sigma _G$ is of rank 1.

Hence, the desired result follows. $\square$

Corollary 8

Let G be a weighted digraph with loops having nonnegative weights and is isomorphic to $\widehat{O}_1.$ Then $\sigma _G$ defined by the signless Laplacian of G represents a pure state.

Corollary 9

Let G be a weighted digraph with loops having nonnegative weights of order n that is not isomorphic to $\widehat{O}_1.$ Then $\sigma _G$ defined by the signless Laplacian of G represents a mixed state.

Example 4

• 1. Consider the graph in Fig. 6 which represents a pure state.

• 2. Consider the graph in Fig. 7 which represents a mixed state.

Fig. 7

Mixed state with 6 vertices

Remark 3

Realization of 1-qubit by weighted digraph: Consider the graph $G=K_2$ for a pure state with edge weight $w\in {\mathbb S}_1^+.$ Then the corresponding density matrix with respect to the Laplacian matrix is given by

$$\begin{aligned} \sigma _G =\frac{1}{2} L(G) = \frac{1}{2}\left[ \begin{matrix} 1 &{} -w \\ - \overline{w} &{} 1 \end{matrix} \right] , \end{aligned}$$

$\text{ where }~ w =e^{i\phi }, 0\le \phi \le 2\pi$. The eigenvalues of $\sigma _G$ are 0 and 1 corresponding to eigenvectors $|\psi _1\rangle = \frac{1}{\sqrt{2} |z_1|}\left[ \begin{matrix} z_1 \\ \overline{w}z_1 \end{matrix} \right]$ and $|\psi _2\rangle = \frac{1}{\sqrt{2} |z_2|} \left[ \begin{matrix} z_2 \\ -\overline{w}z_2 \end{matrix} \right]$, respectively, where $0\ne z_1, z_2\in {\mathbb C}$. Thus, the pure state is given by $\sigma = |\psi _2\rangle \langle \psi _2|.$ Setting $z_2 = r e^{i\theta }, |z_2|=r>0, 0\le \theta \le 2\pi ,$ the vector representation of the pure state is given by

$$\begin{aligned} |\psi \rangle= & {} e^{i\theta } \left( \frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} e^{-i\phi }|1\rangle \right) ,\\\equiv & {} \frac{1}{\sqrt{2}} |0\rangle - \frac{1}{\sqrt{2}} e^{-i\phi }|1\rangle \end{aligned}$$

where $|0\rangle =\left[ \begin{matrix} 1 \\ 0 \end{matrix} \right]$ and $|1\rangle =\left[ \begin{matrix} 0 \\ 1 \end{matrix} \right] .$

Further, the density matrix with respect to the signless Laplacian matrix is given by

$$\begin{aligned} \sigma _G =\frac{1}{2} Q(G) = \frac{1}{2}\left[ \begin{matrix} 1 &{} w \\ \overline{w} &{} 1 \end{matrix} \right] . \end{aligned}$$

Following a similar approach, as above, the corresponding vector representation of the pure state is given by

$$\begin{aligned} |\psi \rangle \equiv \frac{1}{\sqrt{2}} |0\rangle + \frac{1}{\sqrt{2}} e^{-i\phi }|1\rangle , 0\le \phi \le 2\pi . \end{aligned}$$

Now we consider weighted graphs with loops having nonpositive weights. We denote $S_n, n\ge 2$, a star graph with n vertices.

Theorem 11

Consider a weighted digraph G consisting of a weighted digraph $\widehat{G}$ without loops having n number of vertices and loops at each vertex of $\widehat{G}$ with equal weights $-\lambda$ where $\lambda$ is a signless Laplacian eigenvalue of $\widehat{G}$ with multiplicity $n-1.$ Then $\sigma (G)=\frac{1}{\mathrm {Tr}(L_-(G))}L_-(G)$ represents a pure state.

Proof: By Theorem 4, $\sigma (G)$ is positive semi-definite. However, $n-1$ number of eigenvalues of $L_-(G)$ are zero since $\lambda$ is an eigenvalue of $Q(\widehat{G})$ of algebraic multiplicity $n-1.$ Therefore, rank of $\sigma (G)$ is one. Hence, the result follows. $\square$

Corollary 10

Consider a weighted digraph G consists of a weighted digraph $\widehat{G}$ without loops having n number of vertices and loops at each vertex of $\widehat{G}$ with equal weights $-\lambda$ where $\lambda$ is a signless Laplacian eigenvalue of $\widehat{G}$ with multiplicity $k< n-1.$ Then $\sigma (G)=\frac{1}{\mathrm {Tr}(L_-(G))}L_-(G)$ represents a mixed state.

Example 5

• 1. Consider $G=K_n$ along with loops at each vertex of equal weights $-n/(n-1).$ Then $\sigma (G)=\frac{1}{\mathrm {Tr}(L_-(G))}L_-(G)$ represents a pure state. For instance, consider $n=3$ in Fig. 8.

• 2. Consider $G=S_n$ along with loops at each vertex of equal weights $-1.$ Then $\sigma (G)=\frac{1}{\mathrm {Tr}(L_-(G))}L_-(G)$ represents a mixed state. For example, consider $n=4$ in Fig. 9.

Fig. 8

Pure state given by $K_3$, see Theorem 11, along with negative weighted loops

Fig. 9

Mixed state given by $S_4$, see Corollary 10, along with negative weighted loops

Now we consider graphs with both positive and negative weighted loops.

Theorem 12

Let G be a weighted digraph with loops having at least one negative and at least one positive weighted loops. Assume that G has n vertices, k are having positive loop weights, l are having negative loop weights such that $k+l\le n.$ Let $r_1^+, \ldots , r_k^+$ be the positive weights and $r_{k+1}^-, \ldots , r_l^-$ the negative weights such that $r_j^{\pm }=r_j-d_j, j=1,\ldots ,k,k+1,\ldots ,l,\ldots , n$ where $d_j$ is the degree of jth vertex of $\widehat{G}$. Then the density matrix corresponding to $L_{\pm }(G)$ represents a pure state if and only if

$$\begin{aligned} \mathrm {diag}\{r_1, r_2, \ldots , r_n\} + A(\widehat{G}) \end{aligned}$$

has rank one.

Proof: The proof follows from the construction of $L_{\pm }(G)$ and Theorem 7. $\square$

However, we can construct a class of pure states by using the construction mentioned in the following corollary.

Corollary 11

Consider a digraph $\widehat{G}$ without loops having n vertices that represents a pure state obtained by signless Laplacian matrix $Q(\widehat{G})$, that is, only two vertices of G, say ith and jth of $\widehat{G}=(V,E)$ are linked having edge weight $w_{ij}\in {\mathbb C}$, rest of the vertices are isolated. Define $r_i^+=r_i^2-|w_{ij}|$ and $r_j^-=r_j^2-|w_{ij}|$ where $r_i, r_j\in {\mathbb R}_+$ such that $r_i^2 + r_j^2=1$ and $r_ir_j=|w_{ij}|.$ Then the graph G constructed by $\widehat{G}$ along with loops introduced at the ith and jth vertices having weights $r_i^+$ and $r_j^-$, respectively, provides a pure state defined by $L_{\pm }(G).$

Proof: Note that, all the entries of $L_{\pm }(G)=(l_{pq})$ are given by

$$\begin{aligned} (L_{\pm }(G))_{pq}=\left\{ \begin{array}{ll} r_i^2, &{} \hbox { if } p=q=i \\ r_j^2, &{} \hbox { if } p=q=j \\ w_{ij}, &{} \hbox { if } p=j, q=j\\ \overline{w}_{ij}, &{} \hbox { if } p=j, q=i\\ 0 &{} \hbox { otherwise. } \end{array} \right. \end{aligned}$$

Obviously, $L_{\pm }(G)$ is Hermitian, positive semi-definite and $\mathrm {Tr}(L_{\pm }(G))=1.$ Further, rank of $L_{\pm }(G)=1.$ Therefore, G represents a pure state. $\square$

Fig. 10

$G_1$ and $G_2$

Fig. 11

Graph G

Fig. 12

$G_1$

4 Graph structure of entangled pure states

In this section, we provide weighted digraphs whose density matrices represent entangled pure states. Because of the potential applications offered by pure entangled states, they are of immense importance in quantum information and computation. This forms the basis for studying the properties of such states from a graph theoretic approach.

• 1. Bell States: For two-qubit systems, Bell states [1, 2] are maximally entangled states represented as

  $$\begin{aligned} \left| \phi \right\rangle ^{\pm }_{12}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 00 \right\rangle _{12} \pm \left| 11 \right\rangle _{12} \, \right] , \nonumber \\ \left| \psi \right\rangle ^{\pm }_{12}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 01 \right\rangle _{12} \pm \left| 10 \right\rangle _{12} \, \right] \ . \end{aligned}$$

  (10)

  For example, consider the graphs with four vertices in Fig. 10. The density matrices are given by $\sigma (G_i)=\frac{K(G_i)}{\mathrm {Tr}(K(G_i))}$; $K(G_i)\in \{L(G_i), Q(G_i)\}$ where $\sigma (G_1)= \left| \phi \right\rangle _{12}^{+} \left\langle \phi \right| _{12}^{+}$ and $\sigma (G_2) = \left| \psi \right\rangle _{12}^{+} \left\langle \psi \right| _{12}^{+}$. In order to produce the Bell states of the form $\frac{1}{\sqrt{2}}\left[ |00\rangle +e^{i\delta } |11\rangle \right]$ and $\frac{1}{\sqrt{2}}\left[ |01\rangle +e^{i\delta } |10\rangle \right]$ using $G_1$ and $G_2$, one has to replace the edge weights by a factor $e^{i\delta }$ and edge will be unidirectional.

• 2. General 2-qubit and 3-qubit entangled states: Consider the graph in Fig. 11 for the general two-qubit state $\left| \Psi \right\rangle = a\left| 00\right\rangle + b \left| 11\right\rangle$, where $a,b\in {\mathbb C}\setminus \{0\}$ and $|a|^2+|b|^2=1.$ The density matrix associated with G is given by $\sigma (G)=\frac{L_{\pm }(G)}{\mathrm {Tr}(L_{\pm }(G))}=\left| \Psi \right\rangle \left\langle \Psi \right|$. The graph for a general 3-qubit state, $\left| \Phi \right\rangle = a\left| 000\right\rangle + b \left| 111\right\rangle$, will follow similarly by considering 8 vertices where only the first and the last vertices will be linked.

• 3. Three-qubit GHZ and W States: Three-qubit states can be separated into two inequivalent classes, namely GHZ class and W class [16, 17]. These classes have distinct properties and cannot be converted into one another by performing Stochastic Local Operations and Classical Communication (SLOCC). We have already shown that the graph of a general three-qubit GHZ state will be similar to Fig. 11. For specific cases of $a=b=\frac{1}{\sqrt{2}}$, the eight orthogonal GHZ states are,

  $$\begin{aligned} \left| \psi \right\rangle ^{(1),(2)}_{123}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 000 \right\rangle \pm \left| 111 \right\rangle \, \right] , \nonumber \\ \left| \psi \right\rangle ^{(3),(4)}_{123}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 001 \right\rangle \pm \left| 110 \right\rangle \, \right] , \nonumber \\ \left| \psi \right\rangle ^{(5),(6)}_{123}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 010 \right\rangle \pm \left| 101 \right\rangle \, \right] , \nonumber \\ \left| \psi \right\rangle ^{(3),(4)}_{123}= & {} \frac{1}{\sqrt{2}} \left[ \, \left| 011 \right\rangle \pm \left| 100 \right\rangle \, \right] , \nonumber \\ \end{aligned}$$

  (11)

  The graphs corresponding to Eq. (12) are given in Figs. 12, 13, 14, 15. and the density matrices associated with $G_1, G_2, G_3, G_4$ are given $\sigma (G_i)=\frac{K(G_i)}{\mathrm {Tr}(K(G_i))}$ where $K(G_i)\in \{L(G_i), Q(G_i)\}$, and $\sigma (G_1)=\left| \psi \right\rangle _{123}^{(1),(2)} \left\langle \psi \right| _{123}^{(1),(2)}, \sigma (G_2)=\left| \psi \right\rangle _{123}^{(3),(4)} \left\langle \psi \right| _{123}^{(3),(4)}, \sigma (G_3)=\left| \psi \right\rangle _{123}^{(5),(6)} \left\langle \psi \right| _{123}^{(5),(6)}, \sigma (G_4)=\left| \psi \right\rangle _{123}^{(7),(8)} \left\langle \psi \right| _{123}^{(7),(8)}$. The general three-qubit W state is given as $\left| \psi \right\rangle _{123}^{W}=a|001\rangle +b|010\rangle +c|100\rangle$ where $|a|^2+|b|^2+|c|^2=1$. The graph representation of $\left| \psi \right\rangle _{123}^{W}$ is given in Fig. 16. The density matrix for the W class of states can be expressed as $\sigma (G)=\frac{L_-(G)}{\mathrm {Tr}(L_-(G))}$. For a specific case where $a=b=c=\frac{1}{\sqrt{3}}$, Fig. 17 represents the graphical representation for a standard W state. It is evident that the graphs for GHZ and W classes are completely distinct from each other. Therefore, using our approach one can easily identify whether a given three-qubit state belongs to a GHZ class or W class. Similar to $G_i,i =1,\ldots , 4$ graphs with 8 vertices, graphs with 16 vertices can be produced which will provide the GHZ states with 4-qubits. By similar graphs, we mean graphs with 16 nodes, one edge which connects the ith and $(17-i)$th vertices, $i=1, \ldots , 8$ having edge weight 1. Similarly, one can also obtain the graph for a four-qubit W state.

• 4. Cluster and Chi states: The four-qubit cluster [18] and Chi [19] states are given by $\left| \psi \right\rangle _{1234}=\frac{1}{2}(|0000\rangle ) + |0101\rangle + |1010\rangle - |1111\rangle )$ and $\left| \phi \right\rangle _{1234}=\frac{1}{2}(|0000\rangle ) + |0101\rangle + |1011\rangle - |1110\rangle )$, respectively. The corresponding graphs for these two states are given in Figs. 18 and 19, respectively.The two states are different as evident from the edge weights. Similarly, the density matrices corresponding to Cluster and Chi states are represented by $\sigma (G_{i})=\frac{L_-(G_{i})}{\mathrm {Tr}(L_-(G_{i}))}$ where $\sigma (G_{1})=\left| \psi \right\rangle _{1234} \left\langle \psi \right| _{1234}$, and $\sigma (G_{2})=\left| \phi \right\rangle _{1234} \left\langle \phi \right| _{1234}$.

• 5. Brown State: Consider the graph G with 32 vertices given in Fig. 20. The isolated vertices are not shown in the graph, and the weights of the edges and loops are as given below.

  $$\begin{aligned} w_{ij}=\left\{ \begin{array}{ll} -1, &{} i=1, j=4, 15 \\ 1, &{} i=1, j=14, 21, 24, 26, 27\\ -1, &{} i=4, j=14, 21, 24, 26, 27\\ 1, &{} i=4, j=15 \\ -1, &{} i=14, j=15 \\ 1, &{} i=14, j=21, 24, 26, 27\\ - 1, &{} i=15, j=21, 24, 26, 27 \\ 1, &{} i=21, j=24, 26, 27 \\ 1, &{} i=24, j=26, 27\\ 1, &{} i=26, j=27 \\ -6, &{}i=j, i=1,4, 14,15,21,24,26,27. \end{array} \right. \end{aligned}$$

  (12)

  The graph in Fig. 20 represents a five-qubit Brown state [20], namely

  $$\begin{aligned} \left| \psi \right\rangle ^{12345}= & {} \frac{1}{2\sqrt{2}} \left[ \left| 00000 \right\rangle - \left| 00011 \right\rangle +\left| 01101 \right\rangle -\left| 01110 \right\rangle +\left| 10100 \right\rangle \right. \nonumber \\ \quad+ & {} \left. \left| 10111 \right\rangle +\left| 11001 \right\rangle +\left| 11010\right\rangle \right] \end{aligned}$$

  (13)

  In comparison with other non-equivalent classes of five-qubit entangled states, Brown states are said to be more entangled. The reason is evident from the property that all the bipartitions of Brown states are maximally mixed which is not the case with GHZ, Cluster or Chi type of states. The density matrix associated with the graph for Brown state is

  $$\begin{aligned} \sigma (G)= & {} \frac{1}{\mathrm {Tr}(L_-(G))}L_-(G) = \left| \psi \right\rangle _{12345} \left\langle \psi \right| _{12345}. \end{aligned}$$

• 6. 5-qubit Chi state: The five-qubit Chi state [21] can be represented as

  $$\begin{aligned} \left| \phi \right\rangle _{12345}= & {} \frac{1}{2}\left[ |00000\rangle +|00111\rangle + |01010\rangle - |01101 \rangle - |10011\rangle + |10100\rangle \right. \nonumber \\+ & {} \left. |11001\rangle + |11110\rangle \right] . \end{aligned}$$

  (14)

  The graph and weights of edges for the five-qubit Chi state are given by Fig. 21 and Eq. (14), respectively.

  $$\begin{aligned} w_{ij}=\left\{ \begin{array}{ll} -1, &{} i=1, j=14, 20 \\ 1, &{} i=1, j=8, 11, 21, 26, 31 \\ -1, &{} i=8, j=14, 20 \\ 1, &{} i=8, j= 11, 21 , 26, 31 \\ -1, &{} i=11, j=14,20 \\ 1, &{} i=11, j=21, 26, 31 \\ - 1, &{} i=14, j= 21,26,31 \\ 1, &{} i=14, j=20 \\ -1, &{} i=20, j=21,26, 31\\ 1, &{} i=26, j=31 \\ -6, &{} i=j, i=1,4, 14,15,21,24,26,27. \end{array} \right. \end{aligned}$$

  (15)

  The density matrix, therefore, can be given as $\sigma (G) = \frac{1}{\mathrm {Tr}(L_-(G))}L_-(G) = \left| \phi \right\rangle _{12345} \left\langle \phi \right| _{12345}$. Although the difference between Brown and Chi states can be characterized from the edge weights, for a meaningful classification of such states using a graph theoretical approach, one needs to quantify a graph theoretic measure for entanglement. Such a measure will classify quantum states in different classes and provide deeper physical insight into the complex nature of multiqubit entanglement.

Fig. 13

$G_2$

Fig. 14

$G_3$

Fig. 15

$G_4$

Fig. 16

G

Fig. 17

G

Fig. 18

G

Fig. 19

G

Fig. 20

G

Fig. 21

G

Remark 4

Observe that in the graph representation of entangled pure states mentioned above, all the existing weighted edges are clustered in a completely connected subgraph of the original graph. Further, the weight of the loops attached at each of the vertices of the subgraph is $-(m-2)$ where m is the number of vertices involved in the complete subgraph.

5 Conclusion

We define combinatorial, signless and signed Laplacian matrices associated with a weighted digraph having complex edge weights with or without loops. We determine the connection between the existence of zero Laplacian eigenvalues of a weighted digraph and the topological structure of the graph. Using these Laplacian matrices, we define density matrices corresponding to a weighted digraph. We have classified graphs which represent pure and mixed density matrices of quantum states by using the topological structure of the graphs. In particular, it is observed that for entangled pure states, the weighted edges are clustered in a completely connected subgraph of the original graph. Also, the weight of the loops attached at each of the vertices of the subgraph is $-(m-2)$ where m is the number of vertices involved in the complete subgraph. This work initiates a number of directions to the combinatoric visualization of quantum mechanical phenomena. Some of them are listed below.

• 1. A state is called separable if the density matrix,

  $$\begin{aligned} \rho = \sum _i p_i \rho _i^{(A)} \otimes \rho _i^{(B)}. \end{aligned}$$

  Here, $\rho _i^{(A)}$ and $\rho _i^{(B)}$ denotes density matrix of subsystems A and B, where $\otimes$ denotes a tensor product. We denote tensor product of matrices by $\otimes$. The state is entangled otherwise. We have deduced the graphs for several well-known entangled pure states. We have demonstrated that the three-qubit entangled systems can be classified into GHZ and W class using a graph theoretic approach. A criteria of separability of states represented by the Laplacian of simple graphs has been developed in [8]. A combinatorial operation has also been introduced for density matrices defined by Laplacian matrices associated with simple graphs in [10] that act as an entanglement generator for mixed states arising from partially symmetric graphs. These works introduce new results for the separability of density matrices corresponding to weighted digraphs.

• 2. In order to develop further insight into the entanglement properties of multiqubit systems, it would be interesting to define a graph theoretic measure for quantification and classification of entanglement in such systems. This would allow us to interpret entanglement topologically for this class of states.

• 3. Recently, local unitary transformations on a density matrix obtained by signless Laplacian matrix associated with a simple graph have been established as a combinatorial operation which is known as switching of a graph in [9]. This work sheds further light to the problem of unitary equivalence and state classification for the states related to weighted digraphs.

This work is, we hope, a contribution towards a new direction in the field of quantum information.