Quantum discord of states arising from graphs

Abstract

Quantum discord refers to an important aspect of quantum correlations for bipartite quantum systems. In our earlier works, we have shown that corresponding to every graph (combinatorial) there are quantum states whose properties are reflected in the structure of the corresponding graph. Here, we attempt to develop a graph theoretic study of quantum discord that corresponds to a necessary and sufficient condition of zero quantum discord states which says that the blocks of density matrix corresponding to a zero quantum discord state are normal and commute with each other. These blocks have a one-to-one correspondence with some specific subgraphs of the graph which represents the quantum state. We obtain a number of graph theoretic properties representing normality and commutativity of a set of matrices which are indeed arising from the given graph. Utilizing these properties, we define graph theoretic measures for normality and commutativity that results in a formulation of graph theoretic quantum discord. We identify classes of quantum states with zero discord using the developed formulation.

1 Introduction

Graph theory [1] is a well-established branch of mathematics. It has made significant contributions to quantum physics [2] and information theory [3,4,5]. Graphs provide a pictorial representation of quantum states [6]. They have been used to interpret separability property of quantum states [7], and to model useful unitary operations [8]. Quantum correlations [9] are useful resources in quantum information theory [10]. Important facets of quantum correlations are quantum entanglement [11] and quantum discord [12,13,14,15]. Here, we attempt to provide a graph theoretical interpretation of quantum discord.

In quantum mechanics, a density matrix $\rho$ is a positive semidefinite, Hermitian matrix with unit trace, acting on a Hilbert space, say $\mathcal {H}^{(A)}$. A measure of ‘information’ contained in the quantum state $\rho$ is the von Neumann entropy, $S(\rho ) = -{{\mathrm{trace}}}(\rho \log (\rho ))$. A bipartite density matrix acts on a Hilbert space $\mathcal {H}^{(A)} \otimes \mathcal {H}^{(B)}$, where $\otimes$ denotes Kronecker (tensor) product, throughout this article. We denote the reduced density matrix in $\mathcal {H}^{(B)}$ with $\rho _B$. Let $\{|k_B\rangle : k = 1, 2, \ldots \}$ be the standard computational basis of the Hilbert space $\mathcal {H}^{(B)}$. The conditional entropy may be defined with $S(A|\{|k_B\rangle \})$, which is given by $\sum _k p_{k_B} S(\rho _{k_B})$ where $\rho _{k_B} = \frac{1}{p_{k_B}} \langle k_B| \rho |k_B\rangle$, and $p_{k_B} = {{\mathrm{trace}}}_A(\langle k_B| \rho |k_B\rangle )$. Further, conditional entropy may be expressed as $S(\rho ) - S(\rho _B)$. These two quantities are equal for classical systems but differ for quantum systems. Quantum discord is the difference between two classically equivalent faces of mutual information.

Definition 1

(Quantum discord) Given a quantum state $\rho$ acting on a bipartite system $\mathcal {H}^{(A)} \otimes \mathcal {H}^{(B)}$, the quantum discord is defined by [16]

$$\begin{aligned} \mathcal {D}_{\{k_B\}}(\rho ) = S(A|\{|k_B\rangle \}) - \big [S(\rho ) - S(\rho _B)\big ]. \end{aligned}$$

Let $\{\rho ^{(a)}_i\}$ be a set of density matrices in $\mathcal {H}^{(A)}$. Quantum discord is zero for pointer states that may be expressed as,

$$\begin{aligned} \rho = \sum _i p_i \rho ^{(a)}_i \otimes |k_b\rangle \langle k_b|. \end{aligned}$$

(1)

Understanding the nature of zero quantum discord states is an important stepping stone toward understanding quantum discord, in that it acts as preliminary step to distinguish quantum from the classical aspects. It has been used to understand the completely positive evolution of a system [17,18,19], local broadcasting [20, 21]. Thus, finding zero discord quantum states is important in quantum information theory. Corresponding to any graph G, there are quantum states $\rho (G)$, defined below. Here, we present a new combinatorial significance to the pointer states. We study a graph theoretic interpretation of binary, normal and commutating matrices. In this framework, we provide a constructive method to generate at least one quantum state with zero discord in an arbitrary dimensional bipartite system. We come up with an idea of graph theoretic measure of quantum discord applicable for quantum states related to graphs. This article contains a considerable study on combinatorial properties of binary matrices along with their physical significance. A number of important quantum states can be represented with weighted graphs. They require a set of additional criteria. This motivates us to study discord of a larger class of quantum states in a forthcoming work [22].

This article is organized as follows. In Sect. 2, we compile a number of nomenclatures and results from graph theory, which would be of use to us subsequently. We generate density matrices corresponding to combinatorial graphs. The combinatorial properties of normal and commutative matrices are investigated in Sect. 3. These are used to investigate graph theoretic quantum discord in Sect. 4. We also propose a measure of quantum discord in terms of graph theoretic parameters. Section 5 is dedicated to graph theoretic quantum states with zero discord. We then make our conclusions.

2 Preliminaries

In this section, we provide a brief review on simple graphs and describe the quantum states arising from them [5, 6]. A simple graph $G = (V(G), E(G))$ consists of a vertex set V(G) and an edge set $E(G) \subset V(G)\times V(G)$ such that $(i,i)\notin E(G)$ for any $i\in V$ and any edge $(i,j)\in E(G)$ is treated as the same edge $(j,i)\in E(G)$. The number of vertices of G which we denote by $\#(V(G))$ is called the order of G. In this paper, we consider only finite graphs, that is, $\#(V(G))<\infty$. The adjacency matrix of a graph G on N vertices is a symmetric binary matrix, that is, a (0, 1) matrix $A = (a_{ij})_{N \times N}$ defined as [23]

