format: text

text:
# Investigation of a protein complex network

## I Introduction

In recent years complex networks have attracted much of interest to model real-life networks such as social, biological and communication networks ab ; dm ; n1 . Certainly, introducing the essential static and dynamic features of these networks can help us in a better understanding of their various properties ws ; bw ; asb ; m ; ajb ; cnsw . A well known property of most of these networks, the so called small world property ws  indicates that the average distance between any two nodes increases slowly with the size of the network (i.e. as logarithm of the size). This in turn can lead to a fast spreading of effects in the network and so increases the finite size effects when one studies for example diffusion in such a network aks . Extensive studies also indicate the importance of degree (the number of neighbors of a node) distribution for static and dynamic behaviors of the network ab ; dm . One can also add various kinds of correlations, e.g. degree correlation of two neighbors, to the list of these important features n2 ; n3 .
Protein interaction networks are important examples of the real-life networks in which nodes and edges represent proteins and interactions between them respectively u ; i ; a ; w ; pss ; ms ; vfmv . Proteins have been traditionally recognized on the basis of their roles as enzymes, signalling molecules or structural components in cells and micro-organisms. The most rudimentary structural information about the proteome (assembly of proteins in an organism) is the pattern of interactions between different proteins. Determining such connections, helps us in understanding the backbone of functional relationships between proteins and the pathways for the propagation of various signals among them. Besides specific detailed information about the pattern of interactions in a single proteome, which are certainly important for its functioning, some general characteristics of these networks are also important in that they may point to universal properties of organisms. For example, it has been shown that as far as the interaction of individual proteins are concerned, the interaction network of the budding yeast Saccharomyses cerevisiae (S. cerevisiae) is a scale free network. This property is itself a hint to the robustness of the protein interaction network against the random removal of proteins jmbo ; ajb .
However recent progress indicates that each of the central processes in a cell is catalyzed not by a single protein but by the coordinated action of a highly linked set of several proteins, called a protein complex ks ; g ; h . Thus complexes act as protein machines and have been evolved for the same reason that humans have invented mechanical and electronic machines. It is also remarkable that a single protein may be shared in several different complexes. It is expected that a protein with a general functionality is shared by many complexes. On the other hand it seems that the weight of a complex depends on the degree of sophistication of its tasks.
It is in view of this new emerging picture of the proteome as a coordinated ensemble of protein complexes that we study the general properties of the network of protein complexes of the budding yeast. Certainly, analysis of the proteome map at both protein and complex level will result in a better understanding of the proteom functioning. Although from a biological point of view the precise nature of proteins and their interactions in a single living organism are important, from a physical point of view in which we seek the general universal patterns among many different organism p , we can study the most elementary features of a proteome, i.e. the weight distribution of complexes, distribution of the number of proteins shared between two complexes, etc.
Based on extensive information provided in g  we constructed a weighted graph corresponding to the network of complexes. By this we mean that both the nodes and the edges are assigned weights. The weight of a node is equal to the number of proteins in the complex it represents. Two nodes are connected by a weighted edge, whose weight indicates how many proteins are common in the two complexes. Such a point of view seems to be the first step to understand the integration and coordination of cellular functions. Connections in this network not only reflect physical interaction of complexes, but may also represent common regulation, localization, turnover or architecture g . In addition it has a meaningful interpretation in other real-life networks such as social networks when a connection between two communities can only be established by common individuals in them. Note that one may consider a single protein complex as a subgraph of the protein interaction network with a high level of interconnection between its elements. From this point of view the protein complex network is a large scale or coarse grained picture of the protein interaction network. However, we stress that in view of the recent findings, this is not the correct picture for the interactome. In fact the important feature of the recent experiments g ; h  compared to the previous experiments u ; i  is that they uncover not only the pairwise interactions but ternary, quaternary and higher interactions between different proteins in a complex e .
In this work we show that the above protein complex network is a small world one with scale free degree distribution. Moreover it is found that distributions of weights of complexes, weights of edges and coordination numbers of proteins (the number of complexes a protein participates) follow power law behaviors which can in turn refer to a kind of preferential attachment in the evolution of the protein complex network ab . We compare the network with some null models such as Erdös and Rényi random graph er  and a random-selection model in which each complex selects its proteins randomly from the list of all proteins. Unlike the former case the latter model results in a considerable clustering for the network of complexes. Here by clustering we mean the probability that two neighbors of a node be also connected to each other. In this manner the clustering is equivalent to the transitivity of the network (defined as three times the ratio of the number of triangles in the network to the number of connected triples of nodes n4 ). Moreover, we find that the random-selection model can well reproduce the degree distribution of complexes and the dependence of degree of a complex on its weight. However some important distributions of the network such as weight of edges are still far from the predictions of this model in the region of large weights. Following the previous models for the evolution of the protein interaction network w ; vfmv ; pss , we propose a simple evolutionary model based on duplication and divergence (mutation) of proteins. We show that this model reproduces the power law behavior of some essential distributions such as weight of complexes and weight of edges.

