Oskar Leimkuhler, K. Birgitta Whaley (Mar 28 2025).
Abstract: We prove classical simulation hardness, under the generalized
P=NP conjecture, for quantum circuit families with applications in near-term quantum 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 quantum 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 unitary coupled-cluster with single and double excitations. In each case we discuss the implications for achieving exponential quantum advantage in quantum chemistry on near-term hardware.