$$\begin{aligned} a_{ij} = {\left\{ \begin{array}{ll} 1 &{}~\text {if }~ (i,j) \in E(G), \\ 0 &{} ~\text {if }~ (i,j) \notin E(G).\end{array}\right. } \end{aligned}$$

(2)

The degree of a vertex i is $d_i = \sum _{j = 1}^N a_{ij}$. The degree matrix of the graph G is given by $D(G) = {{\mathrm{diag}}}\{d_1, d_2, \ldots , d_N\}$, and we define the total degree of G as $d = \sum _{i = 1}^N d_i = {{\mathrm{trace}}}(D)$. The combinatorial Laplacian matrix and the signless Laplacian matrix associated with the graph G are defined by

$$\begin{aligned} L(G) = D(G) - A(G), \,\, Q(G) = D(G) + A(G), \end{aligned}$$

respectively [23, 24]. Note that, ${{\mathrm{trace}}}(L(G)) = {{\mathrm{trace}}}(Q(G)) = d$ and both L(G), Q(G) are symmetric positive semidefinite matrices.

Recall that density matrix representation of a quantum state is described by a Hermitian positive semidefinite matrix with unit trace [10]. Thus, density matrices corresponding to a graph G are defined by

$$\begin{aligned} \rho _l(G) = \frac{1}{d} L(G) ~\text {and}~ \rho _q(G) = \frac{1}{d} Q(G). \end{aligned}$$

(3)

They were introduced in [5, 6] and represent quantum states of dimension N. We denote $\rho _l(G)$ and $\rho _q(G)$ together by $\rho (G)$ when no confusion arises. It is important to note that L(G) and Q(G) depend on the vertex labelings, and hence, different labelings on the vertex set of a graph generate different quantum states [5, 6].

Given a graph G on $N=mn$ vertices, the vertex set V(G) can be partitioned into m classes, say $C_1, C_2, \ldots , C_m$ such that

$$\begin{aligned} \begin{aligned}&V = C_1 \cup C_2 \cup \cdots \cup C_m\\&C_\mu \cap C_\nu = \emptyset ~\text {for}~ \mu \ne \nu ~\text {and}~ \mu , \nu = 1, 2, \ldots , m\\&C_\mu = \{v_{\mu 1}, v_{\mu 2}, \ldots , v_{\mu n}\}. \end{aligned} \end{aligned}$$

(4)

The induced subgraph of G generated by $C_\mu$, that is the graph with vertex set $C_\mu$ and edge set $\{(i,j )\in E(G) : i, j \in C_\mu \}$, is called a cluster in G, and we denote it by $\langle C_\mu \rangle$. We denote the bipartite graph defined by a pair $C_\mu , C_\nu , \mu \ne \nu$ consisting of the edge set $\{(i,j) \in E(G): i \in C_\mu , j\in C_\nu \}$ and vertex set $C_\mu \cup C_\nu$ as $\langle C_\mu , C_\nu \rangle$ which is a subgraph of G representing the edges between the pair of clusters for any $\mu ,\nu =1,\ldots ,m$. Hence, the adjacency matrix associated with G can be represented as the block matrix

$$\begin{aligned} A(G) = \left[ \begin{array}{llll} A_{11} &{}\quad A_{12} &{}\quad \dots &{}\quad A_{1m} \\ A_{21} &{}\quad A_{22} &{}\quad \dots &{}\quad A_{2m} \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \vdots \\ A_{m1} &{}\quad A_{m2} &{}\quad \dots &{}\quad A_{mm}\end{array}\right] _{mn \times mn}, \end{aligned}$$

(5)

where $A_{\mu \mu }$ denotes the adjacency matrix of the cluster $\langle C_\mu \rangle$ and

$$\begin{aligned} \left[ \begin{array}{cc} 0 &{}\quad A_{\mu \nu } \\ A_{\nu \mu } &{}\quad 0\end{array}\right] = \left[ \begin{array}{cc} 0 &{}\quad A_{\mu \nu } \\ A_{\mu \nu }^t &{}\quad 0\end{array}\right] \end{aligned}$$

(6)

denotes the adjacency matrix associated with the bipartite graph $\langle C_\mu ,C_\nu \rangle$ [7].

Consequently, the density matrices corresponding to the graph G are block matrices $\rho (G)=[\rho _{\mu \nu }]$ such that

$$\begin{aligned} \rho _{\mu \nu } = {\left\{ \begin{array}{ll} \dfrac{s}{d}A_{\mu \nu } &{} ~\text {if}~ \mu \ne \nu \\ \\ \dfrac{1}{d}(D_\mu + sA_{\mu \mu }) &{} ~\text {if}~ \mu = \nu \\ \\ \end{array}\right. } \end{aligned}$$

(7)

where $D = {{\mathrm{diag}}}\{D_1, D_2, \ldots , D_m\}, D_\mu$ is a diagonal matrix whose diagonal entries are the degrees of the vertices belonging to $C_\mu$, $s=1$ if $\rho (G)= \rho _q(G)$, and $s=-1$ if $\rho (G)= \rho _l(G)$. Thus, $\rho (G)$ represents quantum states corresponding to a bipartite system of order $m\times n$. Finally, we conclude the section with the following definition which will be used later.

Definition 2

(Edge characteristic function) Given a graph G, the function $\mathcal {X}: V(G) \times V(G) \rightarrow \{0, 1\}$ defined by

$$\begin{aligned} \mathcal {X}(v_{\mu , i},v_{\nu , j}) \equiv \mathcal {X}_{\mu , \nu }(i,j)= {\left\{ \begin{array}{ll} 1 &{} \text {if }~ (v_{\mu , i},v_{\nu , j}) \in E(G), \\ 0 &{} \text {if }~ (v_{\mu , i},v_{\nu , j}) \notin E(G),\end{array}\right. } \end{aligned}$$

for all $\mu ,\nu =1,\ldots ,m$ and $i,j=1,\ldots ,n$ is called an edge characteristic function.

3 Graph theoretic interpretations of normal and commuting matrices

As mentioned earlier, the zero quantum discord states are given by the normal and commuting blocks of the corresponding density matrices [16]. In this section, we determine the structural properties of a graph on mn vertices such that its density matrix has blocks that are normal and commute pairwise. We derive properties of the clusters $\langle C_\mu \rangle$ and the bipartite graphs $\langle C_\mu ,C_\nu \rangle$ such that the matrices $\rho _{\mu \nu }, \mu ,\nu =1,\ldots ,m$ form a set of normal commutating matrices.

First, we discuss some notations and observations regarding graphs generated from a binary matrix. In what follows, given a vector $a=[a_1 \, a_2 \, \ldots a_n]^t\in \{0,1\}^n$, we denote

$$\begin{aligned} \overline{a}=\{i : a_i=1, 1\le i\le n\}. \end{aligned}$$

Hence, given $a,b\in \{0,1\}^n$ we obtain

$$\begin{aligned} a^tb=\#(\overline{a}\cap \overline{b}). \end{aligned}$$

(8)

For a matrix $M = [m_{ij}]\in \{0,1\}^{n \times n}$, we denote $m_{i*}$ and $m_{*j}$ as the ith row and jth column vectors, respectively. Corresponding to every such matrix M, there is a simple bipartite graph $G_M = (V(G_M), E(G_M))$ of order 2n whose adjacency matrix is given by

$$\begin{aligned} A(G_M)=\mathcal {M} = \left[ \begin{array}{ll} 0 &{} M \\ M^t &{} 0 \end{array}\right] . \end{aligned}$$

(9)

We mention that corresponding to any nonnegative matrix, that is, a matrix whose all the entries are nonnegative such a bipartite graph can also be defined, for example, see [25].

Assuming the partitioned vertex sets of $V(G_M)$ as $C_\mu = \{v_{\mu ,1}, v_{\mu ,2}, \ldots , v_{\mu ,n}\}$ and $C_\nu = \{v_{\nu ,1}, v_{\nu ,2}, \ldots , v_{\nu ,n}\}$, note that $(v_{\mu i}, v_{\nu j}) \in E(G_M)$ if and only if $m_{ij} = 1$. Thus, $G_M = \langle C_\mu , C_\nu \rangle$. As $G_M$ is bipartite, the neighborhood of a vertex $v_{\mu i}$ in $G_M$ is given by

$$\begin{aligned} {{\mathrm{nbd}}}_\mathcal {M}(v_{\mu i}) = \{v_{\nu j}: (v_{\mu i}, v_{\nu j}) \in E(G)\}\subseteq C_\nu . \end{aligned}$$

(10)

Similarly, ${{\mathrm{nbd}}}_\mathcal {M}(v_{\nu i}) \subseteq C_\mu$. Now we define a set of numbers for any $v_{\mu i}\in C_\mu$ and $v_{\nu j}\in C_\nu , 1\le \mu ,\nu \le m$ corresponding to the bipartite graph $\langle C_\mu ,C_\nu \rangle$ with the help of (10) as

$$\begin{aligned} {{\mathrm{nbd}}}(v_{\mu i})= & {} \{j : v_{\nu j}\in {{\mathrm{nbd}}}_\mathcal {M}(v_{\mu i}) \} = \overline{m_{i*}^t}, \end{aligned}$$

(11)

$$\begin{aligned} {{\mathrm{nbd}}}(v_{\nu i})= & {} \{j : v_{\mu j}\in {{\mathrm{nbd}}}_\mathcal {M}(v_{\nu i}) \} = \overline{m_{*i}}, \end{aligned}$$

(12)

which are extensively used in the sequel.

Let $0_{1,n}$ and $0_{n,1}$ be the zero row and column vectors. Note that, the ith row of $\mathcal {M}$, that is $[0_{1,n} \, m_{i*}]\in \{0,1\}^{2n}$ depicts edges incident to $v_{\mu i}, 1\le i\le n$, and hence,

$$\begin{aligned} \overline{[0_{1,n} \, m_{i*}]^t} = \overline{m_{i*}^t}= {{\mathrm{nbd}}}_\mathcal {M}(v_{\mu i}). \end{aligned}$$

Similarly, the $(n + i)$th column of $\mathcal {M}$, that is $\left[ \begin{matrix} m_{*i}\\ 0_{n,1}\end{matrix}\right]$ represents the edges incident to $v_{\nu i}$ and thus

$$\begin{aligned} \overline{ \left[ \begin{array}{l} m_{*i}\\ 0_{n,1}\end{array}\right] } = \overline{m_{*i}}= {{\mathrm{nbd}}}_\mathcal {M}(v_{\nu i}). \end{aligned}$$

In particular, any symmetric matrix $M\in \{0,1\}^{n\times n}$ with diagonal entries zero can be considered as an adjacency matrix of a graph G(M). Let $V(G(M)) = C_\mu = \{v_{\mu ,1}, v_{\mu ,2}, \ldots , v_{\mu ,n}\}$. Then, $(v_{\mu ,i}, v_{\mu ,j}) \in E(G(M))$ if and only if $m_{ij} =1$. Thus, $G(M) = \langle C_\mu \rangle$.

We illustrate the above discussion using the following example.

Example 1

Consider the matrix $M = \begin{bmatrix} 0&1&1 \\ 1&0&0 \\ 1&0&0 \end{bmatrix}$. The corresponding bipartite graph, $G_M$ is:

Consider, $m_{*1} = (0, 1, 1)^t$, that is $\overline{m_{*1}} = \{2, 3\}$. Note that, ${{\mathrm{nbd}}}_{\mathcal {A}}(v_{\nu 1}) = \{v_{\mu ,2}, v_{\mu ,3}\}$. Also, M is a symmetric binary matrix with zero diagonal entries. Thus, M is the adjacency matrix of the following graph G(M)

We characterize commutativity of two binary matrices in the following results by using the bipartite graphs introduced above. Next, we also provide a measure of non-commutativity of two binary matrices using these results.

Theorem 1

Let the bipartite graphs corresponding to the matrices $A, B\in \{0,1\}^{n\times n}$ be $G_A = \langle C_\mu , C_\nu \rangle$ and $G_B = \langle C_\alpha , C_\beta \rangle$, respectively. Then, $AB=BA$ if and only if for all i, j with $1 \le i,j \le n$,

$$\begin{aligned} \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) = \#({{\mathrm{nbd}}}(v_{\nu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i})). \end{aligned}$$

Proof

Note that $AB = BA$ holds if and only if $(AB)_{ij} = (BA)_{ij}$ for all i, j with $1 \le i,j \le n$. Now applying Eq. (8) we get,

$$\begin{aligned} (AB)_{ij}= & {} \sum _{k = 1}^n a_{ik}b_{kj} = a_{i*}^t b_{*j} = \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})),\nonumber \\ (BA)_{ij}= & {} \sum _{k = 1}^n b_{ik}a_{kj} = b_{i*}^t a_{*j} = \#({{\mathrm{nbd}}}(v_{\nu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i})). \end{aligned}$$