The paper is organized as follows. Section (II) is devoted to the description of the budding yeast protein complex network based on the data provided in g . Section (III) gives a comparison between the random-selection model and the real network. The evolutionary model is introduced in section (IV). We conclude the paper in section (V).

## II structural properties of the yeast protein complex network

According to the data we have extracted from g , the S. cerevisiae includes $`n=1398`$ proteins, organized in $`N=232`$ complexes. The resulting network is then composed of $`232`$ nodes and $`E=2043`$ edges. A complex of weight $`m`$ is denoted by a node of weight $`m`$, and if two complexes share $`w`$ proteins, a weight $`w`$ is assigned to the edge connecting them. Figures (1-a) and (1-b) show the distribution of weights of the nodes, $`S(m)`$, and weights of the edges, $`E(w)`$.

Both distributions show the power law behavior ($`S(m)m^{\tau _m}`$ and $`E(w)w^{\tau _w}`$) with exponents respectively equal to $`\tau _m=1.33\pm 0.06`$ and $`\tau _w=2.4\pm 0.1`$, figures (1-a and 1-b). The observed deviation in the number of complexes of weight $`1`$ from the expected power law behavior could be mostly attributed to the experimental limitations g . The average weight of the nodes and the edges turn out to be respectively $`\overline{m}=11.48`$ and $`\overline{w}=1.79`$ with the following dispersions: $`\sigma _m:=\sqrt{\overline{m^2}\overline{m}^2}=14.69`$ and $`\sigma _w=2.9`$. One could attribute the large values of these dispersions to the small size of the network and scale free nature of the related distributions. A curious property of the network is that there is no correlation between the weights of adjacent nodes. In other words, the probability that an emanating edge from a complex of weight $`m`$ encounters another complex of weight $`m^{}`$ is independent of $`m`$. To show this we compute the associated correlation coefficient n2 , $`r_{mm}`$, which in the protein complex network has the value $`0.004`$ and is defined as follows: let $`P(m,m^{})`$ be the probability that an arbitrary edge lies between two complexes of weights $`m`$ and $`m^{}`$. Thus $`\mathrm{\Pi }(m)=_m^{}P(m,m^{})`$ gives the probability of finding a complex of weight $`m`$ at the end point of an arbitrary edge. Now the correlation coefficient is given by

$$r_{mm}:=\frac{_{m,m^{}}mm^{}(P(m,m^{})\mathrm{\Pi }(m)\mathrm{\Pi }(m^{}))}{_mm^2\mathrm{\Pi }(m)(_mm\mathrm{\Pi }(m))^2}.$$
(1)
It is clear that in the absence of any correlation (i.e. when $`P(m,m^{})=\mathrm{\Pi }(m)\mathrm{\Pi }(m^{})`$) we have $`r_{mm}=0`$. If similar complexes have a high tendency for being connected to each other we say that the network is assortative n2  in this respect and the correlation coefficient will be positive. Otherwise the network is dissortative and the correlation coefficient will be negative. Obviously one can apply this definition to any two point distribution to measure the degree of correlation between the two variables.

One may also ask what is the relation between the degree of a complex and its weight. Our results again give a power law dependence for large values of complex weights. The total weight of edges emanating from a complex of weight $`m`$ (its weighted degree) scales as $`k_w(m)m^{\beta _w}`$, where $`\beta _w0.95\pm 0.07`$, figure (2-a).

It is found that the number of neighbors behaves in a similar way $`k(m)m^\beta `$ with $`\beta 0.55\pm 0.07`$, figure (2-b). Obviously $`k_w(m)`$ grows faster than $`k(m)`$ with the weight of complex as expected. Roughly speaking, since $`\beta _w2\beta `$, the above relations suggest that the average weight of an edge emanating from a complex of weight $`m`$ scales as $`m^\beta `$.

To address topological properties of the graph we studied also the degree distribution, $`P(k)`$ and the correlation between degrees of neighboring nodes which can again be detected by computing the related correlation coefficient, $`r_{kk}`$. Note that by degree of a node we mean the number of neighboring nodes, irrespective of the weights of the edges emanating from that node. By weighted degree of a node we mean the sum of weights of the edges emanating from this node. In figure (3) we show that the degree distribution is scale free with a sharp cutoff at its tail. In this figure we see also a power law fit of form $`P(k)k^\gamma `$ with exponent $`\gamma =0.6\pm 0.04`$ to the real data. Moreover, we find the value $`0.06`$ for $`r_{kk}`$ which means that in contrast to the protein interaction networks ms , there is no strong correlation between the degrees of adjacent nodes in protein complex network. Our results shows that the same conclusion is true if we take also the weights of the edges into account.

Usually a given protein takes part in more than one, say $`q`$ complexes. We call $`q`$ the coordination number of that protein. We found that on average a protein takes part in $`\overline{q}=1.91`$ complexes (with $`\sigma _q=1.86`$). Figure (4) shows the number of proteins versus their coordination numbers, $`R(q)`$. The distribution is a scale free one for large coordination numbers, that is $`R(q)q^{\tau _q}`$ with $`\tau _q=2.95\pm 0.12`$ as its exponent.

This indicates that there are a few number of proteins with high coordination numbers. It seems that these are the proteins with exceedingly important role in the functioning of the cell. Let us compute the correlation coefficient which measures the correlation between coordination of proteins and weight of complexes they contribute. To this end we consider the collection of proteins and complexes as a bipartite network in which nodes of the first type represent complexes and those of the second type represent proteins. An edge in this network connects a node of the first kind to a node of the second kind. Thus the number of edges emanating from a protein determines its coordination number and similarly the number of edges connected to a complex gives its weight. Now we define $`P(m,q)`$ as the probability that an arbitrary edge of this bipartite network connects a complex of weight $`m`$ to a protein of coordination number $`q`$. Therefor $`\mathrm{\Pi }(m):=_qP(m,q)`$ and $`\pi (q):=_mP(m,q)`$ are respectively the probability that an arbitrary edge reaches to a complex of weight $`m`$ and a protein of coordination number $`q`$. Now the associated correlation coefficient is defined as

$$r_{mq}:=\frac{_{m,q}mq(P(m,q)\mathrm{\Pi }(m)\pi (q))}{\sqrt{_mm^2\mathrm{\Pi }(m)(_mm\mathrm{\Pi }(m))^2}\sqrt{_qq^2\pi (q)(_qq\pi (q))^2}}.$$
(2)
We find that in the the case of our data $`r_{mq}=0.024`$ which indicates to the absence of correlation in this respect. That is the coordination number of a protein does not affects in its relation with complexes of different weights more than what is expected by chance.

The network of complexes also defines pathways for the propagation of various signals such as phosphorylation and allosteric regulation of proteins. For such functions, a key parameter of the network is its diameter, defined as the shortest path between the remotest nodes in the giant component of the network. Our analysis reveals that the network has a small diameter, $`D=5`$, which points to the small world property of the network. To confirm this we also computed $`\overline{1/d_{i,j}}`$ (where $`d_{i,j}`$ denotes the shortest distance between nodes $`i`$ and $`j`$) and compared it with the corresponding quantity in an equivalent Erdös - Rényi random graph, table (1). The reason behind the computation of $`\overline{1/d_{i,j}}`$ is that the above graph is not connected rather it has a giant component of size $`S_g=198`$, a binary component and $`32`$ single nodes. To have a measure of clustering in the network, its transitivity $`T`$ was extracted and it has been found that it is almost six times greater than the one in an Erdös - Rényi random graph, see table (1). This high level of transitivity which is another hint to the small world property of the protein complex network would give rise to the robustness of the network against the random removal of nodes or edges n4 .

## III The Random-Selection Model

To highlight the special features of the yeast protein complex network and to possibly draw conclusions of biological interest, one may compare it to a random network in which proteins aggregate randomly to form different complexes. We call such a model a random-selection model. The simplest such model may be constructed as a bipartite network nsw  as follows: one takes a bipartite network consisting of two types of nodes. Nodes of the first type represent complexes and those of the second type represent proteins. A bipartite network of this kind consisting of $`N`$ complexes and $`n`$ proteins and the resulting weighted network consisting of only protein complexes are depicted in figure (5).

Here we start from a bipartite network and calculate many of the properties of the resulting protein complex network exactly. A given complex $`\mu `$ contains a number of proteins which we denote by $`m_\mu `$. In general $`0<m_\mu n`$. From the real data one can infer the actual sequence $`(m_1,m_2,\mathrm{}m_N)`$. One thus assigns free (unconnected) stubs to the first type of nodes (the complexes) according to this sequence and then connects these stubs randomly to the second types of nodes (proteins). Each protein connected to a complex means that it is contained in that complex. In this way one obtains another distribution $`R(q)`$, where $`q`$ is the number of complexes a given protein participates in. Clearly a given protein may be contained in more than one complex. Note that a peculiar feature of this model is that certain proteins may not be connected to any complex at all. Later in this section we introduce another slightly improved model in which this effect does not happen.
In the following we calculate many of the interesting quantities of the resulting weighted network of complexes exactly and compare them with real data to check the viability of this model. To proceed let $`S(m)`$ denotes the number of complexes of weight $`m`$. Obviously $`_mS(m)=N`$, where $`N`$ is the total number of complexes. First let us calculate the probability of two complexes of weight $`m`$ and $`m^{}`$ to have $`w`$ proteins in common. Denote this probability by $`P(m,m^{};w)`$. The first complex chooses its $`m`$ members freely from the collection of all proteins. The second complex, has $`\left(\begin{array}{c}n\\ m^{}\end{array}\right)`$ ways for choosing its members from the collection, of which $`\left(\begin{array}{c}m\\ w\end{array}\right)`$ ways are available for choosing $`w`$ members in common from the first complex and $`\left(\begin{array}{c}nm\\ m^{}w\end{array}\right)`$ ways are available for choosing the remaining set disjoint from the first complex. Hence the probability is

