The study of quantum computation teaches us that quantum mechanics (QM)
exhibits exponential computational complexity; it is the only
computational model that credibly challenges the extended ChurchTuring
thesis. As I will argue in my talk, a simple
but thoughtprovoking corollary is that the standard scientific paradigm
of "predict and verify" cannot be applied to testing the physical theory
of QM in the limit of exponential computational complexity; this raises
the question of whether those important aspects of QM are falsifiable.
In the talk I will explain the ingredients required to understand the
above question, including the model of quantum computation, and the
extended Church Turing thesis; I will then describe how QM can after all
be tested in the high complexity regime by extending the usual
scientific paradigm to include /interactive experiments/. The extension
of the scientific paradigm to include the power of interaction is
inspired by the idea of "interactive proofs" which is central in modern
theoretical computer science; the intuition being that (well structured)
interaction greatly enhances the ability to verify the correctness of
claims, even if they are very difficult to prove on one's own.
The ideas I will explore in the talk intertwine seemingly very different
areas of science, including the foundations of QM, cryptography, and
philosophy of science;
they meet Turing's legacy at several points, from the generalization of
Turing machines to quantum computers, to the violation of the
extended ChurchTuring thesis, to the Turing test and the interaction it
involves. I will end my talk with three fundamental open questions that
are raised by this fascinating interdisciplinary research direction.
Based on collaborations with BenOr, Eban, Vazirani, and Yaari.
