Bill Fefferman- On the Extended Church-Turing Thesis, Quantum Mechanics, and Beyond

Abstract: The field of quantum computation is driven by Richard Feynman’s revolutionary observation in the 80s, which was made rigorous by computer scientists in the early 90s: in theory quantum mechanics enables computers to solve certain specific problems much faster than any classical computer. This tells us that the major goal of computer science – characterizing the power of computation – is inextricably tied to the major goal of physics – understanding how Nature works. In this talk we will discuss how my research aims to carry out this vision by pursuing two interrelated questions: what is the ultimate power of computation afforded by Nature, and what does this power tell us about fundamental physics?

We will begin by discussing our results that characterize the computational power of recent “random quantum circuit” experiments, which may be able to achieve quantum advantage over any efficient classical algorithm. We will then focus on our work defining the notion of “pseudoentanglement”, which constructs ensembles of quantum states that have optimally low entanglement, and yet cannot be distinguished from quantum states with high entanglement. This implies that entanglement, the driving force behind quantum computational speedups, is not a property that can be measured by any efficient algorithm.