Quantum social networks

Quantum social networks Ad´an Cabello1,2, Lars Eirik Danielsen3, Antonio J L´opez-Tarrida1 and Jos´e R Portillo4 1 Departamento de F´ısica Aplicada II, Universidad de Sevilla, E-41012 Sevilla, Spain 2 Department of Physics, Stockholm University, S-10691 Stockholm, Sweden 3 Department of Informatics, University of Bergen, PO Box 7803, N-5020 Bergen, Norway 4 Departamento de Matem´atica Aplicada I, Universidad de Sevilla, E-41012 Sevilla, Spain E-mail: [email protected] Abstract We introduce a physical approach to social networks (SNs) in which each actor is characterized by a yes–no test on a physical system. This allows us to consider SNs beyond those originated by interactions based on pre-existing properties, as in a classical SN (CSN). As an example of SNs beyond CSNs, we introduce quantum SNs (QSNs) in which actor i is characterized by a test of whether or not the system is in a quantum state |ψi. We show that QSNs outperform CSNs for a certain task and some graphs. We identify the simplest of these graphs and show that graphs in which QSNs outperform CSNs are increasingly frequent as the number of vertices increases. We also discuss more general SNs and identify the simplest graphs in which QSNs cannot be outperformed. Introduction Social networks (SNs) are a traditional subject of study in social sciences [1–3] and may be tackled from many perspectives, including complexity and dynamics [4–6]. Recently, they have attracted much attention after their tremendous growth through the internet. A SN is a set of people, ‘actors’, with a pattern of interactions between them. In principle, there is no restriction on the nature of these interactions. In practice, in actual SNs, these interactions are based on relationships or mutual acquaintances (common interests, friendship, kinship, etc). However, to our knowledge, SNs have never been discussed on the basis of general interactions which can give rise to them. This is precisely the aim of this work. A first observation is that, while a SN is typically described by a graph in which vertices represent actors and edges represent the result of their mutual interactions, the graph does not capture the nature of the interactions or explain why actor iis linked or not to other actors. From this perspective, the graph gives an incomplete description. jazz Oxford yoga sushi chess Bach runnin g jazz Oxford yoga sushi chess Bach runnin g jazz Oxford yoga sushi chess Bach runnin g jazz Oxford yoga sushi chess Bach runnin g jazz Oxford yoga sushi chess Bach runnin g jazz Oxford yoga sushi chess Bach runnin g Figure 1. A CSN. Each actor is represented by a vertex of a graph and each link by an edge. The characteristic of a CSN is that links can be explained on the basis of pre-existing properties of the actors such as whether or not they are jazz enthusiasts, attended Oxford University, practice yoga, like sushi, will participate in a chess tournament, love the music of J S Bach or run four times a week. In order to account for this, we will consider the following, more general, scenario. We represent each actor iby a yes–no test Tion a physical system Sinitially prepared in a state ρ and with possible outcomes 1 (yes) or 0 (no). Of course, these tests must satisfy some rules so that actual SNs naturally fit within them. More importantly, these rules must allow us to consider SNs beyond classical SNs (CSNs), defined as those in which the links between actors are determined by pre-existing properties of the actors, such as, e.g., their enthusiasm for jazz. First, let us see how a CSN can be characterized in terms of yes–no tests Ti.InanyCSN,it is always possible to identify a minimum set of labels such as ‘jazz’ that describes the presence or absence of a link between any two actors; each actor’s links are described by the value ‘yes’ or ‘no’ for each of these labels. An example is shown in figure 1. The size of that minimum set of labels coincides with a property of the underlying graph G, known in graph theory as its intersection number [7], i(G). For example, for the CSN shown in figure 1, the seven labels which describe the network cannot be reduced to a smaller number since for the underlying graph i(G)=7. Suppose each actor has the complete list of labels with their corresponding value ‘yes’ or ‘no’ as in figure 1. The input physical system Scan be a card, and its state ρ is what is written on it, that is, the name of one of the labels. For instance, for the CSN in figure 1, the state ρmay be ‘jazz’. Then, the outcome of Tiis 1 if actor ihas in its list of labels 2 ‘yes’ for jazz, and 0 if it has ‘no’ for jazz. The initial state of the card does not change after the test. In this characterization of a SN, tests Tinaturally fulfil the following rules. (i) Two actors iand jare linked if and only if there exists some state ρfor which the results of Tiand Tjare both 1, which simply means that iand jshare the pre-existing property described by the label in ρ. (ii) If a test Tiis repeated on the same state ρ, it will always give the same result, which simply means that the actor’s label does not change under the execution of the test. (iii) For any ρ, the order of the tests is irrelevant, which reflects the symmetry of the interaction. Note that, as a consequence of rule (i), if for a given ρthe outcome of Tiis 1, then a test Tjin any jwhich is not linked to iwill never give the outcome 1. This means that, for any ρand any set Iof pairwise non-linked actors, the sum of the outputs of the tests Tiover all actors in Iis upper bounded by 1. Moreover, this results in a restriction on the possible states ρ. For instance, in the previous example, the state ‘jazz or Oxford’ is not allowed. For such a state, the tests Tiand Tjcorresponding to two non-linked actors iand jfor which the values of the labels ‘jazz’ and ‘Oxford’ are, respectively, ‘jazz: yes; Oxford: no’ and ‘jazz: no; Oxford: yes’, would give both the outcome 1, in contradiction with rule (i). Let us consider now more general SNs (GSNs). We denote by Pρ(a,b|Ti,Tj)the joint probability of obtaining outcome a∈{0,1}when performing Tion the system Sinitially prepared in the state ρ, and outcome b∈{0,1}when performing Tjon Sin the state ρiresulting from the previous test Ti. The tests must obey the following rules, which generalize (i)–(iii): (I) Pρ(1,1|Ti,Tj)determines the linkage between actors iand j; they are linked if and only if there exists some ρsuch that Pρ(1,1|Ti,Tj)>0. (II) For any ρ,Pρ(a,a|Ti,Ti)=Pρ(a|Ti), i.e. when Tiis repeatedly performed on Sinitially in the state ρ, it always yields the same result. (III) For any ρ, the order of the tests is irrelevant: Pρ(a,b|Ti,Tj)=Pρ(b,a|Tj,Ti). Note that in a CSN the probabilities Pρ(a|Ti)can take only the values 0 or 1, whereas in a GSN these probabilities can take any values compatible with rules (I)–(III). Moreover, here we will assume that the state ρmay change according to the results of the tests Ti. There is a simple task which highlights the difference between a GSN and a CSN described by the same graph G: the average probability Tthat, for an actor ichosen at random, the test Tiyields the outcome 1. The interesting point is that Tis upper bounded differently depending on the nature of the interactions defining the SN. For the CSN, let us suppose that the card is in the state ρ(e.g., jazz). Then, for an actor ichosen at random, T=1 nn i=1Pρ(1|Ti), where nis the number of actors. The maximum value of Tover all possible states ρis the maximum number of actors sharing the value ‘yes’ for a pre-existing property, divided by the number of actors. This corresponds to ω(G) n, where ω(G)is the clique number [7]ofG, i.e. the number of vertices in the largest clique. Given a graph, a clique is a subset of vertices such that every pair is linked by an edge. The term ‘clique’ comes from the social sciences, where social cliques are groups of people all of whom know each other [8]. In the example of figure 1,thevalueof the clique number for the graph is ω(G)=2. As a consequence, for any CSN represented by that graph, the maximum of Tis ω(G) n=1 3. However, for a GSN described by a graph G, the maximum value for Tcompatible with rules (I)–(III) is α∗(¯ G) n, where ¯ Gdenotes the complement of G, which is the graph ¯ Gon the same vertices such that two vertices of ¯ Gare adjacent if and only if they are not adjacent in G, and α∗(¯ G)is the so-called fractional packing number [9]of ¯ G, defined as max i∈Vwi, where the maximum is taken for all 0 ⩽wi⩽1 and for all cliques cjof ¯ G, under the restriction i∈cjwi⩽1. In the example of figure 1,α∗(¯ G)=5 2. Hence, the maximum of Tsatisfying rules (I)–(III) is 5 12 >1 3, attainable for instance by taking Pρ(1|Ti)=1 3for i=1,3,5 and Pρ(1|Tj)=1 2for j=2,4,6. 3 Figure 2. A QSN can be visualized as a CSN in which each actor ihas a device to measure a quantum state |ψi. Note that the maximum value of Tdoes not change when the outcome 1 is not deterministic, as in a CSN, but occurs with certain probability. In this sense, such ‘randomized’ SNs do not perform better than CSNs. The interesting point is that, since there are graphs for which ω(G)<α ∗(¯ G), then there should exist SNs in which Tgoes beyond the maximum value for CSNs. Quantum social networks We shall introduce now a natural SN for which Tmay be larger than the maximum for any CSN represented by the same graph. A quantum SN (QSN) is defined as a SN in which each actor iis associated with a quantum state |ψi. The states are chosen to reflect the graph of the network in the following sense. Non-adjacent (adjacent) vertices in the graph correspond to orthogonal (non-orthogonal) states. It is always possible to associate quantum states to the actors of any network fulfilling the orthogonality relationships imposed by its graph [10]. Reciprocally, any set of quantum states defines a QSN. A QSN can be constructed from a CSN by assigning to actor ia device to test the quantum state |ψi, as illustrated in figure 2. The characterization of the QSN in terms of yes–no tests Ti satisfying rules (I)–(III) is as follows. Each device receives a system Sin a quantum state ρas input, and gives as output either the state |ψiand the outcome 1, or a state orthogonal to |ψi and the outcome 0. These tests are measurements represented in quantum mechanics by rank-1 projectors. Note that projective measurements are the simplest repeatable measurements in quantum mechanics (in agreement with rule (II)), whereas general measurements represented by POVMs are not repeatable. In a QSN, Tmay be larger than the maximum for any CSN represented by the same graph. If each and every actor is provided with the same input state |, according to quantum mechanics the probability of getting the outcome 1 when performing Tifor a randomly chosen iis now T=1 nn i=1||ψi|2.GivenG, the quantity 1 nmax n i=1||ψi|2, where the maximum is taken over all quantum vectors |and |ψiand all dimensions, gives the maximum value of Tfor any QSN. This number is equal to ϑ( ¯ G) n, where ϑ( ¯ G)is the Lov´ asz 4 number [11]of ¯ G, which can be computed to arbitrary precision by semi-definite programming in polynomial time (see the appendix). The Lov´ asz number was introduced as an upper bound of the Shannon capacity of a graph [12], and it is sandwiched between the clique number ω(G)and the chromatic number χ(G) of a graph: ω(G)⩽ϑ( ¯ G)⩽χ(G)[13]. The interesting point is that, for those graphs such that ϑ( ¯ G)>ω(G), QSNs outperform CSNs. On the other hand, ϑ( ¯ G)is upper bounded by the fractional packing number α∗(¯ G), as was shown by Lov´ asz in [11]. In a nutshell, Tand its three upper bounds fulfil TCSN ⩽ω(G) n QSN ⩽ϑ( ¯ G) n GSN ⩽α∗(¯ G) n. For example, for the SNs in figures 1and 2, one has TCSN ⩽1 3 QSN ⩽√5 6 GSN ⩽5 12 . These numbers, ω(G)(which is equal to the independence number α( ¯ G)of the complement graph), ϑ( ¯ G)and α∗(¯ G)have previously appeared in quantum information, in the discussion of the quantum channel version of Shannon’s zero-error capacity problem [14,15], and in foundations of quantum mechanics, in the discussion of non-contextuality inequalities [16]. We generated all non-isomorphic connected graphs with less than 11 vertices (more than 11×106graphs) and singled out those for which ϑ( ¯ G)>ω(G)(as explained in the appendix). The graph with less number of vertices such that ϑ( ¯ G)>ω(G)is the pentagon, for which ω(G)=2 and ϑ( ¯ G)=√5, which can be attained using a quantum system of dimension d=3 (see figure 3(a)). The second simplest graph for which ϑ( ¯ G)>ω(G)is the one in figures 1and 2. For a given number of vertices, the number of graphs such that the maximum of Tfor QSNs is larger than for CSNs rapidly increases. The complete list of these graphs with less than 11 vertices is provided in the appendix. Interestingly, the probability that the graph of an arbitrary network with a large number of actors contains induced graphs in which a QSN outperforms a CSN is almost identity. This follows from a result in graph theory according to which an arbitrarily large graph contains with almost certainty an induced copy of every graph [17]. A graph His said to contain an induced copy of Gwhen Gis a subgraph of Hobtained by removing some of the vertices and all the edges incident to these vertices. Moreover, a stronger result can be proven. The probability that QSNs outperform CSNs for an arbitrarily large graph is almost identity. This follows from the observation [18] that, while for an n-vertex random graph with edges generated with probability 1/2thevalueof ω(G)is almost surely [19] roughly 2 log2n,thevalueofϑ(G)is almost surely [20]o(√n). Once one has identified a graph for which ϑ( ¯ G)>ω(G), one can compute the quantum states |and |ψiof minimum dimensionality ξ(G)providing the optimal quantum solution, the one that maximizes T. For the simplest graph with quantum advantage these states are given in figure 3(a). The state |is the initial state of Sneeded to obtain the maximum quantum advantage. Social networks with no-better-than-quantum advantage Remarkably, there are graphs for which QSNs outperform CSNs but no GSN outperforms the best QSN: those satisfying ω(G)<ϑ(¯ G)=α∗(¯ G). To single out such graphs is particularly interesting because they would allow us to construct the best GSN in a simple way. We identified all the graphs with less than 11 vertices with ω(G)<ϑ(¯ G)=α∗(¯ G). There are only four of them. The simplest one is in figure 3(b). Its quantum realization requires a d=6 quantum system (e.g., a qubit–qutrit system) and ω(G)=2 and ϑ( ¯ G)=5 2. The second simplest graph contains the first one, and it is shown in figure 3(c). It only requires a d=4 5 2 5 3 4 67 8 9 10 1 2 5 3 4 67 8 9 10 1 3 4 1 2 5 (a) (b) (c) 12 6 7 8 9 10 11 12 13 14 15 16 17 18 3 4 5 (d) Figure 3. Graphs for which QSNs can outperform CSNs. The right side displays the quantum states |ψiand |needed for the maximum quantum advantage using a quantum system of the smallest dimension. (a) is the simplest graph for which QSNs can outperform CSNs. (b)and(c)are the simplest graphs for which QSNs cannot be improved. Graph (c) has the same edges as graph (b) plus extra ones. (d) is the simplest known graph in which the quantum advantage is independent of |. 6 quantum system; for this graph ω(G)=3 and ϑ( ¯ G)=7 2. The other two graphs are the one in figure 3(c) with one or two extra edges, as shown in the appendix. In all the graphs we have explored so far, the quantum advantage requires the preparation of Sin a specific quantum state |. However, as the complexity of the network increases this requirement becomes unnecessary. This is due to the fact that there are graphs for which the quantum advantage is independent of |; thus any quantum state (pure or mixed, including maximally mixed) can be used as the initial state for the tests Ti. As proven in the appendix, any set of quantum states |ψibelonging to the class of the so-called Kochen–Specker sets [21,22] defines a QSN in which the quantum advantage is independent of the state |. The graph corresponding to the SN associated with the simplest Kochen–Specker set [23] is illustrated in figure 3(d). It has ω(G)=4 and ϑ( ¯ G)=9 2, requires ad=4 quantum system and no GSN can outperform it. Methods to generate Kochen–Specker sets [24–27] can be used to obtain QSNs with all these features. Final remarks Any actual SN through the internet, like Facebook or Twitter, is complex enough to potentially benefit from assigning quantum tests to the actors. An example is the following: suppose that a company wants to sell a product to as many Facebook users as possible. Under the (correct) assumption that Facebook is a CSN, the optimal strategy would be to identify the biggest subgroup of mutually linked actors, single out their common interest, and then design a commercial targeting this common interest. However, if Facebook were a QSN with exactly the same links as the actual Facebook, then the company would have a larger positive feedback by linking its commercial to the results of the quantum tests. As in a CSN, the vertices of a QSN can be organized in communities or clusters, with many edges joining vertices of the same cluster and comparatively few edges joining vertices of different clusters. Given a graph G, community detection might be simpler if the graph represents a QSN rather than a CSN. The reason is that a QSN with a given Grequires a (quantum) physical system of dimension (i.e. number of perfectly distinguishable states) dQ=ξ( ¯ G), with ξ( ¯ G)the orthogonal rank of the complement of G, defined as the minimum dsuch that there exists an orthogonal representation of ¯ Gin ddimensions (i.e. a function mapping non-adjacent vertices in Gto orthogonal vectors in Cd). However, building a CSN requires a physical system of dimension dC=i(G)(e.g., for the Gin figure 1, there are i(G)=7 distinguishable states ρ: jazz, ..., running). dQ⩽dCand, in most cases, dQ<dC. As an example, while for the graphs in figures 3(a)–(d), dCis 5,15,10 and 18; dQis 3,6,4 and 4, respectively. Once a community is detected, the study of its induced subgraph will tell us whether or not it has a quantum advantage. Note that QSNs with no global quantum advantage can contain induced subgraphs (e.g., representing communities) with quantum advantage. On the experimental side, constructing a simple QSN with advantage over its classical counterpart is within actual experimental capabilities. The simplest example is a pentagon in which each actor has a device for testing the appropriate quantum state. Acknowledgments The authors thank I Herbauts, S Severini and A Winter for valuable discussions and C Santana for graphical support. This work was supported by the projects no. FIS2008-05596, no. MTM2008-05866, no. FIS2011-29400 and no. P06-FQM-01649, the Research Council of Norway and the Wenner-Gren Foundation. 7 Table A1. Number of non-isomorphic graphs with vertices ranging from 5 to 10 corresponding to SNs in which the assignment of quantum states to the actors provides advantage, and number of them in which the advantage cannot be improved by GSNs. With quantum With no-better-than- Vertices Graphs advantage quantum advantage 52110 6 112 2 0 7 853 28 0 8 11 117 456 0 9 261 080 15 951 0 10 11 716 571 957 639 4 Appendix We explain how we obtained all graphs Gwith less than 11 vertices for which ϑ( ¯ G)>ω(G). We also prove that a set of quantum states belonging to the class of Kochen–Specker sets defines a QSN in which the quantum advantage is independent of the state. A.1. Finding graphs in which QSNs can outperform CSNs To obtain all SNs with less than 11 actors in which the assignment of quantum states can outperform the corresponding CSNs, we generated all non-isomorphic connected graphs using nauty [28], and then we calculated ω(G)(using Mathematica [29]), ϑ( ¯ G)(using SeDuMi [30] and also DSDP [31,32]) and α∗(¯ G)(using Mathematica from the clique-vertex incidence matrix of ¯ G, obtained from the adjacency matrix of ¯ Gcalculated using MACE [33,34] for enumerating all maximal cliques). In addition, we obtained the minimum dimensionality ξ(G)of the quantum system in which the maximum quantum versus classical advantage occurs, or a lower bound of ξ(G), by identifying subgraphs in ¯ Gwhich are geometrically impossible in a space of lower dimensionality. For example, the simplest impossible graph in dimension d=1 consists of two non-linked (non-orthogonal) vertices in ¯ G;ind=2, three vertices, one of them linked to the other two. From these two impossible graphs, one can recursively construct impossible graphs in any dimension dby adding two vertices linked to all vertices of an impossible graph in d−2. For example, if ¯ Gcontains a square, then ξ(G)>3. Finally, we have calculated the minimum dimensionality i(G)needed for a CSN by using a program based on nauty,very-nauty [35] and [36]. Table A1 contains the number of non-isomorphic graphs with a given number of vertices, up to 10 vertices; the number of them in which QSNs outperform CSNs, and for the latter, the number of those for which no GSN outperforms the best QSN. All non-isomorphic graphs with less than 11 vertices (around 106) in which QSNs outperform CSNs are presented in [37]. A.2. State-independent QSNs A Kochen–Specker (KS) [21] set in dimension dis a set of rays Sin the d-dimensional complex space such that there is no function f:S→{0,1}satisfying that for all orthonormal bases b⊆S,u∈bf(u)=1. Proposition. For any KS set in dimension d represented by a graph G, ω(G)<ϑ(¯ G)for any initial state in dimension d. Proof. For an n-ray KS set in dimension d,ϑ( ¯ G)=n d, since ϑ( ¯ G)is the same for any initial state, including the maximally mixed state ρ=1 d1(where 1represents the identity matrix). 8 ω(G)cannot reach this number since, by the definition of KS set in dimension d, there is no way to assign 0 or 1 to their elements in such a way that, for every clique of size din the complement graph ¯ G, which corresponds to a basis b⊆S,d−1 elements are 0 and one is 1. This means that the best possible assignment respecting that two non-adjacent vertices in Gcannot be both 1 includes at least one clique Cin ¯ Gfor which 0 is assigned to the d elements. The KS set can be expanded so that every vector belongs to a clique of size din ¯ G, and the assignments can be replicated an integer number msuch that mω(G)and mϑ( ¯ G) can be expressed as a sum of elements grouped in cliques. The contribution of each clique is either 0 or 1. In mϑ( ¯ G)all cliques’s contribution is 1, whereas in mω(G)the contribution of the clique Cin which the assignment fails is 0.  References [1] Scott J 1991 Social Network Analysis (London: Sage) [2] Wasserman S and Faust K 1994 Social Network Analysis: Methods and Applications (Cambridge: Cambridge University Press) [3] Freeman L C 2006 The Development of Social Network Analysis (Vancouver: Empirical Press) [4] Albert R and Barab´ asi A-L 2000 Phys. Rev. Lett. 85 5234 [5] Albert R and Barab´ asi A-L 2002 Rev. Mod. Phys. 74 47 [6] Barab´ asi A-L 2009 Science 325 412 [7] Harary F 1994 Graph Theory (Reading, MA: Addison-Wesley) [8] Luce R D and Perry A D 1949 Psychometrika 14 95 [9] Scheinerman E R and Ullman D H 1997 Fractional Graph Theory (New York: Wiley) [10] Lov´ asz L, Saks M and Schrijver A 1989 Linear Algebra Appl. 114/115 439 [11] Lov´ asz L 1979 IEEE Trans. Inform. Theory 25 1 [12] Shannon C E 1956 IRE Trans. Inform. Theory 28 [13] Knuth D E 1994 Electron. J. Comb. 1A1 [14] Duan R, Severini S and Winter A 2010 arXiv:1002.2514 [15] Cubitt T S, Leung D, Matthews W and Winter A 2010 arXiv:1003.3195 [16] Cabello A, Severini S and Winter A 2010 arXiv:1010.2163 [17] Diestel R 2010 Graph Theory (Springer: Heidelberg) proposition 11.3.1 [18] Feige U and Krauthgamer R 2003 SIAM J. Comput. 32 345 [19] Alon N and Spencer J H 2000 The Probabilistic Method (New York: Wiley) [20] Juh´ asz F 1982 Combinatorica 2153 [21] Kochen S and Specker E P 1967 J. Math. Mech. 17 59 [22] Peres A 1995 Quantum Theory: Concepts and Methods (Dordrecht: Kluwer) chapter 7 [23] Cabello A, Estebaranz J M and Garc´ ıa-Alcaine G 1996 Phys. Lett. A212 183 [24] Zimba J and Penrose R 1993 Stud. Hist. Phil. Sci. 24 697 [25] Cabello A and Garc´ ıa-Alcaine G 1996 J. Phys. A: Math. Gen. 29 1025 [26] Cabello A, Estebaranz J M and Garc´ ıa-Alcaine G 2005 Phys. Lett. A339 425 [27] Paviˇ ci´ c M, Merlet J-P, McKay B D and Megill N D 2005 J. Phys. A: Math. Gen. 38 1577 [28] McKay B D 2007 nauty User’s Guide (Version 2.4) (Canberra, Australia: Department of Computer Science, Australian National University) [29] Wolfram Mathematica www.wolfram.com/mathematica/ [30] SeDuMi http://sedumi.ie.lehigh.edu/ [31] DSDP: Software for Semidefinite Programming www.mcs.anl.gov/hs/software/DSDP/ [32] Benson S J, Ye Y and Zhang X 2000 SIAM J. Optim. 10 443 [33] MACE (MAximal Clique Enumerator) http://research.nii.ac.jp/∼uno/index.html [34] Makino K and Uno T 2004 SWAT 2004: Proc. 9th Scandinavian Workshop on Algorithm Theory (Berlin: Springer) p 260 [35] Briggs K The very_nauty Graph Library (Version 1.1) http://keithbriggs.info/very_nauty.html [36] Kou L T, Stockmeyer L J and Wong C K 1978 Commun. ACM 21 135 [37] Database of Quantum Social Networks www.ii.uib.no/∼larsed/qsn/ 9