(13)

Hence, the desired result follows. $\square$

Obviously if $AB\ne BA$ the corresponding condition on graphs do not hold. The non-commutativity of A and B is captured in $E(G_A)$, and $E(G_B)$. Hence, we introduce the following quantity as a measure of non-commutativity of any two matrices $A, B\in \{0,1\}^{n\times n}$.

$$\begin{aligned} \mathcal {NC}_1(A,B) = \sum _{i,j} \big | \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) - \#({{\mathrm{nbd}}}(v_{\nu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i}))\big |. \end{aligned}$$

(14)

Corollary 1

Let $A=[a_{ij}]\in \{0,1\}^{n\times n}$ be a symmetric matrix with diagonal entries zero and $B=[b_{ij}]\in \{0,1\}^{n\times n}$. Assume that $G(A) = \langle C_\mu \rangle$ and $G_B = \langle C_\alpha , C_\beta \rangle$ are the graphs corresponding to A and B, respectively. Then, $AB=BA$ if and only if for all i, j with $1 \le i,j \le n$,

$$\begin{aligned} \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) = \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i})). \end{aligned}$$

Proof

We have already justified that, $\overline{a_{i*}^t} = {{\mathrm{nbd}}}(v_{\mu i}) = \overline{a_{*i}}$, for all $i = 1, 2, \ldots , n$. Further $AB=BA$ if and only if $a_{i*}^t b_{*j} = b_{i*}^t a_{*j}$ for all i, j. Applying the symmetry of A, we obtain $a_{i*}^t b_{*j} = a_{j*}^t b_{i*}$. Using the graph theoretic convention $\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) = \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i}))$. $\square$

