Quantum Advantages of Communication Complexity from Bell Nonlocality

Abstract

Communication games are crucial tools for investigating the limitations of physical theories. The communication complexity (CC) problem is a typical example, for which several distributed parties attempt to jointly calculate a given function with limited classical communications. In this work, we present a method to construct CC problems from Bell tests in a graph-theoretic way. Starting from an experimental compatibility graph and the corresponding Bell test function, a target function that encodes the information of each edge can be constructed; then, using this target function, we can construct a CC function, and by pre-sharing entangled states, its success probability exceeds that of the arbitrary classical strategy. The non-signaling protocol based on the Popescu–Rohrlich box is also discussed, and the success probability in this case reaches one.

1. Introduction

Bell nonlocality [1,2,3,4] is one of the most distinctive features that distinguish quantum mechanics from classical mechanics. It is an experimentally verified phenomenon and now serves as a crucial resource for many quantum information tasks, such as quantum computation [5], quantum key distribution (QKD) [6], quantum random number generation [7], and the communication complexity (CC) problem [8]. Among these tasks, CC problems for which distributed parties jointly calculate a function with limited communications are of great importance for investigating the limitations of different physical theories [4,8]. For instance, the set of calculable functions and the success probabilities for calculating a given function may be different for local hidden variable (LHV) theory [2], quantum theory, and non-signaling theory.

CC problems, originally introduced by Yao [9], concern the following question: what is the minimal amount of communication necessary for two or more parties to jointly calculate a given multivariate function $f(x_1,\cdots ,x_n)$ where the k-th party only knows his own input $x_k$ but no information about the inputs of other parties initially? It has been shown from different perspectives that entanglement and Bell nonlocality are closely related to the quantum advantage of the CC problem; see Refs. [8,10,11,12,13,14,15]. Violation of Bell inequalities often leads to quantum advantages of CC problems [8,10,11,12,13] and it is also argued that the quantum advantage of CC problem implies violation of Bell inequalities [14,15]. However, many of the results above are existence proof. In practice, to utilize Bell nonlocality to obtain quantum advantages of a real CC problem, one needs to consider how to explicitly translate the Bell test into a CC problem. In this work, we systematically explore the translation of a Bell test into CC problem via the graph-theoretic method.

We are mainly interested in the CC problems for which only limited classical communications are allowed and the goal for each party is to calculate the function with as high success probability as possible. By introducing the concept of the experimental compatibility graph and its corresponding Bell test function, we explore the relationship between the Bell nonlocality and quantum advantage of CC problems. We show that, from an arbitrary experimental compatibility graph $G^e$, we can construct a corresponding CC problem $F_{G^e}$ for which the quantum protocol exhibits a success probability that exceeds the that of all classical protocols. We also investigate the possibility of using a non-signaling box to solve CC problems, and we show that it has an advantage over all quantum protocols.

The paper is organized as follows: in Section 2, we introduce several graph-theoretic concepts related to Bell nonlocality, including the experimental compatibility graph, compatibility graph, and Bell test functions; in Section 3, we provide the basics of CC problems and define the quantum advantages of the protocol; in Section 4, we present a class of functions based on an arbitrary given experimental graph $G^e$ for which quantum protocols exhibit advantages; finally, in the last section, we make some concluding remarks.

2. Bell Inequalities from Compatibility Graphs

Let us now introduce a general framework for n-party Bell inequalities based on a set of n-point correlation functions $E(x_{i_1},x_{i_2},\cdots ,x_{i_n})=\langle x_{i_1}\otimes x_{i_2}\otimes \cdots \otimes x_{i_n}\rangle$. Many pertinent classes of Bell inequalities are of this correlator form; see, e.g., Refs. [4,16]. To start with, let us first introduce a useful mathematical tool, compatibility graphs. For a set of measurements $\mathcal{M}=\{M_1,\cdots ,M_n\}$, we can assign a corresponding graph $G_{\mathcal{M}}$ called the measurement compatibility graph [17], whose vertices are labeled by measurements, and there is an edge between two vertices if the corresponding measurements are compatible; i.e., they can be measured simultaneously. We denote the vertex set of the graph G as $V\left(G\right)$ and the edge set as $E\left(G\right)$, and an edge is a pair $\langle ij\rangle :=(M_i,M_j)\in V\left(G\right)\times V\left(G\right)$. Similarly, we can introduce the experimental compatibility graph and hypergraph $G_{\mathcal{M}}^e$ [17], in which the vertices are labeled with the measurements involved in the experiment, and an edge represents two or more jointly measured measurements in the experiment. For two-party case, each edge consists of two measurements, and $G_{\mathcal{M}}^e$ is a subgraph of $G_{\mathcal{M}}$, while for the n-party ($n>2$) case, each edge consists of n vertices; thus, $G_{\mathcal{M}}^e$ is a hypergraph. See Figure 1b,c for an illustration of the compatibility graph and two-party experimental compatibility graph.