$$P(m,m^{};w)=\frac{\left(\begin{array}{c}m\\ w\end{array}\right)\left(\begin{array}{c}nm\\ m^{}w\end{array}\right)}{\left(\begin{array}{c}n\\ m^{}\end{array}\right)}$$
(3)
. This equation can be rewritten in the form

$$P(m,m^{};w)=\frac{m!m^{}!}{(mw)!(m^{}w)!}\frac{(nm)!(nm^{})!}{n!w!(n+wmm^{})!},$$
(4)
to make its symmetry under interchange of $`m`$ and $`m^{}`$ manifest. The probability that two such complexes have no common members (be not connected to each other in the network) is:

$$P(m,m^{};0)=\frac{(nm)!(nm^{})!}{n!(nmm^{})!}.$$
(5)
For $`m,m^{}<<n`$ one can approximates $`(nm)!/n!`$ by $`n^m`$ and $`(nm^{})!/(nmm^{})!`$ by $`(nm^{})^m`$. So the above relation takes the form

$$P(m,m^{};0)(1\frac{m^{}}{n})^me^{mm^{}/n}.$$
(6)
Thus the probability of two complexes being connected will be $`1P(m,m^{};0)`$ and the average number of edges will be:

$$E=\frac{1}{2}\underset{m,m^{}}{}S(m)S(m^{})(1P(m,m^{};0).$$
(7)
Moreover the average number of edges with weight $`w`$ is given by:

$$E(w)=\frac{1}{2}\underset{m,m^{}}{}S(m)S(m^{})P(m,m^{};w).$$
(8)
Figure (6-a) shows this quantity for a model network with the same parameters as the yeast protein complex network.

We see that the weight distribution of edges decreases exponentially in contrast to the power law behavior of the protein complex network. This means that in the yeast protein complex there are edges with very high weights. These high weight edges inevitably connect high weight complexes. Thus in the yeast complex network, the hubs (complexes with high degree) are connected to each other intensively. This is in contrast with the protein interaction network ms  where the high degree proteins have a larger tendency to be connected to low degree ones.
In the same way one obtains $`k(m)`$, the average number of neighbors of a given complex of weight $`m`$:

$$k(m)=\underset{m^{}}{}S(m^{})(1P(m,m^{};0))$$
(9)
In figure (6-b) we compare the above expression with the one obtained from the real network. One finds a good agreement between predictions of the model and the real data. From the distribution of weights of complexes $`S(m)`$ and the above relation, one can obtain the distribution of degrees $`P(k)`$ using the relation $`P(k)\mathrm{\Delta }k=S(m)\mathrm{\Delta }m`$. Thus we expect that degree distribution of the random-selection model to be also close to the real one.

What can be said about $`r(q):=\frac{R(q)}{n}`$, the probability that a given protein contributes in $`q`$ complexes? It is not difficult to show that due to the fully random nature of the selection process, the above distribution has a binomial form like

$$r(q)=(\begin{array}{c}N\overline{m}\\ q\end{array})(\frac{1}{n})^q(1\frac{1}{n})^{N\overline{m}q}$$
(10)
where $`\overline{m}`$ is the average weight of complexes. Thus for very large values of $`N`$ and $`n`$ we have

$$r(q)=\frac{\lambda ^q}{q!}e^\lambda ,\lambda =\frac{N}{n}\overline{m}.$$
(11)
Therefore we get a Poisson distribution for coordination numbers of proteins in distinctive contrast to the real distribution which is scale free.

As seen from figure (6), our analytical treatment of this model revealed that some of the general characteristics (the degree of a given complex as a function of its weight and so the degree distribution of complexes) of these networks are close to those of S. cerevisiae protein complex network. Further results derived from numerical simulations given in table (1) show that random-selection model is rather close to the yeast protein complex network.
Note however that certain discrepancies between the random-selection model and the real complex network, i.e. in the distribution of the weights of edges, persist even if we improve this model by fixing the coordination number of proteins from the beginning to be the same as the one derived from real data of the protein complex network (see figure (7)). The evolutionary model that we introduce in the next section is aimed to remove this discrepancy.

## IV The Evolutionary Model

In this section we introduce a simple model aimed at representing the evolution of protein complex network. The model is based on the extension of the hypothesis of evolution by duplications and divergence of proteins w ; pss ; vfmv  to the level of protein complexes. DNA duplication has long been known as an important factor in the evolution of genome size. This process almost certainly explains the presence of large families of genes with related functions in biological complex organisms. Consider a set of proteins which belong to a number of functional units or complexes. In each evolutionary step, the following actions take place. A protein is randomly chosen and duplicated. It means that a new protein is added to the proteome and contributes to all the complexes in which its mother participates. Then the new protein undergoes mutations; it loses its membership in any given complex with probability $`\mu _o`$, and enters any other complex with probability $`\mu _i`$. It is also probable that the protein creates a new complex (novel functionality) by its own with probability $`\mu _c`$. In figure (8) we have shown what happens in a typical step of network evolution.

Note that during this process the new protein may not contribute to any complex and thus leaves the proteome. Starting from one protein in one complex, we have taken $`t=1500`$ evolutionary steps. We found that it was the best number of steps which could intimately produce the desired results. We found that in this situation only about $`7`$ percent of duplicated proteins are stuff and the others takes part at least in one complex. Having $`t`$ we will also have the probability of creating a new complex in each step, because $`N`$ the number of complexes satisfies $`N=1+\mu _ct`$. The other parameters can also be determined by requesting that the number of proteins and some important distributions (e.g. weight distribution of complexes) be as close as possible to the real data. Moreover, note that we also expect that the probability of entering a new complex for a duplicated protein must be much smaller than the probability of exiting one of its inherited complexes. Summing up these points we find, by fitting to the real data, the following values for parameters of the model: $`\mu _o0.4`$ , $`\mu _i0.01`$ and $`\mu _c0.154`$. One can find results of this model in figure (9) and table (1).

In figure (9-a) we see that the model closely reproduces the scale free behavior of the weight distribution of complexes in the region of large weights although there are some deviations from the real data for the number of small complexes. Indeed we expected such a power law behavior in advance due to the presence of preferential attachmentab  in the process of evolution of complexes. Note that although the selection of proteins for duplication is a completely random procedure, complexes with higher weights have a higher chance to include the new duplicated protein. In this way the evolution of complexes is governed by the well known mechanism of preferential attachment which is a principal way to produce scale free behaviors in the realm of complex networksab .
Figure (9-b) shows the weight distribution of edges in the resulted protein complex network of the evolutionary model. The agreement with the real data is excellent. It is one of the essential features of protein complex network which none of the random models studied in this paper could exhibit it. We believe that this fact indicates to the essential role of duplication and divergence of proteins in the evolution of the protein complex network.
Moreover as table (1) shows the evolutionary model results in a small world protein complex network. Both the transitivity and diameter of the model are comparable with the values of the real network of complexes.
This model also exhibits a little tendency for being a negative correlated network in weights and degrees of neighboring complexes. Indeed the related correlation coefficients turn out to be $`r_{mm}=0.05\pm 0.001`$ and $`r_{kk}=0.08\pm 0.002`$. It means that complexes with different weights and degrees have a larger probability to be connected to each other.
Finally it is worthwhile to note that the data studied in this paper are those of the yeast proteome whereas the results given in this section are the average behavior of such a proteome.

## V Conclusion

To summarize, we have shown that the protein complex network of the yeast is a nearly uncorrelated small world scale free network. The power law behavior was also found in other significant distributions such as weight of complexes, weight of edges and coordination number of proteins. Although some of these features (e.g. small world property and high clustering) were expected in advance, this study revealed some distinctive properties of this network like the scale free behavior of weight distribution of edges. We also compared the yeast protein complex network with a random-selection model and a simple evolutionary model. It was found that the random-selection model can satisfactorily reproduce the relation between weight and degree of a complex and also degree distribution of the real network. However this model failed to give the power law behavior of the distribution of weights of edges, a property which could be well reproduced in the evolutionary model. In the latter model the desired distributions automatically arise by just fitting the model parameters using the real data.
From the evolutionary point of view, the above study can also be a hint to the essential role of duplication and divergence processes in the evolution of proteome and this study is indeed an extension of this mechanism to the level of protein complexes. Certainly results of the previous studies on protein interaction network along with the investigation of large scale properties in the protein complex network will help in a better understanding of the general behaviors of such systems.


text:
# The Communication Cost of Simulating Bell Correlations

## Abstract

What classical resources are required to simulate quantum correlations? For the simplest and most important case of local projective measurements on an entangled Bell pair state, we show that exact simulation is possible using local hidden variables augmented by just one bit of classical communication. Certain quantum teleportation experiments, which teleport a single qubit, therefore admit a local hidden variables model.

Recent theoretical research into quantum algorithms Shor (1994), quantum communication complexity Raz (1999), and quantum cryptography Bennett and Brassard (1984) has shown that quantum devices are more powerful than their classical counterparts. Indeed, the flourishing field of quantum information theory Nielsen and Chuang (2000) aims to provide an information-theoretic quantification of the power underlying quantum resources. One important feature of quantum theory lies in the statistical correlations produced by measurements on local components of a quantum system. Almost forty years ago, John Bell showed that such correlations cannot be explained by descriptions based on realistic properties of local subsystems Bell (1964). To experimentally distinguish quantum correlations from those produced by local hidden variables theories, Bell introduced the notion of Bell inequalities, with subsequent experimental evidence falling squarely on the side of quantum theory Aspect et al. (1982a). Bell inequalities, whilst usually considered relevant only to foundational studies of quantum theory, answer a fundamental information-theoretic question: what correlations can be produced between separate classical subsystems, which have interacted in the past, if no communication between the subsystems is allowed? Violation of a Bell inequality, however, does nothing to quantify what classical information-processing resources are required to simulate a particular set of quantum correlations.

The simplest and most important example of quantum correlations involves the correlations produced by projective measurements on a Bell pair. Bell pairs are the maximally-entangled states of two quantum bits (qubits) and are the basic resource currency of bipartite quantum information theory. Various equivalences are known: one shared Bell pair plus two bits of classical communication can be used to teleport one qubit Bennett et al. (1993) and, conversely, one shared Bell pair plus a single qubit of communication can be used to send two bits of classical communication via superdense coding Bennett and Wiesner (1992).

Consider the gedanken experiment of Einstein, Podolsky, and Rosen Einstein et al. (1935) (EPR), as reformulated by Bohm Bohm (1951). Two spatially separate parties, Alice and Bob, each have a spin-$`\frac{1}{2}`$ particle, or qubit. The global spin wave function is the entangled Bell singlet state (also known as an EPR pair) $`|\psi =\frac{1}{\sqrt{2}}\left(|_A|_B|_A|_B\right)`$. The spin states $`|`$, $`|`$ are defined with respect to a local set of coordinate axes: $`|`$ (resp. $`|`$) corresponds to spin along the local $`+\widehat{z}`$ (resp. $`\widehat{z}`$) direction. Alice and Bob each measure their particle’s spin along a direction parameterized by a three-dimensional unit vector: Alice measures along $`\widehat{a}`$, Bob along $`\widehat{b}`$. Alice and Bob obtain results, $`\alpha \{+1,1\}`$ and $`\beta \{+1,1\}`$, respectively, which indicate whether the spin was pointing along ($`+1`$) or opposite ($`1`$) the direction each party chose to measure. Locally, Alice and Bob’s outcomes appear random, with expectation values $`\alpha =\beta =0`$, but their joint probabilities are correlated such that that $`\alpha \beta =\widehat{a}\widehat{b}`$. We refer to these correlations as Bell correlations.

It is not possible to reproduce these correlations using a protocol which draws on random variables shared between Alice and Bob, but does not allow communication after they have selected measurements Bell (1964). So how much communication is required to exactly simulate them Maudlin (1992); Brassard et al. (1999); Steiner (2000); Csirik (2002); Bacon and Toner (2002); Cerf et al. (2000); Massar et al. (2001)? Naively, Alice can just tell Bob the direction of her measurement $`\widehat{a}`$ (or vice versa) but this requires an infinite amount of communication. The question of whether a simulation can be done with a finite amount of communication was raised independently by Maudlin Maudlin (1992), Brassard, Cleve, and Tapp Brassard et al. (1999), and Steiner Steiner (2000). Their approaches differ in how the communication cost of the simulation is defined: Brassard et al. take the cost to be the number of bits sent in the worst case; Steiner, the average. (Steiner’s model is weaker because the amount of communication in the worst case can be unbounded, although such cases occur with probability zero.) Brassard et al. present a protocol which simulates Bell correlations using exactly eight bits of communication (since improved to six bits Csirik (2002)). Surprisingly Bacon and Toner (2002), the only lower bound for the amount of communication is given by Bell’s theorem: at least some communication is needed. Here we present a simple protocol that uses just one bit of communication.

We first note three simple properties of Bell correlations: (i) if $`\widehat{a}=\widehat{b}`$, then we must have $`\alpha =\beta `$: Alice and Bob must output perfectly anticorrelated bits; (ii) either party can reverse their measurement axis and flip their output bit; and (iii) the joint probability is only dependent on $`\widehat{a}`$ and $`\widehat{b}`$ via the combination $`\widehat{a}\widehat{b}`$. In his original paper, Bell gave a local hidden variables model that reproduces these three properties for all possible axes, but his model fails to reproduce Bell correlations because the statistical correlations when $`\widehat{a}\widehat{b}`$ are not as strong as those of quantum mechanics Bell (1964). The protocol we describe below is inspired by Bell’s original protocol. Property (iii) implies that we may restrict attention to rotationally invariant protocols, for which all probabilities depend only on $`\widehat{a}\widehat{b}`$ and not $`\widehat{a}`$ and $`\widehat{b}`$ separately, by randomizing over all inputs with the same dot product. More precisely, suppose $`P`$ is any protocol that simulates the correlations. Then define a new protocol $`P^{}`$ whose hidden variables consist of (i) those required by $`P`$, and (ii) a random rotation $`R\mathrm{SO}(3)`$. Protocol $`P^{}`$ then consists of running protocol $`P`$ on $`R\widehat{a}`$ and $`R\widehat{b}`$ in place of $`\widehat{a}`$ and $`\widehat{b}`$.

We now describe our protocol. Alice and Bob share two random variables $`\widehat{\lambda }_1`$ and $`\widehat{\lambda }_2`$ which are real three-dimensional unit vectors. They are chosen independently and distributed uniformly over the unit sphere.

The protocol proceeds as follows:

1. Alice outputs $`\alpha =\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)`$.
2. Alice sends a single bit $`c\{1,+1\}`$ to Bob where $`c=\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)\mathrm{sgn}(\widehat{a}\widehat{\lambda }_2)`$.
3. Bob outputs $`\beta =\mathrm{sgn}\left[\widehat{b}(\widehat{\lambda }_1+c\widehat{\lambda }_2)\right]`$,

where we have used the $`\mathrm{sgn}`$ function defined by $`\mathrm{sgn}(x)=+1\mathrm{if}x0`$ and $`\mathrm{sgn}(x)=1\mathrm{if}x<0`$. A geometric description of our protocol is given in Fig. 1. We note immediately that Bob obtains no information about Alice’s output from the communication.

We now prove the protocol reproduces the correct expectation values. Each party’s output changes sign under the symmetry $`\widehat{\lambda }_1\widehat{\lambda }_1`$, $`\widehat{\lambda }_2\widehat{\lambda }_2`$, so $`\alpha =\beta =0`$ because $`\widehat{\lambda }_1`$ and $`\widehat{\lambda }_2`$ are uniformly distributed. The joint expectation value $`\alpha \beta `$ can be calculated using

$`\alpha \beta `$ $`=`$ $`E\{\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)\times `$ (1)
$`{\displaystyle \underset{d=\pm 1}{}}{\displaystyle \frac{(1+cd)}{2}}\mathrm{sgn}[\widehat{b}(\widehat{\lambda }_1+d\widehat{\lambda }_2)]\}`$
where $`E\left\{x\right\}=\frac{1}{(4\pi )^2}𝑑\widehat{\lambda }_1𝑑\widehat{\lambda }_2x`$, $`c=\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)\mathrm{sgn}(\widehat{a}\widehat{\lambda }_2)`$ and we have used the trick that $`(1+cd)/2=1`$ if $`c=d`$ and $`0`$ if $`cd`$. After substituting for $`c`$ and expanding Eq. (1), we obtain the sum of four terms (because each term inside the summation sign is itself the sum of two terms) and, using $`\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)c=\mathrm{sgn}(\widehat{a}\widehat{\lambda }_2)`$, we note that the four terms are related by the symmetries $`\widehat{\lambda }_1\widehat{\lambda }_2`$ or $`\widehat{\lambda }_2\widehat{\lambda }_2`$, so each has the same expectation value. Hence

$$\alpha \beta =E\left\{2\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)\mathrm{sgn}\left[\widehat{b}\left(\widehat{\lambda }_2\widehat{\lambda }_1\right)\right]\right\}.$$
(2)
This integral may be evaluated with the help of the two diagrams shown in Fig. 2, with the result that $`\alpha \beta =\widehat{a}\widehat{b}`$, as required.

