Exponential quantum speedups for near-term molecular electronic structure methods

Abstract

We prove classical simulation hardness, under the generalized $\mathsf{P}\neq\mathsf{NP}$ 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 non-orthogonal multi-reference methods designed for near-term hardware by ruling out certain dequantization strategies for computing the off-diagonal matrix elements between reference states. We demonstrate these quantum speedups for two choices of ansatz that incorporate both static and dynamic correlations to model the electronic eigenstates of molecular systems: linear combinations of orbital-rotated matrix product states, which are preparable in linear depth, and linear combinations of states prepared by generalized UCCSD circuits of polynomial depth, for which computing the expectation values of local fermionic observables up to a constant additive error is $\mathsf{BQP}$-complete. We discuss the implications for achieving practical quantum advantage in resolving the electronic structure of catalytic systems composed from multivalent transition metal atoms using near-term quantum hardware.