Davd Poulin, M.B. Hastings, Dave Wecker, Nathan Wiebe, Andrew C. Doherty, and Matthias Troyer
19 June 2014
The simulation of molecules is a widely anticipated application of quantum computers. However, recent studies have cast a shadow on this hope by revealing that the complexity in gate count of such simulations increases with the number of spin orbitals N as N^8, which becomes prohibitive even for molecules of modest size N~100 . This study was partly based on a scaling analysis of the Trotter step required for an ensemble of random artificial molecules. Here, we revisit this analysis and find instead that the scaling is closer to N6 in worst case for real model molecules we have studied, indicating that the random ensemble fails to accurately capture the statistical properties of real-world molecules. Actual scaling may be significantly better than this due to averaging effects. We then present an alternative simulation scheme and show that it can sometimes outperform existing schemes, but that this possibility depends crucially on the details of the simulate molecule. We obtain further improvements using a version of the coalescing scheme of <ref>; this scheme is based on using different Trotter steps for different terms. The method we use to bound the complexity of simulating a given molecule is efficient, in contrast to the approach of <ref> which relied on exponentially costly classical exact simulation.