Our protocol exactly simulates the quantum mechanical probability distribution for projective measurements on the singlet Bell pair state. If a large number of simulations are performed in parallel, the communication may be compressed. To see this, assume Alice’s measurement vector $`\widehat{a}`$ is uniformly distributed (if not, we randomize, as outlined above). Then, if $`\widehat{\lambda }_1\widehat{\lambda }_2=\mathrm{cos}\eta `$, Alice sends $`1`$ with probability $`\eta /\pi `$ and $`1`$ with probability $`1\eta /\pi `$, so that the communication can be compressed to $`_0^{\pi /2}\mathrm{sin}\eta d\eta H(\eta /\pi )0.85`$ bits, where $`H(\eta /\pi )`$ is the Shannon entropy. This encoding depends on the shared unit vectors $`\widehat{\lambda }_1`$ and $`\widehat{\lambda }_2`$: a third party without access to the hidden variables will observe Alice sending uniformly distributed bits to Bob.

Our protocol is easily modified to simulate joint measurements on any maximally entangled state of two qubits, because every such state is related to the singlet by a local change of basis and thus may be simulated by rotating and/or reflecting the input vectors $`\widehat{a}`$ and $`\widehat{b}`$, before running our protocol.

Now consider the following experiment: Alice prepares a qubit in a state unknown to Bob. She then teleports the qubit to Bob, who performs a projective measurement on it, along a direction unknown to Alice. We shall show that this experiment admits a local hidden variables description. We first note that quantum teleportation experiments do not purport to test whether quantum mechanics allows a local hidden variables model; rather they aim to distinguish quantum teleportation from other protocols Alice and Bob might carry out using classical communication, but no entanglement Boschi et al. (1998). From this point of view, teleportation experiments represent “investigations within quantum mechanics” Braunstein et al. (2001), rather than comparisons of quantum mechanics with classical local hidden variables models Hardy (1999). With this distinction in mind, it is still interesting to ask whether teleportation experiments can be explained by a local hidden variables model.

