Researchers of CWI, University of Gdansk, Gdansk University of Technology, Adam Mickiewicz University and the University of Cambridge have proven that quantum communication is based on nonlocality. They show that whenever quantum communication is more efficient than classical communication, it must be possible find a nonlocal correlation somewhere. Their paper ‘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 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.
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.