Implications of computer science principles for quantum physics

Abstract

The Church-Turing thesis is one of the pillars of computer science; it postulates that every classical system has equivalent computability power to the so-called Turing machine. While this thesis is crucial for our understanding of computing devices, its implications in other scientific fields have hardly been explored. What if we consider the Church-Turing thesis as a law of nature? In this talk I will present our first results in connection with quantum information theory [1] by showing that computer science laws have profound implications for some of the most fundamental results of quantum theory.  First I will show how they question our knowledge on what a mixed quantum state is, as we identified situations in which ensembles of quantum states defining the same mixed state, indistinguishable according to the quantum postulates, do become distinguishable when prepared by a computer (or any classical system). Then I will introduce a new loophole for Bell-like experiments: if some of the parties in a Bell-like experiment use a computer to decide which measurements to make, then the computational resources of an eavesdropper have to be limited in order to have a proper observation of non-locality.