Quantum Complexity and Algorithms

Venn diagram showing different complexity classes

Quantum information science addresses foundational scientific questions that cut across disciplines, while advancing progress towards technological goals. In the field of theoretical computer science, perhaps the deepest question is "What can be computed efficiently?" The Extended Church-Turing thesis states that all models of computation are essentially equivalent, but we now understand that computers processing quantum information can be used to solve problems that are otherwise intractable. Understanding this boundary will provide fundamental insight into the nature of computation as well as the physical universe.