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 nonlocal 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.