In a typical n-party Bell scenario, the experimenters share an n-partite system. According to an experimental compatibility graph $G^e$, they can choose a set of measurements $x_{i_1},x_{i_2},\cdots ,x_{i_n}$ for joint measurements, where $x_{i_k}$ is the measurement chosen by the k-th party. After many runs of experiments, they obtain a set of n-point correlation functions $\left\{E(x_{i_1},x_{i_2},\cdots ,x_{i_n})\right|\langle i_1{i}_2\cdots i_n\rangle \in E\left(G^e\right)\}$. To determine whether the obtained measurement statistics are local, viz., obey the LHV theory or not, a function must be calculated,

$$\begin{array}{cc}\hfill {\mathcal{B}}_{G^e}=& \sum _{\langle i_1{i}_2\cdots i_n\rangle \in E\left(G^e\right)}{\gamma }_{\langle i_1{i}_2\cdots i_n\rangle }E(x_{i_1},x_{i_2},\cdots ,x_{i_n})\hfill \\ \hfill & +\sum _{\langle i_1{i}_2\cdots i_{n-1}\rangle \in E\left(G^e\right)}{\gamma }_{\langle i_1{i}_2\cdots i_{n-1}\rangle }E(x_{i_1},x_{i_2},\cdots ,x_{i_{n-1}})\hfill \\ \hfill & +\cdots +\sum _{x_i\in V\left(G\right)}{\gamma }_{\langle x_i\rangle }E\left(x_i\right),\hfill \end{array}$$

(1)

which we refer to as the Bell test function. In this work, we mainly focus on the homogenous case; that is, for the n-party Bell test, the Bell test function only contains n-point correlation functions. It is also convenient for our purpose to assume that ${\gamma }_{\langle i_1{i}_2\cdots i_n\rangle }=\pm 1$. In this case, different colors of edges of $G^e$ represent different coefficients; if ${\gamma }_{\langle i_1{i}_2\cdots i_n\rangle }=+1$, the edge is drawn as a black solid line and deemed a positive edge, and if ${\gamma }_{\langle i_1{i}_2\cdots i_n\rangle }=-1$, the edge is drawn as a red dashed line and deemed a negative edge, as depicted in Figure 1.

Note that for an n-party Bell experiment, $G^e$ is usually an n-partite graph, as the measurements of each party are usually chosen as incompatible measurements. In an LHV world, the value of the test function lies in the range ${\mathcal{R}}_{LHV}=[B_C^1,B_C^2]$; e.g., for the Clauser–Horne–Shimony–Holt (CHSH) type of Bell test function ${\mathcal{B}}_{CHSH}$, the range is ${\mathcal{R}}_{LHV}=[-2,2]$ [16]. However, for quantum theory, the value may lie outside the LHV range ${\mathcal{R}}_{LHV}$; this is called the quantum violation of Bell inequality, which means that quantum theory is not consistent with the LHV assumption. Similar to LHV theory, there also exists a quantum range ${\mathcal{R}}_Q=[B_Q^1,B_Q^2]$ of the value of the Bell test function; e.g., for CHSH type of Bell test function, it is ${\mathcal{R}}_Q=[-2\sqrt{2},2\sqrt{2}]$, and this kind of quantum bound is known as Tsirelson bound. Is it possible for a Bell test function to violate the quantum range? The answer is yes; there are many different kinds of approaches to understand quantum theory from outside; e.g., in non-signaling theory [18], the Bell test function may reach its functional minimal and maximal values. To summarize, we have the following Bell inequalities for a given experiment compatibility graph:

$${\mathcal{B}}_{G^e}\stackrel{LHV}{\in }{\mathcal{R}}_{LHV}\stackrel{Q}{\subseteq }{\mathcal{R}}_Q\stackrel{NS}{\subseteq }{\mathcal{R}}_{NS}.$$

(2)

Note that for a given experimental compatibility graph, the Bell test function is, in general, not unique.

Another crucial issue regards the kind of experimental compatibility graph that can be used to test Bell nonlocality. A necessary condition for this is the following [17,19]: the compatibility graph corresponding to $G^e$ is non-chordal. Chordal graphs are those that do not have any induced cycle with a size of more than three. From Vorob’yev theorem [20,21], if the compatibility graph G corresponding to $G^e$ is chordal, then there always exists a global joint probability distribution that can reproduce all marginal probability distributions that we obtained from the experiment. A result of Fine [22] further suggests that the existence of this kind of global joint probability distribution is equivalent to the existence of an LHV model for all involved measurements. Thus, for the chordal graph, the measurement statistics are always reproducible by the LHV model. In a recent work [23], it was claimed that the above condition is also a sufficient condition.

Here, we present two examples for convenience of our later discussions. We recommend readers to read Refs. [17,19,23,24,25] for more examples.

