Hamiltonian simulation is a very promising area of quantum algorithms where quantum computers can provide a dramatic speedup over classical computers. Until recently, all algorithms had poor scaling in the allowable error. New algorithms allow for complexity scaling logarithmically in the allowable error. One is based on implementing a Taylor series, and another is based on a superposition of different numbers of steps of a quantum walk. These algorithms are still somewhat suboptimal because the complexity has a multiplying factor that is logarithmic in the allowable error, whereas the lower bound has an additive factor. We have now developed general ways of correcting these algorithms, eliminating the multiplying factor, and giving an additive factor that is similar to the lower bound up to double-logarithmic factors.
