David Gosset's paper published in Nature Physics

C&O professor David Gosset, in joint work with Sergey Bravyi and Ramis Movassagh from IBM Research, has published a paper "Classical algorithms for quantum mean values" in Nature Physics.

Gosset and his co-authors developed sub-exponential time classical algorithms for solving certain formulations of the quantum mean value problem

 for constant-depth quantum circuits. Low-depth quantum circuits are of strong interest because of their potential for applications in the near-term before fault-tolerant quantum computers can be built. The quantum mean value problem is important because it is a cornerstone of variational quantum algorithms, which are being intensively studied for their potential for solving some optimization problem faster than classical algorithms on low-depth quantum circuits.

Gosset's work suggests that quantum circuits of larger-than-constant depth are needed for achieving a quantum advantage with variational quantum algorithm.