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 Church-Turing
thesis. As I will argue in my talk, a simple
but thought-provoking 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 Church-Turing 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 Ben-Or, Eban, Vazirani, and Yaari.