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. arxiv:1704.00690
  5. Polynomial-time classical simulation of quantum ferromagnets. Sergey Bravyi, David Gosset. Physical Review Letters 119, 100503, 2017 arxiv:1612.05602
  6. QCMA hardness of ground space connectivity for commuting Hamiltonians. David Gosset, Jenish C. Mehta, Thomas Vidick. Quantum 1,16, 2017 arxiv:1610.03582
  7. Complexity of quantum impurity problems. Sergey Bravyi, David Gosset. Communications in Mathematical Physics 356 (2), 451-500, 2017arxiv:1609.00735
  8. Improved classical simulation of quantum circuits dominated by Clifford gates. Sergey Bravyi, David Gosset. Physical Review Letters 116, 250501, 2016 arxiv:1601.07601
  9. Local gap threshold for frustration-free spin systems. David Gosset, Evgeny Mozgunov. Journal of Mathematical Physics 57, 091910, 2016 arxiv:1512.00088
  10. Correlation length versus gap in frustration-free systems. David Gosset, Yichen Huang. Physical Review Letters 116, 097202, 2016 arxiv:1509.06360
  11. 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
  12. 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
  13. 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
  14. 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
  15. Momentum Switches. Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb. Quantum Information and Computation 15 (7&8), 2015. arxiv:1406.4510
  16. 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
  17. 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
  18. 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
  19. Universal computation by multi-particle quantum walk. Andrew M. Childs, David Gosset, and Zak Webb. Science 339 (6121), 2013. arxiv:1205.3782
  20. Levinson's theorem for graphs II. Andrew M. Childs, David Gosset. Journal of Mathematical Physics 53 102207, 2012. arxiv:1203.6557.
  21. 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
  22. Quantum money. Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, Andrew Lutomirski. Communications of the ACM 55(8), 2012.
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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.
  28. 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
  29. 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
  30. 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.