Elham Kashefi
(University of Edinburgh)
Quantum Turing Test

A fundamental goal in quantum information processing is to test a machine's (or more generally nature's) ability to exhibit quantum behaviour. The most celebrated result in this domain, which has been also demonstrated experimentally, is the celebrated Bell Theorem that verifies the non-local nature of quantum mechanics. Could we generalise such approaches to verify that a given device is in fact taking advantage of quantum mechanics rather than being a disguised classical machine. Considering the exponential regime of quantum mechanics, the issue of efficiency of such tests are the key challenge from the complexity point of view. On the other hand, from the foundational point of view, it is an intriguing open question whether a fully classical scheme could verify any quantum properties of a larger system while being experimentally feasible. We present some recent progress towards this direction that has also surprising consequences on an entirely different open question, the existence of fully homomorphic encryption schemes.