Exponential quantum speedups in quantum chemistry with linear depth

We prove classical simulation hardness, under the generalized P conjecture, for quantum circuit families with applications in near-term chemical ground state estimation. The proof exploits a connection to particle number conserving matchgate circuits with fermionic magic state inputs, which are shown to be universal for quantum computation under post-selection, and are therefore not classically simulable in the worst case, in either the strong (multiplicative) or weak (sampling) sense. We apply this result to quantum multi-reference methods designed for near-term hardware by ruling out certain dequantization strategies for computing the off-diagonal matrix elements. We demonstrate these quantum speedups for two choices of reference state that incorporate both static and dynamic correlations to model the electronic eigenstates of molecular systems: orbital-rotated matrix product states, which are preparable in linear depth, and generalized unitary coupled-cluster with single and double excitations, for which computing the off-diagonal matrix elements is BQP-complete for any polynomial depth. In each case we discuss the implications for achieving exponential quantum advantage in quantum chemistry on near-term hardware.