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. Entanglement subvolume law for 2D frustration-free spin systems. Anurag Anshu, Itai Arad, David Gosset. arxiv:1905.11337
  2. Quantum advantage with noisy shallow circuits in 3D. Sergey Bravyi, David Gosset, Robert Koenig, Marco Tomamichel. arxiv:1904.01502
  3. Approximation algorithms for quantum many-body problems. Sergey Bravyi, David Gosset, Robert Koenig, Kristan Temme. Journal of Mathematical Physics 60 (3), 032203, 2019. arxiv:1808.01734
  4. Simulation of quantum circuits by low-rank stabilizer decompositions. Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, Mark Howard arxiv:1808.00128
  5. A compressed classical description of quantum states. David Gosset, John Smolin. To appear in proceedings of the 14th conference on the theory of quantum computation, communication and cryptography (TQC 2019). Outstanding Paper Award, TQC 2019. arxiv:1801.05721
  6. 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)
  7. Link to journal version online full text (free access) Link to arxiv preprint version
  8. Polynomial-time classical simulation of quantum ferromagnets. Sergey Bravyi, David Gosset. Physical Review Letters 119, 100503, 2017 arxiv:1612.05602
  9. QCMA hardness of ground space connectivity for commuting Hamiltonians. David Gosset, Jenish C. Mehta, Thomas Vidick. Quantum 1,16, 2017 arxiv:1610.03582
  10. Complexity of quantum impurity problems. Sergey Bravyi, David Gosset. Communications in Mathematical Physics 356 (2), 451-500, 2017arxiv:1609.00735
  11. Improved classical simulation of quantum circuits dominated by Clifford gates. Sergey Bravyi, David Gosset. Physical Review Letters 116, 250501, 2016 arxiv:1601.07601
  12. Local gap threshold for frustration-free spin systems. David Gosset, Evgeny Mozgunov. Journal of Mathematical Physics 57, 091910, 2016 arxiv:1512.00088
  13. Correlation length versus gap in frustration-free systems. David Gosset, Yichen Huang. Physical Review Letters 116, 097202, 2016 arxiv:1509.06360
  14. 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
  15. 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
  16. 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
  17. 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
  18. Momentum Switches. Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb. Quantum Information and Computation 15 (7&8), 2015. arxiv:1406.4510
  19. 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
  20. 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
  21. 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
  22. 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
  23. Levinson's theorem for graphs II. Andrew M. Childs, David Gosset. Journal of Mathematical Physics 53 102207, 2012. arxiv:1203.6557.
  24. 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
  25. Quantum money. Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, Andrew Lutomirski. Communications of the ACM 55(8), 2012.
  26. 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
  27. 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
  28. 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
  29. 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
  30. 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.
  31. 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
  32. 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
  33. 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.