Researchers believe quantum computers will soon be able to solve certain problems more efficiently than classical computers. To measure and classify those efficiency gains, we rely on computational complexity theory, a branch of computer science that centers on measuring and comparing the computational effort that goes into solving different kinds of problems. Complexity theory gives us a useful shorthand for describing the various speedups and problem classes we encounter in computing, but it’s also much more than that. In fact, at least one leading expert argues that without complexity theory, we wouldn’t have quantum computing at all.
Scott Aaronson is a professor of computer science and director of the Quantum Information Center at the University of Texas at Austin, as well as one of the world’s foremost experts in quantum computing and computational complexity theory. Aaronson’s research has helped define some of the fundamental capabilities and limitations of quantum computers, and his work as a science communicator has helped popularize quantum and drawn more people to the quantum community via projects like the Complexity Zoo wiki and his Shtetl-Optimized blog. In an interview, Aaronson spoke about the foundational role computational complexity theory has played in the history of quantum computing.
To read more, click here.