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 also an Associate Faculty member at the Perimeter Institute for Theoretical Physics, and a CIFAR fellow in the quantum information science program. I am interested in the theory of quantum computing, quantum algorithms and quantum complexity theory. 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. On the complexity of quantum partition functions. Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan. arXiv:2110.15466
  2. Improved upper bounds on the stabilizer rank of magic states. Hammam Qassim, Hakop Pashayan, David Gosset. arXiv:2106.07740
  3. Improved approximation algorithms for bounded-degree local Hamiltonians. Anurag Anshu, David Gosset, Karen J. Morenz Korol, Mehdi Soleimanifar. arxiv:2105.01193
  4. An area law for 2D frustration-free spin systems. Anurag Anshu, Itai Arad, David Gosset. arxiv:2103.02492
  5. Classical algorithms for Forrelation. Sergey Bravyi, David Gosset, Daniel Grier, Luke Schaeffer. arxiv:2102.06963
  6. Fast simulation of planar Clifford circuits. David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer. arxiv:2009.03218
  7. Beyond product state approximations for a quantum analogue of Max Cut. Anurag Anshu, David Gosset, Karen Morenz. In proceedings of the 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). arxiv:2003.14394>
  8. Classical algorithms for quantum mean values. Sergey Bravyi, David Gosset, Ramis Movassagh. Nature Physics 17 337-341, 2021. arxiv:1909.11485
  9. Entanglement subvolume law for 2D frustration-free spin systems. Anurag Anshu, Itai Arad, David Gosset. Extended abstract in STOC 2020. arxiv:1905.11337
  10. Quantum advantage with noisy shallow circuits . Sergey Bravyi, David Gosset, Robert Koenig, Marco Tomamichel. Nature Physics 1-6, 2020. Extended abstract in FOCS 2019. arxiv:1904.01502
  11. 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
  12. Simulation of quantum circuits by low-rank stabilizer decompositions. Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell, David Gosset, Mark Howard. Quantum 3, pp 181, 2019.arxiv:1808.00128
  13. A compressed classical description of quantum states. David Gosset, John Smolin. 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
  14. 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)
    15. Link to journal version online full text (free access) Link to arxiv preprint version Pat Goldberg Memorial Best Paper Award (IBM Research), 2018.
  15. Polynomial-time classical simulation of quantum ferromagnets. Sergey Bravyi, David Gosset. Physical Review Letters 119, 100503, 2017 arxiv:1612.05602
  16. QCMA hardness of ground space connectivity for commuting Hamiltonians. David Gosset, Jenish C. Mehta, Thomas Vidick. Quantum 1,16, 2017 arxiv:1610.03582
  17. Complexity of quantum impurity problems. Sergey Bravyi, David Gosset. Communications in Mathematical Physics 356 (2), 451-500, 2017arxiv:1609.00735
  18. Improved classical simulation of quantum circuits dominated by Clifford gates. Sergey Bravyi, David Gosset. Physical Review Letters 116, 250501, 2016. Pat Goldberg Memorial Best Paper Award (IBM Research), 2016. arxiv:1601.07601
  19. Local gap threshold for frustration-free spin systems. David Gosset, Evgeny Mozgunov. Journal of Mathematical Physics 57, 091910, 2016 arxiv:1512.00088
  20. Correlation length versus gap in frustration-free systems. David Gosset, Yichen Huang. Physical Review Letters 116, 097202, 2016 arxiv:1509.06360
  21. 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
  22. 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
  23. 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
  24. 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
  25. Momentum Switches. Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb. Quantum Information and Computation 15 (7&8), 2015. arxiv:1406.4510
  26. 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
  27. 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
  28. 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
  29. 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
  30. Levinson's theorem for graphs II. Andrew M. Childs, David Gosset. Journal of Mathematical Physics 53 102207, 2012. arxiv:1203.6557.
  31. 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
  32. Quantum money. Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan Kelner, Andrew Lutomirski. Communications of the ACM 55(8), 2012.
  33. 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
  34. 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
  35. 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
  36. 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
  37. 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.
  38. 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
  39. 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
  40. 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.