Quantum 1, classical 0: Bell nonlocality universally confirmed in any large communication complexity advantage

(Phys.org)—The relationship between communication complexity problems, Bell nonlocal correlations and the advantage of quantum over classical strategies has long been recognized, but has been confirmed in only two problems. Recently, however, scientists at University of Cambridge, University of Amsterdam, CWI, QuSoft, Gdansk University, Gdansk University of Technology, Adam Mickiewicz University, and Jagiellonian University employed a two-part method based on port-based teleportation – a scheme of quantum teleportation where a receiver has multiple (N) output ports and obtains the teleported state by merely selecting one of the N ports^1,2. The researchers used the quantum protocol based on the given communication complexity game to construct a set of quantum measurements on a maximally entangled state to show that any large advantage over the best known classical strategy makes use of Bell nonlocal correlations. In so doing, the researchers assert, they have provided the missing link to the fundamental equivalence between Bell nonlocality and quantum advantage. Moreover, their results have significant implications for classical information processing and the development of more efficient teleportation protocols.

Dr. Sergii Strelchuk discussed the paper, "Quantum communication complexity advantage implies violation of a Bell inequality," that he and his colleagues published in Proceedings of the National Academy of Sciences. Two of the challenges the scientists faced were encountered in demonstrating that any large advantage over the best known classical strategy makes use of Bell nonlocal correlations, and in providing the "missing link" (in the form of a general connection) between a large quantum advantage in communication complexity and Bell nonlocality. "One conceptual issue was finding a procedure that converts any quantum strategy for a given communication complexity problem into a set of correlations – that is, probability distributions corresponding to the measurement outcomes during the protocol," Strelchuk tells Phys.org. "If the quantum algorithm performance beats the best known classical algorithm, these correlations violate a specially tailored Bell inequality that certifies that we indeed make use of nonlocal correlations in our algorithm." He adds that prior to their work, there were just a few instances of this conversion – and moreover, these only worked for very specific problems. "In this study we've found a universal method which works for any algorithm."

Another obstacle was using port-based teleportation to show that if the gap between quantum and classical communication complexity grows arbitrarily large, the ratio of the quantum value to the classical value of the Bell quantity becomes unbounded with the increase in the number of inputs and outputs. "The ratio of Bell quantities indicates the extent to which quantum strategies outperform their classical counterparts." Strelchuk notes. "With the help of recently-discovered port-based teleportation we estimate this ratio and consequently connect two distinct notions: performance of a strategy for the communication complexity problem and violation of the Bell quantity."

To establish the connection between communication complexity and the violation of a Bell inequality, the scientists had to devise two things: a systematic way of obtaining correlations from any quantum strategy, and a suitable Bell inequality which would be violated by these correlations. "A particular obstacle which we had to overcome was to find a way of dealing with strategies which involved multiple rounds of communication, since previous tools allowed us to address only the case of single round algorithms," Strelchuk explains. "Our key insight was to utilize a port-based teleportation protocol, which overcame this limitation wonderfully."

Several of the study's results have implications for classical information processing. In one case, the paper reports that quantum correlations distinguish classical from quantum information theory in the context of more recent findings that quantum correlations can be used as a resource for a number of distributed information processing tasks, producing surprising results – specifically when applied to communication complexity. "There are several problems in computer science in which quantum algorithms outperform their classical counterparts," Strelchuk points out. "Such algorithms make use of entanglement – a resource not available in classical information theory. In certain models of multiparty communication complexity – a scenario where many parties exchange messages to compute the value of some function—quantum algorithms may be exponentially more efficient; however, in some cases quantum algorithms do not offer any speedup. It is therefore important to investigate the problems for which it actually makes sense to use the quantum resources in order to achieve to improvements over the best possible classical algorithms."

The paper also reports a simpler method for one-way communication complexity problems. "For one-way communication complexity problems – that is, where in order to compute the value of a function one party is allowed to send a single message to another – there is no need to use the heavy guns of port-based teleportation. Instead, we use a much simpler procedure called remote state preparation." Quantum teleportation uses prior entanglement and forward classical communication to transmit one instance of an unknown quantum state. Remote state preparation (RSP) has the same goal, but the sender knows classically what state is to be transmitted.

Relatedly, the paper describes potential approaches for devising a more efficient teleportation protocol or improving one of the existing ones based on more efficient methods of exhibiting the Bell nonlocality of quantum communication complexity schemes. "One potential pathway to improvement is to devise a more efficient teleportation protocol. Our central tool, the port-based teleportation protocol, uses a large entangled state to teleport with a high probability of success. Moreover, a teleportation protocol with higher probability of success which consumes less entanglement would result in even larger values of the ratio of the quantum value to the classical value of the Bell quantity – but at present, we don't know if such protocols exist."

Finally, the new method does not cover the protocols with initial entanglement, which the researchers describe as paradoxical because protocols that use initial entanglement should be even more explicitly Bell nonlocal. "Interestingly, if the parties which solve a communication complexity problem are already entangled then it should be possible to devise a Bell inequality that will be violated by the correlations originated from the measurement statistics of the algorithm. However," Strelchuk adds, "a technical requirement in our construction makes it inapplicable to this setting." As a result, the scientists concluded that it is desirable to search for a method of demonstrating the Bell nonlocality of such protocols. "Devising a method of showing that quantum communication complexity advantage implies violation of a Bell inequality when parties share initial entanglement is highly desirable," he acknowledges, "as it would not only prove the equivalence between these two areas at the highest possible level of generality, but it may also shed light on how we could take advantage of pre-shared entanglement to make algorithms more efficient."

Moving forward, Strelchuk says that the researchers want to focus on reducing the gap between classical and quantum communication complexity required for their results to hold. "This gap arises as a technical artifact in our proof," he tells Phys.org, "and there seems to be no apparent reason why it should exist. Another promising direction to pursue is the development of novel teleportation protocols which would consume less entanglement and provide higher probability of success…and the latter direction is interesting in its own right. As witnessed by our results," Strelchuk concludes, "the applications of new teleportation protocols often surpass their intended purpose and find uses in other unrelated areas of quantum information processing."

© 2016 Phys.org