arXiv:1407.4041 · Journal of Statistical Mechanics Theory and Experiment

Investigation graph isomorphism problem via entanglement entropy in strongly regular graphs

M. A. Jafarizadeh, F. Eghbalifam, S. Nami

Published Aug 20, 2015• 2 citations

Abstract

We investigate the quantum networks that their nodes are considered as quantum harmonic oscillators. The entanglement of the ground state can be used to quantify the amount of information one part of a network shares with the other part of the system. The networks which we studied in this paper, are called strongly regular graphs (SRG). These kinds of graphs have some special properties like they have three strata in the stratification basis. The Schur complement method is used to calculate the Schmidt numbers and entanglement entropy between two parts of graph. We could obtain analytically, all blocks of adjacency matrix in several scalable sets of strongly regular graphs. Also the entanglement entropy in the large coupling limit is considered in these graphs and the relationship between entanglement entropy and the ratio of size of boundary to size of the system is found. After that, area-law is studied to show that there are no entanglement entropy for the highest size of system. Then, the graph isomorphism problem is considered in SRGs by using the entanglement entropies in some partitioning of graph. Two SRGs with the same parameters: are isomorphic if they can be made identical by relabeling their vertices. So the adjacency matrices of two isomorphic SRGs become identical by replacing of rows and columns. The non-isomorph SRGs could be distinguished by using the elements of blocks of adjacency matrices in the stratification basis, numerically.

DOI: 10.1088/1742-5468/2015/08/p08013

Related papers

Entanglement entropy in the spinless free fermion model and its application to the graph isomorphism problem

M. A. Jafarizadeh, F. Eghbalifam, S. Nami

Abstract In this paper, the entanglement entropy is investigated in the ground state of a spinless free fermion Hamiltonian where its hopping matrix is given by the adjacency matrix of the graph. The bipartite entanglement entropy is calculated from the eigenvalues of the correlation matrix. The entanglement entropy and mutual information are calculated for some scalable graphs including a complete graph and three sets of strongly regular graphs (SRGs). In addition, the volume law scaling has been shown for these graphs. Then, we use the entanglement entropy as a tool for studying the graph isomorphism problem in some non-isomorphic pairs of graphs in order to distinguish them from each other. Two graphs are isomorphic when they are related to each other by relabeling the graph vertices. We study the graph isomorphism in non-isomorphic SRGs, distance-regular graphs and pseudo distance-regular graphs. Most pairs of non-isomorphic SRGs can be distinguished from each other by using fermionic entanglement entropy.

Journal of Physics A Mathematical and TheoreticalJan 19, 20185 citations

Investigating graph isomorphism in cospectral graphs via multiparticle quantum walk in fermionic basis and entanglement entropy

M. A. Jafarizadeh, F. Eghbalifam, S. Nami

We investigate the graph isomorphism (GI) in some cospectral networks. Two graph are isomorphic when they are related to each other by a relabeling of the graph vertices. We want to investigate the GI in two scalable (n + 2)-regular graphs G4(n; n + 2) and G5(n; n + 2), analytically by using the multiparticle quantum walk. These two graphs are a pair of non-isomorphic connected cospectral regular graphs for any positive integer n. In order to investigation GI in these two graphs, we rewrite the adjacency matrices of graphs in the antisymmetric fermionic basis and show that they are different for thesepairs of graphs. So the multiparticle quantum walk is able to distinguish pairs of non- isomorph graphs. Also we construct two new graphs T4(n; n + 2) and T5(n; n + 2) and repeat the same process of G4 and G5 to study the GI problem by using multiparticle quantum walk. Then we study GI by using the entanglement entropy. To this aim, we calculate entanglement entropy between two parts of network. In our model the nodes are considered as identical quantum harmonic oscillators. The entanglement entropy between two special parts of G4(n; n+2) and G5(n; n+2) are calculated analytically. It is shown that the entanglement entropy can distinguish pairs of non-isomorphic cospectral graphs too.

arXiv:1412.1329Dec 3, 20140 citations

Entanglement entropy in the Hamming networks

M. A. Jafarizadeh, S. Nami, Eghbalifam, F.

