Time complexity in preparing metrologically useful quantum states

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^{\hat{I}}\pm$ interactions with $r$ being the distance between two interacting spins. We focus on states with $F_Q\sim N^{1+{\hat{I}}^3}$ where ${\hat{I}}^3\in (0,1]$, i.e., scaling from the standard quantum limit to the Heisenberg limit. For short-range interactions ($\hat{I}\pm >2d+1$), we prove the minimum time $t$ scales as $t\gtrsim L^3$, where $L\sim N^{1/d}$. For long-range interactions, we find a hierarchy of possible speedups: $t\gtrsim L^{{\hat{I}}^3(\hat{I}\pm -2d)}$ for $2d<\hat{I}\pm <2d+1$, $t\gtrsim \log L$ for $(2-{\hat{I}}^3)d<\hat{I}\pm <2d$, and $t$ may even vanish algebraically in $1/L$ for $\hat{I}\pm <(2-{\hat{I}}^3)d$. These bounds extend to the minimum circuit depth required for state preparation, assuming two-qubit gate speeds scale as $1/r^{\hat{I}}\pm$. We further show that these bounds are saturable, up to sub-polynomial corrections, for all $\hat{I}\pm$ at the Heisenberg limit (${\hat{I}}^3=1$) and for $\hat{I}\pm >(2-{\hat{I}}^3)d$ when ${\hat{I}}^3<1$. Our results establish a benchmark for the time-optimality of protocols that prepare metrologically useful quantum states.

9 pages, 2 figures