There is perhaps no branch of science with a more suitable title than “Complexity Theory.”
Let’s be honest here: complexity theory is darned complex, particularly when you throw quantumness into the mix. It takes a special breed of scientist to become a leading global authority on quantum complexity theory and its related disciplines — which is exactly what John Watrous is.
Watrous is a faculty member at IQC, and a leader in theoretical quantum computer science. His research, when you get down to the nitty-gritty of it, is concerned with determining which types of problems are efficiently solvable by a quantum computer, and which ones are hopelessly complicated.
After much work with collaborators, Watrous made an important breakthrough in the field, proving the equivalence of two classes of computational problems, QIP and PSPACE. This answered a longstanding puzzle in computer science, and was lauded as a highly significant breakthrough in the field. The paper Watrous and his collaborators wrote summarizing their results, titled QIP=PSPACE, won the prestigious”Best Paper Award” at the Symposium on the Theory of Computing last year.
Since the work was so groundbreaking (and complex), we decided to let Watrous tell you about it himself. Enjoy!