This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).
Quantum computing is a scientific field that combines some of the deepest intellectual concerns of computer science and physics. Ultimately, we want to know: what is and is not feasibly computable in the physical universe? After fifteen years of effort, quantum computing theory seems to have reached a point where further progress will necessarily entail progress in classical computing theory. The proposed research embraces this with concrete ideas for advancing both fields and will deepen the connections between quantum computing and frontier topics in classical complexity theory.
This research tackles some of the hardest "barrier problems" about the power of classical and quantum computers. Examples of such problems include: how large is the class of problems that admit efficient quantum algorithms? Can we obtain evidence that this class lies outside the entire "polynomial hierarchy" of classical computation---which, loosely speaking, would imply that quantum computers could solve certain problems much faster than classical computers could even check the answers? Are there "unstructured" problems that quantum computers can solve exponentially faster than classical computers, in addition to "structured" problems such as finding the period of a periodic function (the heart of Shor's factoring algorithm)? Can we go beyond the idealized "black-box model" that encompasses almost everything complexity theorists currently know about the power of quantum computers, to obtain "non-relativizing results" that exploit the structure of quantum circuits? Can we better understand the obstacles to progress on P versus NP and related questions?
