David Gosset

David Gosset

I am an Associate Professor in the Department of Combinatorics and Optimization and the Institute for Quantum Computing at the University of Waterloo. I am interested in the theory of quantum computing, quantum algorithms and quantum complexity theory.

Please contact me if you are interested in joining my group as a graduate student or postdoctoral fellow. I can be reached by email at dgosset at uwaterloo dot ca.

Previously I was a research staff member and manager of the Theory of Quantum Algorithms group at the IBM T.J. Watson Research Center. Before joining IBM I held postdoctoral fellowships at IQC/Waterloo, and at Caltech. I completed my PhD in Physics in 2011 at MIT under the supervision of Eddie Farhi. I did my undergraduate degree in physics and math at UBC.

Publications and Preprints (see also google scholar)

  1. Approximation algorithms for quantum many-body problems. Sergey Bravyi, David Gosset, Robert Koenig, Kristan Temme arxiv:1808.01734
  2. Simulation of quantum circuits by low-rank stabilizer decompositions. Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, Mark Howard arxiv:1808.00128
  3. A compressed classical description of quantum states. David Gosset, John Smolin. arxiv:1801.05721
  4. Quantum advantage with shallow circuits. Sergey Bravyi, David Gosset, Robert Koenig. Science 362 (6412) pp. 308-311, 2018. Link to journal version .pdf (free access)
  5. Link to journal version online full text (free access) Link to arxiv preprint version
  6. Polynomial-time classical simulation of quantum ferromagnets. Sergey Bravyi, David Gosset. Physical Review Letters 119, 100503, 2017 arxiv:1612.05602
  7. QCMA hardness of ground space connectivity for commuting Hamiltonians. David Gosset, Jenish C. Mehta, Thomas Vidick. Quantum 1,16, 2017 arxiv:1610.03582
  8. Complexity of quantum impurity problems. Sergey Bravyi, David Gosset. Communications in Mathematical Physics 356 (2), 451-500, 2017arxiv:1609.00735
  9. Improved classical simulation of quantum circuits dominated by Clifford gates. Sergey Bravyi, David Gosset. Physical Review Letters 116, 250501, 2016 arxiv:1601.07601
  10. Local gap threshold for frustration-free spin systems. David Gosset, Evgeny Mozgunov. Journal of Mathematical Physics 57, 091910, 2016 arxiv:1512.00088
  11. Correlation length versus gap in frustration-free systems. David Gosset, Yichen Huang. Physical Review Letters 116, 097202, 2016 arxiv:1509.06360
  12. Complexity of the XY antiferromagnet at fixed magnetization. Andrew M. Childs, David Gosset, Zak Webb. Quantum Information and Computation 16 (1&2), 2016. arxiv:1503.07083
  13. Gapped and gapless phases of frustration-free spin-1/2 chains. Sergey Bravyi, David Gosset. Journal of Mathematical Physics 56, 061902, 2015. arxiv:1503.04035
  14. Exact synthesis of single-qubit unitaries over Clifford-cyclotomic gate sets. Simon Forest, David Gosset,Vadym Kliuchnikov, David McKinnon. Journal of Mathematical Physics 56, 082201, 2015. arxiv:1501.04944
  15. Universal adiabatic quantum computation via the space-time circuit-to-Hamiltonian construction. David Gosset, Barbara M. Terhal, Anna Vershynina. Physical Review Letters 114, 140501, 2015. arxiv:1409.7745
  16. Momentum Switches. Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb. Quantum Information and Computation 15 (7&8), 2015. arxiv:1406.4510
  17. The Bose-Hubbard model is QMA-complete. Andrew M. Childs, David Gosset, Zak Webb. Theory of Computing 11 (20), 2015. Extended abstract in ICALP 2014. arxiv:1311.3297
  18. An algorithm for the T-count. David Gosset, Vadym Kliuchnikov, Michele Mosca, Vincent Russo. Quantum Information and Computation 14(15&16), 2014. arxiv:1308.4134
  19. Quantum 3-SAT is QMA1-complete. David Gosset, Daniel Nagaj. Siam Journal on Computing 45(3) 1080-1128 (special section on FOCS 2013). Extended abstract in FOCS 2013. arxiv:1302.0290
  20. Universal computation by multi-particle quantum walk. Andrew M. Childs, David Gosset, and Zak Webb. Science 339 (6121) pp. 791-794, 2013. arxiv:1205.3782
  21. Levinson's theorem for graphs II. Andrew M. Childs, David Gosset. Journal of Mathematical Physics 53 102207, 2012. arxiv:1203.6557.
  22. The performance of the quantum adiabatic algorithm on random instances of two optimization problems on regular hypergraphs. Edward Farhi, David Gosset, Itay Hen, Anders W. Sandvik, Peter Shor, A. Peter Young, Francesco Zamponi. Physical Review A 86 052334, 2012. arxiv:1208.3757
  23. Quantum money. Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, Andrew Lutomirski. Communications of the ACM 55(8), 2012.
  24. Quantum money from knots Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter Shor. ITCS '12 Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. arxiv:1004.5127
  25. Unstructured randomness, small gaps, and localization. Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Peter Shor. Quantum Information and Computation 11(9&10), 2011. arxiv:1010.0009
  26. A quantum monte carlo method at fixed energy. Edward Farhi, Jeffrey Goldstone, David Gosset, Harvey B. Meyer. Computer physics communications 182(8), 2011. arxiv:0912.4271
  27. Quantum adiabatic algorithms, small gaps, and different paths. Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, Peter Shor. Quantum information and computation 11(3&4), 2011. arxiv:0909.4766
  28. Quantum state restoration and single-copy tomography for ground states of Hamiltonians. Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Daniel Nagaj, Peter Shor. Physical Review Letters 105 190503, 2010. arxiv:0912.3823.
  29. Quantum-Merlin-Arthur-complete problems for stoquastic Hamiltonians and Markov matrices. Stephen P. Jordan, David Gosset, Peter J. Love. Physical Review A 81 032331, 2010. arxiv:0905.4755
  30. Breaking and making quantum money: toward a new quantum cryptographic protocol. Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jon Kelner, Peter Shor. Proceedings of Innovations in Computer Science 2010. arxiv:0912.3825
  31. Effect of a magnetic field gradient and gravitational acceleration on a time-domain grating-echo interferometer. M. Weel, I. Chan, S. Beattie, A. Kumarakrishnan, D. Gosset, I. Yavin. Physical Review A 73 063624, 2006.