Circuit complexity lower bounds for quantum enhanced metrology

Entangled quantum many-body states with high quantum Fisher information (QFI) enable the detection of an unknown signal with sensitivity beyond the Standard Quantum Limit (SQL). In this work, we present fundamental lower bounds on the quantum circuit complexity of n-qubit pure states enabling beyond-SQL sensitivity scaling, i.e., states for which the QFI is Ω(n^1+δ) for some 0 < δ ≤ 1. Specifically, we establish three theorems proving lower bounds on the minimal circuit depth required to prepare quantum states with metrological advantage. Each addresses a different physical scenario concerning the locality of the sensing Hamiltonian and the connectivity of the quantum circuit architecture. For lattice Hamiltonians in D dimensions and geometrically local circuits, high QFI states have a circuit complexity of Ω(n^δ/D). For Hamiltonians and circuits defined on hypergraphs of constant degree, we show a lower bound of Ω(log(n)). Finally, leveraging known techniques used to construct approximate ground state projectors for area laws, we prove an Ω(log(n)) lower bound for commuting Hamiltonians with constant degree interaction graph and arbitrary circuit connectivity. Our results constitute a “no free lunch” theorem for gaining a quantum advantage in metrology under physically reasonable assumptions.