David Gosset

David Gosset

In August 2018 I will join the Institute for Quantum Computing and the Department of Combinatorics and Optimization at the University of Waterloo as an Associate Professor. 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.

I am interested in the theory of quantum computing, quantum algorithms and quantum complexity theory.

I can be reached by email at dngosset at gmail dot com.

Publications and Preprints (see also google scholar)

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