Talks by David Gosset

Classical algorithms for quantum mean values

David Gosset University of Waterloo
Consider the task of estimating the expectation value of an n-qubit tensor product observable in the output state of a shallow quantum circuit. This task is a cornerstone of variational quantum algorithms for optimization, machine learning, and the simulation of quantum many-body systems. In this talk I will describe three special cases of this problem which are "easy" for classical computers. This is joint work with Sergey Bravyi and Ramis Movassagh.

Classical simulation of quantum circuits via stabilizer rank

David Gosset University of Waterloo

Stabilizer states are a rich class of quantum states which can be efficiently classically represented and manipulated. In this talk I will describe some ways in which they can help us to represent and manipulate more general quantum states. I will discuss classical simulation algorithms for quantum circuits which are based on expressing a quantum state as a superposition of (as few as possible) stabilizer states.

Based on arXiv:1601.07601 (with Sergey Bravyi) and work in progress with Sergey Bravyi, Dan Browne, Padraic Calpin, Earl Campbell and Mark Howard.

"Quantum advantage with shallow circuits"

David Gosset University of Waterloo

We prove that constant-depth quantum circuits are more powerful than their classical counterparts. We describe an explicit (i.e., non-oracular) computational problem which can be solved with certainty by a constant-depth quantum circuit composed of one- and two-qubit gates. In contrast, we prove that any classical probabilistic circuit composed of bounded fan-in gates that solves the problem with high probability must have depth logarithmic in the input size. This is joint work with Sergey Bravyi and Robert Koenig (arXiv:1704.00690).

The Bose-Hubbard model is QMA-complete

David Gosset University of Waterloo
The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons).