Optimal Hamiltonian-simulation query complexity: O(τ + log(1/ε)/log log(1/ε))

Berry-Childs-Cleve-Kothari-Somma 2015 lower bound and Low-Chuang 2017 matching upper bound (quantum signal processing / qubitisation): optimal number of queries to a sparse Hamiltonian oracle needed to simulate e^{−iHt} to accuracy ε is…