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.

One of the most deeply rooted concepts in science and in our everyday life is causality: the idea that events in the present are caused by events in the past and, in turn, act as causes for what happens in the future. It appears naturally that if an event A is a cause of an effect B, then B cannot be a cause of A. According to quantum mechanics, however, objects can lose their well-defined classical properties, for example, when it is not possible to say whether a particle is at one or at the other location. If quantum mechanics governs all phenomena, one might suspect that the order of events could also be indefinite, similarly to the location of a particle. Our team was able to develop a quantum framework that does not presume a fixed background causal structure and allows for correlations in which events are neither causally ordered nor in a probabilistic mixture of definite causal orders, i.e. one cannot say that event A is before or after event B. We have shown both theoretically and experimentally, that quantum devices taking advantage of such underlying indefinite causal structure can solve certain problems more efficiently than any quantum computer with a fixed order of gates.