MASSACHUSETTS INSTITUTE OF TECHNOLOGY
Grant: $578,660 - National Science Foundation - Jun. 1, 2009
No votes have been cast for this award yet
Join the conversation: Post a comment about this award
Award Description: 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?
Project Description: Two PhD students -- Andrew Drucker and Michael Forbes -- are currently being funded from this grant. The PI (Aaronson) is currently preparing research papers about several of the topics discussed in the CAREER proposal for submission to the ACM STOC'2010 conference.
Jobs Summary: Student/Trainee (Fellow) MIT student researcher. May be graduate student or undergraduate. (1) (Total jobs reported: 1)
Project Status: Less Than 50% Completed
This award's data was last updated on Jun. 1, 2009. Help expand these official descriptions using the wiki below.
No comments have been added for this project.