2.1. Example 1

The first example is $2m$-cycle Bell inequality. The experimental compatibility graph is a $2m$-cycle, for which $A_1,A_3,\cdots ,A_{2m-1}$ are observables chosen by Alice and $B_2,B_4,\cdots ,B_{2m}$ are observables chosen by Bob; the i-th vertex connects with the $(i+1)$-th vertex. The Bell test function is thus

$$\begin{array}{cc}\hfill {\mathcal{B}}_{G_{\mathrm{cycle}}^e}=& \sum _{i=1,3,\cdots ,2m-1}{\gamma }_{i}E(A_i,B_{i+1})+\sum _{i=2,4,\cdots ,2m}{\gamma }_{i}E(A_{i+1},B_i)\hfill \end{array}$$

(3)

note that, here, ${\gamma }_i=\pm 1$, and the number of ${\gamma }_i=-1$ must be odd to ensure that it can test Bell nonlocality. As proved in [26,27], Bell inequality is

$$|{\mathcal{B}}_{G_{\mathrm{cycle}}^e}|\stackrel{LHV}{\le }2m-2\stackrel{Q}{\le }2mcos\frac{\pi }{2m}\stackrel{NS}{\le }2m.$$

(4)

When $m=2$, the experimental compatibility graph is a 4-cycle graph, as depicted in Figure 1a; the corresponding Bell inequality is the CHSH inequality.

It is worth mentioning that, although we can construct a Bell test from the arbitrary non-chordal graph, the LHV bound (which corresponds to independent number calculation of a graph) and non-signaling boundary can easily be obtained, but the maximum quantum violation (which corresponds to the Lovász number calculation of a graph [24,28]) is usually very difficult to calculate. The example corresponding to non-cycle experimental compatibility graph can also be constructed.

2.2. Example 2

The experimental compatibility graph of this Bell test is shown in Figure 1d. We denote the graph as $G_{2|3}^e$, and the subscripts here is used to indicate that Alice chooses two observables and Bob chooses three observables to measure. The corresponding Bell test function is

$$\begin{array}{cc}{\mathcal{B}}_{G_{2|3}^e}=\hfill & E(A_1,B_1)+E(A_2,B_1)+E(A_2,B_2)+E(A_1,B_2)\hfill \\ \hfill & +E(A_1,B_3)-E(A_2,B_3).\hfill \end{array}$$

(5)

The LHV bound is 4, and the non-signaling bound is 6, but the exact quantum bound remains unknown.

3. Communication Complexity Problems

Now, let us recall the formal definition of communication complexity; for further information, we refer the reader to Refs. [29,30,31]. For simplicity, consider the two-party case, for which Alice and Bob try to calculate a bivariate function $f:{\mathbb{B}}^n\times {\mathbb{B}}^n\to \mathbb{B}$ collaboratively, where $\mathbb{B}$ denotes the binary set $\{0,1\}$ or $\{\pm 1\}$. An r-round communication complexity protocol $\mathcal{P}$ for computing function $f(x,y)$ is a distributed algorithm consisting of a set of r functions $f_1,\cdots ,f_r:{\cup }_{m\ge 0}{\mathbb{B}}^m\to {\cup }_{m\ge 0}{\mathbb{B}}^m$. Alice first individually calculates function $f_1\left(x\right)=v_1$ and sends the result to Bob; after Bob receives the result, he calculates function $f_2(y,v_1)=v_2$ and sends the result to Alice, etc. Each act of communication is called a round. We suggest that the protocol $\mathcal{P}$ is valid for calculating $f(x,y)$ if the last message sent (i.e., $v_r=f_r(x,v_1,\cdots ,v_{r-1})$ by Alice or $v_r=f_r(y,v_1,\cdots ,v_{r-1})$ by Bob) equals $f(x,y)$ for all possible input values of $x,y$. The communication complexity of the protocol $\mathcal{P}$ is then defined as the $C_{\mathcal{P}}\left(f\right)=|v_1|+\cdots +|v_r|$, where $|v_i|$ denotes the number of bits of the message $v_i$. The protocol defined above is deterministic. For the bounded-error case, Alice and Bob can toss coins individually or jointly to choose the input at each round, and the protocol $\mathcal{P}$ has to calculate f with a success probability greater than or equal to a fixed value $1-\delta$, where $\delta$ is usually chosen as $1/3$, viz, $P_{succ}\ge 2/3$. We assume that if Bob guesses the value $f(x,y)$ as $z=0,1$ during the final round, the successful probability will be

$$p_{succ}\left(\mathcal{P}\right)=\sum _{x,y}p(x,y)p(z=f(x,y)|x,y).$$

(6)

The bounded-error communication complexity is denoted as $C_{\mathcal{P}}^{be}\left(f\right)$, which is the number of communicated bits in the protocol such that $p_{succ}\ge 1-\delta$ for some $\delta <1/2$.

