Quantum non-locality, computation and cryptography – NLQCC

According to the laws of quantum mechanics, it is possible to entangle two particles such that even if one is taken away from the other, it is not possible to describe the state of each one independently of the other. This strange phenomenon, called quantum non-locality, is at the heart of the debates on the validity and on the possible interpretations of quantum physics for more than eighty years.
The advent of quantum computing in the mid-nineties led to a resurgence of research on quantum non-locality. Quantum entangled states have quickly been identified as a crucial element for quantum computation, communication or cryptography. More recently, the idea that studying the computational power and limits of quantum entangled states informs us, in return, on the underlying physics, grew to become an important sub-area of quantum information.
Our project focuses on a specific aspect of this question. It investigates the consequences of quantum non-locality on cryptography and computation. In various contexts, we will apply techniques inspired from computer science to gain better knowledge of foundations of quantum physics.
Quantum systems are particularly well suited to generate randomness. However, formally proving the security of quantum random number generation protocols is a subtle problem. The reason is that this cryptographic task captures deep properties of quantum physics. Specifically, the question of completeness of quantum physics can be completely rephrased in cryptographic terms. This observation led to a large amount of work on this specific task over the last years.
The first part of our project aims to establish a complete theory of random number generation using quantum systems. We will study this task in different adversarial scenarios, each one related to different physical properties. We will look for quantitative relations between cryptographic security and the underlying physical properties. The goal is to give new operational and quantitative interpretations of quantum non-locality. In particular, we will seek for quantitative relations between the amount of violation of Bell's inequality and cryptographic security.
Our approach is based on tools provided by theoretical computer science. Applying these in a new context, we hope to get, in return, a better understanding of the tools themselves. In particular, communication complexity is a very important model in computer science. Using this model seems relevant in our context to handle the information leaked during the execution of quantum cryptographic protocols.
Finally, we will search for new applications of the techniques that we will develop to investigate the information theoretic foundations of quantum physics. In a number of different contexts, two adversaries collaborate during a computation, but without trusting each other. Our project will indirectly lead to a better understanding of this situation.