1. Introduction

Communication complexity studies the amount of communication required to solve a global computational task when the inputs are distributed locally between two or among more remote participants [1]. A typical instance of a communication complexity problem features two participants, Alice and Bob, who are given binary input strings $x$ and $y$, respectively. Their common goal is to obtain the value of some function or relation $f(x,y)$. As initially neither participants have any knowledge of the other’s input, some communication will have to take place between the participants to achieve their goal. From both a practical and a conceptual point of view, there is an urgent need to develop effective communication protocols to reduce complexity, i.e., either by minimizing the amount of information exchange necessary to reach the correct value of $f(x,y)$ certainly [2–4], or by maximizing the probability of guessing $f(x,y)$ correctly with a restricted amount of communication [5,6]. Such studies have wide applications in speeding up distributed computing or optimizing very-large-scale interaction circuits and data structures [7].

Depending on the resources available to the participants, their communication may involve sending classical messages or quantum information. It is known that quantum protocols with quantum resources, such as entanglement and quantum channel, can be superior to the corresponding classical counterparts in communication and computing [8,9]. The quantum communication complexity protocol was first introduced by Yao, where the remote participants are allowed to send information to each other in the form of the qubits [10], then developed to entanglement bits by Cleve and Buhrman [11]. They found that using quantum entanglement can save one bit out of classical communication. In order to extend quantum-classical separation, lots of multi-party high-dimensional complex communication protocols have been proposed [12–15]. And the exponential quantum superiority can be observed when the given communication problem is a Boolean function [16–21].

Considering the different communication scenarios in practice, the reduction of quantum communication complexity has been experimentally demonstrated in the one-way protocol, where the involved participants are only allowed to send messages in one direction, after which the last participant announces the output [22–25]; in the two-way protocol where the involved participants take turns sending messages to each other [26–28]; and in the simultaneous protocol where the involved participants cannot communicate directly with each other but send messages to a "referee" instead, who announces the output based on the received messages [29,30]. However, these reported works are mainly discussed under the error-free condition. The laboratory demonstrations so far only take the non-maximally entangled state and limited detection efficiency into account [31–33]. Experimentalists, on the other hand, know that even the simplest quantum communication complexity protocols involve inefficiencies in state preparation, transmission and measurement. Unfortunately, most quantum communication complexity protocols are extremely sensitive to noise; thus, any imperfections in these processes need to be considered, especially the commonly existing measurement imperfections: measurement basis deviation and choice probability bias [34,35].

Many protocols have been developed to improve the precision of quantum measurement [36–38], to address measurement basis mismatch [39], and to improve the overall robustness [40–44]. These approaches, however, require entanglement sources or well-established technology, which have certain limitations in practical applications. In this paper, we mainly investigate how measurement imperfections affect the quantum communication complexity superiority. We propose a generalized entanglement-assisted communication complexity protocol based on a biased Clauser-Horne-Shimony-Holt (CHSH) game [45,46], then theoretically and experimentally investigate the effects of measurement imperfections on the performance of the protocol in terms of the deviated measurement basis and biased basis choice probability. The dependence of the success probability on the measurement basis and basis choice parameters is analyzed. And the optimal parameters are discovered, which make the quantum communication complexity superiority decreases slowest. The robustness of effective measurement were also investigated by considering the effects of imperfect entangled state as well as dephasing and depolarizing quantum channels. Our work may promote a deeper understanding of the relationship between quantum communication complexity superiority and measurement, and could even find some relevant real-world applications. The structure of the rest of this paper is as follows. In Sec. II, we present the generalized entanglement-assisted communication complexity protocol. The experimental details and results are present in Sec. III. Finally, we present the conclusion and some discussion in Sec. IV

2. Generalized entanglement-assisted communication complexity protocol