When such matrices A, B in the above corollary do not commute, we denote

$$\begin{aligned} \mathcal {N}\mathcal {C}_2(A,B)_{ij} = \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i})), \end{aligned}$$

(15)

and define a measure of non-commutativity of the pair of matrices A, B as

$$\begin{aligned} \mathcal {N}\mathcal {C}_2(A,B) = \sum _{i,j} \big | \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i}))\big |. \end{aligned}$$

(16)

Corollary 2

Let $A=[a_{ij}], B=[b_{ij}]\in \{0,1\}^{n\times n}$ be symmetric matrices with zero diagonal entries. Suppose $G(A) = \langle C_\mu \rangle$ and $G(B) = \langle C_\nu \rangle$. Then, $AB=BA$ if and only if for every i, j with $1 \le i, j \le n$,

$$\begin{aligned} \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})) = \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\nu i})). \end{aligned}$$

Proof

The proof follows from the above corollary by setting $\alpha = \beta = \nu$. $\square$

Thus, given two symmetric binary matrices with diagonal entries zero we denote

$$\begin{aligned} \mathcal {N}\mathcal {C}_3(A,B)_{ij} = \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\nu i})), \end{aligned}$$

(17)

and define a measure of non-commutativity of A and B as

$$\begin{aligned} \mathcal {N}\mathcal {C}_3(A,B) = \sum _{i,j} \big |\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\nu i}))\big |. \end{aligned}$$

(18)

Now we provide graph theoretic interpretation of normality of a binary matrix as follows.

Theorem 2

Let $A=[a_{ij}]\in \{0,1\}^{n\times n}$ and $G_A = \langle C_\mu , C_{\nu } \rangle$ be the bipartite graph corresponding to A. Then, A is normal, that is, $AA^t=A^tA$ if and only if for every i and j with $1 \le i, j \le n$,

$$\begin{aligned} \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\mu j})) = \#({{\mathrm{nbd}}}(v_{\nu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})). \end{aligned}$$

Proof

Let $B = (b_{ij})_{n \times n} = (a_{ji})_{n \times n} = A^t$. Clearly, $b_{i*} = a_{*i}$ and $b_{*i} = a_{i*}$ for all i. Note that,

$$\begin{aligned} (AA^t)_{ij} = \sum _{k = 1}^n a_{ik}b_{kj} = a_{i*}^t b_{*j} = a_{i*}^t a_{j*} = \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\mu j})). \end{aligned}$$

(19)

Similarly, $(A^tA)_{ij} = \#({{\mathrm{nbd}}}(v_{\nu i}) \cap {{\mathrm{nbd}}}(v_{\nu j}))$. Hence, for any two i, and j with $1 \le i,j \le n$ we have, $\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\mu j})) = \#({{\mathrm{nbd}}}(v_{\nu i}) \cap {{\mathrm{nbd}}}(v_{\nu j}))$. $\square$

When $A\in \{0,1\}^{n\times n}$ is not a normal matrix we define its non-normality in terms of the edges in $G_A$ by the following quantity:

$$\begin{aligned} \mathcal {NN}(A) = \sum _{i,j} |\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\mu j})) - \#({{\mathrm{nbd}}}(v_{\nu i}) \cap {{\mathrm{nbd}}}(v_{\nu j}))|. \end{aligned}$$

(20)

4 Quantum discord of states corresponding to graphs

We first recall the clusters for a given graph G on $m \times n$ vertices that are mentioned in Eq. (4). Note that any such simple graph G can be partitioned into edge-disjoint subgraphs $\langle C_\mu \rangle$ and $\langle C_\mu , C_\nu \rangle$, $1 \le \mu , \nu \le m$, and properties of these subgraphs determine some properties of G. In order to determine the zero quantum discord states which arise from G, the blocks of $\rho (G)=[\rho _{\mu \nu }]$ must satisfy the following conditions:

$$\begin{aligned} \rho _{\mu \mu }^t\rho _{\mu \mu }= & {} \rho _{\mu \mu }\rho _{\mu \mu }^t ,\end{aligned}$$

(21)

$$\begin{aligned} \rho _{\mu \nu }^t\rho _{\mu \nu }= & {} \rho _{\mu \nu }\rho _{\mu \nu }^t, \mu \ne \nu \end{aligned}$$

(22)

$$\begin{aligned} \rho _{\mu \nu }\rho _{\alpha \beta }= & {} \rho _{\alpha \beta }\rho _{\mu \nu }, \mu \ne \nu , \alpha \ne \beta , (\mu ,\nu )\ne (\alpha ,\beta ) \end{aligned}$$

(23)

$$\begin{aligned} \rho _{\mu \mu }\rho _{\alpha \beta }= & {} \rho _{\alpha \beta }\rho _{\mu \mu }, \alpha \ne \beta \end{aligned}$$

(24)

$$\begin{aligned} \rho _{\mu \mu }\rho _{\nu \nu }= & {} \rho _{\nu \nu }\rho _{\mu \mu }, \end{aligned}$$

(25)

where $\rho _{\mu \mu }=D_\mu + A_{\mu \mu }$ if $\rho (G)=\rho _l(G)$, $\rho _{\mu \mu }=D_\mu - A_{\mu \mu }$ if $\rho (G)=\rho _s(G)$, $\rho _{\mu \nu }=A_{\mu \nu }, \mu \ne \nu$, and $A_{\mu \mu }, A_{\mu \nu }$ are described in Eqs. (5) and (6). Thus, the quantum states $\rho (G)$ arising from a graph G must satisfy the conditions (21)–(25) to represent a state with zero quantum discord. It is needless to mention that the structural properties of the clusters and the edges between the clusters determine the same.

