Kavli Affiliate: Birgitta Whaley
| First 5 Authors: Oskar Leimkuhler, K. Birgitta Whaley, , ,
| Summary:
We prove classical simulation hardness, under the generalized
$mathsf{P}neqmathsf{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 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 $mathsf{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.
| Search Query: ArXiv Query: search_query=au:”Birgitta Whaley”&id_list=&start=0&max_results=3