Adam Bouland: Thesis Defense: The space around BQP Speaker: Adam Bouland Host: Scott Aaronson Date: Friday, June 30, 2017 Time: 3:00 PM to 4:30 PM Refreshments Time: 2:45 PM Location: G575 Abstract: This thesis explores the computational power of quantum devices from the perspective of complexity theory. Quantum computers hold the promise of solving many problems - such as factoring integers - exponentially faster than classical computers. The computational power of universal quantum devices is captured by the complexity class BQP, which stands for “bounded-error quantum polynomial time.” We hope that quantum devices will be capable of the full power of BQP in the long term. However, quantum computers are very difficult to build, and therefore the experimental devices of the near future may be incapable of universal quantum computation. As a result, a number of recent works have studied the computational power of “weak” models of quantum computers which lie “below BQP.” The first part of this thesis examines the space "below BQP” and describes a number of sub-universal models of quantum computation which can nevertheless perform sampling tasks which are difficult for classical computers. We show that prior models maintain hardness when their set of quantum operations is restricted, and describe two new models of “weak” quantum computation which also show advantage over classical devices. A major theme in this work is that almost any weak device can perform hard sampling tasks. We find that almost any model which is not universal, but not known to be efficiently classically simulable, admits a speedup over classical computing for sampling tasks under plausible assumptions. This work can be seen as progress towards classifying the power of all restricted quantum gate sets. On the other hand, recent developments in quantum gravity have opened up the possibility of modifying quantum mechanics to resolve the black hole information paradox. Inspired by these debates, the second part of this thesis explores the space “above BQP” - i.e. the power of quantum computers in the presence of modified theories of quantum mechanics. We find that almost all modifications allow for drastically more power than BQP, and find that these speedups may be related to superluminal signaling in these models. Surprisingly, we find one model which is merely just a bit more powerful than BQP. Inspired by this model “just above” BQP, we study and resolve an open problem in classical complexity related to the power of statistical-zero knowledge proof systems. Members of committee: Scott Aaronson, Aram Harrow, Ryan Williams Relevant URL: For more information please contact: Deborah Goodwin, 617.324.7303, <a href="mailto:dlehto@csail.mit.edu">dlehto@csail.mit.edu</a> _______________________________________________ qip mailing list qip(a)mit.edu http://mailman.mit.edu/mailman/listinfo/qip