David Gosset

According to our database, David Gosset authored at least 30 papers between 2010 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Triply efficient shadow tomography.

Robbie King, David Gosset, Robin Kothari, Ryan Babbush

Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 2025

2024

Fast simulation of planar Clifford circuits.

David Gosset, Daniel Grier, Alex Kerzner, Luke Schaeffer

Quantum, February, 2024

Quantum advantage from measurement-induced entanglement in random shallow circuits.

Adam Bene Watts, David Gosset, Yinchen Liu, Mehdi Soleimanifar

CoRR, 2024

Classical Simulation of Peaked Shallow Quantum Circuits.

Sergey Bravyi, David Gosset, Yinchen Liu

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

2023

A rapidly mixing Markov chain from any gapped quantum many-body system.

Sergey Bravyi, Giuseppe Carleo, David Gosset, Yinchen Liu

Quantum, November, 2023

Quantum complexity of the Kronecker coefficients.

Sergey Bravyi, Anirban Chowdhury, David Gosset, Vojtech Havlícek, Guanyu Zhu

CoRR, 2023

2022

An area law for 2d frustration-free spin systems.

Anurag Anshu, Itai Arad, David Gosset

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

Improved upper bounds on the stabilizer rank of magic states.

Hammam Qassim, Hakop Pashayan, David Gosset

Quantum, 2021

On the complexity of quantum partition functions.

Sergey Bravyi, Anirban Chowdhury, David Gosset, Pawel Wocjan

CoRR, 2021

Improved approximation algorithms for bounded-degree local Hamiltonians.

Anurag Anshu, David Gosset, Karen J. Morenz Korol, Mehdi Soleimanifar

CoRR, 2021

2020

Beyond Product State Approximations for a Quantum Analogue of Max Cut.

Anurag Anshu, David Gosset, Karen Morenz

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Entanglement subvolume law for 2d frustration-free spin systems.

Anurag Anshu, Itai Arad, David Gosset

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Classical algorithms for quantum mean values.

Sergey Bravyi, David Gosset, Ramis Movassagh

CoRR, 2019

A Compressed Classical Description of Quantum States.

David Gosset, John A. Smolin

Proceedings of the 14th Conference on the Theory of Quantum Computation, 2019

Quantum Advantage with Noisy Shallow Circuits in 3D.

Sergey Bravyi, David Gosset, Robert König, Marco Tomamichel

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2017

Quantum advantage with shallow circuits.

Sergey Bravyi, David Gosset, Robert König

CoRR, 2017

2016

Quantum 3-SAT Is QMA₁-Complete.

David Gosset, Daniel Nagaj

SIAM J. Comput., 2016

Complexity of the XY antiferromagnet at fixed magnetization.

Andrew M. Childs, David Gosset, Zak Webb

Quantum Inf. Comput., 2016

QCMA hardness of ground space connectivity for commuting Hamiltonians.

David Gosset, Jenish C. Mehta, Thomas Vidick

CoRR, 2016

Polynomial-time classical simulation of quantum ferromagnets.

Sergey Bravyi, David Gosset

CoRR, 2016

2015

The Bose-Hubbard Model is QMA-complete.

Andrew M. Childs, David Gosset, Zak Webb

Theory Comput., 2015

Momentum switches.

Andrew M. Childs, David Gosset, Daniel Nagaj, Mouktik Raha, Zak Webb

Quantum Inf. Comput., 2015

2014

An algorithm for the T-count.

David Gosset, Vadym Kliuchnikov, Michele Mosca, Vincent Russo

Quantum Inf. Comput., 2014

2013

Quantum 3-SAT Is QMA1-Complete.

David Gosset, Daniel Nagaj

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

2012

Quantum money.

Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski

Commun. ACM, 2012

Quantum money from knots.

Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

2011

Unstructured randomness, small gaps and localization.

Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Peter W. Shor

Quantum Inf. Comput., 2011

Quantum adiabatic algorithms, small gaps, and different paths.

Edward Farhi, Jeffrey Goldstone, David Gosset, Sam Gutmann, Harvey B. Meyer, Peter W. Shor

Quantum Inf. Comput., 2011

A Quantum Monte Carlo method at fixed energy.

Edward Farhi, Jeffrey Goldstone, David Gosset, Harvey B. Meyer

Comput. Phys. Commun., 2011

2010

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol.

Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor

Proceedings of the Innovations in Computer Science, 2010