Abstract
We investigate the fundamental time complexity, as constrained by Lieb-Robinson bounds, for preparing entangled states useful in quantum metrology. We relate the minimum time to the Quantum Fisher Information (F_Q) for a system of N quantum spins on a d-dimensional lattice with 1/r^α interactions with r being the distance between two interacting spins. We focus on states with F_Q ∼ N^1+γ where γ ∈ (0,1], i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions (α > 2d+1), we prove the minimum time t scales as t L^γ, where L ∼ N^1/d. For long-range interactions, we find a hierarchy of possible speedups: t L^γ(α-2d) for 2d < α < 2d+1, t log L for (2-γ)d < α < 2d, and t may even vanish algebraically in 1/L for α < (2-γ)d. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as 1/r^α. We further show that these bounds are saturable, up to sub-polynomial corrections, for all α at the Heisenberg limit (γ=1) and for α > (2-γ)d when γ<1. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.