  The simulation of molecules is a widely anticipated application of quantum
computers. However, recent studies \cite{WBCH13a,HWBT14a} 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\sim 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 $N^6$ 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 simulated molecule. We obtain further improvements using a version of the
coalescing scheme of \cite{WBCH13a}; 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
\cite{WBCH13a,HWBT14a} which relied on exponentially costly classical exact
simulation.