Consider the following two-participant communication complexity protocol based on a biased Clauser-Horne-Shimony-Holt (CHSH) game [45,46]. A two-qubit entangled state $\vert \psi (\theta )\rangle ={\rm cos}\theta \vert HH\rangle +{\rm sin}\theta \vert VV\rangle$ is shared between Alice and Bob. They are remote enough so that no signal can travel while the experiment is being performed. Alice receives a biased binary input string $x=x_{0}x_{1}\in \lbrace 0,1 \rbrace ^{2}$ with probability distribution $P(x_{0}=0)=p$ $( 0\leq p\leq 1)$ and $P(x_{0}=1)=(1-p)$. Similarly, Bob receives another biased binary input string $y=y_{0}y_{1}\in \lbrace 0,1 \rbrace ^{2}$ with probability distribution $P(y_{0}=0)=q$ $( 0\leq q\leq 1)$ and $P(y_{0}=1)=(1-q)$. Their task is to collectively determine the value of the Boolean function

To increase the success probability, they can use the following measuring strategy: If $x_{0}=0$, Alice measures $A_{0}$; otherwise, she measures $A_{1}$. The identifications are similar for Bob’s measurements $B_{0}$ and $B_{1}$. Suppose the measurement outputs of Alice and Bob are denoted as $a\in \lbrace 0,1 \rbrace$ and $b\in \lbrace 0,1 \rbrace$. After each round of measurement, Alice sends $x_{1} \oplus a$ to Bob and receives $y_{1}\oplus b$ from him. Then, each of them can determine the value of $(x_{1} \oplus a)\oplus (y_{1}\oplus b)$ which equals to $f(x,y)$ as long as $a\oplus b=x_{0}\wedge y_{0}$. Therefore, in this protocol, Alice and Bob can successfully accomplish the task mentioned above with probability

In the case of unbiased choice probability measurements where $p=q=1/2$, for an arbitrary entangled state in the form of $\vert \psi (\theta )\rangle$, the success probability can achieve the maximum value $(2+\sqrt {1+C^{2} })/4$ with $\theta \in [ 0, \pi /2]$ and