Observe that the condition (21) satisfies trivially for any graph G since the matrix $A_{\mu \mu }$ represents a symmetric adjacency matrix associated with the cluster $\langle C_\mu \rangle$. Also, $D_\mu$ is a diagonal matrix. The condition (22) is satisfied by G if all the bipartite graphs $\langle C_\mu , C_\nu \rangle$ meet the normality condition given in Theorem 2. If there are some block matrices $\rho _{\mu \nu }$ which are not normal, hence violate (22), the amount of non-normality can be measured by using formula (20) considering all pairs of $\mu , \nu$ such that $\mu \ne \nu$. Thus, the quantity

$$\begin{aligned} \sum _{\mu \ne \nu } \mathcal {NN}(A_{\mu \nu }) \end{aligned}$$

(26)

measures the violation of (22).

The condition (23) is satisfied if all the pair of bipartite graphs $\langle C_\mu , C_\nu \rangle$, and $\langle C_\alpha , C_\beta \rangle , 1\le \mu ,\nu ,\alpha ,\beta \le m, \mu \ne \nu , \alpha \ne \beta , (\mu ,\nu )\ne (\alpha ,\beta )$ satisfy Theorem 1. If the condition gets violated, the amount of non-commutativity defined in (14) can be used to measure the violation of condition (23) due to all pairs of $A_{\mu \nu }, A_{\alpha \beta }$ as

$$\begin{aligned} \sum _{\mu \ne \nu , \alpha \ne \beta }\mathcal {NC}_1(A_{\mu \nu }, A_{\alpha \beta }). \end{aligned}$$

(27)

Note that, the condition (24) deals with the commutativity between $\rho _{\mu \mu }$ and $\rho _{\alpha \beta }, \alpha \ne \beta$, that is, the graph G will satisfy $\rho _{\mu \mu } \rho _{\alpha \beta } = \rho _{\alpha \beta } \rho _{\mu \mu }, 1\le \mu ,\alpha ,\beta \le m$. Thus,

$$\begin{aligned} \begin{aligned}&\frac{1}{d}(D_{\mu } +s A_{\mu \mu })\frac{s}{d}A_{\alpha \beta } = \frac{s}{d}A_{\alpha \beta } \frac{1}{d}(D_{\mu } +s A_{\mu \mu })\\&\quad \Rightarrow ~ D_{\mu }A_{\alpha \beta } +s A_{\mu \mu }A_{\alpha \beta } = A_{\alpha \beta }D_{\mu } +s A_{\alpha \beta }A_{\mu \mu }, \end{aligned} \end{aligned}$$

(28)

where $s=1$ if $\rho (G)=\rho _l(G)$ and $s=-1$ if $\rho (G)=\rho _s(G)$. Rearranging the terms, we obtain

$$\begin{aligned} (D_{\mu }A_{\alpha \beta } - A_{\alpha \beta }D_{\mu }) + s (A_{\mu \mu }A_{\alpha \beta } - A_{\alpha \beta }A_{\mu \mu }) = 0. \end{aligned}$$

(29)

Recall that $D_\mu$ represents the diagonal matrix having the diagonal entries as the degrees of the vertices belong to $C_\mu$ and $A_{\mu \mu }$ is the adjacency matrix of the cluster $\langle C_\mu \rangle$. Besides, $A_{\alpha \beta }$ corresponds to the bipartite graph $\langle C_\alpha , C_\beta \rangle$. Thus, the above equation holds if for all i, j with $1 \le i,j \le n$

$$\begin{aligned} \begin{aligned}&(D_{\mu }A_{\alpha \beta })_{ij} - (A_{\alpha \beta }D_{\mu })_{ij} + s \{ (A_{\mu \mu }A_{\alpha \beta })_{ij} - (A_{\alpha \beta }A_{\mu \mu })_{ij} \} = 0\\&\quad \Rightarrow ~ d_{\mu i}(A_{\alpha \beta })_{ij} - (A_{\alpha \beta })_{ij}d_{\mu j} + s \{ (A_{\mu \mu }A_{\alpha \beta })_{ij} - (A_{\alpha \beta }A_{\mu \mu })_{ij} \} = 0. \end{aligned} \end{aligned}$$

(30)

Further, $(A_{\alpha \beta })_{ij}$ is either 0 or 1 depending on the existence of the edge $(v_{\alpha i}, v_{\beta j})$ in G. Thus, the graph G satisfies condition (24) if

$$\begin{aligned} \mathcal {X}_{\alpha \beta }(i,j)(d_{\mu i} - d_{\mu j}) + s (\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\beta j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\alpha i})))= 0\nonumber \\ \end{aligned}$$

(31)

as follows from Corollary 1 for all $1\le \mu ,\alpha ,\beta \le m, \alpha \ne \beta$, where $\mathcal {X}_{\alpha \beta }$ denotes the edge characteristic function defined in Definition 2. Moreover, the violation of the condition (24) can be represented by

$$\begin{aligned} \sum _{\mu ,\alpha \ne \beta } \sum _{i,j} \big |\mathcal {X}_{\alpha \beta }(i,j)(d_{\mu i} - d_{\mu j}) +s\mathcal {NC}_2(A_{\mu \mu }, A_{\alpha \beta })_{ij}\big | \end{aligned}$$

(32)

where $\mathcal {NC}_2(A_{\mu \mu }, A_{\alpha \beta })_{ij}$ is given by Eq. (15), $s=1$ if $\rho (G)=\rho _l(G)$ and $s=-1$ if $\rho (G)=\rho _s(G)$.

Finally, the condition (25) holds if $\rho _{\mu \mu }\rho _{\nu \nu } = \rho _{\nu \nu }\rho _{\mu \mu }$ which implies that

$$\begin{aligned} \begin{aligned}&\frac{1}{d}(D_\mu +s A_{\mu \mu }) \frac{1}{d}(D_\nu +s A_{\nu \nu }) = \frac{1}{d}(D_\nu +s A_{\nu \nu }) \frac{1}{d}(D_\mu +s A_{\mu \mu })\\&\quad \Rightarrow D_\mu D_\nu +s D_\mu A_{\nu \nu } +s A_{\mu \mu }D_\nu + A_{\mu \mu }A_{\nu \nu } \\&\qquad = D_\nu D_\mu +s D_\nu A_{\mu \mu } +s A_{\nu \nu }D_\mu + A_{\nu \nu }A_{\mu \mu }\\&\quad \Rightarrow (A_{\mu \mu }A_{\nu \nu } - A_{\nu \nu }A_{\mu \mu }) +s (D_\mu A_{\nu \nu } - A_{\nu \nu }D_\mu ) +s (A_{\mu \mu }D_\nu - D_\nu A_{\mu \mu }) = 0\\&\quad \Rightarrow (A_{\mu \mu }A_{\nu \nu } - A_{\nu \nu }A_{\mu \mu })_{ij} +s (D_\mu A_{\nu \nu } - A_{\nu \nu }D_\mu )_{ij} +s (A_{\mu \mu }D_\nu - D_\nu A_{\mu \mu })_{ij} = 0, \end{aligned} \end{aligned}$$