The bounded-error communication complexity problem concerns the problem of obtaining the lower bound of the amount of communication needed for all parties to obtain the value of a given function f with successful probability $P_{succ}\ge 1-\delta$. We can naturally ask the inverse question: what is the highest successful probability for calculating the function f if the amount of communication $C\left(f\right)$ is restricted to be upper bounded $C\left(f\right)\le C_{bd}$ ? Note that unlike in the regular communication complexity problem where the bound of successful probability $1-\delta$ does not matter so much, in this kind of CC problem, the communication bound is of considerable importance. Since there exists a trivial protocol for calculating the arbitrary function f, for which Alice communicates her entire input to Bob, $p_{succ}$ can always reach 1 if the allowed communication is greater than or equal to $min\left\{\right|x|+1,|y|+1\}$.

There are two types of quantum communication complexity protocols: (i) the preparation measurement protocol and (ii) the entanglement-assisted protocol, which is similar to the categorification of quantum key distribution protocol. In this work, we mainly discuss the entanglement-assisted protocol.

The performance of a usual CC protocol $\mathcal{P}$ is characterized by the amount of communication, i.e., classical or quantum bits $C(\mathcal{P},f|p_{\mathrm{succ}})$ required to achieve the success probability $p_{\mathrm{succ}}$. The quantum advantage of the CC problem is that there exists a quantum protocol ${\mathcal{P}}_Q$ such that for any classical protocol ${\mathcal{P}}_C$, we have $C({\mathcal{P}}_C,f|p_{\mathrm{succ}})>C({\mathcal{P}}_Q,f|p_{\mathrm{succ}})$.

The performance of the CC protocol $\mathcal{P}$ for calculating function f can also be characterized by the maximal achievable success probability $p_{\mathrm{succ}}(\mathcal{P},f|C_{bd})$ given a bounded amount of communication $C_{bd}$. Here, the communication could be classical bits or qubits; we suggest that there is a quantum advantage for the ICC problem for calculating f if there is a quantum protocol ${\mathcal{P}}_Q$ such that $p_{\mathrm{succ}}({\mathcal{P}}_Q,f|C_{bd})>p_{\mathrm{succ}}({\mathcal{P}}_C,f|C_{bd})$ for all classical protocol ${\mathcal{P}}_C$.

There is a simple and well-known example of the CC problem in Ref. [32], for which Alice and Bob receive bit strings $(x,a)\in {\mathbb{B}}^2$ and $(y,b)\in {\mathbb{B}}^2$, respectively, and they tend to calculate a function f given by the following language:

$$L_{\mathrm{Bell}}=\{(x,a;y,b)\in {\mathbb{B}}^2\times {\mathbb{B}}^2|a\oplus b=x\wedge y\}.$$

(7)

All input strings distribute uniformly, and the two parties are allowed to exchange only two classical bits. Their goal is to calculate $L_{\mathrm{Bell}}$ with as high successful probability as possible. In Ref. [10], Brukner et al. present the optimal classical protocol and prove that by using entangled quantum states that violate CHSH inequality, the quantum solution of the problem has a higher success probability than that of the optimal classical protocol, thus exhibiting the quantum advantage. This protocol works in the entanglement-assisted sense.

4. From Bell Inequality Violation to the Quantum Advantage for ICC Problems

We now discuss how to translate a Bell test into an ICC problem using a compatibility graph. To start with, let us consider the two-party case. For a given experimental compatibility graph $G^e$, which is a bipartite graph, the vertices are labeled with $x_A=v_1,\cdots ,v_n$ by Alice and $x_B=u_1,\cdots ,u_m$ by Bob. There are some edges corresponding to ${\gamma }_{\langle ij\rangle }=1$ (called positive edges, drawn as black solid edge in Figure 1) and some others corresponding to ${\gamma }_{\langle ij\rangle }=-1$ (called negative edges, drawn as red dashed edge in Figure 1). We introduce a function that we refer to as the target function

