Dr. Elham Kashefi Explores the 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 the efficiency of such tests is 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. Kashefi presents some recent progress towards this direction that also has surprising consequences on an entirely different open question, the existence of fully homomorphic encryption schemes. Presented by Dr Elham Kashefi, School of Informatics, the University of Edinburgh. Recorded on Friday 11 May 2012 at the Informatics Forum, The University of Edinburgh. The Turing Research Symposium was organised by the Royal Society of Edinburgh and the University of Edinburgh School of Informatics in partnership with SICSA and supported by Cambridge University Press.