Abstract:
A central question in computing is figuring out how hard a problem is. The famous distinction is between problems that can be quickly solved in polynomial time (P) and those that can be quickly verified (NP). Quantum computers can rapidly solve some problems that would take classical computers a long time and their appearance has changed the nature of this question. In 2020, a remarkable result known as MIP*=RE proved that classical computers with access to quantum randomness can reliably verify problems that classical computers cannot solve, even with unlimited resources. I will give a beginner’s introduction to this ground breaking result and describe why it is important to computer scientists, mathematicians, and physicists. Einstein’s pal Gödel comes into this story not once, but twice!