Paths to Quantum Supremacy
Abstract
This proposal is about the theoretical aspects of the above questions. Its starting point isBosonSampling: a rudimentary form of optical quantum computing, proposed by the PI and hisstudent Alex Arkhipov in 2011, which has since been demonstrated in experiments involving 3-4photons. Crucially, the PI and Arkhipov proved that BosonSampling samples a probabilitydistribution that is hard to sample classically, assuming fundamental conjectures incomputational complexity theory. The current proposal will push that work further~forexample, by understanding the complexity-theoretic effects of photon losses. The proposal willinvolve direct collaboration between mathematicians and computer scientists on the one hand,and experimental physicists on the other. It will branch out far beyond BosonSampling, to studyother ~physics-inspired~ quantum computing models, including the commuting-Hamiltoniansmodel, stoquastic Hamiltonians, the one-clean-qubit model, models with limited entanglement,and models based on permutations and the Yang-Baxter equation. Finally, the proposal willdeepen our understanding of classical computing, by developing new techniques to understandwhen its apparent limitations are really fundamental, and when quantum computing can providean advantage.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Sep 23, 2016
- Source ID
- N000141613164
Entities
People
- Scott Aaronson
Organizations
- Office of Naval Research
- United States Navy
- University of Texas at Austin