If one allows an infinite amount of classical communication from Alice to Bob, then there is a trivial local hidden variables model, for Alice can just send a classical description of the state to Bob, who then simulates his measurement. We now give a local hidden variables model that requires only two bits of communication, which is the same amount as the quantum teleportation protocol. The construction is based on Ref. Cerf et al. (2000), where the procedure is termed “classical teleportation.” It is sufficient to consider the case where Alice prepares the qubit in a pure state, which we suppose has spin aligned along the axis $`\widehat{a}`$. We suppose Bob’s measurement is aligned along the axis $`\widehat{b}`$. Alice and Bob share uniformly distributed random three-dimensional unit vectors $`\widehat{\lambda }_1`$ and $`\widehat{\lambda }_2`$ (which can be thought of as hidden variables carried by the Bell pair used for teleportation). The protocol is as follows:

1. Alice sends $`c_1=\mathrm{sgn}(\widehat{a}\widehat{\lambda }_1)`$ and $`c_2=\mathrm{sgn}(\widehat{a}\widehat{\lambda }_2)`$ to Bob.
2. Bob outputs $`\beta =\mathrm{sgn}\left[\widehat{b}\left(c_1\widehat{\lambda }_1+c_2\widehat{\lambda }_2\right)\right]`$.

It is easy to verify that $`\beta =\widehat{a}\widehat{b}`$, as required. We also note that the two bits sent appear completely random to a party without access to the hidden variables.

