463 citations · 2.5k across the 46 of their papers we have counts for
5 papers · 2 filters
On the complexity of quantum partition functions
Sergey Bravyi, Anirban Chowdhury, David Gosset +1
The partition function and free energy of a quantum many-body system determine its physical properties in thermal equilibrium. Here we study the computational complexity of approxi…
Improved upper bounds on the stabilizer rank of magic states
Hammam Qassim, Hakop Pashayan, David Gosset
In this work we improve the runtime of recent classical algorithms for strong simulation of quantum circuits composed of Clifford and T gates. The improvement is obtained by establ…
Improved approximation algorithms for bounded-degree local Hamiltonians
Anurag Anshu, David Gosset, Karen J. Morenz Korol +1
We consider the task of approximating the ground state energy of two-local quantum Hamiltonians on bounded-degree graphs. Most existing algorithms optimize the energy over the set…
An area law for 2D frustration-free spin systems
Anurag Anshu, Itai Arad, David Gosset
We prove that the entanglement entropy of the ground state of a locally gapped frustration-free 2D lattice spin system satisfies an area law with respect to a vertical bipartition…
Classical algorithms for Forrelation
Sergey Bravyi, David Gosset, Daniel Grier +1
We study the forrelation problem: given a pair of -bit Boolean functions and , estimate the correlation between and the Fourier transform of . This problem is know…