(33)

holds for all $1 \le i,j \le n$. Note that, $A_{\mu \mu }$ and $A_{\nu \nu }$ represent the adjacency matrices corresponding to the clusters $\langle C_\mu \rangle$ and $\langle C_\nu \rangle$, respectively, and commutativity of such matrices has been discussed in Corollary 2. Note that,

$$\begin{aligned} (D_\mu A_{\nu \nu } - A_{\nu \nu }D_\mu )_{ij} = d_{\mu i}(A_{\nu \nu })_{ij} - (A_{\nu \nu })_{ij} d_{\mu j} = \mathcal {X}_{\nu \nu }(i,j)(d_{\mu i} - d_{\mu j}) \end{aligned}$$

(34)

$$\begin{aligned} (A_{\mu \mu }D_\nu - D_\nu A_{\mu \mu })_{ij} = (A_{\mu \mu })_{ij}d_{\nu j} - d_{\nu i}(A_{\nu \nu })_{ij} = \mathcal {X}_{\mu \mu }(i,j)(d_{\nu j} - d_{\nu i}) \end{aligned}$$

(35)

which follows from the definition of the edge characteristic function $\mathcal {X}$, and

$$\begin{aligned} (A_{\mu \mu }A_{\nu \nu } - A_{\nu \nu }A_{\mu \mu })_{ij} = \#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\nu i})). \end{aligned}$$

(36)

Combining Eqs. (34)–(36), we obtain

