  The quantum Fisher information (QFI) is a fundamental quantity of interest in
many areas from quantum metrology to quantum information theory. It can in
particular be used as a witness to establish the degree of multi-particle
entanglement in quantum many-body-systems. In this work, we use polynomials of
the density matrix to construct monotonically increasing lower bounds that
converge to the QFI. Using randomized measurements we propose a protocol to
accurately estimate these lower bounds in state-of-art quantum technological
platforms. We estimate the number of measurements needed to achieve a given
accuracy and confidence level in the bounds, and present two examples of
applications of the method in quantum systems made of coupled qubits and
collective spins.
