All quantum communication involves nonlocality

5 April 2016

Harry Buhrman, professor in Computer Science at the UvA and director of the research center Qusoft, has proven with colleagues from several international universities that quantum communication is based on nonlocality. They show that whenever quantum communication is more efficient than classical communication, it must be possible to find a nonlocal correlation somewhere. The article 'Quantum communication complexity advantage implies violation of a Bell inequality’, appeared in this month's issue of the influential journal PNAS.

It has long been known that quantum mechanics predicts counterintuitive effects such as instantaneous interaction at a distance between far-apart entangled particles. This teleportation effect, which Albert Einstein famously called ‘spooky action at a distance’, was long thought to show that the theory of quantum mechanics was incomplete. However, in 1964 physicist J.S. Bell proved that no theory involving the principle of locality can ever reproduce all predictions of quantum mechanics. In other words: it is impossible to find classical explanations for quantum correlations. This evidence for the existence of nonlocality became known as Bell’s inequality.

Quantum advantage

For a long time the existence of quantum correlations was merely of interest to philosophically minded physicists, and was considered an exotic peculiarity, rather than a useful resource for practical problems in physics or computer science. This has changed dramatically in recent years. Quantum correlation proved to be very useful in information processing. In several communication tasks, using quantum effects substantially reduced the communication complexity: the minimum number of steps necessary to complete a certain task between two parties. In such cases, there is a so-called quantum advantage in communication complexity.

It has been suspected that all advantages in quantum communication are ultimately based on violations of Bell’s inequality, and are therefore a result of nonlocal correlations. Until now, violations of Bell’s inequality were only proven for a handful of quantum protocols. In their PNAS paper, the researchers now provide a universal method which derives a violation of Bell’s inequality in every case in which there is a (sufficiently large) quantum communication advantage. This result is an important step in quantum communication theory, and deepens the understanding of the link between non-locality and quantum communication protocols.


Quantum computing research is concentrated in the QuSoft research institute, which is a joint initiative of CWI, UvA and VU. The mission of QuSoft is to develop new protocols, algorithms and applications that can be run on small and medium-sized prototypes of a quantum computer. The main focus of the center is on the development of quantum software, which requires fundamentally different techniques and approaches from conventional software.

Publication details

Harry Buhrman, Łukasz Czekaj, Andrzej Grudka, Michał Horodecki, Paweł Horodecki, Marcin Markiewicz, Florian Speelman, and Sergii Strelchuk: 'Quantum communication complexity advantage implies violation of a Bell inequality' in PNAS 2016 113 (12) 3191-3196; published ahead of print March 8, 2016, doi:10.1073/pnas.1507647113

Source: CWI

Published by  Faculty of Science