$$\begin{aligned} \begin{aligned}&\big [\#({{\mathrm{nbd}}}(v_{\mu i}) \cap {{\mathrm{nbd}}}(v_{\nu j})) - \#({{\mathrm{nbd}}}(v_{\mu j}) \cap {{\mathrm{nbd}}}(v_{\nu i})) \big ] \\&\quad +s \big [\mathcal {X}_{\nu \nu }(i,j)(d_{\mu i} - d_{\mu j})\big ] +s \big [\mathcal {X}_{\mu \mu }(i,j)(d_{\nu j} - d_{\nu i})\big ] = 0 \end{aligned} \end{aligned}$$

(37)

which must be satisfied for all $1\le i,j\le n$ in order to satisfy condition (25).

Further, observe that if the vertices belong to $C_\mu , \mu = 1, 2, \ldots , m$ have equal degree, then $d_{\mu i} - d_{\mu j} = 0$ as well as $d_{\nu j} - d_{\nu i} = 0$. Then, G satisfies condition (25) if and only if for any two subgraphs $\langle C_\mu \rangle$ and $\langle C_\nu \rangle$, conditions of Corollary 2 is fulfilled. Thus, a measure of violation of the (25) can be defined by

$$\begin{aligned} \sum _{\mu \ne \nu } \sum _{i,j} \big | \mathcal {NC}_3 (A_{\mu \mu }, A_{\nu \nu })_{ij} + s \big [\mathcal {X}_{\nu \nu }(i,j)(d_{\mu i} - d_{\mu j}) + \mathcal {X}_{\mu \mu }(i,j)(d_{\nu j} - d_{\nu i})\big ] \big |, \end{aligned}$$

(38)

where $\mathcal {NC}_3 (A_{\mu \mu }, A_{\nu \nu })_{ij}$ is given by (17), $s=1$ if $\rho (G)=\rho _l(G)$ and $s=-1$ if $\rho (G)=\rho _s(G)$.

Based on the discussions above, it is obvious that given a graph G on $m \times n$ vertices with a labeling on the vertices and clusters $\langle C_\mu \rangle , 1\le \mu \le m$ a notion of quantum discord for the quantum states $\rho (G)$ can be defined by using Eqs. (26), (27), (32) and (38). This definition of quantum discord would then be philosophically different compared to the existing measures of quantum discord, for example see [26], as it depends on the structural properties of the clusters in the graph. Thus, we introduce the following definition of quantum discord for states arising from a graph.

Definition 3

(Graph theoretic quantum discord) Let G be a graph on $m \times n$ vertices and $\langle C_\mu \rangle , C_\mu =\{v_{\mu i} : 1\le i\le n\}, 1\le \mu \le m$ be the clusters in G. Then, the quantum discord of the states $\rho (G)=\frac{1}{d}[D(G)+sA(G)], s\in \{1,-1\}$ is given by

$$\begin{aligned} \begin{aligned} \mathcal {QD}(G)&= \sum _{\mu \ne \nu } \mathcal {NN}(A_{\mu \nu }) + \sum _{\mu \ne \nu } \mathcal {NN}(A_{\mu \nu }) \\&\quad + \sum _{\mu ,\alpha \ne \beta } \sum _{i,j} \big |\mathcal {X}_{\alpha \beta }(i,j)(d_{\mu i} - d_{\mu j}) +s\mathcal {NC}_2(A_{\mu \mu }, A_{\alpha \beta })_{ij}\big | \\&\quad + \sum _{\mu \ne \nu } \sum _{i,j} \big | \mathcal {NC}_3 (A_{\mu \mu }, A_{\nu \nu })_{ij} \\&\quad +s \big [\mathcal {X}_{\nu \nu }(i,j)(d_{\mu i} - d_{\mu j}) + \mathcal {X}_{\mu \mu }(i,j)(d_{\nu j} - d_{\nu i})\big ] \big |, \end{aligned} \end{aligned}$$

where $1\le \nu \le m$, $1\le j\le n$, $A(G)=[A_{\mu \nu }], d_{\mu i}$ is the degree of $v_{\mu i}$, and d is the total degree of G.

We mention that different labelings on the vertices of the same graph G can produce different states with different quantum discord. The definition helps to generate zero quantum discord states defined by graphs. Indeed, a procedure to create such states with a given dimension $m\times n$ would be to define the edges of the graph such that the quantities defined in Eqs. (26), (27), (32) and (38) become zero.

Now we discuss whether $\mathcal {QD}(G)$ is a valid measure of quantum correlation for bipartite states represented by the density matrices $\rho (G)$ of order mn. First we recall that a general measure $\mathcal {M}$ of quantum correlation is expected to possess the following properties [27].

• 1. $\mathcal {M}$ is nonnegative.

• 2. $\mathcal {M}$ is zero for classically correlated states.

• 3. $\mathcal {M}$ in invariant under local unitary transformation.

Setting $\mathcal {M}(\rho (G))=\mathcal {QD}(G)$ for any graph G on mn vertices, we have the following observations. First note that $\mathcal {QD}(G)\ge 0$ by default. Further, by definition of $\mathcal {QD}(G)$ it is zero for classically correlated states with zero quantum discord. Finally, a general picture of graph theoretic analogue of local unitary transformations on $\rho (G)$ is not yet known, see [8]. In fact, it is a hard problem to characterize local unitary operations which transform a given $\rho (G)$ in to an another state $\rho (H)$ for some other graph H. However, we show in the next theorem that $\mathcal {QD}(G)$ is a promising measure for quantum correlation as it is invariant under local unitary operators of the form $P_1\otimes P_2$, where $P_i$, $i=1,2$ are permutation matrices, which are special unitary matrices.

Let the permutation matrices $P_1$ and $P_2$ act on the Hilbert spaces $\mathcal {H}^{(A)}$, and $\mathcal {H}^{(B)}$, respectively. Hence, $P_1 \otimes P_2 = (P_1 \otimes I)(I \otimes P_2)$ is a local unitary operator acting on $\mathcal {H}^{(A)} \otimes \mathcal {H}^{(B)}$. Then, we have the following theorem:

Theorem 3

Let $P_2$ be a permutation matrix acting on the Hilbart space $\mathcal {H}^{(B)}$. Let $\rho (G)$ be a quantum state with zero discord in the bipartite system $\mathcal {H}^{(A)} \otimes \mathcal {H}^{(B)}$. Consider a graph H, such that, $A(H) = (I \otimes P_2)^t A(G) (I \otimes P_2)$. Then, $\rho (H)$ and $\rho (G)$ have equal quantum discord.

Proof

Note that,

$$\begin{aligned} \begin{aligned}&(I \otimes P_2)^t \rho (G) (I \otimes P_2) \\&\quad = (I \otimes P_2^t) \frac{1}{d}\begin{bmatrix} D_1 +s A_{11}&s A_{12}&\dots&s A_{1m} \\ s A_{21}&D_2 +s A_{22}&\dots&s A_{2m} \\ \vdots&\vdots&\ddots&\vdots \\ s A_{m1}&s A_{m2}&\dots&D_m +s A_{mm}\end{bmatrix}(I \otimes P_2) \\&\quad = \frac{1}{d}\begin{bmatrix} P_2^t(D_1 +s A_{11})P_2&s P_2^tA_{12}P_2&\dots&s P_2^tA_{1m}P_2 \\ s P_2^t A_{21} P_2&P_2^t (D_2 +s A_{22}) P_2&\dots&s P_2^t A_{2m} P_2 \\ \vdots&\vdots&\ddots&\vdots \\ s P_2^t A_{m1} P_2&s P_2^t A_{m2} P_2&\dots&P_2^t (D_m +s A_{mm}) P_2 \end{bmatrix}. \end{aligned} \end{aligned}$$

Recall the subgraphs $\langle C_\mu \rangle$ and $\langle C_\mu , C_\nu \rangle$ in G and the fact that graph isomorphisms are represented by permutation matrices. Hence, the above equation can be interpreted as a graph isomorphism operation. The adjacency matrices of the new subgraphs corresponding to $\langle C_\mu \rangle$ and $\langle C_\mu , C_\nu \rangle$ are given by $P_2^t A_{\mu \mu } P_2$, and $\begin{bmatrix} 0&P_2^t A_{\mu \nu }P_2 \\ P_2^t A^t_{\mu \nu }P_2&0 \end{bmatrix}$, respectively. Note that, the permutation matrix $P_2$ does not switch one vertex of $C_\mu$ to another vertex of $C_\nu$ when $\mu \ne \nu$ but only changes the labeling of vertices of $C\mu , 1\le \mu \le m$. Thus, the normality and commutativity conditions hold as earlier in the new graph. Thus, $\rho (H)$ and $\rho (G)$ have equal quantum discord. $\square$

The Werner state [28] is a class of quantum states, important in quantum information processing. A Werner state is represented by,

$$\begin{aligned} \rho _{x,d} = \frac{d - x}{d^3 - d}I + \frac{xd - 1}{d^3 - d}F, \end{aligned}$$

(39)

where $F = \sum _{i,j}^d |i\rangle \langle j| \otimes |j\rangle \langle i|$, $x \in [0, 1]$ and d is the dimension of the individual subsystems. Note that, $\rho _{x,d}$ is a symmetric matrix of order $d^2$. It can be shown that these states have nonzero quantum discord even though some of them are separable [29].

Example 2

We may represent $\rho _{1,3}$, and $\rho _{1,4}$ as a simple graph having 9 and 16 vertices in Fig. 1.

Fig. 1

Graphs of the Werner states. a Graph for $\rho _{1,3}$, b graph for $\rho _{1,4}$

Theorem 4

Every Werner state has nonzero discord.

Proof

Consider the subgraph $\langle C_\mu , C_\nu \rangle$ for any $\mu$ and $\nu$, with $\mu \ne \nu$. Using lemma 2, we may conclude that $A_{\mu , \nu }$ is not a normal matrix. Thus, every Werner state has a nonzero discord. $\square$

A detailed study of quantum discord of states represented with weighted graphs will be presented in an upcoming work [22].

5 Graph theoretic zero quantum discord states

As discussed above, we can generate zero quantum discord bipartite states of dimension $m\times n$ arising from graphs for any m, n by generating graphs G for which $\mathcal {QD}(G)=0$. In fact states arising from a graph G have zero quantum discord if and only if $\mathcal {QD}(G)=0$. In this section we determine certain standard graphs which have always zero quantum discord for any labeling on the vertices.

First we have the following theorem for complete graphs on $N=mn$ vertices which are graphs in which any pair of distinct vertices are adjacent.

Theorem 5

Let G be a complete graph on $N=mn$ vertices. Then, the states $\rho (G)$ have zero quantum discord, that is, $\mathcal {QD}(G)=0$.

Proof

As G is a complete graph, degree of every vertex is $N -1$. Thus, total degree of G is $d = N(N - 1)$. Then, the blocks of $\rho (G)$ are given by

$$\begin{aligned} \rho _{\mu \nu } = {\left\{ \begin{array}{ll} \frac{\pm 1}{d}A_{\mu \mu } = \frac{1}{d}\left[ (N - 1) I_n + J_n - I_n\right] = \frac{1}{d}[(N - 2)I_n + J_n] &{} ~\text {for}~ \mu = \nu \\ \frac{\pm 1}{d}A_{\mu \nu } = \frac{\pm 1}{d}J_n &{} ~\text {for}~ \mu \ne \nu \end{array}\right. } \end{aligned}$$

(40)

where $1\le \mu ,\nu \le m$ and $J_n$ is the all-one matrix of order n. Note that, all the blocks $\rho _{\mu \nu }$ are normal and commute pairwise. Hence, the desired result follows. $\square$

We conclude from Theorem 5 that for any m and n there is a graph G of order mn for which the corresponding bipartite states of dimension $m\times n$ have zero quantum discord. In the next theorem, we prove that given any n, the complete bipartite graphs G on 2n vertices, that is, G consist of two clusters $\langle C_\mu \rangle , \mu =1,2$ with n vertices such that no two vertices of $C_\mu$ for a fixed $\mu$ are adjacent and all pairs of vertices $u\in C_1, v\in C_2$, $(u, v)\in E(G)$ provide zero quantum discord bipartite states $\rho (G)$ of dimension $2\times n$.

Theorem 6

Let G be a complete bipartite graph on 2n vertices with two clusters, each on n vertices. Then, $\mathcal {QD}(G)=0$, that is, $\rho (G)$ have zero quantum discord.

Proof

Let $C_1 = \{v_{1,1}, v_{1,2}, \ldots , v_{1,n}\}$, $C_2 = \{v_{2,1}, v_{2,2}, \ldots , v_{2,n}\}$ be the bipartition of G. Then,

$$\begin{aligned} \rho (G) = \frac{1}{2n}\left[ \begin{array}{ll} nI_n &{}\quad s J_n \\ s J_n &{}\quad nI_n \end{array}\right] . \end{aligned}$$

It is easy to verify that all the block matrices commute with each other and they are normal matrices. Hence, $\mathcal {QD}(G)=0$. $\square$

Next, we provide an example of two isomorphic graphs such that for one, the corresponding bipartite states have zero quantum discord and for the other, the corresponding states have nonzero quantum discord. Thus, the following example establishes that quantum discord is not invariant under graph isomorphism, hence depends on labeling of the vertices.

Example 3

In Fig. 2, there are two isomorphic complete bipartite graphs G and H with vertex set $V = \{1,2,3,4,5,6\}$. It consists of two clusters $C_1 = \{1,2,3\}$ and $C_2 = \{4,5,6\}$. A simple calculation shows that $\mathcal {QD}(H)\ne 0$ and from Theorem 6, $\mathcal {QD}(G)=0$. It is interesting to observe that H is a 3-regular graph which confirms that regular graphs need not represent states with zero quantum discord.

Fig. 2

Isomorphic complete bipartite graphs with different quantum discords

Now we consider partially symmetric graphs which were introduced in [7] and show that states corresponding to bipartite partially symmetric regular graphs have always zero quantum discord. First, we recall the following definition from [7].

Definition 4

(Partially symmetric graph) A graph G with clusters $C_1, C_2, \ldots , C_m$ is called a partially symmetric graph if the edge $(v_{\mu i}, v_{\nu j}) \in E(G)$ indicates $(v_{\nu i}, v_{\mu j}) \in E(G)$.

Note from the definition that every block of the adjacency matrix of a partially symmetric graph is a symmetric matrix. Then, we have the following theorem.

Theorem 7

Every bipartite partially symmetric regular graph has zero quantum discord.

Proof

Let G be a partially symmetric regular bipartite graph. Then,

$$\begin{aligned} \rho (G) = \left[ \begin{array}{ll} rI_n &{}\quad s A_n \\ s A_n &{}\quad rI_n \end{array}\right] , \end{aligned}$$

where r is the regularity of the graph and $s\in \{1,-1\}$. Since $A_n$ is a symmetric matrix, it is normal. Besides, all these block matrices commute with each other. Hence, $\mathcal {QD}(G)=0$. $\square$

Theorem 8

Let $G = \langle C_\mu , C_\nu \rangle$ be a regular graph satisfying the condition of Theorem 2. Then, the states $\rho (G)$ have zero quantum discord.

Proof

The proof is similar to the last theorem. Here the matrix $A_n$ is a normal matrix instead of symmetric matrix. Indeed the quantum states corresponding to G are given by

$$\begin{aligned} \rho (G) = \frac{1}{2nr}\left[ \begin{array}{ll} rI_n &{}\quad s A_n \\ s A^t_n &{}\quad rI_n \end{array}\right] = \frac{1}{2n}\left[ \begin{array}{cc} I_n &{}\quad s \frac{1}{r} A_n \\ s \frac{1}{r} A^t_n &{}\quad I_n \end{array}\right] , \end{aligned}$$

(41)

where $s \in \{1,-1\}$. $\square$

Consider the matrix $\begin{bmatrix} rI_n&A_n \\ A^t_n&rI_n \end{bmatrix}$ in the above equation by putting $s = 1$. Every row and column has equal sum 2r. The matrix $\frac{1}{2r}\begin{bmatrix} rI_n&A_n \\ A^t_n&rI_n \end{bmatrix}$ is an example of a doubly stochastic matrix. Doubly stochastic matrices are widely used in different branches of science [30].

Finally, as it is well known that there are separable quantum states with nonzero quantum discord, in the following example we confirm the same also for the states arising from graphs.

Example 4

Consider the bipartite partially symmetric graph G representing a separable two-qubit mixed state.

Note that $\begin{bmatrix} 2&0 \\ 0&1\end{bmatrix}$ and $\begin{bmatrix} -1&-1 \\ -1&0\end{bmatrix}$ do not commute, hence $\mathcal {QD}(G)\ne 0$ although $\rho (G)=\dfrac{1}{5}L(G)$ represents a 2-qubit separable state.

6 Conclusions and open problems

This work is important from the perspective of mathematics and theoretical quantum information. Calculating the exact amount of quantum discord is a computationally formidable task [31]. Here, we derive graph theoretic criteria for normality and commutativity of binary matrices. The blocks of a density matrix of a zero discord state are normal and commuting. We apply combinatorial tools to find out graph theoretic criterion for zero quantum discord. Further, we propose a graph theoretic measure of discord. This work initiates a number of directions for future research.

• 1. Given a positive integer n, calculate the exact number of binary normal matrices. There is no general formula for this problem till date, although some lower bound exists. This work provides a graph theoretic visualization to the structure of binary normal matrices, which may be useful for solving this problem.

• 2. The Werner states play an important role in quantum information theory. It was proved in [29] that they have nonzero quantum discord. These states can be represented by weighted graphs and will be considered in a forthcoming work.