$$t(x_A,x_B)=\left\{\begin{array}{c}0,\mathrm{for}\langle v_i{u}_j\rangle \mathrm{positive}\mathrm{edge},\hfill \\ 1,\mathrm{for}\langle v_i{u}_j\rangle \mathrm{negative}\mathrm{edge}.\hfill \end{array}\right.$$

(8)

Consider the following two-party scenario: Alice and Bob receive $(x_A,y_A)$ and $(x_B,y_B)$, respectively, where $y_A,y_B=\pm 1$ and $x_A=1,\cdots ,n$, $x_B=1,\cdots ,m$, and the condition $\langle x_A{x}_B\rangle \in E\left(G^e\right)$ (i.e. it is an edge of the experimental compatibility graph $G^e$) are promised. The function they calculate is

$$F_{G^e}(x_A,y_A;x_B,y_B)=y_A{y}_B{(-1)}^{t(x_A,x_B)}.$$

(9)

Note that this is a partial function; for some inputs, the function is not defined—see

Table 1. Value of $F_{G_{6-cycle}^e}$; columns are indexed by $(x_A,y_A)$ and rows are indexed by $(x_B,y_B)$.

	(1, +1)	(1, −1)	(2, +1)	(2, −1)	(3, +1)	(3, −1)
(1, +1)	1	−1	1	−1	−	−
(1, −1)	−1	1	−1	1	−	−
(2, +1)	−	−	1	−1	1	−1
(2, −1)	−	−	−1	1	−1	1
(3, +1)	1	−1	−	−	−1	1
(3, −1)	−1	1	−	−	1	−1

for an example. In this way, we can construct a CC function from an arbitrary given experimental compatibility graph.

For the n-party case, the corresponding experimental graph is an n-partite hypergraph; the vertices of k-th party are labeled with $x_k=u_1^k,\cdots ,u_{m_k}^k$; the edge $\langle u_{i_1}^1\cdots u_{i_n}^n\rangle$ consists of n vertices, one from each party. Similar to the two-party case, we can define the target function

$$t(x_1,\cdots ,x_n)=\left\{\begin{array}{c}0,\mathrm{for}\langle u_{i_1}^1\cdots u_{i_n}^n\rangle \mathrm{positive}\mathrm{edge},\hfill \\ 1,\mathrm{for}\langle u_{i_1}^1\cdots u_{i_n}^n\rangle \mathrm{negative}\mathrm{edge}.\hfill \end{array}\right.$$

(10)

The function to be calculated is

$$F_{G^e}(x_1,y_A;\cdots ;x_n,y_n)=y_1\cdots y_n{(-1)}^{t(x_1,\cdots ,x_n)}.$$

(11)

The CC problem to be solved is as follows: the n parties try to calculate the function (11), and the k-th party receives the bit string $(x_k,y_k)$ with $x_k=u_1^k,\cdots ,u_{m_k}^k$. The probability distribution for the input strings is

$$p(x_1,y_1;\cdots ;x_n,y_n)=\frac{1}{2^n}\times \frac{1}{\left|E\right(G^e\left)\right|}.$$

(12)

Each party is allowed to broadcast one classical bit of information, and n parties broadcast the information simultaneously such that their broadcast bits are independent.

4.1. Optimal Classical Protocol

Let us now introduce an optimal classical protocol ${\mathcal{P}}_C$ for the above CC problem. To make things clearer, we take the two-party case as an example. The main step is to calculate the target function part ${(-1)}^{t(x_A,x_B)}$. To do this, Alice and Bob firstly relabel their vertices as $x_A^{\prime }$ and $x_B^{\prime }$ such that the values $x_A^{\prime }+x_B^{\prime }$ are different for different edges. This can be achieved since $G^e$ is a finite graph. For example, for Bob’s fixed vertex $u_1$, the range of $u_1+v_i$ is $[N_1,N_1^{\prime }]$; we can then set $u_2^{\prime }>N_1^{\prime }$, and then all $u_2^{\prime }+v_i>N_1^{\prime }$. The intersection of ranges of $u_1+v_i$ and $u_2^{\prime }+v_i$ is empty. By repeating the procedure m times, we achieve our goal. In fact, we can do more to relabel the vertices such that the values corresponding to negative edges are odd numbers and the values corresponding to positive edges are even numbers. This is because $v_i^{\prime }+u_j^{\prime }$ are now different for different edges. If the value is not as what we require, we can add a very large number to make the parity correct. In this way, we see that

$${(-1)}^{t(x_A^{\prime },x_B^{\prime })}={(-1)}^{x_A^{\prime }+x_B^{\prime }}.$$

(13)

Before starting the calculation for a given experimental compatibility graph $G^e$, Alice and Bob firstly come together to discuss and fix the procedure in order to conduct the relabeling process. In fact, the easiest way is to relabel the vertices before calculation as $x_A^{\prime }$ and $x_B^{\prime }$.

With the above preparation, we now present our classical protocol. Alice and Bob, when receiving inputs $(x_A,y_A)$ and $(x_B,y_B)$, choose to locally calculate two functions $a(x_A,{\lambda }_A)$ and $b(x_B,{\lambda }_B)$ such that $a(x_A,{\lambda }_A)={(-1)}^{x_A^{\prime }}$ and $a(x_A,{\lambda }_A)={(-1)}^{x_B^{\prime }}$. Note that, here, ${\lambda }_A,{\lambda }_B$ characterize their local classical resources, and they may be classically correlated. Then, Alice and Bob broadcast the results $e_A=y_{A}a(x_A,{\lambda }_A)$ and $e_B=y_{B}b(x_B,{\lambda }_B)$, respectively. After receiving the result, they both output it with the answer function

$${\mathrm{Ans}}_{{\mathcal{P}}_C}(x_A,y_A;x_B,y_B)=e_A{e}_B.$$

(14)

The success probability of the protocol is

$$\begin{array}{cc}{p}_{\mathrm{succ}}\left({\mathcal{P}}_C\right|C_{bd}=2)=\hfill & \frac{1}{\left|E\right(G^e\left)\right|}(\sum _{\langle ij\rangle \mathrm{positive}}p(ab=1|v_i{u}_j)\hfill \\ \hfill & +\sum _{\langle ij\rangle \mathrm{negative}}p(ab=-1|v_i{u}_j)).\hfill \end{array}$$

(15)

The protocol can achieve a success probability of $(B_C+|E\left(G^e\right)\left|\right)/2|E\left(G^e\right)|$, where $B_C$ is the classical bound for Bell inequality. For the $2m$-cycle case, it is $p_{\mathrm{succ}}\left({\mathcal{P}}_C\right|C_{bd}=2)=(2m-1)/2m$, and especially for the well-known CHSH case $m=2$, $p_{\mathrm{succ}}\left({\mathcal{P}}_C\right|C_{bd}=2)=3/4$.

For the n-party case, the protocol works similarly. The main difference is that the experimental compatibility graph is now an n-partite hypergraph. By relabeling the vertices, we have

$${(-1)}^{t(x_1,\cdots ,x_n)}={(-1)}^{x_1^{\prime }+\cdots +x_n^{\prime }}.$$

(16)

After receiving the input bit strings, each party chooses to locally calculate a function $e_k=y_{i}a(x_k,{\lambda }_k)$ with $a_k(x_k,{\lambda }_k)={(-1)}^{x_k^{\prime }}$. Finally they broadcast $e_k$ simultaneously and output the value

$${\mathrm{Ans}}_{{\mathcal{P}}_C}(x_1,y_1;\cdots ;x_n,y_n)=e_1\cdots e_n.$$

(17)

The success probability is similar to Equation (15). The protocol can achieve a success probability of $(B_C+|E\left(G^e\right)\left|\right)/2|E\left(G^e\right)|$, where $B_C$ is the classical bound for Bell inequality. In this protocol, each party indeed only broadcasts one classical bit of information.

Before we discuss the quantum advantage of the entanglement-assisted protocol, we need to prove that this is in fact the optimal classical protocol.

Proof of the optimality of the protocol.—We now show that the above protocol is optimal; i.e., there is no classical protocol reaching a higher success probability. For the two-party case, what we need to show is that when Alice and Bob initially share classical randomness, there is no $C_{bd}=2$ protocol for which Alice and Bob can calculate the function $F_{G^e}$ with success probability greater than $(B_C+|E\left(G^e\right)\left|\right)/2|E\left(G^e\right)|$. Firstly, we observe that an n-bit Boolean function $f(x_1,\cdots ,x_n)$ with values $\pm 1$ can be decomposed as

$$f(x_1,\cdots ,x_n)=\sum _{i_1,\cdots ,i_n=0,1}{T}_{i_1,\cdots ,i_n}{x}_1^{i_1}\cdots x_m^{i_n}.$$

(18)

Since $f(x_1,\cdots ,x_n)=\pm 1$, we have $|T_{i_1,\cdots ,i_n}|\le 1$. In fact, the expansion coefficients are given by

$$T_{i_1,\cdots ,i_n}=\frac{1}{2^n}\sum _{x_1,\cdots ,x_n=\pm 1}f(x_1,\cdots ,x_n)x_1^{i_1}\cdots x_n^{i_n}.$$

(19)

Now, consider the function $F_{G^e}(x_A,y_A;x_B,y_B)$; for convenience, we introduce the new variables ${\tilde{x}}_A={(-1)}^{x_A^{\prime }}$ and ${\tilde{x}}_B={(-1)}^{x_B^{\prime }}$. Using the expansion of Equation (18), the broadcast bits become

$$e_i=e_i({\tilde{x}}_i,y_i)=(T_{00}+T_{10}{\tilde{x}}_i)+(T_{01}+T_{11}{\tilde{x}}_i)y_i=c_i\left({\tilde{x}}_i\right)+d_i\left({\tilde{x}}_i\right)y_i,$$

(20)

where $|c_i\left({\tilde{x}}_i\right)|+|d_i\left({\tilde{x}}_i\right)|=1$ and $|c_i\left({\tilde{x}}_i\right)|,|d_i\left({\tilde{x}}_i\right)|=0,1$, with $i=A,B$. The inner product of Alice’s answer function with function $F_{G^e}$ can be defined as

$$\begin{array}{c}\hfill \langle {\mathrm{Ans}}_A,F_{G^e}\rangle =\sum _{\begin{array}{c}{x}_A,y_A,\hfill \\ x_B,y_B\hfill \end{array}}\frac{\mu (x_A,x_B)}{4}{\mathrm{Ans}}_A(x_A,y_A,e_B)F_{G^e}(x_A,y_A;x_B,y_B).\end{array}$$

(21)

Here, $\mu (x_A,x_B)/4$ is the probability distribution over the inputs. We see that when ${\mathrm{Ans}}_A(x_A,y_A,e_B)=F_{G^e}(x_A,y_A;x_B,y_B)$, they contribute $+1$ to the above summation; otherwise, they contribute $-1$. Note the fact that $1={\sum }_{x_A,y_A,x_B,y_B}\frac{\mu (x_A,x_B)}{4}$; the success probability for Alice to output the correct answer can thus be written as $p_{\mathrm{succ}}=\frac{1}{2}(1+\langle {\mathrm{Ans}}_A,F_{G^e}\rangle )$. Inserting the expression of $F_{G^e}$ and the expansion ${\mathrm{Ans}}_A(x_A,y_A,e_B)={\mathrm{Ans}}_A({\tilde{x}}_A,y_A,e_B)={\sum }_{j_{\tilde{x}}{j}_y{j}_e}{T}_{j_{\tilde{x}}{j}_y{j}_e}{\tilde{x}}_A^{j_{\tilde{x}}}{y}_A^{j_y}{e}_B^{j_e}$ into it, we obtain

$$p_{\mathrm{succ}}=\frac{{\sum }_{x_A,x_B}{(-1)}^{t(x_A,x_B)}(T_{011}+T_{111}{\tilde{x}}_A)d_B\left({\tilde{x}}_B\right)}{\left|E\right(G^e\left)\right|}.$$

(22)

From the definition of the expansion coefficients, we have $|T_{011}+T_{111}{\tilde{x}}_A| \le 1$. Using Bell inequality, for arbitrary functions $f\left(x_A\right)$, $g\left(x_B\right)$ with $|f\left(x_A\right)|,|g\left(x_B\right)|\le 1$, we have

$$\sum _{x_A,x_B}{\gamma }_{\langle x_A{x}_B\rangle }f\left(x_A\right)g\left(x_B\right)=\sum _{x_A,x_B}{(-1)}^{t(x_A,x_B)}f\left(x_A\right)g\left(x_B\right)\le \frac{B_C+\left|E\left(G\right)\right|}{2}.$$

(23)

Thus, the success probability must satisfy $p_{\mathrm{succ}}\stackrel{C}{\le }\frac{B_C+\left|E\left(G^e\right)\right|}{2\left|E\right(G^e\left)\right|}$. Since the protocol we gave before reaches the bound, it is the optimal classical protocol. Similarly for Bob, we can define $\langle {\mathrm{Ans}}_B,F_{G^e}\rangle$. From symmetry of the problem expression, the same result holds for Bob. For the n-party case, the proof is completely the same.

The proof here is similar in character to that in Ref. [10]. Another way to prove optimality is to use the traditional communication complexity theoretic approach, for which we first prove a lower bound of the deterministic protocol. Then, using a famous theorem [29]—which states that the communication complexity $R_{ϵ}\left(f\right)$ of the randomized protocol for computing the function f with error $ϵ$ has a relationship with the communication complexity $D_{ϵ}\left(f\right|\mu )$ of the deterministic protocol for computing the function f with error $ϵ$, for which inputs are distributed with $\mu$ as $R_{ϵ}\left(f\right)={max}_{\mu }{D}_{ϵ}\left(f\right|\mu )$—the lower bound of the deterministic protocol can be proved by assuming a protocol tree with a depth of 2 (for the two-party case) and discussing the partitions of the inputs by different nodes of the protocol tree.

4.2. Entanglement-Assisted Protocol

The quantum protocol works as follows: We take the two-party case as an example. Alice and Bob pre-share an entangled quantum state ${|\psi \rangle }_{AB}$, upon which Alice and Bob can choose $\pm 1$-valued observables $A_1,\cdots ,A_m$ and $B_1,\cdots ,B_n$ and obtain a violated value of Bell inequality corresponding to the experimental compatibility graph $G^e$. Now, if Alice and Bob receive input values $x_A=v_i$ and $x_B=u_j$, they can measure the corresponding observables $A_i$ and $B_j$ and output $a_A=a_i$ and $b_B=b_j$. Then, Alice and Bob broadcast the classical bits $e_A=y_A{a}_A$ and $e_B=y_B{b}_B$, respectively. After receiving the communicated bits, Alice and Bob both give their answers as ${\mathrm{Ans}}_A={\mathrm{Ans}}_B=e_A{e}_B$. The success probability is still Equation (15). We see that it can exceed the bound of classical protocol, thus exhibiting the quantum advantage.

For further clarification, let us first take $G_{2m-cycle}^e$ as an example (see Example 1). Suppose that Alice and Bob pre-share the singlet state $|{\psi }^{-}\rangle =\frac{1}{\sqrt{2}}\left(\right|01\rangle -|10\rangle ).$ The observables for Alice are $A_i={\mathbf{m}}_i·\mathbf{\sigma }$, where

$${\mathbf{m}}_i=(cos\frac{(2i-1)\pi }{2m},0,sin\frac{(2i-1)\pi }{2m}),i=1,\cdots ,m,$$

and for Bob, they are $B_j={\mathbf{n}}_j·\mathbf{\sigma }$, where

$${\mathbf{n}}_j=(cos\frac{j\pi }{m},0,sin\frac{j\pi }{m}),j=1,\cdots ,m.$$

With these measurements, Alice and Bob can achieve a success probability $p_{\mathrm{succ}}=\frac{cos\pi /2m+1}{2}$, which corresponds to the Tsirelson bound of the $2m$-cycle Bell inequality. We note that the success probability is a monotone increasing function, and when $m\to \infty$, it tends to 1.

Another example is $G_{2|3}^e$, as illustrated in Example 2. Alice and Bob still pre-share the singlet state, and Alice chooses to measure $A_1={\sigma }_x$ and $A_2={\sigma }_z$, while Bob chooses to measure $B_j={\mathbf{n}}_j·\mathbf{\sigma }$ with

$$\begin{array}{cc}\hfill & {\mathbf{n}}_1=(cos\frac{\pi }{4},0,cos\frac{\pi }{4}),\hfill \\ \hfill & {\mathbf{n}}_1=(cos\frac{3\pi }{4},0,cos\frac{3\pi }{4}),\hfill \\ \hfill & {\mathbf{n}}_3=(cos(\frac{\pi }{4}+\theta ),0,cos(\frac{3\pi }{4}+\theta )),\theta \ll 1.\hfill \end{array}$$

The optimal classical protocol can achieve a success probability of $5/6$. Here, the quantum protocol can almost reach the success probability of $(3\sqrt{2}+6)/12$ for sufficiently small $\theta$, which is greater than the success probability for the optimal classical protocol; thus, it exhibits a quantum advantage. Note that the above problem is closely related to the problem of simulation of nonlocal correlation via classical communication [33]. Our result here matches well with previous results that suggested that by two bits of classical communication, Bell nonlocal measurement statistics can be simulated.

4.3. Popescu–Rohrlich Box Protocol

Let us now consider a non-signaling world, which is beyond quantum mechanics. Suppose that Alice and Bob pre-share a black box such that for the positive edge $\langle ij\rangle$ of the experimental compatibility graph $G^e$, the probability distribution of outputs for measurements $A_i,B_j$ is

$$p(a_i,b_j|A_i,B_j)=\left\{\begin{array}{c}1/2,a_i{b}_j=1,\hfill \\ 0,a_i{b}_j=-1.\hfill \end{array}\right.$$

(24)

Additionally, for negative edges, the distribution is

$$p(a_i,b_j|A_i,B_j)=\left\{\begin{array}{c}0,a_i{b}_j=1,\hfill \\ 1/2,a_i{b}_j=-1.\hfill \end{array}\right.$$

(25)

This kind of black box is known as a Popescu–Rohrlich box [18] or a perfect nonlocal box. It can be easily confirmed whether the box satisfies the non-signaling principle.

With the help of the Popescu–Rohrlich box, we can reach a success probability of $p_{\mathrm{succ}}=1$. The protocol works in a similar manner to that of the entanglement-assisted protocol. After receiving the inputs $x_A^{\prime }=v_i$ and $x_B^{\prime }=u_j$, Alice and Bob choose to measure $A_i$ and $B_j$ jointly and output $a_i$ and $b_j$ with a probability of $p(a_i,b_j|A_i,B_j)$. After many runs of the experiment, Alice and Bob check their success probability. It is obvious from Equation (15) that for the Popescu–Rohrlich box, the success probability is $p_{\mathrm{succ}}=1$. This matches well with the result in Refs. [34,35], which states that using a perfect nonlocal box can make CCP trivial for arbitrary Boolean function.

5. Conclusions and Discussions

Identifying the bound of classical theory and quantum theory is of great importance for understanding the nature of our universe. In this work, we attempt to gain a better understanding of the problem from a communication complexity theoretic perspective. By restricting the classical communications, two parties can calculate a given function with different success probabilities; this shows that the strength of quantum correlations is much stronger than that of the classical one. These results shed new light on the bound between classical and quantum worlds. From a practical point of view, our result provides a method to construct a CC function from an arbitrary given experimental compatibility graph or hypergraph. When the graph is a bipartite graph, it gives a two-party CC function, and when the graph is multipartite, it gives a multi-party CC function. Our construction may have potential applications in practical CC problems where quantum advantages from Bell nonlocality need to be extracted.