It is usual in teleportation experiments to have (i) a third party Victor supply Alice with a quantum state unknown to her, and (ii) Bob hand off the teleported state to Victor (or another party) to measure, rather than measuring it himself. Such a distinction is not important for the question we address, because the qubit transmitted from Victor to Alice, for example, can carry hidden variables describing its state. The point is that local hidden variables are hidden: although it is convenient to describe a local hidden variables model as if Alice and Bob had access to the hidden variables, the model still exists even if the hidden variables are inaccessible to them. There is no way for the experimenters to tell whether their experiment is described by quantum theory or by “gremlins” within their apparatus, executing the local hidden variables protocol described above.

Are there quantum teleportation experiments which do not have such a local hidden variables description? One obvious possibility is an experiment that teleports entanglement itself. But there is a more subtle possibility. If we allow Bob to measure the qubit using elements of a positive operator-valued measure, then there may not be a local hidden variables description which respects the two bit classical communication bound. More generally, if Alice teleports $`n`$ qubits (which requires $`2n`$ bits of communication) and Bob makes a joint measurements on them, then it is known that any exact local hidden variables theory requires that Alice send at least a constant times $`2^n`$ bits of communication in the worst case Brassard et al. (1999). Whether this holds for protocols with bounded error is an important open question.

Finally, using the classical teleportation protocol, we obtain a (not necessarily optimal) protocol to simulate joint projective measurements on partially entangled states of two qubits, which uses two bits of communication: Alice first simulates her measurement and determines the post-measurement state of Bob’s qubit; Alice and Bob then execute the classical teleportation protocol.

The results presented here offer an intriguing glimpse into the nature of correlations produced in quantum theory. If we interpret Bell inequality violation to mean that some communication is necessary to simulate Bell correlations, then our results prove that the minimal amount, one bit, is all that is necessary for projective measurements on Bell pairs. Is our straightforward protocol an indication of a deep structure in quantum correlations? We hope that our protocol and the development of a general theory of the communication cost of simulating quantum correlations will help shed light on this fundamental question.

Acknowledgements.—We thank John Preskill, Andrew Doherty, Patrick Hayden, Andre Methot, Carlos Mochon, and Michael Steiner for useful suggestions. This work was supported in part by the National Science Foundation under grant EIA-0086038, through the Institute for Quantum Information.