  In quantum metrology, one of the major applications of quantum technologies,
the ultimate precision of estimating an unknown parameter is often stated in
terms of the Cram\'er-Rao bound. Yet, the latter is no longer guaranteed to
carry an operational meaning in the regime where few measurement samples are
obtained, which we illustrate through a simple example. We instead propose to
quantify the quality of a metrology protocol by the probability of obtaining an
estimate with a given accuracy. This approach, which we refer to as probably
approximately correct (PAC) metrology, ensures operational significance in the
finite-sample regime. The accuracy guarantees hold for any value of the unknown
parameter, unlike the Cram\'er-Rao bound which assumes it is approximately
known. We establish a strong connection to multi-hypothesis testing with
quantum states, which allows us to derive an analogue of the Cram\'er-Rao bound
which contains explicit corrections relevant to the finite-sample regime. We
further study the asymptotic behavior of the success probability of the
estimation procedure for many copies of the state and apply our framework to
the example task of phase estimation with an ensemble of spin-1/2 particles.
Overall, our operational approach allows the study of quantum metrology in the
finite-sample regime and opens up a plethora of new avenues for research at the
interface of quantum information theory and quantum metrology.
