Time complexity in preparing metrologically useful quantum states

We investigate the fundamental time complexity imposed by Lieb–Robinson-type bounds on the preparation of any entangled quantum state useful in quantum metrology. In particular, we study how the amount of quantum Fisher information $F_Q$ contained in a pure or mixed quantum state sets a minimum time needed to create such a state from a classical state using either a short-range or long-range interacting Hamiltonian. For a system of $N$ spins or qudits, we focus on metrologically useful states where $F_Q \sim N^{1+\gamma}$ for a linear probe Hamiltonian with $\gamma \in (0,1]$, i.e. varying between the standard limit and the Heisenberg limit. Assuming an arbitrary Hamiltonian on a $d$-dimensional lattice where spin-spin interactions decay no slower than $1/r^{\alpha}$ distance $r$, we prove that for any $\alpha>2d+1$, the minimum time required to prepare the state scales as $t \gtrsim L^\gamma$, where $L\sim N^{1/d}$ is the linear system size. For $2d<\alpha<2d+1$, a polynomial speedup may be obtained, with $t \gtrsim L^{\gamma(\alpha-2d)}$. For $(2-\gamma)d<\alpha<2d$, $t \gtrsim \log L$ and for $\alpha<(2-\gamma)d$, $t$ may vanish algebraically in $1/L$. These time complexity bounds also apply to the minimum circuit depth required for creating such state if the speed of the two-qubit gates also scales as $1/r^{\alpha}$. We further show that for $\gamma=1$ and all $\alpha \ge 0$, or for $0<\gamma<1$ and $\alpha > (2-\gamma)d$, our bounds can be saturated up to sub-polynomial corrections in $L$. Our results can help determine whether existing or future protocols for preparing metrologically useful quantum states are time optimal.