Quantum Correlations and Quantum Communication Complexity

Compared with classical physics and our everyday experience, the quantum world is highly counterintuitive. A pair of quantum systems can be entangled such that even if they are kilometres apart, they remain correlated stronger than any two classical objects could ever be - the feature referred to as "quantum non-locality" and quantified by violation of Bell's inequalities. Even though quantum non-locality does not allow us to send information faster than the speed of light, it surprisingly can produce effects as if information had been transferred: it can save on classical communication when remote partners need to jointly perform a task that none of them can perform individually due to lack of the input data of other partners. Nowadays, quantum non-locality, just like energy, is increasingly recognized as a precious resource for saving communication, i.e. for reducing "communication complexity". Any progress in this area will have a tremendous impact on future attempts to further minimize microchip area or optimize computer networks.
In this project we will push the current understanding of potentials and limits of quantum non-locality as a resource for reduction of communication complexity. In particular, we will combine theoretical studies on quantum correlations with information science to develop real-life relevant communication tasks for which there is a significant, potentially exponential, quantum advantage over any classical solution. The proposed research will also exploit new multi-partite quantum non-locality schemes towards the still lacking first experimental demonstration of quantum communication complexity, which takes into account experimental imperfections and is based on entanglement. The envisioned results of this research will develop the field of quantum communication complexity to become comparable with quantum key distribution - the only commercial application of quantum information processing thus far. In turn, they will yield a new outlook on foundations of quantum mechanics.