We investigate the Hamming networks that their nodes are considered as quantum harmonic oscillators. The entanglement of the ground state can be used to quantify the amount of information each part of a network shares with the rest of the system via quantum fluctuations. Therefore, the Schmidt numbers and entanglement entropy between two special parts of Hamming network, can be calculated. To this aim, first we use the stratification method to rewrite the adjacency matrix of the network in the stratification basis. Then the entanglement entropy and Schmidt number for special partitions are calculated analytically by using the generalized Schur complement method. Also, we calculate the entanglement entropy between two arbitrary subsets (two equal subsets have the same number of vertices) in H(2; 3) and H(2; 4) numerically, and we give the minimum and maximum values of entanglement entropy in these two Hamming network.

arXiv:1503.04986Mar 17, 20153 citations

Entanglement entropy in the quantum networks of a coupled quantum harmonic oscillator

M. A. Jafarizadeh, S. Nami, F. Eghbalifam

We investigate the entanglement of the ground state in the quantum networks that their nodes are considered as quantum harmonic oscillators. To this aim, the Schmidt numbers and entanglement entropy between two arbitrary partitions of a network are calculated. In partitioning an arbitrary graph into two parts there are some nodes in each part which are not connected to the nodes of the other part. So, these nodes of each part can be in distinct subsets. Therefore, the graph is separated into four subsets. The nodes of the first and last subsets are those which are not connected to the nodes of the other part. In theorem 1 , by using the generalized Schur complement method in these four subsets, we prove that all the graphs whose connections between the two alternative subsets are complete, have the same entropy. A large number of graphs satisfy this theorem. Then the entanglement entropy in the limit of the large coupling and large size of the system is investigated in these graphs. Also, the asymptotic behaviors of the Schmidt numbers and entanglement entropy in the limit of infinite coupling are shown. One important quantity about partitioning is the conductance of the graph. The conductance of the graph is considered in various graphs. In these graphs we compare the conductance of the graph and the entanglement entropy.

Journal of Statistical Mechanics Theory and ExperimentMay 18, 20152 citations

Entanglement entropy in the Hypercube networks

M. A. Jafarizadeh, F. Eghbalifam, S. Nami

We investigate the hypercube networks that their nodes are considered as quantum harmonic oscillators. The entanglement of the ground state can be used to quantify the amount of information each part of a network shares with the rest of the system via quantum fluctuations. Therefore, the Schmidt numbers and entanglement entropy between two special parts of Hypercube network, can be calculated. To this aim, first we use the stratification method to rewrite the adjacency matrix of the network in the stratification basis which is the matrix representation of the angular momentum. Then the entanglement entropy and Schmidt number for special partitions are calculated an- alytically by using the generalized Schur complement method. Also, we calculate the entanglement entropy between two arbitrary equal subsets (two equal subsets have the same number of vertices) in H(3, 2) and H(4, 2) numerically, and we give the minimum and maximum values of entanglement entropy in these two Hypercube network. Then we can conjecture the minimum and maximum values of entanglement entropy for equal subsets in H(d, 2).

arXiv:1411.0310Nov 2, 20142 citations

Entanglement entropy and Schmidt numbers in quantum networks of coupled quantum oscillator

M. A. Jafarizadeh, S. Nami, F. Eghbalifam

We investigate the entanglement of the ground state in the quantum networks that their nodes are considered as quantum harmonic oscillators. To this aim, the Schmidt numbers and entanglement entropy between two arbitrary partitions of a network, are calculated. In partitioning an arbitrary graph into two parts there are some nodes in each parts which are not connected to the nodes of the other part. So these nodes of each part, can be in distinct subsets. Therefore the graph separates into four subsets. The nodes of the first and last subsets are those which are not connected to the nodes of other part. In theorem I, by using generalized Schur complement method in these four subsets, we prove that all graphs which their connections between all two alternative subsets are complete, have the same entropy. A large number of graphs satisfy this theorem. Then the entanglement entropy in the limit of large coupling and large size of system, is investigated in these graphs. One of important quantities about partitioning, is conductance of graph. The con- ductance of graph is considered in some various graphs. In these graphs we compare the conductance of graph and the entanglement entropy.

arXiv:1407.4044Jul 15, 20140 citations