While in the case of biased choice probability measurement where $p\neq 1/2$ or $q\neq 1/2$, the maximum average success probability equals to $(1/2+ \sqrt {(q^{2}+(1-q)^{2})(p^{2}+(1-p)^{2})/2}$ for $1/2\leq (2q)^{-1} \leq p\leq 1$; and equals to $1-(1-p)(1-q)$ for $1\geqslant p\geqslant 1/(2p)\geqslant 1/2$. Both of them are achieved at $\theta =\pi /4$ and

 

Fig. 1. Generalized entanglement-assisted communication complexity protocol. Alice and Bob receive biased input strings $x=x_{0}x_{1}\in \lbrace 0,1 \rbrace ^{2}$ and $y=y_{0}y_{1}\in \lbrace 0,1 \rbrace ^{2}$ to decide their specific measurement. After each round of measurement, they send one bit information $x_{1}\oplus a$ and $y_{1} \oplus b$ to each other to check whether the relation $a\oplus b=(x_{0}\wedge y_{0})$ is satisfied. If the relation is satisfied, they can successfully determine the correct value of the function $f(x,y)=x_{1}\oplus y_{1}\oplus (x_{0}\wedge y_{0})$; otherwise, they can not. The entangled state shared between them is used to improve the success probability.

Download Full Size | PDF

3. Experimental setup and results

Figure 2 shows our experimental setup. A 405 nm continuous-wave diode laser is used to pump a 10 mm long periodically poled potassium titanyl phosphate (PPKTP) crystal inside a polarization Sagnac interferometer clockwise and counter-clockwise to generate a class of two-qubit polarization-entangled states ${\rm cos}\theta \vert HH\rangle +{\rm sin}\theta \vert VV\rangle$ [47]. The parameter $\theta$ is flexibly controlled by the half-wave plate (HWP, H0) after the first polarization beam splitter (PBS). The generated photons are filtered by an interference filter centered at 810 nm with a bandwidth of 3 nm (IF@810), then separated by a PBS.The signal photon is sent to Alice. The idler photon passes through a qubit Pauli channel for state preparation and is sent to Bob. The qubit Pauli channel consists of two semi-circular HWPs (H1 and H1). By changing the axes and action time of these HWPs, we can simulate the noiseless, dephasing or depolarizing quantum channel as desired. To accomplish the communication complexity task, Alice and Bob select some measurements acting on their own photon, which can be easily realized by using the combination of motorized wave plates (quarter-wave plate (QWP), HWP) and PBS. Two single-mode fibers collect the photons and bring them to the single-photon avalanche diodes. The detected electronic signals are sent to a coincidence logic unit within a 3 ns window and integrated over an exposure time of 3 s. The total number of coincidences in this time and for each measurement choice is approximate $3\times 10^{6}$, sufficient to make the statistical errors small.

 

Fig. 2. (a). Experimental setup. A pair of photons in a state $\vert \psi (\theta )\rangle$ is generated via the spontaneous parametric down-conversion process by pumping a type-II cut PPKTP crystal located in a Sagnac interferometer with an ultraviolet laser at 405 nm. A half-wave plate (HWP, H0) in front of the laser is used to control the parameter $\theta$. These two photons are filtered by interference filters (IFs). One of the photons is sent to Alice directly, the other to Bob through a qubit Pauli channel. The polarization analyzer consisting of motorized wave plates and a polarization beam splitter (PBS) on both sides is used for different measurement settings. The photons are detected by single-photon detectors, and the signals are sent for coincidence. (b). The structure of H1 and H2. (c). Implementation of qubit Pauli channel. $T$ is the repetition time, $\tau _{1}$, $\tau _{2}$ and $\tau _{3}$ represent the time intervals of $\sigma _{1}$, $\sigma _{2}$ and $\sigma _{3}$ activation, respectively. The total Pauli operator time $\tau =0$ corresponds to noiseless channel ($I$), $\tau _{1} =\tau _{2} =0$ and $\tau _{3}>0$ corresponds to dephasing channel, $0<\tau _{1} =\tau _{2} =\tau _{3}<T/3$ corresponds to depolarizing channel.

Download Full Size | PDF

First, we investigate the effect of measurement basis deviation on the performance of quantum complexity protocol in the unbiased choice probability case. We measure the success probability $P_{Q}$ for several values of measurement basis parameters $\eta _{1}$ and $\eta _{2}$ with the maximally entangled state. Experimentally, we increase $\eta _{1}$ and $\eta _{2}$ from $0$ to $\pi$ at intervals of $\pi /16$. As shown in Fig. 3 (a) and Fig. 3 (b), the experimental data (dots) are compared with theoretical expectations (surfaces and lines), showing a good agreement. Obviously, the success probability can outperform the optimal classical bound for certain region of measurement basis (the red region above the yellow plane). And the maximum success probability is expected to be $(2+\sqrt {2})/4$ in the maximally entangled state case, which can be obtained by adopting some optimal measurement parameters, such as $\eta _{1}=7\pi /16$ and $\eta _{2}=11\pi /16$ (marked as a green star in (b)). As the measurement basis parameters $\eta _{1}$ and $\eta _{2}$ deviate from the optimal setting, the success probability $P_{Q}$ decreases and reaches the minimum value $1/4$ at some worst measurement parameters, such as $\eta _{1}=3\pi /16$ and $\eta _{2}=7\pi /16$ (marked as a blue square in (b)). Since the line segment between two points is the shortest, the rate of change in that direction is the largest. Therefore, we chose $\eta _{2}$ as the linear function of $\eta _{1}$ to study the effect of measurement basis deviation on the average success probability. Figure 3 (c) and Fig. 3 (d) respectively present the variation of the corresponding maximum and minimum success probability with the basis parameter $\eta _{1}$, where $\eta _{2}=K*\eta _{1}+B$. The brown, orange and red lines correspond to $K=5$, $K=1$, and $K=1/5$. It clearly shows the $K$ gets smaller, the success probability changes slower. And the situation is similar when the measurement basis deviates located in the region close to the extreme value. Since entanglement is a fragile resource, we first analyze the robustness of the effective measurement basis by changing the degree of entanglement of the shared state. Figure 4 (a) presents the distribution of $P_{Q}$ with different values of $\eta _{1}$ and $\eta _{2}$ in a period when the shared state is a non-maximally entangled pure state. Here, we use concurrence as a measure of entanglement, which can be obtained by quantum state tomography. The regions enclosed by the red curve and blue curve correspond to the effective range of $\eta _{1}$ and $\eta _{2}$ that can obtain higher-than-classical success probability when state concurrence $C=0.5358\pm 0.004$ and $C=0.9729\pm 0.003$, respectively. The light yellow region represents the disappearance of quantum superiority in both cases. In our experiment, $\eta _{1}$ increases from $4\pi /16$ to $12\pi /16$ and $\eta _{2}$ increases from $3\pi /16$ to $13\pi /16$, with an interval of $\pi /16$. The experimental data are marked as blue dots, red dots, and black stars in the corresponding regions, respectively. It is clear that, for a given concurrence, it is possible to obtain success probability beating the classical limit for certain region of measurement basis parameters. And the larger concurrence, the wider is the effective measurement basis parameters region, the stronger the robustness. In addition, with the optimal measurement setting described by Eq. (4), we can obtain the maximum quantum success probability, which is marked as the blue dot in Fig. 4(b). It clearly shows the superiority of communication complexity emerges when the shared state is entangled, increasing with state concurrence. For the maximum experimental entangled state $C=0.9729\pm 0.003$, the success probability $P_{Q}$ reaches the maximum value $0.8456\pm 0.0004$, about $239$ standard deviations above the optimal classical bound. We also investigate the robustness of the effective measurement basis by considering the effects of dephasing channel and depolarizing channel, respectively. These noise channels can be simulated by a sequence of two semi-circular HWPs (H1 and H2), as shown in Fig. 2(b). By a suitable control of their axes, H1 and H2 are set to act either as $\sigma _{1}$, $\sigma _{2}$ or $\sigma _{3}$. And we could also adjust the activation time $\tau _{1}$, $\tau _{2}$ and $\tau _{3}$ of the corresponding Pauli operators through remote control, as shown in Fig. 2(c). The condition $\tau _{1}= \tau _{2}=0$ corresponds to the depolarizing channel with the noise parameter $p_{d}=\tau _{3} /T$, $T$ represents the repetition time. It maps the initial state $\rho (\theta )= \vert \psi (\theta )\rangle \langle \psi (\theta ) \vert$ into $\varepsilon (\rho (\theta ))=(1-\dfrac {p_{d}}{2})\rho (\theta )+\dfrac {p_{d}}{2} (I\otimes \sigma _{3})\rho (\theta )(I\otimes \sigma _{3})$. And the condition $\tau _{1}= \tau _{2}= \tau _{3}$ corresponds to the depolarizing channel with $p_{d}=(\tau _{1}+\tau _{2}+ \tau _{3}) /T=\tau /T$, it maps the initial state $\rho (\theta )$ into $\varepsilon (\rho (\theta ))=(1-p_{d})\rho (\theta )+\dfrac {p_{d}}{3}((I\otimes \sigma _{1})\rho (\theta )(I\otimes \sigma _{1})+(I\otimes \sigma _{2})\rho (\theta )(I\otimes \sigma _{2})+(I\otimes \sigma _{3})\rho (\theta )(I\otimes \sigma _{3}))$. We increase $p_{d}$ from $0$ to $1$ with an interval of $0.1$ by fixing the Pauli operator activation time and varying the repetition time. The maximum quantum success probability $P_{Q}$ and concurrence $C$ of state $\varepsilon (\rho (\theta ))$ as function of $p_{d}$ in the case of $\theta =\pi /4$ is shown in Fig. 5. It clearly shows with the increase of the noise, the quantum superiority disappears slower in dephasing channel, indicating that the effective measurement basis is more robustness to the dephasing noise. Notably, unlike the entangled pure state case, the quantum superiority in dephasing and depolarizing channels may disappear even the state concurrence greater than zero. This is because there are mixed states that are entangled but do not violate the CHSH inequality.

 

Fig. 3. The influence of measurement basis on the success probability with the maximally entangled state. (a). The 3D plot of success probability $P_{Q}$ as functions of measurement basis parameters $\eta _{1}$ and $\eta _{2}$. (b). The contour map of (a). (c). $P_{Q}$ varies with $\eta _{1}$, which starts from an optimal measurement setting ($\eta _{1}=7 \pi /16$ and $\eta _{2}=11\pi /16$, marked as a green star in (b)) to other optimal measurement settings along three directions (dotted lines of the same color in (b)). (d). $P_{Q}$ varies with $\eta _{1}$, which starts from a worst measurement setting ($\eta _{1}=3\pi /16$ and $\eta _{2}=7\pi /16$, marked as a blue square in (b)) to other worst measurement settings along three directions (lines of the same color in (b)). The experimentally obtained success probabilities are shown as markers, while the theoretical predictions are also represented as surfaces and lines. The errors in $P_{Q}$ are obtained by performing 50 Monte Carlo simulation runs by taking into account of the Poisson photon counting statistics. The error bars are too small to be visible.

Download Full Size | PDF

 

Fig. 4. The influence of measurement basis deviation on the success probability with different entangled pure states. (a). The success probability distribution as functions of measurement basis parameters $\eta _{1}$, $\eta _{2}$ and state concurrence $C$. The light red region represents the success probabilities larger than the optimal classical bound when $C =0.5358\pm 0.004$. It extended to the light blue region when $C$ increased to $C= 0.9729\pm 0.003$. The light yellow region represents the case for which the success probability is smaller than the optimal classical bound even $C= 0.9729\pm 0.003$. The blue dots, red dots, and black stars in the corresponding regions are the experimental success probabilities. (b). The maximum success probability $P_{Q}$ as a function of state concurrence $C$. Red line and blue dots are theoretical and experimentally obtained values, respectively. The horizontal yellow dashed line denotes the optimal classical bound. Error bars are estimated by the Poissonian statistics of two-photon coincidences, which are too small to be visible.

Download Full Size | PDF

 

Fig. 5. The robustness of effective measurement basis in dephasing channel (a) and depolarizing channel (b). Red and purple lines and markers are theoretical and experimentally obtained values of maximum success probability $P_{Q}$ and state concurrence $C$, respectively. The horizontal yellow dashed line denotes the optimal classical bound. Error bars are estimated by the Poissonian statistics of two-photon coincidences, which are too small to be visible.

Download Full Size | PDF

We further measure the influence of biased measurement choice probability on the success probability with the maximally entangled state. As shown in Fig. 6(a), there is good agreement between the experimental result of success probabilities and the theoretical predictions. The quantum superiority can be observed inside the region enclosed by the black dashed curves, and the maximum success probability can be achieved when Alice and Bob adopt unbiased choice measurements, i.e., $p=q=1/2$. Figure 6(b) plots the difference between quantum and classical success probability $\Delta P= P_{Q} -P_{C}$ as functions of $p$ and $q$. It clearly shows that with the increase of the biasness of the measurement basis choice probability, both the quantum and classical success probability increase, but the value of the quantum-classical difference decreases. And the quantum superiority disappears slowest when $p=1/2$ or $q=1/2$ and fastest when $p=q$.

 

Fig. 6. The influence of biased measurement basis choice probability on the success probability. (a). The contour plot of success probability $P_{Q}$ as functions of measurement basis choice probability parameters $p$ and $q$. (b). The 3D plot of the difference between the quantum and classical success probability $\Delta P= P_{Q} -P_{C}$ versus $p$ and $q$. The black dashed curves in (a) and the white curves in (b) represent the boundary of existing quantum superiority, inside which quantum strategy can perform better than the best classical strategy. Experimentally obtained success probabilities are shown as dots. Theoretical predictions are also represented as surface plots and curves compared with the experimental data. Error bars are estimated by the Poissonian statistics of two-photon coincidences, which are too small to be visible.

Download Full Size | PDF

4. Conclusions

In conclusion, we propose a generalized entanglement-assisted communication complexity reduction protocol and comprehensively investigate the effects of measurement basis deviation and choice probability bias on quantum superiority. We find that when the participants share a specific entangled state, the quantum success probability is not always greater than the maximum classical success probability. The maximum quantum success probability can be achieved by using an optimal measurement setting and increases as the entanglement degree of the shared state increases. In addition, we find the measurement basis approximates the optimal measurement region, or the biased basis choice probability appeared only on one side; the quantum superiority is relatively insensitive to such imperfections. These results can enhance the test of quantum communication complexity, and can also be applied to other scientific experiments, such as the fundamental tests of nonlocal correlation [48,49] and quantum random access code [50,51].