# Quantum metrology in the finite-sample regime

Johannes Jakob Meyer, Sumeet Khatri, Daniel Stilck França, Jens Eisert, Philippe Faist

<figure><img src="image_1.png" /></figure>

## To cite this version:

Johannes Jakob Meyer, Sumeet Khatri, Daniel Stilck França, Jens Eisert, Philippe Faist. Quantum metrology in the finite-sample regime. 2023. hal-04280236

HAL Id: hal-04280236

https://hal.science/hal-04280236v1

Preprint submitted on 10 Nov 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
Quantum metrology in the finite-sample regime

Johannes Jakob Meyer,¹ Sumeet Khatri,¹ Daniel Stilck França,¹,²,³ Jens Eisert,¹,⁴,⁵ and Philippe Faist¹

¹Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

²Department of Mathematical Sciences, University of Copenhagen, 2100 København, Denmark

³Ecole Normale Superieure de Lyon, 69342 Lyon Cedex 07, France

⁴Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany

⁵Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany

(Dated: July 14, 2023)

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ér-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ér-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ér-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.

Metrology, the scientific study of measurements, has naturally evolved to encompass the realm of quantum theory. Quantum metrology seeks to realize practical advantages by harnessing quantum effects. The growing quantum technologies sector, especially, holds high expectations for achieving unparalleled sensitivity with quantum sensors. Anticipated applications range from the calibration of atomic clocks over gravitational-wave detection to potential medical uses [1–5]. It is crucial that the theory of quantum metrology accommodates the emerging technological capabilities of near-term quantum sensors, which necessitates an in-depth understanding of their performance in realistic settings, where the size of experiments might be limited.

A standard question in quantum metrology is to determine the value of an unknown parameter that has been encoded in a quantum state. For instance, suppose we wish to estimate the difference of time $t$ between two events. One might prepare an initial clock state $\rho_0$, e.g., an ensemble of spin-$\frac{1}{2}$ particles, in some standard state when the first event occurs, let the system evolve under its natural dynamics – say, a magnetic field of fixed strength – resulting in a state $\rho(t)$, and perform a measurement on the system when the second event occurs. The accuracy to which $t$ is determined can be improved through suitable choices of the initial state, the dynamics, and the final measurement. A similar scheme can be employed to sense the value of an unknown parameter in a Hamiltonian, such as the strength of an external field. In this case, one lets the system evolve under the unknown Hamiltonian for a fixed amount of time. In either case, the problem reduces to estimating the value of a

<figure><img src="image_3.png" /><figcaption>FIG. 1. The setup we consider for quantum metrology in the finite-sample regime consists in applying a measurement onto the quantum state $\rho(t)$, and inferring an estimate $\hat{t}$ of the value of the unknown parameter $t$ from the outcome of the measurement. The estimation process is successful if the estimate $\hat{t}$ and the true parameter value $t$ differ by at most some fixed error tolerance $\delta$. Our approach quantifies the probability that the estimation procedure is successful. In contrast, the standard quantum Cramér-Rao bound quantifies the variance of the outcome $\hat{t}$ for a given estimation procedure that reveals the correct parameter in expectation; its operational meaning is guaranteed only after collecting many outcomes.</figcaption></figure>

parameter $t$ among a parametrized set of states $t \mapsto \rho(t)$.

A standard treatment of this problem proceeds as follows [1, 2, 5, 6]. One assumes that $t$ is already known to be close to some value $t_0$. The task is to refine one's knowledge of $t$ by accessing the expectation value of some observable. A central result in quantum metrology quantifies the variance $\sigma^2$ of a quantum measurement whose expectation value is equal to $t$. The quantum Cramér-Rao bound states that [5, 7–9]

$$ \sigma^2 \ge \frac{1}{\mathcal{F}}, \qquad (1) $$

where $\mathcal{F}$ is the quantum Fisher information, a quantity
that measures how distinguishable the states of the fam-
ily $\rho(t)$ are around $t_0$. Furthermore, there exists a quan-
tum measurement which achieves equality in Eq. (1).
One thus frequently resorts to the quantum Fisher in-
formation as a measure of sensitivity, including when
quantifying the advantages of using entangled states for
quantum sensing [1], the effect of noise on the sensitivity
of probe states [10, 11], as well as the advantages of using
quantum error correction in metrology [12]. The quan-
tum Fisher information naturally generalizes the classical
Fisher information and enjoys the geometrical interpreta-
tion of being the metric tensor associated with the fidelity
of quantum states [5, 6, 13].

In this work, we consider the regime where few mea-
surement samples are available. This regime is increas-
ingly expected to be relevant when considering the lim-
ited capabilities of quantum sensors in the near term.
Specifically, we revisit some of the founding assumptions
that lead to the quantum Cramér-Rao bound which are
difficult to justify in the few-sample regime. First, the ex-
pectation value of an observable can only be reliably es-
timated if sufficiently many samples are available. Thus,
access to few samples of the measurement that achieves
equality in the quantum Cramér-Rao bound might not
provide meaningful information about the unknown pa-
rameter. Second, few samples from a quantum measure-
ment are unlikely to yield the degree of precision that
is compatible with the assumption that the parameter
is already approximately known. Relaxing this second
assumption furthermore enables us to consider general
families of states $\rho(t)$ without the smoothness properties
required to apply the quantum Cramér-Rao bound.

We establish a general finite-sample analysis of quan-
tum metrology rooted in fundamental principles of quan-
tum information theory. We consider a general one-
parameter family of states $t \mapsto \rho(t)$, where $t$ is known
to belong to some real interval $I \subseteq \mathbb{R}$ (Fig. 1). We then
consider a quantum measurement whose outcome leads
to an estimate $\hat{t}$ of the value $t$. In our model, the measure-
ment is applied only once. Access to a finite number $n$ of
samples is modeled by explicitly considering the copies of
the state in parallel, $\rho^{\otimes n}(t)$. The estimation procedure
is successful if $\hat{t}$ is within some fixed estimation error
tolerance $\delta$ of the true parameter value $t$. We then ask,
"What is the probability that our estimate of the underly-
ing parameter is within a given estimation error tolerance
around the true value?" and "What is the smallest esti-
mation error tolerance such that this success probability
is at least some given threshold?" For these questions to
have a well-defined answer, we can either assume prior
knowledge about the underlying parameter $t$ or we take
the worst-case among all possible values of $t$. In our work,
we explore both settings in depth.

We show that computing the optimal success proba-
bility over all possible measurements for a fixed estima-
tion tolerance belongs to a class of convex optimization
problems known as semi-infinite programs, which are es-
sentially semi-definite programs with an infinite number

of semi-definite constraints. We explicitly show how the
semi-infinite program reduces to a semi-definite program
upon discretization.

We also establish close connections between metrology
in the finite-sample regime and multi-hypothesis testing
of quantum states [14–17]. In quantum multi-hypothesis
testing, one receives an unknown state from a fixed set
of quantum states, and seeks to identify which state was
provided. The metrological task considered here can be
intuitively understood as a continuous version of multi-
hypothesis testing of quantum states, where we seek to
identify the value of an unknown parameter *t* in the
family of states ρ(t). In contrast to the discrete multi-
hypothesis task, it is impossible to determine the value
of *t* exactly given the parameter’s continuous nature. In-
stead, the parameter *t* should be determined up to some
fixed precision, quantified by δ. We make this intu-
itive connection rigorous by proving upper bounds on
the success probability of the metrological task in terms
of the success probability of a related multi-hypothesis
testing task. More specifically, we show that determin-
ing the parameter *t* to precision δ is at least as hard
as distinguishing quantum states corresponding to pa-
rameters that are at least 2δ apart. Along the same
vein, we express quantities of interest, such as the suc-
cess probability of our estimation procedure, in terms of
known single-shot entropy measures such as the condi-
tional min-entropy [17, 18]. We also connect our frame-
work to known estimation lower bounds in terms of the
the hypothesis testing relative entropy [19].

We then connect the finite-sample regime to the many-
sample regime as follows. We study the behavior of the
success probability of the estimation where a finite num-
ber *n* of copies of the state are available, and consider
the limit *n* → ∞. In this regime, we prove an upper
bound on the rate with which the success probability ap-
proaches one in terms of the Chernoff divergence of quan-
tum states. This result extends known distinguishability
rates in multi-hypothesis testing [15].

Exploiting the connection to multi-hypothesis testing allows us to formulate an analogue of the quantum Cramér-Rao bound that is valid in the single-shot regime. The estimation error tolerance $\delta$ replaces the standard deviation $\sigma$ on the left-hand side of the inequality of Eq. (1), and we obtain correction terms on the right-hand side that depend on the desired success probability and properties of the set of states $\rho(t)$.

We then turn to an alternative setting, in which
the parameter to be estimated is accessed through
the use of a parameter-dependent quantum channel.
This setting offers richer estimation strategies than the
parameter-dependent state setting. For instance, an es-
timation strategy may interleave the application of the
parametrized channel on a probe system with interac-
tions with a memory system. We extend a selection of our
earlier results to such general strategies, like the formula-
tion of the optimal success probability as a convex prob-
lem as well as the rigorous connection to multi-hypothesis
testing of quantum channels. Such generalizations become possible by viewing such strategies in their entirety as quantum combs [20, 21] or general strategies of indefinite causal order [22].

We further consider the task of estimating the parameter $t$ in a family of pure states $|\psi(t)\rangle$ for which the parameter $t$ corresponds to time, and whose evolution is governed by a fixed Hamiltonian. Furthermore, $t$ is to be estimated globally over the entire period of the Hamiltonian [23]. We establish a closed-form expression of the worst-case estimation success probability, exploiting the group-covariant structure of this set of states with respect to time evolution. We finally consider examples of this setting on an ensemble of spin-$\frac{1}{2}$ particles. We numerically compute the optimal success probability, as well as the optimal estimation error tolerance, for a collection of states. The GHZ state fails in the global estimation setting considered here, despite the state being optimal for local estimation. We compare the sensitivity of a selection of states, including a standard ensemble of spins prepared in a superposition of a ground and an excited state (i.e., a spin-coherent state) as well as a uniform superposition over all distinct energy levels (the Holland-Burnett state [24]). We also determine the state that achieves optimal success probability, for any $n$ and for any fixed estimation error tolerance.

To further motivate our approach, consider the following example [11, 25, 26] (see Section II of the supplementary material for details). Alice prepares a particle in the state $\rho_0 = |+\rangle\langle+|$, where $|\pm\rangle = (|0\rangle \pm |1\rangle)/\sqrt{2}$. The particle evolves according to the Hamiltonian $H = (\omega/2)Z$ for some fixed $\omega$, causing it to rotate in the X-Y-plane of the Bloch sphere. At time $t$, Alice sends the particle instantaneously over to Bob through a completely dephasing channel acting in the Pauli-X basis, defined as $\rho_0 \mapsto \langle+|\rho_0|+\rangle|+\rangle\langle+| + \langle-|\rho_0|-\rangle|-\rangle\langle-|$. As a consequence, Bob thus receives the state $\rho(t) = \cos^2(\omega t/2)|+\rangle\langle+| + \sin^2(\omega t/2) |-\rangle\langle-|$. The quantum Fisher information that Bob has with respect to $t$ is [25, 26]

$$ \mathcal{F} = \begin{cases} \omega^2 & \text{if } t \notin (\pi/\omega)\mathbb{Z}, \\ 0 & \text{if } t \in (\pi/\omega)\mathbb{Z}. \end{cases} \quad (2) $$

That is, $\mathcal{F}$ is constant equal to $\omega^2$ except in a discrete set of points where $\mathcal{F} = 0$. While the discontinuity at $t \in (\pi/\omega)\mathbb{Z}$ is concerning given the operational nature of the quantum Fisher information, it can be attributed to the vanishing first-order expansion of $\rho(t)$ at those points and therefore to a failure of the first-order approximation of the curve $\rho(t)$ [25, 26]. Consider now a point $t \approx 0$ with $t > 0$ arbitrarily small. The quantum Cramér-Rao bound guarantees the existence of a measurement $\hat{T}$ with expectation value $\langle\hat{T}\rangle = t$ and with variance $\langle\Delta\hat{T}\rangle^2 = 1/\omega^2$. This operator is $\hat{T} = t\mathbb{I} + \omega^{-1}(-\tan(\omega t/2)|+\rangle\langle+| + \cot(\omega t/2)|-\rangle\langle-|)$ (compare Section II of the supplementary material). The eigenvalue of $\hat{T}$ associated with $|\rangle$ diverges as $\sim 1/t$.

In fact, both eigenvalues contribute significantly to the expectation value and variance of $\hat{T}$; the effect of the divergent eigenvalue associated with $|\rangle$ is kept finite only thanks to the corresponding outcome happening with vanishingly small probability $\sim t^2$. That is, a measurement of $\hat{T}$ almost certainly yields the outcome $|+\rangle$; the outcome $|\rangle$, necessary for an accurate estimation of the expectation value, only occurs after an expected $\sim 1/t^2$ number of samples. Therefore, a naive estimation of the expectation value of this observable yields little useful information on $t$ if fewer than $\sim 1/t^2$ samples are collected. One of the main goals of this work is to develop a rigorous and precise analysis of the accuracy limits of sensing a parameter in the regime where the number of samples is insufficient to accurately estimate the expectation value of the sensing observable given through the Cramér-Rao bound.

Our inherently operational, information-theoretic approach to the estimation task guarantees an operational meaning to the estimation error achieved by a given measurement, in contrast to the variance of an observable whose operational meaning is ensured only in the asymptotic limit of many samples. Our approach is strongly inspired by recent advancements in single-shot quantum information theory [17, 18, 27, 28], whose aim is to quantify the resource requirements of information-theoretic tasks beyond the traditional regime where many independent and identically distributed (i.i.d.) copies of a quantum state are available. The approach of quantifying the performance of a quantum metrology protocol through the probability of obtaining a sufficiently accurate estimate is also similar in spirit to the de-facto standard approach to computational learning theory, namely probably approximately correct (PAC) learning [29]. As such, we will also refer to our framework as probably approximately correct (PAC) metrology. Our approach can also be understood as constructing sets known as confidence intervals in the field of statistics, and characterizing the effect of different choices of quantum measurements on their size. Our approach is thus closely related to confidence region estimation of quantum states [19, 30–33].

Our framework enables the study of estimation procedures that can interpolate between local estimation, as in the context of the quantum Cramér-Rao bound, and global estimation, where the possible values of the underlying parameters are not constrained to a very small neighborhood of a known value. Intuitively, the local setting corresponds to the case where the possible range of values for the parameter in question is small compared to the right hand side of the quantum Cramér-Rao bound Eq. (1). The global setting requires states to remain distinguishable over the full range of values that the unknown parameter might take. Probe states that are accurate in the local estimation setting are not necessarily accurate for global estimation. For instance, the n-qubit GHZ state $|GHZ\rangle = (|00\dots0\rangle + |11\dots1\rangle)/\sqrt{2}$ is optimal for local estimation of a parameter $t$ of a non-interacting ensemble of spin-$\frac{1}{2}$ particles. However, its
very short period $2\pi/n$ prohibits us from distinguishing
values of $t$ spaced by more than $2\pi/n$. In contrast, the
state $|+\rangle^{\otimes n} = [(|0\rangle + |1\rangle)/\sqrt{2}]^{\otimes n}$ has a period of $2\pi$ and
is capable of identifying greater time intervals at the cost
of a worse accuracy in the setting of local estimation.

While the general approach of using the quantum
Fisher information can be extended to the global esti-
mation regime by considering Bayesian prior information
about the underlying parameter [2, 34–38], this does sim-
ilarly suffer from possible issues in the few-shot regime
we outlined above. Our alternative approach, on the
other hand side, can interpolate between the local and
the global setting, both in the presence and absence of
prior information about the underlying parameter, and
is applicable in the few-shot setting.

Our approach furthermore does not suffer from ap-
parent inconsistencies that can arise when the family of
quantum states $\rho(t)$ is not sufficiently well-behaved (e.g.,
if the derivative vanishes), in contrast to the singularities
and divergences that the quantum Fisher information is
prone to in such cases [25, 26].

Our framework is summarized in Fig. 2. We identify three key quantities of interest: the success probability at fixed estimation error tolerance, the best achievable tolerance at fixed success probability, and the sample complexity, which quantifies the minimum number of experimental repetitions needed to achieve a desired success probability and tolerance. We discuss two scenarios of these measures, one assuming information in the form of a prior – referred to as Bayesian – and one that captures guarantees that can be made agnostic to the underlying parameter – referred to as minimax. The minimax setting enables a rigorous treatment of the lack of any prior knowledge on the unknown parameter. In particular, attempts to capture this lack of knowledge in the Bayesian setting, e.g. by picking a uniform prior, fail to achieve the worst-case statements that are enabled by the minimax setting. The minimax setting indeed leads to guarantees that hold even when an adversary can choose a parameter value that a particular metrology strategy is least likely to work for.

Prior works focusing on metrology with finite repeti-
tions [39–45] in both the classical and quantum case usu-
ally take a “large deviation” perspective, such that the
number of samples is understood to be finite but still
large. A notion of success probability already appeared
in Ref. [46]. The authors of Refs. [43, 47] have quantified
asymptotic properties related to the achievable precision
under statistical assumptions on the estimators, some-
thing that can be tightened with our results as we explain
in the supplementary material. References [44, 45, 48]
have extended this approach to quantum state tomog-
raphy. The problem of optimizing the metrological tol-
erance with a given guarantee on the success probabil-
ity has been treated in Refs. [19, 46, 49, 50], where some
bounds have been given. In a spirit similar to our work,
connections between quantum metrology and hypothe-
sis testing have been used to obtain precision bounds in

<figure><img src="image_4.png" /><figcaption>FIG. 2. The fundamental quantities forming the *probably approximately correct* (PAC) metrology framework quantifying non-asymptotic quantum metrology. The success probability, defined intuitively through the statement given in the above figure, forms the cornerstone of the framework. The tolerance is obtained from it by answering the question: “What is the smallest tolerance that still guarantees a given success probability?” Similarly, the sample complexity is the answer to the question: “How many repetitions of an experiment do I need to perform to achieve a certain tolerance at a fixed success probability?” We rigorously define them in Definition 1 (success probability), Definition 2 (tolerance) and Definition 3 (sample complexity). The relation to the theory of PAC learning [29] lies in the spirit of how the quality of a protocol is quantified through the success probability – beyond that, there is no overlap between the frameworks.</figcaption></figure>

the standard approach to quantum metrology [51]. The
reverse direction of using metrology bounds to quantify
channel discrimination has also been explored [52]. Our
analysis of the phase estimation problem has overlaps
with work by Imai and Hayashi [53], where the asymp-
totic distribution of phase estimates is analyzed. Alter-
native methods for multi-parameter estimation are re-
viewed in [54]. The authors of Ref. [55] have studied the
case of a fixed measurement with a focus on the admissi-
bility of said measurement. The connection to previous
work is explored in greater detail in Section I of the sup-
plementary material.

After summarizing the main contributions of our work
in Section I, we outline the non-asymptotic framework for
quantum metrology in Section II and discuss optimizing
over metrology protocols in Section III. We describe the
optimal post-processing in the practically relevant case
of a fixed quantum measurement in Section III B. We
go on to describe the intimate connection to hypothesis
testing in Section IV and show in Section V how it can
be used to understand the achievable asymptotic per-
<figure><img src="image_5.png" /><figcaption>FIG. 3. Metrological tasks consist of estimating some physical properties of a quantum system. A basic protocol involves preparing a probe state $ρ_0$, letting it interact with the quantum system of interest, and then measuring the output state. We describe the most general protocols in Section IX. (a) In quantum parameter estimation, the parameter $t \in \mathbb{R}$ indicates the physical property of interest, which may be governed by an underlying random process with probability density function $\mu$. In our PAC metrology framework, we identify the success of the estimation procedure by correctly identifying the parameter $t$ up to a given tolerance $\delta$. (b) In quantum hypothesis testing, a set of quantum states with labels $x \in \mathcal{X}$ is given and the task is to design a measurement that maximizes the probability of correctly identifying the label $x$. (c) The core contribution of our work is a rigorous connection between quantum hypothesis testing and quantum parameter estimation. Specifically, we show that the parameter estimation problem of (a) is at least as hard as distinguishing states that are mutually at least $2\delta$ apart in the hypothesis testing setting of (b) – see Theorem 10.</figcaption></figure>

performance in general quantum metrology problems. Section VII is dedicated to the optimal metrological tolerance for a fixed success probability and relates it to the hypothesis testing relative entropy. We showcase the various applications of our quantifiers in Section XI where we perform a minimax analysis of the phase estimation problem. We discuss the generalization of our definitions and results to multivariate quantum metrology and their relation to learning from quantum systems in Section XII. Our work concludes with a detailed outline of future directions in Section XIII and a discussion of our results in Section XIV.

# I. OVERVIEW OF OUR MAIN RESULTS

We establish the following main results.

* *A framework for quantum metrology in the finite-sample regime.*

The framework of PAC metrology established in Section II and summarized in Fig. 2 constitutes an approach to quantum metrology that is both operational and valid in the single- and few-shot settings. We give rigorous definitions in Definition 1 (success probability), Definition 2 (tolerance) and Definition 3 (sample complexity). We show that the optimization of the success probability over metrological protocols can be carried out as a convex optimization problem, concretely a semi-infinite program [56, 57], an infinite reading of a semi-definite program [58, 59]. We further establish properties of the proposed quantifiers, relate them to entropic quantities and detail their practical computation.

* *A rigorous connection to hypothesis testing.*

In Theorem 10, we establish rigorously that the task of estimating a parameter encoded in a state $ρ(t)$ is at least as hard as performing a quantum multi-hypothesis test between parametrized states $\{ρ(t_i)\}_{i=1}^M$ associated to parameter values that are separated by at least twice the tolerance $\delta$, i.e. $|t_i - t_j| > 2\delta$ for $i \neq j$ (see Fig. 3). We also extend this upper bound to the case of parametrized quantum channels in Corollary 23. We make use of this theorem to derive a simple relation of success probability to the fidelity of states in Corollary 12 that forms the base of our further results.

* *Asymptotic rates of quantum metrology.*

We exploit the hypothesis testing bound of Theorem 10 to study the rate with which the success probability approaches one when using more and more copies of the same quantum state $ρ^{\otimes n}(t)$ while maintaining a fixed tolerance. In particular, we provide upper and lower bounds on error rates in Theorems 13 and 14 and show the exact asymptotic rate for commuting problems in Corollary 15.

* *A single-shot Cramér-Rao-like bound.*

The metrological tolerance, which quantifies the smallest deviation of metrological estimates that still guarantees a given success probability, fulfills a role similar in spirit to the standard deviation in the asymptotic framework of quantum metrology. We exemplify this similarity by giving a bound in Theorem 18 that resembles the Cramér-Rao bound but is valid in the single-shot setting. It establishes, among other insights, that the best achievable tolerance under many copies of the same state is $\delta = O(1/\sqrt{n \min_t F(t)})$, similar in scaling to the quantum Cramér-Rao bound on the standard deviation.

* *A finite-sample analysis of phase estimation.*
We devote Section XI to a minimax analysis of the phase estimation problem on an ensemble of spin-1/2 particles, i.e. the estimation of a phase imprinted by a Hamiltonian evolution. For the general case of a covariant Hamiltonian evolution, we give the measurement achieving the optimal success probability and provide a formula in closed form in Theorem 24. This allows us to find the optimal probe state in the phase estimation scenario and to establish the optimal asymptotic rate of the error probability in Theorem 25. We perform exhaustive numerics that showcase the differences of the single-shot analysis from the asymptotic framework, highlighting that the optimal probe states in this instance of global estimation are notably different from the optimal states for local estimation. We furthermore give evidence that in the setting of i.i.d. copies of the same state, the quantum Cramér-Rao bound gives a faithful estimate of the achievable minimax tolerance.

## II. A FRAMEWORK FOR QUANTUM METROLOGY IN THE FINITE-SAMPLE REGIME

We consider the task of estimating an unknown parameter that is encoded in a quantum state. Let $t \mapsto \rho(t)$ be a one-parameter family of quantum states, where the parameter $t$ belongs to some fixed real interval $t \in I \subseteq \mathbb{R}$. For technical convenience, we assume that the interval $I$ is given as the domain of the function $t \mapsto \rho(t)$ and henceforth omit explicit mention of $I$, all while assuming that $t$ belongs to the domain of $t \mapsto \rho(t)$.

We first review the general abstract basics of Bayesian parameter estimation and the alternative minimax parameter estimation setting. These definitions work independently of the actual metrological problem and, as we show later, can be easily generalized to multivariate quantum metrology and metrology of quantum channels. We then consider the setting depicted in Fig. 1, where a parameter is to be extracted from a parametrized quantum state through a quantum measurement. This allows us to rigorously establish our framework as outlined in Fig. 2.

Through this development, we establish measures of performance that have a direct operational meaning in the non-asymptotic setting where only few experimental repetitions can be performed. Our approach revolves around the question: “What is the probability $\eta$ of outputting an estimate that is within a given tolerance $\delta$ around the true value?”

We first see how we can answer this question in the general setting of Bayesian parameter estimation. Suppose the value of the underlying parameter is distributed according to a prior distribution $\mu(t)$, $t \sim \mu(t)$. Given a value of $t$, we assume that the probability of our estimation procedure producing the estimate $\tau$ is distributed according to $\nu(\tau|t)$. Then we can compute the Bayesian

success probability as

$$ \eta = \int d\mu(t) d\nu(\tau|t) w_{\delta}(t-\tau), \quad (3) $$

where $w_{\delta}(t-\tau) := \chi[|t-\tau| \le \delta]$ represents a window of size $\delta$ around the true value, with $\chi(\cdot)$ the indicator function that is equal to one when its argument is true and zero otherwise.

An alternative setting applies to the case where we have no prior information about the parameter $t \in I$. Suppose that for a fixed value of $t$, the probability of our estimation procedure producing the estimate $\tau$ is again distributed according to $\nu(\tau|t)$. In this case, the probability of success, in the worst case over $t$, is determined as

$$ \bar{\eta} = \inf_{t \in I} \int d\nu(\tau|t) w_{\delta}(t-\tau). \quad (4) $$

While this setting is radically different from Bayesian estimation on the conceptual level, we exploit a close relation between these settings at the technical level in order to simplify our derivations. Specifically, the quantity in Eq. (4) can be expressed as the Bayesian success probability of Eq. (3) minimized over all possible priors with support in $I$:

$$ \bar{\eta} = \inf_{\mu: \mu(I)=1} \int d\mu(t) d\nu(\tau|t) w_{\delta}(t-\tau). \quad (5) $$

Indeed, the minimum in Eq. (5) is achieved by a prior $\mu(t)$ that is concentrated at the time $t$ where the minimum in Eq. (4) is achieved. In other words, we might consider an adversary who gets to choose the prior $\mu(t)$ according to which the parameter value is distributed. The worst thing that can happen is that an adversary chooses a very unfortunate prior. In this case, we can still guarantee the success probability lower bounded by $\bar{\eta}$. We refer to this setting as the minimax setting, following standard terminology in statistics. The name stems from the two optimizations that are involved when we optimize Eq. (5) over possible estimation procedures: one optimization ranges over the estimation procedure and the other one over $\mu(t)$.

The window function $w_{\delta}(t-\tau)$ in the definitions above identifies the successful events as those where $t$ and $\tau$ differ by at most $\delta$. More general window functions can be employed to quantify alternative definitions of success. For instance, if the parameter represents an angle $t \in [0, 2\pi]$, a meaningful window function would identify $t$ and $\hat{t}$ as $\delta$-close under the topology of the unit circle.

We now turn to our specific setup in quantum metrology as depicted in Fig. 1. We consider the setting where the parameter in question is encoded in a set of states $t \mapsto \rho(t)$. In this case any prediction must be obtained from performing some sort of quantum measurement on the given state and subsequently classically post-processing the outcome of the measurement into a prediction. We can combine both of these elements into a
POVM $\tau \mapsto Q(\tau)$ such that

$$ \nu(\tau|t) = \mathrm{Tr}[\rho(t)Q(\tau)]. \qquad (6) $$

This leads us to the following formal definition.

**Definition 1** (Success probability). For a given tolerance $\delta$, a set of states $\rho(t)$, possibly with prior $\mu(t)$, and a measurement $Q(\tau)$, the Bayesian success probability is given by

$$ \eta(\delta, \mu, \rho, Q) := \int d\mu(t) d\tau w_{\delta}(t-\tau) \mathrm{Tr}[\rho(t)Q(\tau)]. \quad (7) $$

The minimax success probability is given by

$$ \bar{\eta}(\delta, \rho, Q) := \inf_t \int d\tau w_{\delta}(t-\tau) \mathrm{Tr}[\rho(t)Q(\tau)]. \quad (8) $$

We observe that the success probability can be more compactly written using the convolution notation

$$ (w * \rho)(t) := \int d\tau w(t-\tau)\rho(\tau) \quad (9) $$

as

$$ \eta(\delta, \mu, \rho, Q) = \int d\mu(t) \mathrm{Tr}[\rho(t)(w_{\delta} * Q)(t)] \quad (10) \\ = \int dt \mathrm{Tr}[(w_{\delta} * [\mu \cdot \rho])(t)Q(t)], $$

and we will use this notation in the rest of this work.

The success probability of Definition 1 quantifies the probability that our metrology protocol outputs a correct estimate. This is very reminiscent of the strategy used to quantify the performance of learning algorithms pioneered by Valiant [29], which was coined as probably approximately correct (PAC) learning. As this naming also conveys the essence of our approach to quantum metrology, we refer to it as probably approximately correct (PAC) metrology.

As we show in Section V of the supplementary material, both the Bayesian and minimax success probabilities have basic continuity properties in all their arguments and allow for intuitive majorization relations.

In addition to the success probability as a measure of metrological performance, it is equally fair and operationally relevant to reverse the question and ask: “What is the smallest tolerance $\delta$ that still guarantees a success probability of $\eta$?” We condense this reasoning into the following rigorous definition:

**Definition 2** (Estimation tolerance). For a given success probability $\eta$, a set of states $\rho(t)$, possibly with prior $\mu(t)$, and a measurement $Q(\tau)$, the Bayesian estimation error tolerance is given by

$$ \delta(\eta, \mu, \rho, Q) := \inf \{\delta' \ge 0 \mid \eta(\delta', \mu, \rho, Q) \ge \eta\}. \quad (11) $$

The minimax estimation error tolerance is given by

$$ \bar{\delta}(\eta, \rho, Q) := \inf \{\delta' \ge 0 \mid \bar{\eta}(\delta', \rho, Q) \ge \eta\}. \quad (12) $$

Looking at the estimation error tolerance instead of the success probability allows for a simpler comparison with the standard bounds encountered in quantum metrology, as the tolerance has comparable meaning to the standard deviation of an estimator, which is the target of the quantum Cramér-Rao bound.

Both the success probability and the tolerance introduced in Definitions 1 and 2 are truly single-shot quantities, in that they consider a single outcome of the quantum measurement. Usually, however, the desired performance can only be achieved by performing multiple repetitions of the same experiment. We model multiple repetitions of an experiment by having access to n copies of the parametrized state, i.e., $t \mapsto \rho^{\otimes n}(t)$. The measurement $Q(\tau)$ is then collectively measure the n copies of the state.

The multi-copy scenario leads us to a third operationally relevant question: “How many repetitions n of my experiment do I need to perform to obtain a desired tolerance $\delta$ with a fixed success probability $\eta$?” We can cast this sample complexity into the following definition:

**Definition 3** (Sample complexity). For a given success probability $\eta$ and tolerance $\delta$, a set of states $\rho(t)$, possibly with prior $\mu(t)$, and a sequence of measurements $\{Q^{(n)}(\tau)\}$ the Bayesian sample complexity is given by

$$ \begin{gathered} n(\eta, \delta, \mu, \rho, \{Q^{(n)}\}) \\ := \min \{n' \in \mathbb{N} \mid \eta(\delta, \mu, \rho^{\otimes n'}, Q^{(n')}) \ge \eta\}. \end{gathered} \quad (13) $$

The minimax sample complexity is given by

$$ \bar{n}(\eta, \delta, \rho, \{Q^{(n)}\}) := \min \{n' \mid \bar{\eta}(\delta, \rho^{\otimes n'}, Q^{(n')}) \ge \eta\}. \quad (14) $$

Results in the context of more general metrology tasks, like state tomography or Hamiltonian learning are therefore usually phrased in terms of the sample complexity. We explore this connection and the multivariate generalization of this framework in Section XII, where we show how our definitions and results generalize to these settings and how the languages can be compared.

Practical settings in quantum metrology often involve estimating an unknown parameter present in the dynamics of a system, rather than directly encoded into the state itself. Such dynamics might involve interactions with an environment system, or another quantum system whose properties we seek to estimate. Formally, the task becomes that of estimating an unknown parameter present in a quantum channel by applying the unknown channel on suitable inputs and performing suitable subsequent measurements. In simple cases, the channel parameter estimation problem can reduce to a state estimation problem: One prepares a fixed initial state $\rho_0$ and sends it through the channel, resulting in a state $\rho(t)$; the task is now to estimate the parameter $t$ encoded in the quantum state. The channel estimation problem, however, provides a richer landscape of estimation strategies
when more than one copy of the channel is available. We discuss this setting in Section IX.

With the preceding definitions that form our few-shot framework of PAC metrology, we have established a set of quantities that capture the performance of finite-sample quantum metrology protocols. Here, we discuss the optimal values these quantities can take, when we optimize over all possible metrological prescriptions. This brings us to the following definitions of optimal counterparts of the Definitions 1, 2 and 3.

**Definition 4 (Optimal Bayesian quantities).** The optimal Bayesian success probability is obtained by optimizing the Bayesian success probability over all possible POVMs:

$$ \eta^*(\delta, \mu, \rho) := \sup_{Q(\tau)} \eta(\delta, \mu, \rho, Q). \quad (15) $$

We use it to define the optimal Bayesian tolerance

$$ \delta^*(\eta, \mu, \rho) := \inf \{\delta' \ge 0 \mid \eta^*(\delta', \mu, \rho) \ge \eta\} \quad (16) $$

and optimal Bayesian sample complexity

$$ n^*(\eta, \delta, \mu, \rho) := \min \{n' \in \mathbb{N} \mid \eta^*(\delta, \mu, \rho^{\otimes n'}) \ge \eta\}. \quad (17) $$

The optimal minimax quantities are defined analogously.

**Definition 5 (Optimal minimax quantities).** The optimal minimax success probability is obtained by optimizing the minimax success probability over all possible POVMs:

$$ \bar{\eta}^*(\delta, \rho) := \sup_{Q(\tau)} \bar{\eta}(\delta, \rho, Q). \quad (18) $$

We use it to define the optimal minimax estimation tolerance

$$ \bar{\delta}^*(\eta, \rho) := \inf \{\delta' \ge 0 \mid \bar{\eta}^*(\delta', \rho) \ge \eta\} \quad (19) $$

and optimal minimax sample complexity

$$ \bar{n}^*(\eta, \delta, \rho) := \min \{n' \in \mathbb{N} \mid \bar{\eta}^*(\delta, \rho^{\otimes n'}) \ge \eta\}. \quad (20) $$

The optimal Bayesian and minimax success probabilities have desirable properties such as convexity in their arguments and data-processing under noise channels, a point we elaborate on in Section V of the supplementary material.

We do not have an a-priori restriction on the domain of the parameter $t$ when calculating the success probability. However, it is often easier to compute it, both analytically and numerically, if we restrict it to a finite interval. While this is trivially giving a bound in the minimax case, the following lemma ensures that we can also use the restriction to a subinterval to compute bounds for the optimized Bayesian success probability:

**Lemma 6 (Subdivision trick).** For a given tolerance $\delta$ and a set of states $\rho(t)$ with prior distribution $\mu(t)$, define the restriction of a prior to an interval $I \subseteq \mathbb{R}$ as

$$ \mu|_{I}(t) := \chi[t \in I]\mu(t)/\mu(I). \quad (21) $$

Let us further denote with $I_t$ the interval of size $T$ centered at $t$. Then, we have that

$$ \eta^*(\delta, \rho, \mu) \le \frac{1}{T} \int dt \, \mu(I_t) \eta^*(\delta, \rho, \mu|_{I_t}) \quad (22) \\ \le \max_t \eta^*(\delta, \rho, \mu|_{I_t}). $$

The proof is provided in Section VC of the supplementary material. The above immediately implies corresponding subdivision lower bounds on the optimal tolerance and optimal sample complexity.

### III. COMPUTING OPTIMAL MEASUREMENTS

#### A. Generally optimal measurements through convex optimization

Of the three quantities, the success probability is the most amenable to optimization. It is linear in the chosen measurement, and we can show that the optimization over the measurement $Q(\tau)$ can be cast into the form of a convex problem [59]. Specifically, it assumes the form of a semi-infinite problem [56, 57], so a semi-definite problem with infinitely many objective variables and finitely many constraints, or the other way around. For the theory of semi-definite programming to largely take over, the involved functions must be analytically defined, smooth, and convex [57], which can be safely assumed here. In what follows, we refer to such infinite readings of semi-definite problems as convex problems. This does not only provide a path to more easily compute them, but is also a reliable tool to prove upper and lower bounds.

**Proposition 7 (POVM optimization).** For a given tolerance $\delta$ and a set of states $\rho(t)$ with prior distribution $\mu(t)$, the optimal success probability $\eta^*(\delta, \mu, \rho)$ can be computed using the convex program

$$ \max_{Q(t) \ge 0} \left\{ \left| \int dt \operatorname{Tr}[(w_{\delta} * [\mu \cdot \rho])(t)Q(t)] \right| \int dt Q(t) = \mathbb{I} \right\}. \quad (23) $$

The optimal success probability is equally characterized by the convex program

$$ \min_{X \ge 0} \left\{ \operatorname{Tr}[X] \mid X \ge (w_{\delta} * [\mu \cdot \rho])(t) \text{ for all } t \right\}. \quad (24) $$

The minimax success probability can be computed in a similar way by additionally optimizing over all priors.

The second convex program in Eq. (24) is derived through the notion of duality in semi-infinite programming. The proof of the above proposition, along with a
more detailed statement is provided in Proposition 2 of the supplementary material, where we also explicitly give the convex formulation of the minimax success probability.

From a practical standpoint, it is also important that the above semi-infinite program can actually be implemented numerically while having guarantees on the quality of the approximation.

**Proposition 8 (Discretization).** There exists a discretization of the convex-program of Proposition 7 that yields a semi-definite program that can be solved with standard tools. If $\rho(t)$ is Lipschitz with respect to the trace distance, the error of the discretization can be made arbitrarily small by choosing a suitable scale of the discretization.

We give the detailed statements of the above in Section III F of the supplementary material. The optimal tolerance and sample complexity can in principle be computed by combining the above semi-definite program with binary search [60].

## B. Maximum-likelihood-inspired post-processing of the outcome of a fixed measurement

The general structure of the solutions to the convex problem of Proposition 7 is unclear a priori. Consequently, the optimal measurement for a given metrological problem might be either impractical or impossible to implement in an experiment. Here, we study the performance of strategies that naturally model strategies that deal with experimental restrictions on the possible measurements that can be performed.

As shown in Fig. 4, we consider an estimation strategy that begins by applying a fixed quantum measurement described by a POVM $\{M(\lambda)\}_\lambda$. For instance, the POVM might represent a projective measurement in a fixed basis. Subsequently, the procedure infers from the outcome $\lambda$ an estimate $\tau^*(\lambda)$ for the value $t$ that is encoded in the measured state. We focus on a particular post-processing strategy $\tau^*(\lambda)$ inspired by the maximum-likelihood estimation technique.

If we only fix the quantum-to-classical measurement, the question of the optimal post-processing of the measurement outcomes for such a fixed measurement of the quantum system arises. The authors of Ref. [55] studied such a setting, but focusing on more fundamental point of view on when a quantum-to-classical measurement can be considered admissible in a statistical sense. A fixed measurement can be discrete, like a measurement in a specific basis, or continuous, like a pretty good measurement. We can model both cases in a unified way by assuming a POVM with continuous outcomes $\{M(\lambda)\}_\lambda$. For a given set of states $\rho(t)$, we can define the likelihood function

$$ \Lambda(\lambda | t) := \mathrm{Tr}[\rho(t) M(\lambda)] \quad (25) $$

<figure><img src="image_6.png" /><figcaption>FIG. 4. Metrology setting with fixed measurement as discussed in Section III B. A parametrized state $\rho(t)$ is measured with a POVM $\{M(\lambda)\}_\lambda$ fixed by, e.g., experimental feasibility restrictions. We show that the optimal way of post-processing the measurement outcome $\lambda$ into predictions of the underlying parameter $t$ is given by a smoothed analogue of maximum a posterior estimation in the Bayesian case. A similar strategy also manages to provide a guarantee on the achievable success probability in the minimax case.</figcaption></figure>

which captures the distribution over measurement outcomes for a fixed value of the underlying parameter $t$. The joint distribution of measurement outcomes and underlying parameters is then given by

$$ (\lambda, t) \sim \mu(t) \Lambda(\lambda | t). \quad (26) $$

If we denote the marginal distribution of the measurement outcomes $\lambda$ as

$$ \nu(\lambda) := \int d\mu(t) \Lambda(\lambda | t), \quad (27) $$

then the joint distribution is related to the posterior distribution of the underlying parameter given an observed measurement outcome $\lambda$ as

$$ P(t|\lambda) := \frac{\mu(t)\Lambda(\lambda|t)}{\int d\mu(t) \Lambda(\lambda|t)}. \quad (28) $$

With this notation, we equivalently have that the joint distribution can be written as

$$ (\lambda, t) \sim \nu(\lambda) P(t|\lambda). \quad (29) $$

As the measurement $\{M(\lambda)\}$ is fixed, the only thing left to optimize is the prediction we make when observing a certain measurement outcome $\lambda$. We denote this prediction as $\tau^*(\lambda)$ and refer to this function as a prediction strategy. The POVM $Q(\tau)$ associated to the combination of fixed POVM $\{M(\lambda)\}_\lambda$ together with a prediction strategy $\tau^*(\lambda)$ is given by collecting all POVM effects $M(\lambda)$ associated to a particular prediction $\tau$:

$$ Q_{M,\tau^*}(\tau) = \int d\lambda \chi[\tau^*(\lambda) = \tau] M(\lambda). \quad (30) $$

With this POVM, it is straightforward to see that the Bayesian success probability takes the form

$$ \begin{aligned} \eta(\delta, \mu, \rho, Q_{M,\tau^*}) &= \int d\mu(t) d\lambda w_\delta(t - \tau^*(\lambda)) \Lambda(\lambda | t) \\ &= \int d\nu(\lambda) (w_\delta * P(\cdot | \lambda))(\tau^*(\lambda)). \end{aligned} \quad (31) $$
In the second line, we see that the posterior distribution of $t$ given the observed measurement outcomes is critical to the success probability.

A look at Eq. (31) reveals that the optimal prediction strategy is to always predict the $\tau^*$ that maximizes the smoothed posterior probability $w_\delta * P(\cdot | \lambda)$. In accordance with the naming conventions of classical statistics, we refer to this prediction rule

$$ \tau_{\text{SMAP}}^{*}(\lambda) := \underset{\tau}{\operatorname{argmax}} (w_{\delta} * P(\cdot | \lambda))(\tau) \quad (32) $$

as the smoothed maximum a posteriori (SMAP) estimate. This represents a smoothed version of maximum a posteriori estimation, the Bayesian generalization of maximum likelihood estimation. The so achieved Bayesian success probability is consequently

$$ \begin{aligned} \eta(\delta, \mu, \rho, Q_{M,\tau_{\text{SMAP}}^*}) &= \int d\nu(\lambda) \max_{\tau} (w_{\delta} * P(\cdot | \lambda))(\tau) \\ &= \int d\nu(\lambda) \|w_{\delta} * P(\cdot | \lambda)\|_{\infty}. \end{aligned} \quad (33) $$

The relation to the function infinity norm allows us to derive some simple upper bounds on the success probability from Young's convolution inequality, as stated in Lemma 14 of the supplementary material. We will later make use of smoothed maximum a posteriori estimation to obtain lower bounds on the asymptotic error rate of quantum metrology protocols. To summarize:

**Theorem 9** (Optimal post-processing of a fixed measurement in the Bayesian setting). For a given tolerance $\delta$, state set $\rho(t)$ with prior $\mu(t)$ and a fixed POVM $\{M(\lambda)\}_\lambda$, the optimal Bayesian success probability of an estimation strategy that measures $\{M(\lambda)\}$ and post-processes the result is achieved by the smoothed maximum a posteriori estimator:

$$ \sup_{\tau^*} \eta(\delta, \mu, \rho, Q_{M,\tau^*}) = \eta(\delta, \mu, \rho, Q_{M,\tau_{\text{SMAP}}^*}). \quad (34) $$

Having established the optimal strategy in the Bayesian setting, we now turn to the minimax case. With the definitions introduced earlier, the minimax success probability associated to a prediction strategy $\tau^*$ is given by

$$ \bar{\eta}(\delta, \rho, Q_{M,\tau^*}) = \min_t \int d\lambda w_\delta(t - \tau^*(\lambda)) \Lambda(\lambda | t). \quad (35) $$

The minimum over $t$ is outside the integration over the different measurement outcomes $\lambda$, which means that, contrary to the Bayesian case, we cannot optimize the prediction for each $\lambda$ independently. We can, however, still establish a lower bound on the minimax success probability for the optimal prediction strategy. To do so, we

need to go via the minimax error probability:

$$ \begin{aligned} & 1 - \bar{\eta}(\delta, \rho, Q_{M,\tau^*}) \tag{36} \\ &= 1 - \min_t \int d\lambda w_\delta(t - \tau^*(\lambda)) \Lambda(\lambda | t) \\ &= \max_t \int d\lambda \Lambda(\lambda | t) - \min_t \int d\lambda w_\delta(t - \tau^*(\lambda)) \Lambda(\lambda | t) \\ &= \max_t \int d\lambda [1 - w_\delta(t - \tau^*(\lambda))] \Lambda(\lambda | t). \end{aligned} $$

Here, we have exploited that $\int d\lambda \Lambda(\lambda | t) = 1$ for all $t$. We have thus reformulated the minimax error probability as a function of the complement of the window function. We can then exchange integration and maximization to obtain the upper bound on the error

$$ 1 - \bar{\eta}(\delta, \rho, Q_{M,\tau^*}) \le \int d\lambda \max_t [1 - w_\delta(t - \tau^*(\lambda))] \Lambda(\lambda | t) \quad (37) $$

The above bound can now be optimized independently for all $\lambda$ which gives us a strategy analogous to the maximum a posterior estimation we have used in the Bayesian case. We will refer to as smoothed minimax complementary likelihood (SMCL) estimate,

$$ \tau_{\text{SMCL}}^{*}(\lambda) := \underset{\tau}{\operatorname{argmin}} \max_{t} [1 - w_{\delta}(t - \tau)] \Lambda(\lambda | t). \quad (38) $$

This strategy amounts to choosing $\tau$ such that the largest values of $\Lambda(\lambda | t)$ are contained in the window centered around $\tau$. Using this strategy then establishes the bound

$$ \begin{aligned} & 1 - \sup_{\tau^*} \bar{\eta}(\delta, \rho, Q_{M,\tau^*}) \tag{39} \\ & \le \int d\lambda \min_{\tau} \max_{t} [1 - w(t - \tau)] \Lambda(\lambda | t) \end{aligned} $$

on the minimax error probability that can be achieved using the optimal post-processing.

## IV. FINITE-SAMPLE QUANTUM METROLOGY AS CONTINUOUS HYPOTHESIS TESTING

One might imagine that, intuitively, determining a parameter encoded in a quantum system is intimately related to the task of distinguishing states for different values of the parameter. This reasoning has already been used in the standard approach to quantum metrology to obtain asymptotic bounds, for example through the quantum Ziv-Zakai bound [51]. These approaches, however, are still hampered by the limitations of the standard approach to quantum metrology. As we outline below, by choosing the success probability as a measure of metrological performance, the connection to the task of distinguishing quantum states is much more natural and fundamental.
The optimal probability of success for distinguishing a set of N quantum states {$ρ_i$}N$_{i=1}$ with prior probabilities {$p_i$}N$_{i=1}$ – a test between N quantum hypotheses – is given by<fnref n="1" />

$$P_s^*(\{p_i \rho_i\}_{i=1}^N) := \sup_{\substack{\text{POVMs} \\ \{Q_i\}_{i=1}^N}} \sum_{i=1}^N p_i \text{Tr}[\rho_i Q_i]. \quad (40)$$

Similarly, the optimal minimax success probability is defined as

$$\bar{P}_s^*(\{\rho_i\}_{i=1}^N) := \sup_{\substack{\text{POVMs} \\ \{Q_i\}_{i=1}^N}} \min \text{Tr}[\rho_i Q_i]. \quad (41)$$

Already, Yuen et al. [61] have studied an extension of this definition with an additional cost matrix $C_{ij}$ and the associated optimal expected cost

$$\inf_{\substack{\text{POVMs} \\ \{Q_i\}_{i=1}^N}} \sum_{i=1}^N \sum_{j=1}^N p_i C_{ij} \text{Tr}[\rho_i Q_j] \quad (42)$$

and have shown that this constitutes a semi-infinite problem. A look at Proposition 7 shows that our notion of Bayesian success probability can be understood as a continuous version of this definition in which the complement of the window function, $1 - w_δ$, takes the role of the cost function.

Because of this close resemblance of metrological problems to generalized multi-hypothesis testing problems, it is unsurprising that every quantum multi-hypothesis testing problem can be written as a particular metrology problem with suitably chosen prior distribution and tolerance (see Section VII A of the supplementary material). We, however, also establish a result in the other direction that bounds the optimal Bayesian and minimax success probability for a metrological problem through multi-hypothesis testing. It is intuitively clear that being able to determine a parameter $t$ to a precision $δ$ means that we must be able to sufficiently well distinguish between states that are at least $2δ$ apart. We make this reasoning rigorous in the below theorem.

**Theorem 10 (Hypothesis testing bound).** For a given tolerance $δ$, fix any set $S = \{(λ, s)\}$ of prior probabilities $λ \in [0, 1]$ and shifts $s \in R$ such that for all distinct $s, s' \in S$ we have that $|s - s'| > 2δ$ and $\sum_{λ \in S} λ = 1$. Then, for a state set $ρ(t)$ with prior $μ(t)$ we have the upper bound

$$\eta^*(\delta, \mu, \rho) \le \int dt P_s^*(\{\lambda \mu(t+s)\rho(t+s)\}_{(\lambda,s) \in S}). \quad (43)$$

<figure><img src="image_7.png" /><figcaption>FIG. 5. A visualization of Theorem 10. Telling the time with a certain tolerance $δ$ is at least as hard as deducing if an adversary manipulated the clock, under the guarantee that the manipulation is not smaller than twice the tolerance $δ$.</figcaption></figure>

Optimizing over the prior probabilities $λ$ then yields the analogous upper bound in the minimax setting

$$\bar{\eta}^*(\delta, \rho) \le \inf_t \bar{P}_s^*(\{\rho(t+s)\}_{s \in S}). \quad (44)$$

We established that a metrological problem is at least as hard as determining whether an adversary has manipulated the clock used for the experiment by shifting its time by one of the values $s$ in the set $S$ with probability $λ$. The tolerance $δ$ gives us a lower bound on the distance between the different shifts and therefore works in our favor. The proof of the theorem is presented in Section VII B of the supplementary material. It also generalizes to parametrized quantum channels as discussed in Section IX.

We note that application of Theorem 10 is especially useful analytically when restricting to two shifts, because then the analytic expression for the success probability of binary hypothesis testing due to Helstrom [62] can be used. Looking at the minimax case with two shifts, we further obtain what can be considered as an analogue of Le Cam’s two point method [63]:

**Corollary 11 (Two-point method).** For a given tolerance $δ$ and state set $ρ(t)$, we have the upper bound on the minimax success probability

$$\bar{\eta}^*(\delta, \rho) \le \inf_{|t-t'|>2\delta} \bar{P}_s^*(\rho(t), \rho(t')). \quad (45)$$

The above result, together with the Fuchs-van-de Graaf inequalities allows us to further deduce a relation to the quantum fidelity

$$F(\rho, \sigma) := \text{Tr}[(\sigma^{1/2}\rho\sigma^{1/2})^{1/2}] \quad (46)$$

which we will use later to give a concise sample complexity bound, as shown in Section VII C of the supplementary material.

**Corollary 12.** For a given tolerance $δ$ and state set $ρ(t)$, we have the minimax error probability lower bound

$$1 - \bar{\eta}^*(\delta, \rho) \ge \frac{1}{4} \sup_{|t-t'|>2\delta} F(\rho(t), \rho(t'))^2. \quad (47)$$

<footnote n="1">¹ This is the definition of symmetric hypothesis testing, where all states are treated equally and the average success probability is used as quantifier. In asymmetric hypothesis testing, the states are treated independently.</footnote>
We can use similar reasoning as in the derivation of Theorem 10 to obtain a lower bound that makes use of asymmetric hypothesis testing. The resulting bounds are presented in Section VIID of the supplementary material.

We explore other directions that yield metrology bounds of different forms in Section VIIIF of the supplementary material. Along the way, we present some bounds for quantum multi-hypothesis testing in Section VIIIE of the supplementary material.

## V. ASYMPTOTIC BEHAVIOR OF THE SUCCESS PROBABILITY IN THE I.I.D. REGIME

In this section, we consider our framework in the limit where many independent and identically distributed (i.i.d.) copies of the state are available. We aim to understand this asymptotic limit of our framework in order to connect our finite-sample approach to standard approaches in metrology and information theory where many copies of the state are assumed to be available. We exploit Theorem 10 to compute an upper bound on the asymptotic rate with which both the Bayesian and minimax success probability approach one. Formally, we define the asymptotic error rate as

$$R^*(\delta, \mu, \rho) := \lim_{n \to \infty} -\frac{1}{n} \log (1 - \eta^*(\delta, \mu, \rho^{\otimes n})), \quad (48)$$

when the limit exists. The minimax rate $\bar{R}^*(\delta, \rho)$ is defined analogously.

We relate the asymptotic rate of a metrological problem to the asymptotic rate of hypothesis testing [15, 64], which is given in terms of the Chernoff divergence

$$C(\rho, \sigma) := - \inf_{0 \le s \le 1} \log \mathrm{Tr}[\rho^s \sigma^{1-s}]. \quad (49)$$

By analogy to multi-hypothesis testing, where the asymptotic rate is given by the smallest Chernoff divergence between two states that are to be discriminated, we obtain the following upper bound:

**Theorem 13 (Upper bound on asymptotic rate).** For a given tolerance $\delta$ and a set of states $\rho(t)$, possibly with prior $\mu(t)$, the Bayesian and the minimax rate obey the upper bounds

$$\bar{R}^*(\delta, \rho) \le R^*(\delta, \mu, \rho) \le \inf_{|t-t'|>2\delta} C(\rho(t), \rho(t')), \quad (50)$$

where the optimization is over time values that have non-vanishing support in the possible priors.

We emphasize that for the above statement and the ones are to follow in this section, we implicitly assumed that the support of $\mu$ encompasses the whole admissible set of values for the parameter $t$ that is used to compute the minimax success probability. Restrictions to smaller admissible sets of parameters are possible and the results

carry over straightforwardly. The above theorem establishes that a metrological problem is asymptotically at most as hard as the hardest binary hypothesis testing problem of two states whose associated time values are at least $2\delta$ apart. The proof of the theorem uses Theorem 10 together with Laplace's principle and is presented in Section VIIIG of the supplementary material.

In quantum multi-hypothesis testing, the smallest pairwise rate is actually achievable [15] and, because of the results below on the commuting case, we believe this to also be true in the case of quantum metrology, at least under suitable regularity assumptions. While we were not yet able to prove this general statement, we succeeded in establishing a lower bound that guarantees an asymptotic rate equal to the best pairwise hypothesis testing rate for a fixed measurement sequence. Formally, we consider a fixed sequence of measurements $\{M^{(n)}\}$ for $n \in \mathbb{N}$ with outcomes $\lambda$ (compare to Section III B), and denote the channel that maps states to their output distributions over $\lambda$ as

$$\mathcal{M}^{(n)}[\rho] = \int d\lambda |\lambda\rangle\langle\lambda| \mathrm{Tr}[\rho M^{(n)}(\lambda)]. \quad (51)$$

This sequence achieves the following rate for binary state discrimination:

$$R(\rho, \sigma, \{M^{(n)}\}_{n \in \mathbb{N}}) := \lim_{n \to \infty} -\frac{1}{n} \log \left( 1 - P_s^*(\mathcal{M}^{(n)}[\rho^{\otimes n}], \mathcal{M}^{(n)}[\sigma^{\otimes n}]) \right). \quad (52)$$

With this notation in place, we have the following theorem, which adds the additional assumption that the set of states is continuous:

**Theorem 14 (Asymptotic rate with fixed measurement scheme).** For a given tolerance $\delta > 0$, a continuous set of states $\rho(t)$, possibly with prior $\mu(t)$ of full support, and any fixed measurement sequence $\{M^{(n)}\}$ for $n \in \mathbb{N}$, we have

$$R^*(\delta, \mu, \rho) \ge \bar{R}^*(\delta, \rho) \ge \inf_{|t-t'|>2\delta} R(\rho(t), \rho(t')), \{M^{(n)}\}. \quad (53)$$

In the above theorem, the possible values of $t$ are constrained to the domain of $\rho(t)$ and priors that have full support on said domain. Priors with restricted support fulfill the theorem with $t$ and $t'$ contained in the restricted domain. The proof uses a discretization argument together with the smoothed maximum a posteriori estimation technique introduced in Section III B and is given in Section VII of the supplementary material. In the case where an optimal measurement sequence is known, however, this lower bound already achieves the rate. This is particularly true in the commuting (i.e., classical) case:

**Corollary 15 (Asymptotic rate for commuting states).** For a given tolerance $\delta > 0$, a continuous set of states $\rho(t)$ such that $[\rho(t), \rho(t')] = 0$ for all $t, t'$, possibly with
prior $\mu(t)$, we have that

$$R^*(\delta, \mu, \rho) = \bar{R}^*(\delta, \rho) = \inf_{|t-t'|>2\delta} C(\rho(t), \rho(t')), \quad (54)$$

where the optimization is over time values that have non-vanishing support in the possible priors.

We believe that the strong connection we established here to hypothesis testing between multiple quantum states serves as a motivation to further explore the connection between quantum metrology and quantum information tasks. This should be a fruitful endeavor that allows researchers both with a background in quantum metrology as well as in quantum information processing to make an impact on quantum metrology.

## VI. RELATION TO ENTROPIC QUANTITIES

In the single-shot approach to quantum information theory [17, 28], many quantum information processing tasks can be quantified through generalized notions of entropy. In this section, we explore how our definitions relate to some of these concepts.

We start by giving an alternative definition of the optimal Bayesian success probability. To do so, we define the conditional min-entropy of a bipartite and positive semi-definite classical-quantum operator [65]

$$H_{\min}(T|S)_X := -\inf_{\sigma_S} D_{\max}(X_{TS} | \mathbb{I}_T \otimes \sigma_S), \quad (55)$$

where the max-relative entropy [66] of two positive semi-definite operators X and Y is given by

$$D_{\max}(X \| Y) := \log \|Y^{-1/2}XY^{-1/2}\|_{\infty}. \quad (56)$$

We then have the following corollary of the dual formulation of the optimal success probability in Proposition 7.

**Corollary 16** (Relation to conditional min-entropy). For a given tolerance $\delta$ and a set of states $\rho(t)$ with prior distribution $\mu(t)$, define the classical-quantum operator

$$X_{TS} := \int dt |t\rangle\langle t|_T \otimes (w_\delta * [\mu \cdot \rho])(t)_S, \quad (57)$$

where T is the time register and S the system register. Then

$$-\log \eta^*(\delta, \mu, \rho) = H_{\min}(T|S)_X. \quad (58)$$

Another angle on the same fact is given by defining the max-relative entropy radius [16] of a set of positive semi-definite operators $\mathcal{X}$ as

$$r_{\max}(\mathcal{X}) := \inf_{\sigma} \max_{x \in \mathcal{X}} D_{\max}(x \| \sigma). \quad (59)$$

In this case, the optimal success probability can be understood as the max relative entropy radius of the set of states “smoothed” using the window function

$$\log \eta^*(\delta, \mu, \rho) = r_{\max}(\{(w_\delta * [\mu \cdot \rho])(t)\}). \quad (60)$$

Both relations can be thought of continuous analogues of the known connection between the success probability of multi-hypothesis testing and the conditional min-entropy of classical-quantum states [16, 65]. In addition to the various known operational meanings of the conditional min-entropy [18, 65, 67–69], the relation of Corollary 16 endows it with yet another operational meaning, this time in the context of quantum metrology. Notably, the operator $X_{TS}$ of Corollary 16 is not normalized, unlike in the case of multi-hypothesis testing, due to the window function $w_\delta$. Another instance in which the conditional min-entropy of a non-normalized operator has an operational meaning is in the context of channel simulation [68, 69]. We provide the proofs of both relations in Section IV of the supplementary material.

Finally, we exploit the connection between quantum metrology and hypothesis testing derived in Ref. [19] to give an alternative lower bound on the optimal minimax success probability $\bar{\eta}^*$. The lower bound is expressed in terms of the hypothesis testing relative entropy [17, 70–74]

$$D_{\min}^{\eta}(\rho \| \sigma) := -\log \beta_{\min}^{\eta}(\rho \| \sigma), \quad (61)$$

where the asymmetric hypothesis testing error $\beta_{\min}^\eta$ is defined as

$$\beta_{\min}^{\eta}(\rho \| \sigma) := \inf_{0 \le M \le \mathbb{I}} \{\mathrm{Tr}[M\sigma] | \mathrm{Tr}[M\rho] \ge \eta\}. \quad (62)$$

We have the following proposition, reminiscent of a comparable result in Ref. [19].

**Proposition 17** (Lower bound on estimation tolerance in terms of the hypothesis testing relative entropy). For a set of states $\rho(t)$ and any $0 \le \eta \le \bar{\eta}^*(\delta, \rho)$, the minimax tolerance satisfies

$$\bar{\delta}(\eta, \rho) \ge \frac{1}{2} \int dt \exp(-D_{\min}^{\eta}(\rho(t) \| \sigma)) \quad (63)$$

for any state $\sigma$.

The proof exploits the SDP dual formulation of the hypothesis testing relative entropy and is given next to the more general statement of Theorem 32 of the supplementary material. We provide a proof that is independent of Ref. [19] for completeness.

## VII. A CRAMÉR-RAO-LIKE BOUND IN THE FINITE-SAMPLE REGIME

In this section, we want to further our understanding of the metrological tolerance defined in Definition 2 and its ultimate limits when optimizing over metrological protocols. Basic exploration of the definition of (optimal) tolerance was performed in Ref. [50], where the authors proposed a dimension-dependent lower bound that allowed them to conclude that the tolerance can only decrease asymptotically as $O(1/n)$, which corresponds to
Heisenberg scaling. Ref. [49] derived an upper bound in the case of i.i.d. repetitions with a fixed measurement.

In the asymptotic approach to quantum metrology, the most important tool is the *quantum Cramér-Rao bound*, which gives a lower bound on the standard deviation of any locally unbiased estimate, relating it to the inverse square root of the quantum Fisher information. This inherently geometric quantity measures how quickly the quantum states $\rho(t)$ change when the parameter $t$ is altered. As the first contribution of this section, we derive a lower bound that fulfills a similar role for the minimax tolerance.

We derive the bound from Corollary 12, which we rephrase in terms of the sandwiched Rényi relative entropies, which are defined in terms of a constant $\alpha \in (0, 1) \cup (1, \infty)$ as [17]

$$ \tilde{D}_{\alpha}(\rho \| \sigma) := \frac{1}{\alpha - 1} \log \mathrm{Tr} \left[ \left( \sigma^{\frac{1-\alpha}{2\alpha}} \rho \sigma^{\frac{1-\alpha}{2\alpha}} \right)^{\alpha} \right]. \quad (64) $$

In our case, the value $\alpha = \frac{1}{2}$ is crucial, as it connects to the fidelity of quantum states defined in Eq. (46):

$$ \begin{aligned} \tilde{D}_{\frac{1}{2}}(\rho \| \sigma) &= -\frac{1}{2} \log \mathrm{Tr}[(\sigma^{1/2} \rho \sigma^{1/2})^{1/2}] \quad (65) \\ &= -\frac{1}{2} \log F(\rho, \sigma). \end{aligned} $$

With this notation at hand, Corollary 12 can be rephrased as

$$ \log \left( \frac{1}{4(1 - \bar{\eta}^*(\delta, \rho))} \right) \le 4 \inf_{|t-t'| > 2\delta} \tilde{D}_{\frac{1}{2}}(\rho(t), \rho(t')). \quad (66) $$

Before we come to the formal statement, let us outline how this bound comes about in the case of i.i.d. copies. We can make the choice $t' = t + 2\delta$ in the above bound. For sufficiently small $\delta$ we can perform a Taylor expansion. We denote the Taylor expansion as

$$ \begin{aligned} \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t+\tau)) \\ &= \frac{1}{2} f_2(t) \tau^2 + \frac{1}{3!} f_3(t) \tau^3 + \frac{1}{4!} f_4(t) \tau^4 + \dots, \end{aligned} \quad (67) $$

where we envision $\tau = 2\delta$. The values $f_k(t)$ are the Taylor coefficients of the function $\tau \mapsto \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t+\tau))$ at $\tau = 0$, an explicit formula is given in Eq. (71). Because of the relationship between the sandwiched Rényi relative entropy and the fidelity, we have that the coefficient $f_2(t)$ is a constant multiple of the quantum Fisher information $f_2(t) = \frac{1}{8}\mathcal{F}(t)$, see Section VIII B of the supplementary material.

Let us now drop the explicit time dependence. If we could ignore the higher order terms in the Taylor expansion, we could simply choose $2\delta = \tau \propto 1/\sqrt{f_2}$ to render the error probability lower bound constant, which would give us the desired scaling of the bound. We will, however, need to work a bit harder to get something analytically meaningful. Let us choose $\tau = \gamma/\sqrt{f_2}$ in the above

expansion. Then, as long as $2\delta = \tau$ is within the radius of convergence of the Taylor series, we have

$$ \begin{aligned} \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t+\tau)) \\ &= \frac{1}{2}\gamma^2 + \frac{1}{3!} \frac{f_3}{f_2^{3/2}} \gamma^3 + \frac{1}{4!} \frac{f_4}{f_2^2} \gamma^4 + \dots. \end{aligned} \quad (68) $$

We immediately observe that the validity of the second order approximation depends on the ratios $f_p/f_2^{p/2}$. To get some intuition for these ratios, it is rather instructive to look at the case of i.i.d. copies, i.e., $\rho(t) \to \rho^{\otimes n}(t)$. In this case, the additivity of the sandwiched Rényi relative entropy implies that

$$ \tilde{D}_{\frac{1}{2}}(\rho^{\otimes n}(t) \| \rho^{\otimes n}(t+\tau)) = n \tilde{D}_{\frac{1}{2}}(\rho(t), \rho(t+\tau)). \quad (69) $$

This in turn means that all coefficients $f_p$ grow linearly in $n$, i.e. $f_p \to nf_p$ which implies that

$$ \frac{f_p}{f_2^{p/2}} \to \frac{1}{n^{\frac{p-2}{2}}} \frac{f_p}{f_2^{p/2}}, \quad (70) $$

meaning that higher order ratios decay more quickly, justifying the second order approximation in the limit of large $n$. Note that this is the same regime in which the asymptotic Cramér-Rao bound is attainable as well.

With the intuition we gained, we can now make sense of the following theorem.

**Theorem 18** (Non-asymptotic Cramér-Rao-like bound). For a given smooth set of states $\rho(t)$, we define

$$ f_k(t) := -\frac{1}{2} \frac{\partial^k}{\partial \tau^k} \log F(\rho(t), \rho(t+\tau)) \Big|_{\tau=0} \quad (71) $$

and the coefficient

$$ q := \sup_t \sup_{3 \le p \le \mathbb{N}} \left| \frac{f_p(t)}{f_2^{p/2}(t)} \right|^{\frac{1}{p-2}}. \quad (72) $$

We then have for any desired minimax success probability $\bar{\eta} > 3/4$ that

$$ \bar{\delta}^*(\bar{\eta}, \rho) \ge \frac{\Gamma}{\sqrt{\inf_t \mathcal{F}(t)}}, \quad (73) $$

where

$$ \frac{q}{6\sqrt{2}} \log \frac{1}{4(1 - \bar{\eta})} > \sqrt{\log \frac{1}{4(1 - \bar{\eta})} - \Gamma} > 0. \quad (74) $$

The bound holds as long as $\Gamma/\sqrt{\inf_t \mathcal{F}(t)}$ does not exceed the smallest convergence radius of the Taylor expansion of the sandwiched Rényi relative entropy.

We note that the coefficient $q$ is a measure of closeness to a Gaussian shape of the fidelity curve $\tau \mapsto F(\rho(t), \rho(t+\tau))$ and again emphasize that $f_2(t)$ relates to the quantum Fisher information as $f_2(t) = \frac{1}{8}\mathcal{F}(t)$. The
proof is presented in Section VIII B of the supplementary material. As we discussed above, in the case of i.i.d. copies $\rho(t) \rightarrow \rho^{\otimes n}(t)$, we have $q = O(1/\sqrt{n})$ giving a bound that is asymptotically constant.

The above gives a lower bound for the optimal minimax tolerance that, asymptotically, has the expected scaling both in the quantum Fisher information and the desired logarithmic dependence on the success probability. It furthermore is valid in the single-shot setting, where the finite-size corrections depend on the higher-order derivatives of the sandwiched Rényi relative entropy. We find it conceivable that the ratio of third to second derivative could give the factual second-order asymptotics, but to conclude that it would be necessary to find a matching upper bound (i.e. a protocol) with similar performance guarantees.

It is also interesting to gather some intuition about the workings of the above bound. First of all, the right-hand side involves the quantum Fisher information, which is a local quantity that captures how much states change *infinitesimally*. This quantity yet puts a bound on $\bar{\delta}$, which quantifies the estimation accuracy globally over the range of possible parameter values. This is because we effectively reduce to a setting where the quantum Fisher information captures the dominant contributions to the sandwiched Rényi relative entropy even at non-infinitesimal distances – the case when it is dominated by the second order expansion. The coefficient $q$ measures how close we are to this setting.

The proof of the above theorem hinges on the convergence of the Taylor expansion of the sandwiched Rényi relative entropy. As the convergence radius is the distance to the closest pole of the function, we can conclude that the smallest radius of convergence is

$$r := \min\{|\tau| \mid F(\rho(t), \rho(t+\tau)) = 0 \text{ for some } t\}. \quad (75)$$

This shows that in the case of i.i.d. copies, for example, the radius of convergence is independent of the number of copies. We thus do not expect the radius of convergence to be an issue in practically relevant scenarios.

We further observe that the expansion we use is very reminiscent of the Edgeworth/Gram-Charlier series expansion method in statistics [75], where the ratio $f_p/f_2^{p/2}$ can be understood as the normalized $p$-th cumulant. It is an important direction of research to further our understanding of the higher derivatives of the sandwiched Rényi relative entropy.

## VIII. BOUNDS ON THE OPTIMAL SAMPLE COMPLEXITY

The sample complexity defined in Definition 3 captures the number of copies of a quantum system needed to achieve a target tolerance with a guaranteed success probability. It is a quantity for which bounds follow in a relatively straightforward manner from our previous

results. This is because any bound that relates the tolerance and the success probability to each other can be used to establish a sample complexity bound. In this way, the sample complexity is – in a way – mathematically secondary to success probability and tolerance.

We can use Corollary 12 in the form of Eq. (66) to obtain the following concise minimax sample complexity lower bound that involves the sandwiched Rényi relative entropy of order 1/2 introduced in Eq. (65).

**Corollary 19 (Two-point sample complexity bound).** For a given tolerance $\delta$ and state set $\rho(t)$, we have the following lower bound on the minimax sample complexity

$$\bar{n}^*(\eta, \delta, \rho) \geq \frac{1}{4 \inf_{|t-t'|>2\delta} \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t'))} \log \frac{1}{4(1-\eta)}. \quad (76)$$

The above result concerns the sample complexity in the setting of parametrized states. When talking about sample complexities, we usually present them in Big-O notation, where the relevant limits are $\delta \to 0$ and $\eta \to 1$. In the limit $\delta \to 0$, the above bound is dominated by close values $t' = t + 2\delta$, motivating a Taylor expansion. As we have discussed in detail in Section VII, we have

$$\tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t+2\delta)) = \frac{1}{4} \mathcal{F}(t)\delta^2 + O(\delta^3), \quad (77)$$

where $\mathcal{F}(t)$ is the quantum Fisher information at time $t$. This means Corollary 19 immediately implies an i.i.d. sample complexity lower bound of

$$\bar{n}^*(\eta, \delta, \rho) \geq O \left( \frac{1}{\min_t \mathcal{F}(t)} \frac{1}{\delta^2} \log \frac{1}{1-\eta} \right). \quad (78)$$

The above result applies to i.i.d. states. It is, however, equally important to have a sample complexity bound that does not rely on the i.i.d. structure of the underlying state. This can, for example, happen when quantum metrology with quantum channels is performed. In that case, we deal with a parametrized family of states $\rho^{(n)}(t)$ for $n \in \mathbb{N}$. To get results about this case from Corollary 12, we have to work harder. Luckily, we already performed the heavy lifting in Section VII and can build on our non-asymptotic Cramér-Rao like bound of Theorem 18. Said result hinges on two quantities, first the smallest quantum Fisher information $\inf_t \mathcal{F}(t)$ and second the coefficient $q$ that quantifies the validity of a quadratic approximation to the sandwiched Rényi relative entropy.

Many results in the existing literature on quantum metrology concern themselves with the asymptotic scaling of the quantum Fisher information, which is usually $\mathcal{F} = O(n)$ in the standard quantum limit and $\mathcal{F} = O(n^2)$ in the Heisenberg limit [76]. We can use results of this type in the form of the following Corollary:

**Corollary 20 (Sample complexity scaling bound).** In the setting of Theorem 18, where $\rho(t)$ is replaced with a
parametrized family of states {$ρ^{(n)}(t)$}$_{n}$$_{∈}$N, assume that we have the asymptotic scalings in n:

$$
\inf_t \mathcal{F}^{(n)}(t) = O(n^\alpha) \quad (79)
$$

$$
q^{(n)} = o(1), \qquad (80)
$$

for α > 0. Then we have that

$$
\bar{n}(\eta, \delta) \ge O \left( \left[ \frac{\log \frac{1}{1-\eta}}{\delta^2} \right]^{\frac{1}{\alpha}} \right). \quad (81)
$$

The proof of the above Corollary is exhibited in Sec-
tion IX of the supplementary material. As was shown in
Section VII, in the case of i.i.d. copies, we have α = 1 and
q = O(n⁻¹/²) = o(1), reproducing the scaling of Corol-
lary 19 up to a worse dependence on the inverse error
probability.

IX. METROLOGY OF QUANTUM CHANNELS
IN THE FINITE-SAMPLE REGIME

So far in this work, we have considered the task of esti-
mating a parameter *t* encoded in a set of states ρ(*t*) and
we have presented results on the optimal success proba-
bility, tolerance and sample complexity for this task. In
practice, as alluded to in Fig. 3, parametrized quantum
states arise from the interaction of some probe system
with some physical system whose properties in the form
of the parameter *t* we wish to determine. In this case,
the primary object of interest is not a set of parametrized
states *t* ↦→ ρ(*t*), but a set of parametrized quantum chan-
nels *t* ↦→ 𝒩(*t*), which represent the evolution of the probe
system and its properties. The goal is then to estimate
the parameter *t*, given access to the quantum channel
𝒩(*t*), with the same goals as before: optimize the esti-
mation success probability, the tolerance, and the sam-
ple complexity, i.e. the number of times the channel is
accessed.

Access models. As quantum channels represent evolu-
tions of quantum systems, the possible ways of interact-
ing with multiple copies of them to extract the under-
lying parameter are much richer than in the case of a
parametrized quantum state where the only way of in-
teracting is to choose a suitable POVM. As we show in
Fig. 6, a variety of access models for multiple copies of
quantum channels can be distinguished. In the simplest
case, the same single-shot protocol is repeated multiple
times and the individual outcomes are processed classi-
cally, effectively reducing to the case of the parametrized
quantum state – we therefore refer to it as the i.i.d. case.
In the parallel case, we use n copies of the channel in
parallel, but possibly with entangled inputs and mea-
surements. If adaptive processing is allowed, then every
use of the channel can be followed by a round of adap-
tive quantum processing before the next channel use.
Such causally-ordered strategies are modeled by quan-
tum combs [20, 21]. Finally, the most general conceivable

access to *n* copies of a quantum channel allows for indef-
inite causal order of the channel uses, e.g. through the
use of a quantum switch [77]. Such strategies can lead
to an asymptotic quadratic advantage over the Heisen-
berg limit for infinite-dimensional systems [76, 78], and
there exists a strict performance hierarchy in the finite-
dimensional case [79].

If we fix a particular way of interacting with *n* copies
of a parametrized quantum channel in a particular ac-
cess model and subsequently measuring a POVM that
predicts the underlying parameter, we will refer to this
as a *strategy*. Luckily, we can give a formal description of
access models and strategies via the Choi representation
formalism. In this framework, every *strategy* within an
access model for *n* copies of the channel, $S_n$, is a func-
tion $\tau \mapsto P_n(\tau)$, $P_n \in S_n$, that maps possible predictions
to positive semi-definite operators. With this, we can
extend Definition 1 of the success probability as follows.

**Definition 21 (Success probability (channels)).** For a given tolerance $\delta$, a set of channels $\mathcal{N}(t)$ of which we can access $n$ copies, possibly with prior $\mu(t)$, and a strategy $P_n(\tau)$, the Bayesian success probability is given by

$$
\eta(\delta, \mu, \mathcal{N}, P_n) \\
:= \int d\mu(t) d\tau w_\delta(t-\tau) \mathrm{Tr}[C[\mathcal{N}(t)]^{\otimes n} P_n(\tau)], \quad (82)
$$

where $C[\mathcal{N}(t)]$ is the Choi representation of the quantum channel $\mathcal{N}(t)$. The minimax success probability is given by

$$
\bar{\eta}(\delta, \mathcal{N}, P_n) \\
:= \inf_t \int d\tau w_\delta(t-\tau) \operatorname{Tr}[C[\mathcal{N}(t)]^{\otimes n} P_n(\tau)]. \quad (83)
$$

The Bayesian and minimax tolerance sand sample
complexities in the channel case are then defined similar
to Definitions 2 and 3 from the above defined Bayesian
and minimax success probabilities.

The natural next step is now to define the optimal (Bayesian) success probability relative to an access model as

$$
\eta^*(\delta, \mu, \mathcal{N}, \mathcal{S}_n) := \sup_{P_n \in \mathcal{S}_n} \eta(\delta, \mu, \mathcal{N}, P_n). \quad (84)
$$

The optimal Bayesian tolerance and sample complexity,
as well as the corresponding minimax quantities are de-
fined analogously.

In Section III, we have shown that the optimal Bayesian and minimax success probabilities can be computed by solving a convex optimization problem without duality gap. As evidenced in Fig. 6, protocols that involve a parametrized quantum channel have more moving parts that can and need to be optimized. Let us, for example, take the simplest case of only one use of the parametrized quantum channel. In this case we have to optimize over both the probe state ρ₀ that is fed into the quantum channel and the measurement Q(τ). Naively,
<figure><img src="image_8.png" /><figcaption>FIG. 6. The different types of protocols that can be realized when accessing multiple (in this case, two) copies of the same parametrized channel $\mathcal{N}(t)$. We distinguish: (a) the i.i.d. case when the same single-shot protocol is repeated multiple times. (b) the parallel case where the probe state can be entangled by a suitable unitary transformation. (c) the adaptive case where an auxiliary system can be used as a memory to coherently adjust processing based on the outcomes of the first use of the channel. The gray shaded area represents an instance of a quantum comb. (d) the case of indefinite causal order, where a superposition of orders of invocations of the quantum channel can be used to boost the sensitivity. The blue and orange arrows represent the two orders of invocation. The solid black line in the middle indicates an auxiliary system. The gray shaded area represents a general strategy with indefinite causal order.</figcaption></figure>

the objective is then a nonlinear function of the arguments of the optimization $\rho_0$ and $Q(\tau)$ and we would not expect that this can be cast as a semi-infinite program. However, if we change our perspective and combine the preparation of the probe state and the measurement into a single object represented by a parametrized quantum comb, we can exploit the convexity of the set of quantum combs to again cast the computation of the optimal success probability as a semi-definite program. This reasoning then immediately means that also the case of adaptively interacting with $n$ copies of the channel can be efficiently optimized for. The same is true for strategies involving indefinite causal order as we summarize in the following proposition.

**Proposition 22 (Joint optimization).** For a given tolerance $\delta$, a set of channels $\mathcal{N}(t)$ of which we can access $n$ copies, possibly with prior $\mu(t)$, the optimal success probability $\eta^*(\delta, \mu, \mathcal{N}, S_n)$ and optimal minimax success probability $\eta^*(\delta, \mathcal{N}, S_n)$ can be computed using a semi-definite program without duality gap for both adaptive $S_n = S_n^{ada}$ and indefinitely causally ordered $S_n = S_n^{ico}$ access.

The detailed statements of the convex programs and their duals are given in Section III of the supplementary material.

**Connection to hypothesis testing.** The core contribution of this work is the rigorous connection of PAC metrology with quantum hypothesis testing given in Section IV. There, we gave an upper bound on the success probability through the success probability of corresponding multi-hypothesis testing problems between quantum states. As we show below, these results also carry over to the case of parametrized quantum channels. In this case, the reduction is to multi-hypothesis testing between channels under different access models. Formally, we define the optimal Bayesian success probability

of testing $n$ copies of the quantum channels $\{\mathcal{N}_i\}_{i=1}^N$ with prior probabilities $\{p_i\}_{i=1}^N$ under the access model $S_n$ as

$$P_s^*(\{p_i\}_{i=1}^N, S_n) := \sup_{\{P_i\}_{i=1}^N \subset S_n} \sum_{i=1}^N p_i \operatorname{Tr}[C[\mathcal{N}_i]^\otimes n P_i] \quad (85)$$

under the condition that the set $\{P_i\}_{i=1}^N$ corresponds to a valid combination of processing and POVM. The minimax statement is given analogously by choosing the prior probabilities adversarially for the chosen strategy. The fact that our results from the state case carry over to this more general case comes with little surprise when we realize that upon fixing the strategy $P(\tau)$ to the optimal strategy and executing it right until before the final measurement is performed, we obtain a parametrized set of states to which we can then apply Theorem 10, leading to the following result.

**Corollary 23 (Hypothesis testing bound (channels)).** For a given tolerance $\delta$, fix any set $S = \{(\lambda, s)\}$ of prior probabilities $\lambda \in [0, 1]$ and shifts $s \in \mathbb{R}$ such that for all distinct $s, s' \in S$ we have that $|s - s'| > 2\delta$ and $\sum_{\lambda \in S} \lambda = 1$. Then, for a set of channels $\mathcal{N}(t)$ of which we can access $n$ copies with prior $\mu(t)$ and a fixed access model $S_n$ we have the upper bound

$$\eta^*(\delta, \mu, \mathcal{N}, S_n) \le \int dt P_s^*(\{\lambda \mu(t+s)\mathcal{N}(t+s)\}_{(\lambda,s) \in S}, S_n). \quad (86)$$

Optimizing over the prior probabilities $\lambda$ then yields the analogous upper bound in the minimax setting

$$\bar{\eta}^*(\delta, \mathcal{N}, S_n) \le \inf_t \bar{P}_s^*(\{\mathcal{N}(t+s)\}_{s \in S}, S_n). \quad (87)$$
Because of the richer structure embodied by different access models for multiple copies of the same parametrized channel $N(t)$, we can define multiple types of asymptotic rates to generalize the analysis carried out in Section V. Of particular interest to us are the rates corresponding to i.i.d. strategies $R_{iid}^*$ (item (a) in Fig. 6), because there we can make use of our results on the asymptotics of the state case, and the rates corresponding to parallel strategies $R_{par}^*$ (item (b) in Fig. 6).

## X. PHASE ESTIMATION OF A PURE STATE HAMILTONIAN EVOLUTION

In this section, we analyze one of the most prototypical scenarios of quantum metrology, namely phase estimation with pure states. We analyze the minimax success probability, as it represents the most stringent achievable guarantees. It is further important to emphasize that our analysis takes the perspective of global estimation, contrary to the local estimation routinely seen in the literature.

As a first step, we establish a general result on the minimax success probability in the $U(1)$-group-covariant setting, which applies beyond phase estimation. We consider a set of states $|\psi(t)\rangle$ generated by unitary evolution of a pure initial probe state $|\psi\rangle$ under a Hamiltonian $H$, reflecting the evolution of a closed quantum system

$$|\psi(t)\rangle = e^{-itH}|\psi\rangle = U(t)|\psi\rangle. \qquad (88)$$

To ensure that $t$ can be understood as a “phase”, $H$ is assumed to be such that all differences between eigenvalues are integer-valued, in which case the recurrence time of the Hamiltonian is guaranteed to be $2\pi$. Let now $H$ decompose as $H = \sum_{\lambda} \lambda \Pi_{\lambda}$, where $\lambda$ are the different eigenvalues and $\Pi_{\lambda}$ are the projectors onto the possibly degenerate eigenspaces. Then, we can expand

$$|\psi\rangle = \sum_{\lambda} \psi_{\lambda} |\psi_{\lambda}\rangle, \qquad (89)$$

where we defined the normalized projections of $|\psi\rangle$ onto the eigenspaces of $H$ such that $\Pi_{\lambda}|\psi\rangle = \psi_{\lambda}|\psi_{\lambda}\rangle$.

For such a covariant set of states $\psi(t) = |\psi(t)\rangle\langle\psi(t)|$, the following theorem establishes that the pretty good measurement [80–85] is minimax optimal, and we obtain a closed form solution for the optimal minimax success probability. This result is well in line with known results on the optimality of the pretty good measurement in other covariant state discrimination and parameter estimation tasks [23, 86–91].

**Theorem 24 (Minimax optimal measurement).** For a state set $\psi(t)$ given by a pure initial probe state $\rho_0 = |\psi\rangle\langle\psi|$ evolving under a Hamiltonian with integer eigenvalue differences for time $t \in [0, 2\pi]$, the pretty good measurement

surement

$$Q_{\text{PGM}}(t) = R^{-1/2}\psi(t)R^{-1/2}, \quad \text{where } R = \int dt \, \psi(t), \qquad (90)$$

achieves the optimal minimax success probability, equal to

$$\bar{\eta}^*(\delta, \psi) = \sum_{\lambda, \lambda'} |\psi_{\lambda}| |\psi_{\lambda'}| |\hat{w}_{\delta}(\lambda - \lambda')|, \qquad (91)$$

where $\hat{w}_{\delta}(\omega) = \sin(\delta\omega)/(\pi\omega)$ is the Fourier transform of the rectangular window $w_{\delta}$ at frequency $\omega$.

The above theorem establishes a direct relation between the amplitudes of the probe state $|\psi\rangle$ and the minimax success probability. It especially shows that only the spectrum of the Hamiltonian and the absolute values of the amplitudes matter. The result holds for any window function. The proof exploits strong duality and complementary slackness to establish a formula for the optimal dual variable and is presented in Section XI of the supplementary material.

One important consequence of Theorem 24 is that it greatly simplifies the search for a minimax optimal probe state. If we arrange the absolute values of the amplitudes in a vector $\psi := (|\psi_{\lambda}|)_{\lambda}$ and construct the matrix associated to the Fourier transform, $W_{\lambda,\lambda'} := \hat{w}_{\delta}(\lambda - \lambda')$, then the optimal minimax success probability is given by the quadratic form

$$\bar{\eta}^*(\delta, \psi) = \langle \psi, W\psi \rangle. \qquad (92)$$

The optimal probe state is hence obtained by solving the following optimization problem:

$$\psi^* := \underset{\psi}{\operatorname{argmax}} \{ \langle \psi, W\psi \rangle | \psi_{\lambda} \ge 0 \text{ for all } \lambda, \|\psi\|_2 = 1 \}. \qquad (93)$$

Because of the positivity constraint on the entries of the vector, this is in general an NP-hard optimization problem [92].

## XI. PHASE ESTIMATION WITH AN ENSEMBLE OF SPIN-$\frac{1}{2}$ PARTICLES

We now turn our attention to the special phase estimation on a spin chain [93]. This is a covariant problem in the above sense with the single-spin Hamiltonian given by $H = \text{diag}(0, 1)$. If we have $n$ spins separately evolving under this Hamiltonian, the effective Hamiltonian is given by summing up the local terms on the individual copies

$$H_n = \sum_{i=1}^{n} H_i, \quad H_i = \mathbb{I}^{\otimes i-1} \otimes H \otimes \mathbb{I}^{\otimes n-i}. \qquad (94)$$

As we have seen in Theorem 24, only the spectrum of the Hamiltonian matters. For the Hamiltonian $H_n$, it is given
<figure><img src="image_9.png" /><figcaption>FIG. 7. Optimal error probability of quantum metrology that can be guaranteed for any prior distribution for different probes in the phase estimation scenario for $\bar{\delta} = 0.04$. We compare a generalized GHZ state (Eq. (95), red), a tensor power of plus states (green), the Holland-Burnett state (Eq. (96), orange), the Gaussian state (Eq. (99), yellow) and the optimal state (Eq. (93), blue). The generalized GHZ state never performs well because it cannot resolve the time globally. For $n \ll 1/\delta$, the Holland-Burnett state performs almost optimally but has comparable asymptotic performance to the tensor power probe. The Gaussian probe performs almost optimally in a larger regime than the Holland-Burnett and has an intermediary asymptotic. The overset plots show the energy profiles of the optimal probe for $n = 41$ (A), the optimal probe for $n = 561$ (B) and the tensor power probe for $n = 561$ (C). The asymptotic rate in the i.i.d. case is consistent with $R \approx \delta^2$, whereas the optimal entangled rate is consistent with $R \approx \delta$. We present additional numerical results for different values of $\bar{\delta}$ in Section XII B of the supplementary material.</figcaption></figure>

by $\text{spec}(H_n) = \{0, 1, \dots, n\}$, which grows linearly in $n$. We can therefore treat the equivalent problem of a Hamiltonian with spectral decomposition $H = \sum_{k=0}^n k|k\rangle\langle k|$, where the eigenstates $|k\rangle$ are understood to be any eigenstate of the Hamiltonian $H_n$ with energy $k$, e.g., $|3\rangle$ could be $|001101\rangle$ for $n = 6$.

Applying Theorem 24 allows us to compute the optimal minimax success probability (Fig. 7) and the optimal minimax tolerance (Fig. 8) for different kinds of probe states. We note that our analysis of the asymptotics of the minimax success probability has significant overlap with prior work by Imai and Hayashi in Ref. [53]. They discuss the asymptotic distribution of phase estimates and discuss the asymptotic rate.

Our first and most obvious candidate for a probe state is a generalized Greenberger-Horne-Zeilinger (GHZ) state

$$|\text{GHZ}_n\rangle := \frac{1}{\sqrt{2}}(|0\rangle + |n\rangle), \qquad (95)$$

which is optimal in the standard approach to quantum metrology [94–96]. However, in the minimax setting, it fails spectacularly – with a minimax success probability amounting to random guessing and a similarly high tolerance (see Figs. 7 and 8). This is an immediate con-

<figure><img src="image_10.png" /><figcaption>FIG. 8. Optimal tolerance of quantum metrology that can be guaranteed for any prior distribution for different probes in the phase estimation scenario for fixed success probability $\bar{\eta} = 0.99$. We compare a generalized GHZ state (Eq. (95), red), an tensor power of plus states (green), the Holland-Burnett state (Eq. (96), orange), the Gaussian state (Eq. (99), yellow) and the optimal state (Eq. (93), blue). The generalized GHZ state never performs well because it cannot resolve the time globally. The tensor power of plus states performs adequately for small $n$, but only achieves standard quantum limited scaling $O(1/\sqrt{n})$ asymptotically. For small $n$, the Holland-Burnett state does not perform satisfactorily, but achieves the optimal Heisenberg scaling $O(1/n)$ in the asymptotic limit. The Gaussian probe performs almost optimally except for very small $n$. We present additional numerical results for different values of $\eta$ in Section XII B of the supplementary material.</figcaption></figure>

sequence of the fact that the standard approach to quantum metrology is concerned with local estimation. In our case, however, the probe needs to be able to perform well in a task of global estimation, i.e., the probe state should allow us to discern values in the whole interval $[0, 2\pi]$. The recurrence time of $\sim 2\pi/n$ of the generalized GHZ state, means it can very well resolve small differences in values, but not larger ones. A clock can serve as a good metaphor for this phenomenon: If we want to tell the time, we need to make use of the hour, minute and second hand. In this picture, the generalized GHZ state corresponds to a clock with only a second hand – which is very suitable if you want to time a short sprint but useless when telling the time of the day.

The analogy of a clock inspires the use of another state, namely the Holland-Burnett (HB) state

$$|\text{HB}_n\rangle := \frac{1}{\sqrt{n+1}} \sum_{k=0}^{n} |k\rangle, \qquad (96)$$

which consists of an equal superposition of all energy eigenstates. Metaphorically, this state uses all the available hands of the clock equally. The Holland-Burnett state indeed has a much more desirable performance. As shown in Fig. 7, this probe state achieves almost optimal success probability in the regime where $n \ll 1/\delta$. This behavior can be explained by expanding the Fourier
transform of the window function, $\hat{w}_{\delta}(\omega) = \frac{\delta}{\pi} \text{sinc}(\delta\omega)$, around $\omega = 0$, because the largest frequency scales as $O(n)$:

$$ \hat{w}_{\delta}(\omega) = \frac{\delta}{\pi} [1 - O(\delta^2\omega^2)]. \qquad (97) $$

The zeroth order contribution to this term is given by

$$ \begin{aligned} \bar{\eta}^*(\delta, \psi) &= \frac{\delta}{\pi} \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}| + O(\delta^2\omega^2) \quad (98) \\ &= \frac{\delta}{\pi} \|\psi\|_1^2 + O(\delta^2\omega^2). \end{aligned} $$

In this limit, a probe that maximizes the one-norm of the amplitude vector is clearly optimal, which corresponds to the Holland-Burnett state. This state was also identified in recent work as a suitable probe state for (multi-)phase estimation [97]. In the case of the optimal tolerance, see Fig. 8, we observe the inverse of this behavior: For small $n$, the performance is not satisfactory. Asymptotically, however, the Holland-Burnett state achieves the same Heisenberg scaling $\bar{\delta}^* = O(1/n)$ as the optimal probe. As we show in additional numerics presented in Section XII B of the supplementary material, the critical value of $n$ at which the Holland-Burnett state starts to enter the Heisenberg-scaling regime increases with increasing success probability.

Next, we have analyzed the performance of a separable probe state. We chose i.i.d. copies of the optimal single-spin probe state, the $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ state. We observe in Fig. 7 that the success probability achieved with this state reaches towards unity much more slowly than the optimal probe state, with an asymptotic rate quadratically smaller. When looking at the optimal tolerance in Fig. 8, we observe the expected asymptotic scaling of the standard quantum limit $\bar{\delta}^* = O(1/\sqrt{n})$.

We additionally compare the aforementioned probe states with a Gaussian probe whose amplitudes have a Gaussian shape:

$$ \psi_{\lambda} \propto \exp \left( -\frac{1}{2} \frac{2\delta}{n+1} \left( \lambda - \frac{n}{2} \right)^2 \right). \qquad (99) $$

The optimality of the choice of the standard deviation, $\sqrt{(n+1)/2\delta}$, is discussed in Section XII of the supplementary material. Regarding the success probability, we observe in Fig. 7 that the Gaussian probe performs close to optimally in a larger regime than the Holland-Burnett state and achieves better asymptotics, but also does not match the optimal probe. In the case of the tolerance, we do, however, observe in Fig. 8 that it nearly reproduces the optimal probe state. As we show in additional numerics presented in Section XII B of the supplementary material, a gap in tolerance opens between the optimal and the Gaussian probe when the target success probability is increased, but the Gaussian probe preserves Heisenberg scaling and a good performance.

Last but not least, we study the optimal probe state. Normally, we would need to solve the optimization problem of Eq. (93). However, in the special case we encounter here, in which $W$ is defined through the Fourier transform of a rectangular window function and the eigenvalue spectrum has no gaps, we can build on prior work studying a similar problem in the context of classical signal processing [98], where $W$ is referred to as the prolate matrix. In Ref. [98], Slepian establishes that the largest eigenvector of the matrix $W$ is given by the so-called discrete prolate spheroidal sequence (DPSS) of zeroth order. While he studies the problem without the positivity constraint on the eigenvector, we can build on a different result of Slepian to show that the largest eigenvector is always non-negative. In the case of phase estimation, we can therefore compute the optimal probe by finding the eigenvector associated to the largest eigenvalue of $W$.

In our numerical investigations, we observe in Fig. 7 that the success probability tends towards unity with an asymptotic rate quadratically greater than what is possible with the separable probe and also outperforms the Gaussian probe significantly. It further achieves a clear Heisenberg scaling $\bar{\delta}^* = O(1/n)$ for the tolerance as evident in Fig. 8. To get a feeling for the amplitude distributions of the different probes, we plot in Fig. 7 the amplitude distribution over the eigenvalues of the optimal probe states for $n = 41$ and $n = 561$. These plots clearly show that the optimal probe state for small $n$ has a flat spectrum, whereas asymptotically a moderately concentrated shape is optimal. We compare this with the corresponding shape of the tensor power probe at $n = 561$, which is much more concentrated, explaining its inferior performance.

Our numerical results make it quite clear that the setting of optimizing the success probability for a fixed tolerance and of optimizing the tolerance for a fixed success probability are qualitatively different. We especially see that probes that perform well in one setting do not necessarily perform well in the other.

Finally, we also want to shine a light on the relation of the minimax tolerance with the quantum Cramér-Rao bound. To this end, in Fig. 9, we plot the achievable tolerance for a subset of the states presented above together with the quantum Cramér-Rao bound for a fixed success probability of $\bar{\eta} = \text{erf}(1/\sqrt{2}) \approx 0.6827$, representing the probability that the value of a normally distributed random variable is within one standard deviation of its mean. We observe that the quantum Cramér-Rao bound only faithfully predicts the achievable precision in the case of i.i.d. copies, but is overly optimistic otherwise. This underscores the interpretation that the quantum Cramér-Rao bound necessitates a degree of regularity of the underlying problem to be tight, and its connection to maximum-likelihood estimation which is optimal for Gaussian distributions. The sometimes overly optimistic estimate obtained from the quantum Cramér-Rao bound is especially evident for the GHZ state, which
<figure><img src="image_11.png" /><figcaption>FIG. 9. Optimal tolerance of quantum metrology that can be guaranteed for any prior distribution for different probes in the phase estimation scenario compared to the quantum Cramér-Rao bound embodied by the inverse square root of the quantum Fisher information. The success probability is fixed to $\bar{\eta} = \text{erf}(1/\sqrt{2}) \approx 0.6827$, representing the probability that the value of a normally distributed random variable is within one standard deviation of the mean. We compare a generalized GHZ state (Eq. (95), red), an tensor power of plus states (green), and the optimal state (Eq. (93), blue). The quantum Cramér-Rao bound is shown in dashed lines. We observe that the quantum Cramér-Rao bound faithfully predicts the achievable precision in the case of i.i.d. copies for the chosen success probability, underpinning the interpretation that the quantum Cramér-Rao quantifies the i.i.d. case with a Gaussian shape for the fidelity curve. Both for the GHZ state and the optimal state, the quantum Cramér-Rao bound is way too optimistic, showcasing a decoupling of the quantum Cramér-Rao bound from the achievable performance in the few-shot and entangled regime.</figcaption></figure>

achieves the maximum quantum Fisher information, but the actual achievable tolerance is very bad. Nevertheless, these numerical experiments also suggest a positive result about the quantum Cramér-Rao bound. We observe that there exist settings where it gives a good measure of metrological precision, even in the global and non-asymptotic regime – this is indicated by the fact that the agreement with the achievable precision is already very good at $n \approx 10$ repetitions. These results highlight that there are regimes where the quantum Cramér-Rao bound faithfully predicts the achievable precision, but that it is too optimistic in the case of few shots and entangled strategies.

**Analytical results.** The numerical observations presented in Fig. 7 motivate an analytical study of the asymptotics of the minimax error probability, extending the results of Section IV. There, we established results on the asymptotic rate for i.i.d. copies of the same state, which corresponds to the case of the tensor power probe discussed above. We observe that when entangled probe states are allowed – corresponding to the parallel setting – the asymptotic rate is much improved, as the rates we

observe numerically are consistent with

$$ \bar{R}_{\text{iid}}^{*}(\bar{\delta}) \approx \bar{\delta}^{2}, \qquad (100) $$

$$ \bar{R}_{\text{par}}^{*}(\bar{\delta}) \approx \bar{\delta}. \qquad (101) $$

In the following, we make this observation rigorous.

As we already argued above, the optimal probe for phase estimation on a spin chain is given by the discrete prolate spheroidal sequence (DPSS) of zeroth order [98]. We can combine two results by Slepian to obtain the following result on the optimal rate in the parallel case:

**Theorem 25 (Optimal minimax rate).** For a given minimax tolerance $0 < \bar{\delta} < \pi/2$, the parallel minimax error rate is given by

$$ \begin{aligned} \bar{R}_{\text{par}}^{*}(\bar{\delta}) &= \log \left( \frac{1 + \sin \frac{\bar{\delta}}{2}}{1 - \sin \frac{\bar{\delta}}{2}} \right) \\ &= \bar{\delta} + O(\bar{\delta}^3). \end{aligned} $$

The proof combines two results from Ref. [98] and exploits the Perron-Frobenius theorem to establish positivity of the DPSS of zeroth order and is given in Section XII of the supplementary material. While the DPSS has no closed-form, there exist efficient approximations involving the modified Bessel function of the first kind of zeroth order $I_0$ [99]. In our case, the optimal probe can thus be approximated by choosing

$$ \psi_{\lambda} \propto I_0 \left( \frac{\bar{\delta}n}{2} \sqrt{1 - \left( \frac{2\lambda + 1}{n+1} - 1 \right)^2} \right) \qquad (102) $$

and subsequently normalizing.

We can use the result on the rate for i.i.d. probes of Theorem 13 to calculate

$$ \bar{R}_{\text{iid}}^{*}(\bar{\delta}) \leq -\log \cos^2(\bar{\delta}) \approx \bar{\delta}^2 \qquad (103) $$

for small $\bar{\delta}$, see Theorem 41 of the supplementary material. Combined with the above Theorem 25 this implies that entangled strategies have a quadratic advantage in the asymptotic minimax rate, which can be understood as the rate analogue of the dichotomy between the standard quantum and Heisenberg limits.

We further perform a theoretical analysis of the optimal standard deviation for the Gaussian probe. We can use tail bound estimates for the Gaussian distribution to prove that the optimal choice of standard deviation (see Eq. (99)) achieves half the optimal rate.

**Theorem 26 (Minimax rate for Gaussian probes).** For a given minimax tolerance $\bar{\delta} > 0$, the Gaussian probe achieves the minimax error rate of

$$ \bar{R}_{\text{Gauss}}(\bar{\delta}) = \frac{\bar{\delta}}{2}. \qquad (104) $$
The proof is presented in Section XII of the supplementary material.

Building on the previous result, we can also give a guarantee on the asymptotic tolerance achieved by the Gaussian probe.

**Observation 27** (Asymptotic tolerance of Gaussian probe). For a given minimax success probability $\bar{\eta}$, the Gaussian probe achieves a minimax tolerance of

$$ \bar{\delta}_{\text{Gauss}} = \frac{\alpha}{n+1}, \qquad (105) $$

where

$$ \alpha \approx 2 \log \left( \frac{2}{\pi(1 - \bar{\eta})} \right), \qquad (106) $$

up to logarithmic factors.

The argument is likewise presented in Section XII of the supplementary material.

## XII. EXTENSIONS AND CONNECTIONS TO OTHER FIELDS

This section is dedicated to exploring the various connections and possible generalizations of our definitions and results to other areas of quantum metrology and quantum information theory.

### A. Multi-parameter quantum metrology

Measuring multiple parameters at the same time [13, 100] creates additional challenges, such as having to reconcile measurements [101, 102] and probe states [52] that are optimal for each parameter but might be incompatible. It furthermore offers a framework to study networks of quantum sensors [103] and the optimal estimation of functions of multiple parameters [104].

We can capture arbitrary instances of multivariate quantum metrology by replacing the parameter space $\mathbb{R}$ with an arbitrary set $\mathcal{X}$. We equip the set $\mathcal{X}$ with a positive real-valued function $d(x, y)$ that quantifies the estimation error associated with an estimate $y$ when the true value of the parameter is $x$. A natural choice for $d(x, y)$ might be a suitable distance measure. In this case, the success probability for a given set of states $x \mapsto \rho(x)$, prior distribution $\mu(x)$ and POVM $y \mapsto Q(y)$, is

$$ \eta(\delta, \mu, \rho, Q) = \int_{\mathcal{X}} d\mu(x) \int_{\mathcal{X}} dy w_{\delta}(d(x, y)) \text{Tr}[\rho(x)Q(y)]. \qquad (107) $$

The definitions for the tolerance and sample complexity, the corresponding minimax quantities and the optimal quantities follow analogously as in the previous sections. Some of our proofs extend naturally to general parameter

sets $\mathcal{X}$. In Section X of the supplementary material, we give a generalization of Theorem 10 to the multivariate case and use it to derive a multi-parameter analog of Corollary 11.

### B. Confidence region tomography and shadow tomography

A particularly well-studied variant of multivariate quantum metrology concerns the task of state tomography, in which the parameter space $\mathcal{X}$ is taken to be the quantum state space itself. A suitable distance measure, such as the infidelity or the trace distance, typically quantifies the estimation error.

This extension of our framework connects with a series of works in quantum tomography on establishing confidence regions in state space given measurement data [30–33]. Confidence region estimators process the measurement data to output a subset of the state space (the confidence region) in which the true state lies with high probability. The region can furthermore be specified as the set of all states that are at least $\delta$-close to some reference state in a suitable distance measure.

Another setting that connects to the multi-parameter estimation version of our framework is shadow tomography [105, 106]. Shadow tomography aims at predicting the expectation values of a set of $M$ observables $\mathcal{O} = \{O_i\}_{i=1}^M$ when evaluated on a given quantum state $\rho$. If we define a distance measure

$$ d_{\mathcal{O}}(\rho, \sigma) := \sup_{O \in \mathcal{O}} |\text{Tr}[O(\rho - \sigma)]|, \qquad (108) $$

then shadow tomography with precision $\delta$ is equivalent to finding an approximation of the quantum state $\hat{\rho}$ that fulfills $d_{\mathcal{O}}(\rho, \hat{\rho}) \le \delta$. Defining a measurement scheme then corresponds to a POVM with effects labeled by quantum states, $Q(\hat{\rho})$, and the minimax success probability is hence

$$ \bar{\eta}(\delta, Q, \rho) = \min_{\rho} \int d\hat{\rho} \text{Tr}[\rho Q(\hat{\rho})] w_{\delta}(d_{\mathcal{O}}(\rho - \sigma)), \qquad (109) $$

where both the minimization and integration are over all quantum states. A probabilistic procedure introduced in Ref. [106] achieves the sample complexity

$$ \bar{n}^*(\eta, \delta, \rho) \le O \left( \frac{1}{\delta^2} \log \left( \frac{M}{1 - \eta} \right) \max_{1 \le i \le M} \|O_i\|_{\text{shadow}}^2 \right), \qquad (110) $$

where the shadow norm $\|\cdot\|_{\text{shadow}}$ captures properties of the particular randomized protocol used. We thus see that contemporary techniques like shadow tomography are captured by our PAC metrology framework.

In the same spirit, other tomography tasks, e.g. the tomography of quantum channels and non-Markovian processes in the form of quantum combs, can be considered in the PAC metrology framework. Exploring the ultimate limitations of these tasks would constitute an intriguing direction of future work.
### C. Cryptography and adversarial parameter estimation

There is an emerging subfield of quantum metrology concerned with its intersection with cryptography [107, 108]. As an example, we might seek a metrological protocol where the precision with which an eavesdropper might estimate a parameter should be as low as possible. This regime corresponds to a regime of small success probability, $\eta \to 0$.

We make use of the fact that the success probability and tolerance have a functional relationship that corresponds to an inversion of the success probability seen as a function of the tolerance. This allows us to analyze the limit of small success probability for smooth, i.e., arbitrarily often differentiable, measurements $Q(\tau)$.

**Proposition 28.** For a given set of states $\rho(t)$, possibly with prior $\mu(t)$, a smooth measurement $Q(\tau)$ and a small success probability $\eta$, the Bayesian tolerance is given by

$$ \delta(\eta, \mu, \rho, Q) = \frac{\eta}{2} \left( \int d\mu(t) \operatorname{Tr}[\rho(t)Q(t)] \right)^{-1} + O(\eta^2), \quad (111) $$

whereas the minimax tolerance is given by

$$ \bar{\delta}(\eta, \rho, Q) = \frac{\eta}{2} \left( \inf_t \operatorname{Tr}[\rho(t)Q(t)] \right)^{-1} + O(\eta^2). \quad (112) $$

Both statements hold conditioned on the inverted quantity to be nonzero.

The proof is shown in Section VIII of the supplementary material.

Let us now assume that Alice performs a quantum metrology protocol and obtains a quantum state $\rho_A(t)$ which it communicates to Bob via a quantum channel $N$, such that he receives the state $\rho_B(t) = N[\rho_A(t)]$. At the same time, an eavesdropper Eve tries to obtain as much information as possible about the transmitted state. The state Eve can obtain in the worst case is modeled by the complementary channel $N_c$ [109], which describes the information the environment can obtain when viewing $N$ as part of a larger, unitary evolution. As such, we assume that Eve holds the state $\rho_E(t) = N_c[\rho_A(t)]$. The above proposition tells us that, if we want to limit the precision with which Eve can estimate the parameter $t$ from the state $\rho_E(t)$, we need to choose the initial state of Alice such that the quantity

$$ \begin{aligned} & \sup_{Q(t)} \int d\mu(t) \operatorname{Tr}[\rho_E(t)Q(t)] \\ & = \sup_{Q(t)} \int d\mu(t) \operatorname{Tr}[\rho_A(t)N_c^\dagger[Q(t)]] \end{aligned} \quad (113) $$

is as small as possible.

### D. Optimization over constrained sets of measurements

In the formulation of the success probability as a convex problem of Proposition 7, we optimize over all possible quantum measurements of the system. We already obtained the optimal post-processing for the practically important case of a fixed measurement. In this section, we discuss another possible way of including practical constraints that might limit the possible measurements by only optimizing over POVMs from a set $Q$ that represents the set of measurements that can be implemented on the system.

In this case, we obtain a restricted optimal success probability $\eta_Q^*(\delta, \mu, \rho)$ quantified as

$$ \eta_Q^*(\delta, \mu, \rho) := \max \left\{ \int dt \operatorname{Tr}[(w_\delta * [\mu \cdot \rho])(t)Q(t)] \mid \int dt Q(t) = \mathbb{I}, Q \in \mathcal{Q} \right\}. \quad (114) $$

A particular case of interest appears when $Q$ is a convex set, in particular, if it is specified by semidefinite constraints. In this case, the optimization above is a convex optimization problem. Such a situation occurs, for instance, if we assume that Alice prepares a state $\rho(t)$ and sends it to a noisy channel $\mathcal{E}$ to Bob, who attempts to estimate $t$ using any possible POVM on his system. Bob's optimal POVM $Q(t)$ can be mapped to the POVM $\mathcal{E}^\dagger(Q(t))$ on Alice's system through the ad joint map $\mathcal{E}^\dagger$ of $\mathcal{E}$. Consequently, Bob's optimization over any POVM can be equivalently expressed as Alice optimizing over all POVMs in the image of $\mathcal{E}^\dagger$. The thus defined set $Q = \{\mathcal{E}^\dagger[Q] \mid \int dt Q(t) = \mathbb{I}, Q(t) \ge 0\}$ is a convex set and Bob's optimal success probability can as such be computed efficiently.

The minimax variant, as well as the corresponding tolerance and sample complexity are then defined analogously to their non-restricted counterparts.

### E. Estimation of properties beyond parameters

We now consider the setting where we seek to estimate some property $x$, e.g., the expectation value of an observable, of a general unknown state $\rho$. Crucially, multiple states might share the same property value $x$, hindering the use of our analysis which assumed that the unknown state belongs to a set of states that is fully specified by one parameter.

This task can be treated by the introduction of so-called “nuisance” parameters. Nuisance parameters are additional parameters that ensure that each quantum state is associated with a distinct set of parameter values. The consequence of introducing nuisance parameters is to reduce the property estimation problem to a multi-parameter estimation problem. In our case, we can perform a similar strategy that proceeds like the example of shadow tomography discussed above. By taking
the space of quantum states as the parameter space, we introduce the maximal possible number of nuisance parameters, and by introducing a distance function

$$d_x(\rho, \sigma) := |x(\rho) - x(\sigma)|, \qquad (115)$$

we obtain a way to only pick out the relevant parameter $x$. These settings are of extremely high importance for practical applications, e.g. for near-term applications on NISQ devices [110]. There exists a large variety of existing techniques to treat this particular application [111], but these tools pertain to the local estimation setting. It is therefore an intriguing direction of future research to see how these analytical approaches can be generalized to the framework of PAC metrology.

## XIII. FUTURE DIRECTIONS

In the standard approach to quantum metrology built on top of the quantum Cramér-Rao bound, most fundamental questions have already been answered. In our single-shot PAC metrology framework, on the contrary, a broad collection of open question – both fundamental and practical – is still looking for answers. In this section, we highlight some questions of particular interest.

**Optimal measurements in the finite-sample regime.** A significant open question that remains open is the development of measurement schemes or protocols with guarantees on either the success probability or the estimation tolerance. While the formulation of the success probability as a convex problem provides an efficient way to compute the optimal POVM associated with a discretized version of the estimation problem, a closed form of the optimal measurement remains elusive beyond the covariant case treated in Section X. Furthermore, solutions to the convex optimization problem are not likely to provide additional insight on measurement schemes that are perhaps sub-optimal but far more convenient to implement than the optimal measurement.

Natural candidates for measurement schemes are adaptive protocols [112] as well as the pretty good measurement that constitutes the optimal measurement in the pure and covariant setting of Theorem 24. Promising candidates might furthermore be constructed using the class of measurements studied in Section III B.

**Open Problem 1** (Measurement schemes with performance guarantees). Develop measurement schemes with provable performance guarantees that are either practical to implement or that achieve close-to-optimal estimation error tolerance or success probability in the finite-sample regime.

Such measurement schemes would significantly aid in deriving upper bounds on the optimal estimation tolerance and lower bounds on the success probability in various settings. So far, such lower bounds have been elusive because of a lack of such schemes. For instance, an open

question would be whether a measurement scheme is capable of achieving the rate given in Theorem 13.

**A finite-sample analogue of the quantum Cramér-Rao bound.** The quantum Cramér-Rao bound of Eq. (1) is the fundamental cornerstone of the standard approach to quantum metrology. It relates an operational quantity (the standard deviation of the optimal unbiased estimate of a parameter) to a geometric property of the underlying set of quantum states (the quantum Fisher information). We call the quantum Fisher information a geometric property because it quantifies the distance between quantum states whose parameters are close to each other when “distance” is measured through the fidelity of quantum states. States that are close in terms of the fidelity are difficult to distinguish, and we have already learned in Theorem 10 that this is a prerequisite for successful parameter estimation.

In our finite-sample approach, the estimation tolerance fulfills a role comparable to that of the standard deviation. We expect that the smallest achievable estimation tolerance should – similar to the standard deviation – be constrained by a quantity that captures geometric properties of the underlying set of quantum states. As our framework pertains to cases where the estimation is not necessarily local, we expect that the we need quantities that go beyond the quantum Fisher information in the sense that they capture the geometry of the given state set at non-infinitesimal length scales. Moreover, there is the additional factor of the desired success probability $\eta$ that factors into any relation between the optimal estimation tolerance and the structure of the given state set.

We managed to derive Theorem 18 by quantifying how well the fidelity is approximated by a Gaussian as

$$F(\rho(t), \rho(t + \tau)) \approx \exp\left(-\frac{1}{8}\mathcal{F}(t)\tau^2\right). \qquad (116)$$

In that sense, we quantified how close we are to a case where the quantum Fisher information dictates not only the behavior in an infinitesimally small neighborhood but also for larger values of the perturbation $\tau$. It is of immense interest if we can obtain more general statements of the same kind that resemble the Cramér-Rao bound in the following sense.

**Open Problem 2** (Finite-sample analogue of the Cramér-Rao bound). Find improved lower bounds on the optimal Bayesian and minimax estimation tolerance that put fundamental limits on the achievable estimation tolerance based on geometric properties of the underlying state set, i.e., bounds of the form

$$\bar{\delta}^*(\eta, \rho) \geq \frac{f(\eta)}{\sqrt{\mathcal{I}}}, \qquad (117)$$

where $f(\eta)$ quantifies the dependence on the success probability and $\mathcal{I}$ is a measure that captures the geometric structure of the given state set in the finite-sample setting. Note that $\mathcal{I}$ can in general also depend on the desired success probability.
An important improvement of our quantum Cramér-Rao-like bound of Theorem 18 would be a bound that accurately predicts the achievable estimation tolerance in the i.i.d. limit – i.e. given a state $\rho^{\otimes n}(t)$ where $n \to \infty$ – in the sense that there exists a matching upper bound. It would not be surprising if a different geometric quantity than the quantum Fisher information would appear in such a bound. This is because the converse on hypothesis testing involving the fidelity of quantum states we use to derive Theorem 18 is known to not be tight in certain settings and that a proper converse should rely on the Chernoff divergence which is in turn associated to a different geometrical quantity, namely the Wigner-Yanase-Dyson information.

As we have argued above, Theorem 18 builds on the insight that there are settings (e.g., the i.i.d. setting) where the quantum Fisher information carries information about the set of states beyond infinitesimal perturbations. As such, we expect that the development of quantities that better capture the distinguishability of states in non-infinitesimal neighborhoods could lead to a more general Cramér-Rao-like bound valid in the single-shot setting.

**Advantage of entangled measurement strategies.** A further open question is to delineate the boundary of performance between different classes of protocols using entangled and non-entangled probe states, adaptive and non-adaptive processing and coherent and incoherent measurements. In particular, it is unclear whether optimal measurements in the finite-sample regime require the use of large amounts of coherence. When estimating a single parameter in the many-sample regime, the Heisenberg scaling can be achieved only with the use of entangled probe states and without the use of coherent measurements [113] – does a similar statement also hold in the non-asymptotic case?

**Open Problem 3** (Understanding relevant resources). What advantages can be gained from resources like entanglement of the probe state, coherence of the measurement and adaptivity? Can we quantify the gaps in tolerance and success probability between these different allowed resources?

Naturally, finding general purpose strategies, e.g. specific adaptive protocols, that give a competitive baseline success probability would significantly simplify addressing the above problem.

In our investigations of the phase estimation example, we observe an exact quadratic relation between the asymptotic rates for i.i.d. states and entangled states for small $\delta$. This echoes the quadratic relation between the standard quantum and the Heisenberg limits in the standard approach to quantum metrology. Understanding the generality of this phenomenon – especially for channels where Heisenberg-limited scaling is impossible [114] – would further deepen our understanding of the asymptotic rate for entangled inputs.

**Open Problem 4** (Standard quantum and Heisenberg

limit for rates). For a given set of channels $\mathcal{N}(t)$ with prior $\mu(t)$, do we in general have that

$$ \lim_{\delta \to 0} \frac{[R_{\text{par}}^*(\delta, \mu, \mathcal{N})]^2}{R_{\text{iid}}^*(\delta, \mu, \mathcal{N})} = 1, \quad (118) $$

where the symbols $R_{\text{par}}^*$ and $R_{\text{iid}}^*$ have been defined in Section IX.

**The effect of noise on estimation performance.** While noise can be implicitly treated in our formalism by including it in the construction of the parametrized set of states $\rho(t)$ or channels $\mathcal{N}(t)$, a much deeper understanding of the influence of noise is desirable, especially with an eye towards practical applications. It would be instructive to see how much the influence of noise destroys advantages of entanglement in this setting [114–116]. As we have outlined in Section XII, the minimax success probability also pertains to communication tasks, where the study of noisy channels is of utmost importance. Can we therefore relate the decrease in success probability (or the increase in tolerance) to properties of the noise channel? A deeper understanding of noise could then be used to study the application of quantum error correction to quantum metrology [11, 12] in this context.

**Incompatibility in finite-sample multi-parameter quantum metrology.** As discussed in Section XII A, our definitions extend in a natural way to multi-parameter quantum metrology. In this setting, challenges arise that are not present in the single-parameter setting, such as the incompatibility of measurements and probes that are optimal for different parameters [52, 101]. These phenomena particular to multi-parameter quantum metrology have been extensively studied in the asymptotic context. We expect that a quantification of incompatibility and other multi-parameter phenomena through our finite-sample framework could deepen our understanding of these effects.

**Quantifying generalized communication tasks.** The minimax setting of quantum metrology has a further interesting interpretation, as it directly quantifies how well a sender Alice can communicate a scalar parameter $t \in \mathbb{R}$ to a receiver Bob when she encodes the parameter in a set of states $\rho(t)$. It is important to note here, that the worst-case nature of the minimax setting is critical in quantifying the performance, as Alice wants to be able to communicate any value $t$ with similar guarantees. In this sense, the minimax setting of quantum metrology quantifies a generalization of the commonly encountered task of communicating one of multiple discrete symbols [17]. In practical scenarios, Alice will usually send the state through a quantum channel $\mathcal{N}$ that degrades the message, giving an additional impetus to study quantum metrology with the noise model $\rho(t) \mapsto \mathcal{N}[\rho(t)]$ [11].

**Further open questions of information-theoretic nature.** In Section V, we have given an upper bound on the asymptotic rate of quantum metrology, which is tight for commuting states. It is an open question to determine under which general conditions on the set of states this bound is tight.
**Open Problem 5** (Asymptotic rate (states)). For a given tolerance $\delta > 0$, a set of states $\rho(t)$, possibly with prior $\mu(t)$, when do we have that

$$R^*(\delta, \mu, \rho) = \overline{R}^*(\delta, \rho) = \inf_{|t-t'|>2\delta} C(\rho(t), \rho(t'))? \quad (119)$$

Naturally, it is also interesting to quantify the second-order asymptotics of the success probability, which will, however, first require progress on the second-order asymptotics of the symmetric hypothesis testing error probability for quantum state discrimination. Another quite natural extension is the case of mixed asymptotics: We fix a desired scaling of the tolerance, decreasing slower than the optimal scaling; how fast can the success probability still attain unity?

As already outlined in Section IX, the setting of parametrized quantum channels offers much richer structure in its asymptotics, owing to the possibility of different strategies (separable use, parallel use, adaptive use and indefinite causal order). Given that Corollary 23 explicitly relates the success probability of quantum metrology under different access modes with the success probability of a corresponding hypothesis testing problem with similar access modes, we expect that the asymptotics of quantum metrology with different kinds of strategies should relate to the asymptotics of the corresponding multi-hypothesis testing tasks.

## XIV. DISCUSSION

Our work extends the foundations of quantum metrology to the regime where few measurement samples can be obtained. To study this regime, we present a truly single-shot framework for quantum metrology that removes two important assumptions that are used to derive the quantum Cramér-Rao bound. First, our approach quantifies estimation accuracy directly as the probability that the true estimate lies close to the parameter value instead of quantifying the variance of an unbiased estimator. This definition guarantees operational significance even in regimes where the variance is only a poor indicator of single-shot performance. Second, we remove the assumption of a local estimation setting. We have developed two ways of doing so: the Bayesian approach which allows us to reconnect to the local setting by choosing suitably narrow prior distributions and the minimax setting that truly quantifies the absence of knowledge about the underlying parameter.

In the setting of our framework (Fig. 1), a parameter $t$ is encoded in a set of quantum states $t \mapsto \rho(t)$. We quantify the probability that a measurement embodied by a POVM $\tau \mapsto Q(\tau)$ produces an estimate $\hat{t}$ of $t$ that is within a tolerance $\delta$ of the true value. “Probability” is evaluated with respect to the random nature of the measurement outcomes, either in the worst case over possible parameter values (minimax setting) or in the case where the parameter value is sampled from a prior probability

distribution (Bayesian setting). Our framework therefore captures any standard setting in quantum metrology in which an unknown parameter in the quantum state, possibly imprinted via a parameter-dependent dynamics, is to be estimated by the application of a quantum measurement.

The optimal success probability optimized over all possible POVMs $\tau \mapsto Q(\tau)$ can be obtained from a semi-infinite program, an extension of semidefinite programming that enables the inclusion of a continuous POVM as a variable. The rich structure offered by such a convex optimization enables numerical computations as well as some of our proofs including the derivation of both upper and lower bounds on the success probability. The solution to the convex optimization problem might be difficult to obtain, which is why there is a need for good “general purpose” measurement strategies, i.e. POVMs $Q(\tau)$ that give guarantees on an achievable success probability without the need to perform the convex optimization. A possible candidate for such a general purpose strategy could be the pretty good measurement.

Another practically relevant case arises when the quantum measurement is fixed, for instance by experimental constraints, and only the post-processing of measurement outcomes into predictions of the parameters may be optimized. In this setting, we showed that a strategy generalizing maximum a-posteriori estimation is optimal for the Bayesian setting and gives bounds in the minimax setting.

Our quantum metrology setting naturally extends quantum multi-hypothesis testing. Instead of selecting one of finitely many alternatives, we need to discriminate states from the set $\{\rho(t)\}_t$. This continuous generalization of hypothesis testing requires a tolerance $\delta$ in the precision to which the parameter is to be estimated. This difference seems to significantly complicate extensions of existing error bounds for multi-hypothesis testing to our continuous hypothesis testing setting: Such analyses typically analyze a protocol by assuming a unique correct output rather than a range of acceptable outputs. We make this connection rigorous by giving a general upper bound on the success probability of the estimation procedure in our metrology setup by showing that estimating a parameter to precision $\delta$ implies the ability to successfully distinguish between states with parameter values separated by at least $2\delta$ in a hypothesis testing setting. We exploit this result to give bounds on the success probability in terms of the fidelity of quantum states, a more tractable and familiar quantity.

This connection provides an important application of quantum hypothesis testing. The main use of quantum hypothesis testing so far is the study the asymptotic behavior of entropy measures, which is then applied for instance to the study of quantum communication scenarios beyond the i.i.d. regime. The application of quantum hypothesis testing to quantum metrology, an inherently physical setting, highlights a need to extend existing bounds and protocols in quantum hypothesis testing
to more general settings relevant to metrology, which in-
clude an error tolerance on the unknown parameter. This
connection is an exciting opportunity for quantum infor-
mation theory to inform the development of estimation
procedures and the derivation of fundamental bounds in
quantum metrology.

The fact that quantum metrology can be seen as a gen-
eralization of multi-hypothesis testing also opens upon
a wealth of open questions of a distinctly information-
theoretic flavor. We analyzed the asymptotic behavior of
the success probability of quantum metrology and have
shown a bound on the asymptotic error rate in terms of
the Chernoff divergence, a bound which can be achieved
in the case of commuting states. As such, we estab-
lished that the quantifier of the asymptotic properties
of hypothesis testing also applies to quantum metrolo-
gy. Our metrology setting also opens new kinds of
questions regarding the asymptotic behavior of quantum
information-theoretic quantities that appear in hypothe-
sis testing tasks. Theorem 13 bounds the rate at which
the success probability η approaches one as the number
of i.i.d. copies n goes to infinity, supposing that the es-
timation tolerance δ is kept constant. The asymptotic
behavior of δ, keeping η fixed, is in turn bounded by
Theorem 18. A particularly relevant regime to study is
a “mixed asymptotics” regime where δ → 0 and η → 1
simultaneously as n → ∞ . For instance, what is the
behavior of η if the tolerance decays as δ ∼ 1 / √ n ?

We take much inspiration from recent developments in
single-shot quantum information theory, where many re-
sults are expressed through entropic quantities that have
explicit single-shot interpretations. Popular examples are
min-, max- and Rényi-relative entropies. Similarly, our
single-shot framework for quantum metrology can be con-
nected to entropic quantities. In particular, we give an
alternative definition of the optimal success probability
of quantum metrology as a generalized conditional min-
entropy and bound the optimal tolerance through the hy-
pothesis testing relative entropy. One one hand, these re-
lations further strengthen the connection between quan-
tum metrology and quantum information theory, demon-
strating that concepts deeply rooted in quantum informa-
tion theory can offer alternative alternative approaches
to proving accuracy bounds in quantum metrology (e.g.
[19]). On the other hand, these relations further demon-
strate the broad usefulness and applicability of the tool-
box of single-shot entropy measures [17, 18, 117]. We
further anticipate opportunities to exploit new relations
between quantum metrology and entropy measures to de-
rive a deeper understanding of the fundamental accuracy
bounds through the lens of single-shot quantum informa-
tion theory.

Next to the success probability, the estimation toler-
ance is the second important pillar of our single-shot
framework for quantum metrology. It corresponds to the
natural question of quantifying the estimation accuracy
that can be obtained with a fixed success probability. It
is important because it fulfills a similar role as the stan-

dard deviation that is used as a measure of estimation
precision in the standard approach to quantum metro-
logy. The importance of providing useful lower bounds on
the optimal estimation tolerance is further underscored
by its use to manifestly express advantages that can be
obtained with entangled quantum states as opposed to
classical estimation strategies, such as Heisenberg scal-
ing [1]. We derived a general lower bound on the esti-
mation tolerance that resembles the quantum Cramér-
Rao bound. This bound involves the standard quantum
Fisher information and contains corrections pertaining to
the explicit single-shot nature of the estimation tolerance.
Obtaining improved bounds on the optimal tolerance –
especially bounds that are achievable in reasonable limits
– is a pressing question in the area of single-shot quantum
metrology.

Metrological problems are in many cases given by parametrized channels $t \mapsto \mathcal{N}(t)$ instead of parametrized quantum states. This setting offers a much richer structure of both the available ways of interacting with the quantum channel itself (e.g., adaptive versus non-adaptive protocols) as well as the underlying complications of the metrological protocols. We have adapted some of our central results, such as the formulation of the success probability as a convex program, as well as our central theorem about the connection to hypothesis testing, to this setting. There is a plethora of open questions of operational relevance, especially concerning the power of particular types of protocols with more restricted access to the parametrized quantum channel, which are detailed in the preceding section.

An important class of parametrized channels are uni-
tary evolutions under a given Hamiltonian. We study
this setting by establishing a closed-form expression for
the optimal minimax success probability associated to a
covariant state set, i.e. when a pure state evolves under
a given Hamiltonian and the parameter range is identical
to the recurrence time of said Hamiltonian. It is an inter-
esting question of further research if metrology protocols
that use adaptive processing with a memory system can
achieve a higher minimax success probability.

We apply this result to the traditional problem of phase
estimation using an ensemble of spin-½ particles. This is
one of the most basic, but still technologically impor-
tant, applications of quantum metrology. The closed-
form expression we derive for the optimal minimax suc-
cess probability allows us to characterize the optimal
probe state through a foundational result of Slepian [98]
and to compute the optimal asymptotic rate achievable
via entangled probe states. It also facilitates numerical
experiments for up to $n = 1000$ particles that we use to
compare different kinds of probe states in terms of the
achievable minimax success probability and minimax es-
timation tolerance. We observe that reasonable guesses
for good probe states, like the Holland-Burnett state or a
Gaussian profile do only coincide with the optimal state
in certain limits. The GHZ state is a poor probe state
this global estimation task because its period is much
shorter than the whole parameter range. Another out-
come of our numerical experiments was that there seem
to be settings where the quantum Cramér-Rao bound
faithfully predicts the optimal minimax estimation toler-
ance – in our case in the limit of many i.i.d. copies of the
optimal probe state when the success probability is fixed
at the probability that a normally distributed random
variable is within one standard deviation of the mean.

The observation that the quantum Cramér-Rao bound
can faithfully predict finite-sample performance is per-
haps surprising, given that we could expect the finite-
sample estimation tolerance to deviate significantly from
the optimal estimator variance, whose operational signif-
icance only appears in the many-sample regime. Indeed,
there is much fine print to this observation – the phase
estimation setting is highly regular and we analyzed it in
the pure state setting where many information measures
collapse into the quantum Fisher information. It nev-
ertheless proves that the quantum Fisher information,
which serves as a proxy for the single-shot distinguisha-
bility of neighboring quantum states ρ(t) and ρ(t + dt),
is likely to still be relevant in some finite-sample estima-
tion scenarios. Theorem 18 provides a specific connection
between the optimal estimation error tolerance and the
quantum Fisher information which involves the presence
of additional error terms. Quantifying the magnitude of
these error terms in various settings is likely to provide
clarity onto the regimes where the optimal estimation
tolerance is well approximated by the inverse square root
of the quantum Fisher information.

Our work reinforces the value of an operational ap-
proach to fundamental questions in quantum metrology,
especially in the finite-sample regime which is increas-
ingly relevant for current and near-term quantum tech-
nologies. The foundations of our approach are formal-
ized in our framework of probably approximately cor-
rect (PAC) metrology. Furthermore, the newly reinvigo-

rated connection between quantum metrology and quan-
tum information theory offers exciting opportunities for
progress in metrology using advanced techniques devel-
oped in quantum information theory, for instance, the use
of matrix analysis and convex optimization to character-
ize quantum information entropy measures. Contrary to
quantum metrology in the standard many-sample regime,
where many fundamental questions are already answered,
our operational approach to quantum metrology finite-
sample regime offers a plethora of intriguing questions
and research directions with the potential of uncovering
new practical estimation procedures with increased accu-
racy in quantum sensors and quantum clocks.

ACKNOWLEDGEMENTS

The authors would like to thank Sergii Strelchuk, Wil-
fred Salmon, Francesco Albarelli, Jasminder Sidhu and
Maximilian Reichert for valuable feedback on earlier ver-
sions of this manuscript.

This work has been supported by the DFG (CRC 183, FOR 2724), by the BMBF (Hybrid), the BMWK (PlanQK, EniQmA), the Munich Quantum Valley (K-8), QuantERA (HQCC) and the Einstein Foundation (Einstein Research Unit on Quantum Devices). This work has also been funded by the DFG under Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689).

AUTHOR CONTRIBUTIONS

J. J. M. led the project, derived a significant majority of the technical results and wrote the manuscript draft. All authors contributed substantially to the technical results and to writing the paper.

[1] V. Giovannetti, S. Lloyd, and L. Maccone, Advances in quantum metrology, *Nature Phot.* **5**, 222 (2011).

[2] M. G. A. Paris, Quantum estimation for quantum tech-
nology, *Int. J. Quant. Inf.* **07**, 125–137 (2011).

[3] C. L. Degen, F. Reinhard, and P. Cappellaro, Quantum sensing, *Rev. Mod. Phys.* **89**, 035002 (2017).

[4] L. Pezzè, A. Smerzi, M. K. Oberthaler, R. Schmied, and P. Treutlein, Quantum metrology with nonclassical states of atomic ensembles, *Rev. Mod. Phys.* **90**, 035005 (2018).

[5] S. L. Braunstein and C. M. Caves, Statistical distance and the geometry of quantum states, *Phys. Rev. Lett.* **72**, 3439–3443 (1994).

[6] J. J. Meyer, Fisher information in noisy intermediate-scale quantum applications, *Quantum* **5**, 539 (2021).

[7] H. Cramér, *Mathematical methods of statistics* (Princeton University Press, 1946).

[8] C. R. Rao, Information and the accuracy attainable in the estimation of statistical parameters, *Bull. Calcutta Math. Soc.* **37**, 81 (1945).

[9] C. W. Helstrom, Minimum mean-squared error of estimates in quantum statistics, *Phys. Lett. A* **25**, 101 (1967).

[10] R. Demkowicz-Dobrzanski, J. Kolodynski, and M. Guta, The elusive Heisenberg limit in quantum enhanced metrology, *Nature Comm.* **3**, 1063 (2012).

[11] P. Faist, M. P. Woods, V. V. Albert, J. M. Renes, J. Eis-
ert, and J. Preskill, Time-energy uncertainty relation for
noisy quantum metrology (2022), arXiv:2207.13707.

[12] S. Zhou, M. Zhang, J. Preskill, and L. Jiang, Achieving the Heisenberg limit in quantum metrology using quantum error correction, *Nature Commun.* **9**, 78 (2018).

[13] J. Liu, H. Yuan, X.-M. Lu, and X. Wang, Quantum fisher information matrix and multiparameter estimation, *J. Phys. A* **53**, 023001 (2020).

[14] K. M. R. Audenaert, J. Calsamiglia, R. Muñoz-Tapia, E. Bagan, L. Masanes, A. Acin, and F. Verstraete, Discriminating states: The quantum Chernoff bound, *Phys.*
Rev. Lett. 98, 160501 (2007).

[15] K. Li, Discriminating quantum states: The multiple Chernoff distance, Ann. Stat. 44, 1661 (2016).

[16] K. M. R. Audenaert and M. Mosonyi, Upper bounds on the error probabilities and asymptotic error exponents in quantum multiple state discrimination, J. Math. Phys. 55, 102201 (2014).

[17] S. Khatri and M. M. Wilde, Principles of quantum communication theory: A modern approach, arXiv:2011.04672 (2020).

[18] R. Renner, Security of Quantum Key Distribution, Ph.D. thesis, ETH Zürich (2005), arXiv:quant-ph/0512258.

[19] M. Walter and J. M. Renes, A Heisenberg limit for quantum region estimation, in 2014 IEEE Int. Symp. Inf. Th. (2014) pp. 1126-1130.

[20] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Theoretical framework for quantum networks, Phys. Rev. A 80, 022339 (2009).

[21] G. Gutoski and J. Watrous, Toward a general theory of quantum games, in Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, STOC '07 (Association for Computing Machinery, New York, NY, USA, 2007) pp. 565-574, arXiv:quant-ph/0611234.

[22] G. Chiribella, G. M. D'Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, Phys. Rev. A 88, 022318 (2013), 0912.0195.

[23] A. S. Holevo, Probabilistic and Statistical Aspects of Quantum Theory (Springer Science & Business Media, 2011).

[24] M. J. Holland and K. Burnett, Interferometric detection of optical phase shifts at the heisenberg limit, Phys. Rev. Lett. 71, 1355 (1993).

[25] D. Šafránek, Discontinuities of the quantum Fisher information and the Bures metric, Phys. Rev. A 95, 052320 (2017), arXiv:1612.04581.

[26] S. Zhou and L. Jiang, An exact correspondence between the quantum Fisher information and the Bures metric, arXiv:1910.08473 (2019).

[27] G. Bowen and N. Datta, Beyond i.i.d. in quantum information theory, arXiv:quant-ph/0604013 (2006).

[28] M. Tomamichel, Quantum information processing with finite resources (Springer Cham, 2016) arXiv:1504.00233.

[29] L. G. Valiant, A theory of the learnable, Comm. ACM 27, 1134 (1984).

[30] R. Blume-Kohout, Robust error bars for quantum tomography, ArXiv e-prints (2012), arXiv:1202.5270.

[31] M. Christandl and R. Renner, Reliable quantum state tomography, Phys. Rev. Lett. 109, 120403 (2012), arXiv:1108.5329.

[32] P. Faist and R. Renner, Practical and reliable error bars in quantum tomography, Phys. Rev. Lett. 117, 010404 (2016), arXiv:1509.06763.

[33] J. Wang, V. B. Scholz, and R. Renner, Confidence polytopes in quantum state tomography, Phys. Rev. Lett. 122, 190401 (2019).

[34] G. A. Durkin and J. P. Dowling, Local and global distinguishability in quantum interferometry, Phys. Rev. Lett. 99, 070801 (2007), quant-ph/0607088.

[35] J. Liu and H. Yuan, Valid lower bound for all estimators in quantum parameter estimation, New J. Phys. 18, 093009 (2016).

[36] J. Rubio and J. Dunningham, Bayesian multiparameter quantum metrology with limited data, Phys. Rev. A 101, 032114 (2020).

[37] J. Rubio, J. Anders, and L. A. Correa, Global quantum thermometry, Phys. Rev. Lett. 127, 190402 (2021).

[38] J. Boeyens, S. Seah, and S. Nimmrichter, Uninformed Bayesian quantum thermometry, Phys. Rev. A 104, 052214 (2021).

[39] R. R. Bahadur, Rates of convergence of estimates and test statistics, Ann. Math. Stat. 38, 303 (1967).

[40] R. R. Bahadur and J. C. Gupta, Distribution optimality and second-order efficiency of test procedures, Lecture Notes-Monograph Series 8, 315 (1986).

[41] R. R. Bahadur, 1. some limit theorems in statistics, in Some Limit Theorems in Statistics (Society for Industrial and Applied Mathematics, 1971) pp. 1-40.

[42] V. Spokoiny, Parametric estimation. Finite sample theory, Ann. Stat. 40, 2877 (2012), 1111.3029.

[43] M. Hayashi, Two quantum analogues of Fisher information from a large deviation viewpoint of quantum estimation, J. Phys. A 35, 7689 (2002).

[44] T. Sugiyama, P. S. Turner, and M. Murao, Error probability analysis in quantum tomography: A tool for evaluating experiments, Phys. Rev. A 83, 012105 (2011).

[45] T. Sugiyama, Finite sample analysis in quantum estimation, Springer Theses (Springer Tokyo, 2014).

[46] M. Walter and J. M. Renes, Lower bounds for quantum parameter estimation, IEEE Trans. Inf. Th. 60, 8007 (2014), 1310.2155.

[47] Y. Yang, G. Chiribella, and M. Hayashi, Attaining the ultimate precision limit in quantum state estimation, Commun. Math. Phys. 368, 223 (2019).

[48] T. Sugiyama, P. S. Turner, and M. Murao, Precision-guaranteed quantum tomography, Phys. Rev. Lett. 111, 160406 (2013).

[49] T. Sugiyama, Precision-guaranteed quantum metrology, Phys. Rev. A 91, 042126 (2015), 1407.8065.

[50] Y. Yang, G. Chiribella, and M. Hayashi, Quantum stop-watch: how to store time in a quantum memory, Proc. Roy. Soc. A 474, 20170773 (2018), 1703.05876.

[51] M. Tsang, Ziv-Zakai error bounds for quantum parameter estimation, Phys. Rev. Lett. 108, 230401 (2012).

[52] F. Albarelli and R. Demkowicz-Dobrzanski, Probe incompatibility in multiparameter noisy quantum metrology, Phys. Rev. X 12, 011039 (2022), 2104.11264.

[53] H. Imai and M. Hayashi, Fourier analytic approach to phase estimation in quantum systems, New J. Phys. 11, 043034 (2009).

[54] R. Demkowicz-Dobrzanski, W. Gorecki, and M. Guta, Multi-parameter estimation beyond quantum Fisher information, J. Phys. A 53, 363001 (2020).

[55] W. Salmon, S. Strelchuk, and D. Arvidsson-Shukur, Only classical parameterised states have optimal measurements under least squares loss, Quantum 7, 998 (2023), publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.

[56] R. Hettich and K. O. Kortanek, Semi-infinite programming: Theory, methods, and applications, SIAM Rev. 35, 380 (1993).

[57] L. Vandenberghe and S. Boyd, Connections between semi-infinite and semidefinite programming, in *Semi-infinite programming*, edited by R. Reemtsen and J.-J. Rückmann (Springer US, Boston, MA, 1998) pp. 277-294.
[58] L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Rev. 38, 49 (1996).

[59] S. P. Boyd and L. Vandenberghe, *Convex Optimization* (Cambridge University Press, Cambridge, UK, 2004).

[60] I. F. D. Oliveira and R. H. C. Takahashi, An enhancement of the bisection method average performance preserving minmax optimality, *ACM Trans. Math. Softw.* 47, 5:1 (2020).

[61] H. Yuen, R. Kennedy, and M. Lax, Optimum testing of multiple hypotheses in quantum detection theory, *IEEE Trans. Inf. Th.* 21, 125 (1975).

[62] C. W. Helstrom, Quantum detection and estimation theory, *J. Stat. Phys.* 1, 231 (1969).

[63] B. Yu, Assouad, Fano, and Le Cam, in *Festschrift for Lucien Le Cam: Research papers in probability and statistics*, edited by D. Pollard, E. Torgersen, and G. L. Yang (Springer, 1997) pp. 423–435.

[64] K. M. R. Audenaert, M. Nussbaum, A. Szkola, and F. Verstraete, Asymptotic error rates in quantum hypothesis testing, *Commun. Math. Phys.* 279, 251 (2008).

[65] R. König, R. Renner, and C. Schaffner, The operational meaning of min- and max-entropy, *IEEE Trans. Inf. Th.* 55, 4337 (2009), 0807.1338.

[66] N. Datta, Min- and max-relative entropies and a new entanglement monotone, *IEEE Trans. Inf. Th.* 55, 2816 (2009), 0803.2770.

[67] F. Dupuis, M. Berta, J. Wullschleger, and R. Renner, One-Shot Decoupling, *Comm. Math. Phys.* 328, 251 (2014), arXiv:1012.6044.

[68] R. Duan and A. Winter, No-signalling-assisted zero-error capacity of quantum channels and an information theoretic interpretation of the Lovász number, *IEEE Trans. Inf. Th.* 62, 891 (2016), arXiv:1409.3426.

[69] K. Fang, X. Wang, M. Tomamichel, and M. Berta, Quantum channel simulation and the channel’s smooth max-information, *IEEE Trans. Inf. Th.* 66, 2129 (2020), 1807.05354.

[70] F. Hiai and D. Petz, The proper formula for relative entropy and its asymptotics in quantum probability, *Com munications in Mathematical Physics* 143, 99 (1991).

[71] F. Dupuis, L. Kraemer, P. Faist, J. M. Renes, and R. Renner, Generalized entropies, in *XVIIth International Congress on Mathematical Physics* (World Scientific, Singapore, 2013) pp. 134–153, arXiv:1211.3141.

[72] N. Datta, M. Mosonyi, M.-H. Hsieh, and F. G. S. L. Brandão, A smooth entropy approach to quantum hypothesis testing and the classical capacity of quantum channels, *IEEE Trans. Inf. Th.* 59, 8014 (2013), 1106.3089.

[73] L. Wang and R. Renner, One-shot classical-quantum capacity and hypothesis testing, *Phys. Rev. Lett.* 108, 200501 (2012), arXiv:1007.5456.

[74] M. Tomamichel and M. Hayashi, A hierarchy of information quantities for finite block length analysis of quantum tasks, *IEEE Transactions on Information Theory* 59, 7693 (2013), arXiv:1208.1478.

[75] D. L. Wallace, Asymptotic approximations to distributions, *The Annals of Mathematical Statistics* 29, 635 (1958).

[76] S. Kurdzialek, W. Gorecki, F. Albarelli, and R. Demkowicz-Dobrzanski, *Using adaptiveness and causal superpositions against noise in quantum metrology* (2023), arXiv:2212.08106.

[77] G. Chiribella, G. M. D’Ariano, P. Perinotti, and B. Valiron, Quantum computations without definite causal structure, *Phys. Rev. A* 88, 022318 (2013).

[78] X. Zhao, Y. Yang, and G. Chiribella, Quantum metrology with indefinite causal order, *Phys. Rev. Lett.* 124, 190503 (2020).

[79] Q. Liu, Z. Hu, H. Yuan, and Y. Yang, Optimal strategies of quantum metrology with a strict hierarchy, *Phys. Rev. Lett.* 130, 070803 (2023), 2203.09758.

[80] V. P. Belavkin, Optimal multiple quantum statistical hypothesis testing, *Stochastics* 1, 315 (1975).

[81] V. P. Belavkin, Optimum distinction of non-orthogonal quantum signals, *Radiotekhnika i Elektronika* 20, 1177 (1975).

[82] A. S. Holevo, On asymptotically optimal hypothesis testing in quantum statistics, *Theo. Proba. Appl.* 23, 411 (1979).

[83] V. P. Belavkin and V. P. Maslov, Design of optimal dynamic analyzers: Mathematical aspects of wave pattern recognition, *Advances in Science and Technology in the USSR* (1988), quant-ph/0412031.

[84] P. Hausladen and W. K. Wootters, A ‘pretty good’ measurement for distinguishing quantum states, *J. Mod. Opt.* 41, 2385 (1994).

[85] L. P. Hughston, R. Jozsa, and W. K. Wootters, A complete classification of quantum ensembles having a given density matrix, *Phys. Lett. A* 183, 14 (1993).

[86] A. S. Holevo, Covariant measurements and uncertainty relations, *Rep. Math. Phys.* 16, 385 (1979).

[87] M. Ban, K. Kurokawa, R. Momose, and O. Hirota, Optimum measurements for discrimination among symmetric quantum states and parameter estimation, *Int. J. Th. Phys.* 36, 1269 (1997).

[88] M. Hayashi, Asymptotic estimation theory for a finite-dimensional pure state model, *J. Phys. A* 31, 4633 (1998).

[89] G. Chiribella and G. M. D’Ariano, Extremal covariant positive operator valued measures, *J. Math. Phys.* 45, 4435 (2004).

[90] G. Chiribella, G. M. D’Ariano, P. Perinotti, and M. F. Sacchi, Covariant quantum measurements that maximize the likelihood, *Phys. Rev. A* 70, 062105 (2004).

[91] G. Chiribella and G. Mauro D’Ariano, Extremal covariant measurements, *J. Math. Phys.* 47, 092107 (2006).

[92] K. G. Murty and S. N. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, *Math. Prog.* 39, 117 (1987).

[93] R. Demkowicz-Dobrzański, Optimal phase estimation with arbitrary a priori knowledge, *Phys. Rev. A* 83, 061802 (2011).

[94] D. J. Wineland, J. J. Bollinger, W. M. Itano, F. L. Moore, and D. J. Heinzen, Spin squeezing and reduced quantum noise in spectroscopy, *Phys. Rev. A* 46, R6797 (1992).

[95] D. J. Wineland, J. J. Bollinger, W. M. Itano, and D. J. Heinzen, Squeezed atomic states and projection noise in spectroscopy, *Phys. Rev. A* 50, 67 (1994).

[96] S. F. Huelga, C. Macchiavello, T. Pellizzari, A. K. Ekert, M. B. Plenio, and J. I. Cirac, Improvement of frequency standards with quantum entanglement, *Phys. Rev. Lett.* 79, 3865 (1997).

[97] G. Chesi, R. Rubboli, A. Riccardi, L. Maccone, and C. Macchiavello, A protocol for global multiphase estimation, arXiv:2301.07380 (2023).
[98] D. Slepian, Prolate spheroidal wave functions, fourier analysis, and uncertainty — v: the discrete case, *Bell Syst. Tech. J.* **57**, 1371 (1978).

[99] A. T. Walden, Accurate approximation of a 0th order discrete prolate spheroidal sequence for filtering and data tapering, *Sig. Proc.* **18**, 341 (1989).

[100] F. Albarelli, J. F. Friel, and A. Datta, Evaluating the Holevo Cramér-Rao bound for multiparameter quantum metrology, *Phys. Rev. Lett.* **123**, 200503 (2019).

[101] F. Belliardo and V. Giovannetti, Incompatibility in quantum parameter estimation, *New J. Phys.* **23**, 063055 (2021).

[102] X.-M. Lu and X. Wang, Incorporating Heisenberg's uncertainty principle into quantum multiparameter estimation, *Phys. Rev. Lett.* **126**, 120503 (2021).

[103] T. J. Proctor, P. A. Knott, and J. A. Dunningham, Multi-parameter estimation in networked quantum sensors, *Phys. Rev. Lett.* **120**, 080501 (2018), 1707.06252.

[104] K. Qian, Z. Eldredge, W. Ge, G. Pagano, C. Monroe, J. V. Porto, and A. V. Gorshkov, Heisenberg-scaling measurement protocol for analytic functions with quantum sensor networks, *Phys. Rev. A* **100**, 042304 (2019).

[105] S. Aaronson, Shadow tomography of quantum states, in *Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing*, STOC 2018 (2018) pp. 325–338.

[106] H.-Y. Huang, R. Kueng, and J. Preskill, Predicting many properties of a quantum system from very few measurements, *Nature Phys.* **16**, 1050 (2020).

[107] N. Shettell, E. Kashefi, and D. Markham, Cryptographic approach to quantum metrology, *Phys. Rev. A* **105**, L010401 (2022).

[108] N. Shettell, M. Hassani, and D. Markham, Private network parameter estimation with quantum sensors (2022), 2207.14450.

[109] M. M. Wilde, *Quantum Information Theory*, 2nd ed. (Cambridge University Press, 2017).

[110] M. Cerezo, A. Arrasmith, R. Babbush, S. C. Benjamin, S. Endo, K. Fujii, J. R. McClean, K. Mitarai, X. Yuan, L. Cincio, and P. J. Coles, Variational quantum algorithms, *Nature Rev. Phys.* **3**, 625 (2021).

[111] M. Tsang, F. Albarelli, and A. Datta, Quantum semiparametric estimation, *Phys. Rev. X* **10**, 031023 (2021).

[112] D. W. Berry and H. M. Wiseman, Optimal states and almost optimal adaptive measurements for quantum interferometry, *Phys. Rev. Lett.* **85**, 5098 (2000).

[113] V. Giovannetti, S. Lloyd, and L. Maccone, Quantum Metrology, *Phys. Rev. Lett.* **96** (2006).

[114] R. Demkowicz-Dobrzański, J. Kołodyński, and M. Gută, The elusive Heisenberg limit in quantum-enhanced metrology, *Nature Commun.* **3**, 1063 (2012).

[115] S. F. Huelga, C. Macchiavello, T. Pellizzari, A. K. Ekert, M. B. Plenio, and J. I. Cirac, Improvement of frequency standards with quantum entanglement, *Phys. Rev. Lett.* **79**, 3865 (1997).

[116] A. Smirne, J. Kołodyński, S. F. Huelga, and R. Demkowicz-Dobrzański, Ultimate precision limits for noisy frequency estimation, *Phys. Rev. Lett.* **116**, 120801 (2016).

[117] P. Faist, The entropy zoo (2015), https://phfaist.com/entropyzoo.

[118] J. S. Sidhu and P. Kok, A geometric perspective on quantum parameter estimation, arXiv:1907.06628 (2019), 1907.06628.

[119] Z. Ji, G. Wang, R. Duan, Y. Feng, and M. Ying, Parameter Estimation of Quantum Channels, IEEE Trans. Inf. Th. **54**, 5172 (2008), quant-ph/0610060.

[120] A. Hentschel and B. C. Sanders, Efficient Algorithm for Optimizing Adaptive Quantum Metrology Processes, *Phys. Rev. Lett.* **107**, 233601 (2011).

[121] M. Hayashi, Comparison between the Cramer-Rao and the mini-max approaches in quantum channel estimation, *Commun. Math. Phys.* **304**, 689 (2011).

[122] R. Demkowicz-Dobrzański, J. Czajkowski, and P. Sekatski, Adaptive quantum metrology under general Markovian noise, *Phys. Rev. X* **7**, 041009 (2017).

[123] H. Yuan and C.-H. F. Fung, Fidelity and Fisher information on quantum channels, *New J. Phys.* **19**, 113039 (2017).

[124] H. Yuan and C.-H. F. Fung, Quantum parameter estimation with general dynamics, *npj Quantum Information* **3**, 14 (2017).

[125] V. Katariya and M. M. Wilde, Geometric distinguishability measures limit quantum channel estimation and discrimination, *Quantum Information Processing* **20**, 78 (2021), 2004.10708.

[126] V. Katariya and M. M. Wilde, RLD Fisher information bound for multiparameter estimation of quantum channels, *New J. Phys.* **23**, 073040 (2021).

[127] C. W. Helstrom, *Quantum Detection and Estimation Theory* (Academic Press, 1976).

[128] D. Slepian and H. O. Pollak, Prolate spheroidal wave functions, Fourier analysis and uncertainty-I, *Bell System Technical Journal* **40**, 43 (1961).

[129] J. Rubio, P. Knott, and J. Dunningham, Non-asymptotic analysis of quantum metrology protocols beyond the Cramér-Rao bound, *J. Phys. Comm.* **2**, 015027 (2018).

[130] J. Rubio and J. Dunningham, Quantum metrology in the presence of limited data, *New J. Phys.* **21**, 043037 (2019).

[131] B. A. Chase and J. M. Geremia, Single-shot parameter estimation via continuous quantum measurement, *Phys. Rev. A* **79**, 022314 (2009).

[132] M. Tsang, Continuous quantum hypothesis testing, *Phys. Rev. Lett.* **108**, 170502 (2012).

[133] R. Reemtsen and J.-J. Rückmann, eds., *Semi-Infinite Programming* (Springer US, 1998).

[134] A. Charnes, P. R. Gribik, and K. O. Kortanek, Separably-infinite programs, *Zeitschrift für Operations Research* **24**, 33 (1980).

[135] A. Shapiro, Semi-infinite programming, duality, discretization and optimality conditions, *Optimization* **58**, 133 (2009).

[136] G. Chiribella, Optimal networks for quantum metrology: semidefinite programs and product rules, *New J. Phys.* **14**, 125008 (2012).

[137] G. Chiribella, G. M. D'Ariano, and P. Perinotti, Memory effects in quantum channel discrimination, *Phys. Rev. Lett.* **101**, 180501 (2008).

[138] R. Ito and R. Mori, Lower bounds on the error probability of multiple quantum channel discrimination by the Bures angle and the trace distance, arXiv:2107.03948 (2021).

[139] O. Oreshkov, F. Costa, and Č. Brukner, Quantum correlations with no causal order, *Nature Commun.* **3**, 1092 (2012).
[140] J. Bavaresco, M. Murao, and M. T. Quintino, Unitary channel discrimination beyond group structures: Advantages of sequential and indefinite-causal-order strategies, *J. Math. Phys.* **63**, 042203 (2022), 2105.13369.

[141] M. Araújo, C. Branciard, F. Costa, A. Feix, C. Giarmatzi, and Č. Brukner, Witnessing causal nonseparability, *New J. Phys.* **17**, 102001 (2015).

[142] G. Gutoski, Properties of local quantum operations with shared entanglement, *Quant. Inf. Comp.* **9**, 739 (2009).

[143] G. Chiribella and D. Ebler, Optimal quantum networks and one-shot entropies, *New J. Phys.* **18**, 093053 (2016).

[144] J. Bavaresco, M. Murao, and M. T. Quintino, Strict hierarchy between parallel, sequential, and indefinite-causal-order strategies for channel discrimination, *Phys. Rev. Lett.* **127**, 200504 (2021), 2011.08300.

[145] D. Freeman, A. M. Powell, and M. A. Taylor, A Schauder basis for $L_2$ consisting of non-negative functions, *Math. Ann.* **381**, 181 (2021).

[146] Y. Ohnishi and J. Honorio, Novel change of measure inequalities with applications to PAC-Bayesian bounds and Monte Carlo estimation, arXiv:2002.10678 (2020).

[147] W. Beckner, Inequalities in Fourier analysis, *Ann. Math.* **102**, 159 (1975).

[148] A. S. Holevo, An analogue of statistical decision theory and noncommutative probability theory, *Trudy Moskovskogo Matematicheskogo Obshchestva* **26**, 133 (1972).

[149] J. Lumbreras, E. Haapasalo, and M. Tomamichel, Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states (2022).

[150] H.-C. Cheng, A simple and tighter derivation of achievability for classical communication over quantum channels, arXiv:2208.02132 10.48550/arXiv.2208.02132 (2022), 2208.02132.

[151] G. Vazquez-Vilar, Multiple quantum hypothesis testing expressions and classical-quantum channel converse bounds, in *2016 IEEE Int. Symp. Inf. Th. (ISIT)* (2016) pp. 2854–2857.

[152] J. Haah, A. W. Harrow, Z. Ji, X. Wu, and N. Yu, Sample-optimal tomography of quantum states, *IEEE Trans. Inf. Th.* **63**, 5628 (2017), 1508.01797.

[153] M. Nussbaum and A. Szkoła, The Chernoff lower bound for symmetric quantum hypothesis testing, *Ann. Stat.* **37**, 1040 (2009).

[154] M. Jarzyna and J. Kolodynski, Geometric approach to quantum statistical inference, arXiv:2008.09129 (2020).

[155] P.-A. Wedin, Perturbation theory for pseudo-inverses, *BIT Num. Math.* **13**, 217 (1973).

[156] R. Wong, *Asymptotic approximations of integrals*, Computer science and scientific computing (Academic Press, 1989).

[157] K. Takahashi and A. Fujiwara, Information geometry of sandwiched Rényi α-divergence, *J. Phys. A* **50**, 165301 (2017).

[158] I. Chatzigeorgiou, Bounds on the Lambert function and their application to the outage analysis of user cooperation, *IEEE Commun. Lett.* **17**, 1505 (2013), 1601.04895.
Supplementary Material:
Quantum metrology in the finite-sample regime

Johannes Jakob Meyer,¹ Sumeet Khatri,¹ Daniel Stilck França,¹,²,³ Jens Eisert,¹,⁴,⁵ and Philippe Faist¹

¹Dahlem Center for Complex Quantum Systems, Freie Universität Berlin, 14195 Berlin, Germany

²Department of Mathematical Sciences, University of Copenhagen, 2100 København, Denmark

³Ecole Normale Superieure de Lyon, 69342 Lyon Cedex 07, France

⁴Helmholtz-Zentrum Berlin für Materialien und Energie, 14109 Berlin, Germany

⁵Fraunhofer Heinrich Hertz Institute, 10587 Berlin, Germany

(Dated: July 14, 2023)

<table>
  <tbody>
    <tr>
      <td>I. Relation to prior art</td>
      <td>34</td>
    </tr>
    <tr>
      <td>II. The Cramér-Rao bound in the presence of finite samples</td>
      <td>35</td>
    </tr>
    <tr>
      <td>III. Optimization through convex programming</td>
      <td>36</td>
    </tr>
    <tr>
      <td>A. Measurement optimization</td>
      <td>36</td>
    </tr>
    <tr>
      <td>B. Probe optimization</td>
      <td>40</td>
    </tr>
    <tr>
      <td>C. Optimization with respect to strategies with definite causal order</td>
      <td>41</td>
    </tr>
    <tr>
      <td>D. Optimization with respect to strategies with indefinite causal order</td>
      <td>48</td>
    </tr>
    <tr>
      <td>E. Numerical implementation</td>
      <td>53</td>
    </tr>
    <tr>
      <td>F. Discretizing the success probability</td>
      <td>54</td>
    </tr>
    <tr>
      <td>IV. Relation to entropy measures</td>
      <td>59</td>
    </tr>
    <tr>
      <td>A. Max-entropy radius</td>
      <td>59</td>
    </tr>
    <tr>
      <td>B. Conditional min-entropy</td>
      <td>59</td>
    </tr>
    <tr>
      <td>V. Properties of the proposed quantifiers</td>
      <td>60</td>
    </tr>
    <tr>
      <td>A. Properties of the unoptimized quantifiers</td>
      <td>60</td>
    </tr>
    <tr>
      <td>B. Properties of the optimized quantities</td>
      <td>64</td>
    </tr>
    <tr>
      <td>C. Subdivision trick</td>
      <td>64</td>
    </tr>
    <tr>
      <td>VI. Optimal post-processing with fixed measurement</td>
      <td>65</td>
    </tr>
    <tr>
      <td>VII. Relation to hypothesis testing</td>
      <td>66</td>
    </tr>
    <tr>
      <td>A. Multi-hypothesis testing as a special case of metrology</td>
      <td>66</td>
    </tr>
    <tr>
      <td>B. Upper bound on success probability from multi-hypothesis testing</td>
      <td>67</td>
    </tr>
    <tr>
      <td>C. Upper bound via binary hypothesis testing</td>
      <td>69</td>
    </tr>
    <tr>
      <td>D. Upper bound on the success probability from asymmetric hypothesis testing</td>
      <td>70</td>
    </tr>
    <tr>
      <td>E. Fano-type bounds for quantum multi-hypothesis testing</td>
      <td>71</td>
    </tr>
    <tr>
      <td>F. Further bounds</td>
      <td>75</td>
    </tr>
    <tr>
      <td>G. Upper bound on asymptotic rate</td>
      <td>76</td>
    </tr>
    <tr>
      <td>H. Relation to Wigner-Yanase-Dyson information</td>
      <td>78</td>
    </tr>
    <tr>
      <td>I. Lower bound on success probability</td>
      <td>79</td>
    </tr>
    <tr>
      <td>VIII. Optimal tolerance</td>
      <td>87</td>
    </tr>
    <tr>
      <td>A. Lower bounds via asymmetric hypothesis testing</td>
      <td>87</td>
    </tr>
    <tr>
      <td>B. Lower bound via symmetric hypothesis testing</td>
      <td>91</td>
    </tr>
    <tr>
      <td>IX. Optimal sample complexity</td>
      <td>93</td>
    </tr>
    <tr>
      <td>X. Beyond univariate metrology</td>
      <td>93</td>
    </tr>
    <tr>
      <td>XI. The covariant case: Pure Hamiltonian evolution</td>
      <td>95</td>
    </tr>
    <tr>
      <td>XII. Minimax analysis of phase estimation</td>
      <td>100</td>
    </tr>
    <tr>
      <td>A. Chernoff bound and entanglement advantage</td>
      <td>105</td>
    </tr>
    <tr>
      <td>B. Additional numerics</td>
      <td>105</td>
    </tr>
  </tbody>
</table>
# I. RELATION TO PRIOR ART

Because of its technological importance, quantum metrology is a very important subfield of quantum information theory. Most works in the literature focus on the asymptotic theory of local estimation centered around the quantum Fisher information – a good overview can be found in Ref. [118]. In this work, we establish an inherently single-shot characterization of quantum metrology via an operational characterization of the success probability of parameter estimation. From this characterization, we establish a coherent framework to quantify the quality of quantum metrology protocols by analyzing the success probability, the tolerance and the sample complexity. We develop a deep understanding of these quantities through analytical bounds and numerical experiments.

Due to the prominent role of quantum metrology in the field of quantum information science, it comes as no surprise that parts of our definitions and some analytical results concerning those have already appeared in the literature. In the following, we exemplify how our work goes well beyond the prior art by giving a detailed account of the similarities and differences between our results and the results already found in the literature.

In Ref. [43], the author also defines a notion of success probability with a given tolerance similar to Definition 1. They study the properties of *consistent* protocols that ensure that the success probability, asymptotically, approaches unity for all nonzero tolerances. For those protocols, a large-deviation analysis where the number of samples is finite but still assumed large is performed. This allows the author to bound the local curvature of the asymptotic rate defined in Eq. (48) of the main text. In our work, we go beyond this result by establishing bounds that hold in the single-shot setting and that we then use to establish bounds on the asymptotic rate that hold for fixed tolerance $\delta$ and that at the same time give tighter constraint on its local curvature (see Section VII H).

Refs. [44, 45, 48] contain what is essentially the multi-parameter generalization of Ref. [43] to the multi-parameter setting, with quantum state tomography as the most prominent application. It is a common feature of all these works that they assume the sequence of quantum measurements associated with the different numbers of possible copies of the state to be fixed. This allows the authors to make good use of tools from classical estimation theory. Especially in Ref. [49], the author analyzes the scaling of the tolerance for a fixed success probability when a measurement is fixed and a maximum-likelihood estimate is performed. This can be seen as studying a particular prediction rule as introduced in Section III B. We wish to emphasize that all our results except for the lower bound on the asymptotic rate and the developments of Section III B pertain to the case where measurements are not fixed a priori but the optimal measurement can be chosen.

The setting of fixed measurements (compare Section III B) was also studied in Ref. [55]. There, the authors fixed on the question if there exists a measurement that is *admissible* in a estimation-theoretical sense, i.e., if there is a measurement basis that works equally well for all possible values of the underlying parameter.

The optimal achievable tolerance was also studied in Ref. [19, 46]. The authors there studied parametrized quantum states as classical-quantum states, similar to what we use in Corollary 16 to relate the success probability of quantum metrology to the conditional min-entropy.

The authors of Ref. [50] also put forth a definition similar to the minimax tolerance of Definition 2, referring to it as “inaccuracy”. They furthermore obtain a lower bound on the minimax tolerance by making a particular multi-hypothesis testing reduction. Their lower bound, however, is limited by its dependence on the dimension of the underlying quantum systems.

Parameter estimation of quantum channels using the Fisher information has been considered in Refs. [79, 119-126]. We note that while in some of these works the number of channel uses is finite, the estimation strategies are still evaluated using the quantum Fisher information. In this work, on the other hand, we evaluate strategies for quantum channel parameter estimation using our inherently single-shot success probability.

Phase estimation, as studied in Section XI of the main text, is the generally most-studied application of quantum metrology. It is an instance of a covariant estimation problem whose study dates back to the foundational works of Holevo and Helstrom, with important contributions from Belavkin and Maslov [23, 62, 83, 127]. Already in these works, it has been shown that covariant measurements are optimal for covariant estimation problems, but not necessarily which covariant measurement. The authors of Ref. [87] have shown that the pretty good measurement is optimal both for symmetric multi-hypothesis testing as well as covariant estimation with a maximum likelihood approach. In Section XI, we extend this result by showing that the pretty good measurement also achieves the optimal minimax tolerance in the case of covariant estimation with pure states.

We note that our study of phase estimation goes well beyond these results, as it also covers the single-shot regime and as we also give results on the optimal minimax tolerance of phase estimation. Our study of phase estimation has novel results valid in the single-shot regime and gives explicit bounds on the optimal asymptotic tolerance. Our results on the asymptotic rate (Theorem 25) do however overlap significantly with prior work of Ref. [53]. The authors establish the distributions of measurement outcomes that can be realized asymptotically in phase estimation and build on the continuous version of the work of Slepian and Pollak [128] to claim the asymptotic rate of Theorem 25. The authors of Ref. [53] did not prove the required positivity of the DPSS of zeroth order necessary for such a claim, as
such we filled a small gap in their proof. Furthermore, Refs. [34, 93, 97, 129] have also went beyond the asymptotic regime and considered the phase estimation problem from both the local and global perspectives.

Another approach to non-asymptotic metrology was studied in Refs. [129, 130]. The authors explicitly evaluate the mean-squared error for phase estimation problems with a small but increasing finite number of independent repetitions of a single-repetition estimation scheme, and they examine its convergence to the Cramér-Rao bound as the number of repetitions increases. Similarly, in Ref. [35], the authors consider a finite number of independent repetitions of a single-repetition estimation scheme, but they also develop a Cramér-Rao-like bound on the mean-squared error that applies to biased estimators. Notably, in these works, the estimation performance is evaluated using the mean-squared error [129, 130] and the quantum Fisher information [35], both of which are asymptotic quantities, while in this work our estimation procedure is evaluated using the inherently single-shot $\delta$-accurate estimation success probability presented in Definition 1.

It is worth mentioning that Ref. [51] also uses a reduction of the parameter estimation problem to hypothesis testing, but it does so in a different way than in our work. In particular, in Ref. [51], the author defines a quantum version of the Ziv-Zakai bound from classical estimation theory, which provides a bound on the mean-squared error, in terms of binary hypothesis tests. The quantum Ziv-Zakai bound is then formulated in terms of the optimal binary symmetric hypothesis testing error probability. While the quantum Ziv-Zakai bound can improve upon the quantum Cramér-Rao bound in the regime of finite samples [129], it is still hampered by the fact that hypothesis testing is used to bound an inherently asymptotic quantity. Starting from the inherently operational single-shot definition of the success probability allows us to develop a way stronger connection to hypothesis testing, as evident in Section IV.

Further work on continuous hypothesis testing includes Refs. [131, 132]. The “continuous” in these works actually refers to measuring the (unknown) system at different points in time and then deciding which among two possible states the system was in initially, or about deciding among two possibilities for the dynamics of the system. However, notably, in Ref. [131] (Section IV), the authors already allude to a continuous version of quantum hypothesis testing as we view it.

## II. THE CRAMÉR-RAO BOUND IN THE PRESENCE OF FINITE SAMPLES

Here, we review how the operational relevance of the Cramér-Rao bound might be compromised in the regime where limited data is available. Consider a one-parameter family of states $\rho(t)$. Suppose we know that the true value $t$ of the parameter is close to some value $t_0$. We seek an observable $T$ that reveals the true value $t$ in the neighborhood of $t_0$ in its expectation value, i.e. $\langle T \rangle_{\rho(t_0+dt)} = t_0 + dt + O(dt^2)$. The observable $T$ serves as estimator for the true parameter. A formulation of the Cramér-Rao bound states that the minimal variance achieved by such an estimator is the inverse of the quantum Fisher information,

$$ \min_T \langle (T - t_0)^2 \rangle_{\rho(t_0)} = \frac{1}{\mathcal{F}(\rho(t_0))}, \qquad (120) $$

where the quantum Fisher information $\mathcal{F}(\rho(t))$ is defined as $\mathcal{F}(\rho(t)) := \text{Tr}[\rho(t)L^2]$, where the SLD operator $L$ is a solution to the equation $(\rho(t)L + L\rho(t))/2 = \partial_t \rho(t)$.

The estimation strategy considered by the Cramér-Rao bound requires the estimation of the expectation value of the corresponding observable $T$. In practice, this requires repeated measurements of $T$ and averaging the corresponding individual outcomes. However, in the presence of limited data, an accurate estimation of the expectation value might require a large amount of data. In the following, we review such a situation. In such a setting, the fundamental accuracy limits might be fundamentally different than the one predicted by the Cramér-Rao bound.

Consider the following situation detailed in Refs. [25, 26]. Let $\omega > 0$, then the one-parameter family of qubit states $\rho(t)$ and the derivative $\partial_t \rho(t)$ are given as

$$ \rho(t) = \begin{pmatrix} \cos^2(\omega t/2) & 0 \\ 0 & \sin^2(\omega t/2) \end{pmatrix}, \qquad \partial_t \rho(t) = -\frac{\omega}{2} \sin(\omega t) \begin{pmatrix} 1 & 0 \\ 0 & -1 \end{pmatrix}. \qquad (121) $$

This evolution actually induces a discontinuity in the quantum Fisher information: As shown in Ref. [25], the quantum Fisher information $\mathcal{F}(\rho(t))$ is

$$ \mathcal{F}(\rho(t)) = \begin{cases} 0 & \text{if } \omega t = m\pi, m \in \mathbb{Z}, \\ \omega^2 & \text{otherwise.} \end{cases} \qquad (122) $$

Now consider the regime where $t_0 \approx 0$, $t_0 \neq 0$. According to the Cramér-Rao bound, it is possible to estimate the value of $t$ close to $t_0$ with optimal sensitivity $1/\omega^2$ with a suitable observable. As computed e.g. in Ref. [11] [Appendix H.2],
the optimal observable in question is

$$ T = t_0 \mathbb{I} + \frac{1}{\omega} \begin{pmatrix} -\tan(\omega t_0/2) & 0 \\ 0 & \frac{1}{\tan(\omega t_0/2)} \end{pmatrix}. \quad (123) $$

We can check indeed that

$$ \mathrm{Tr}[T\rho(t_0 + dt)] = t_0 + dt + O(dt^2). \quad (124) $$

It is, however, instructive to write out the expectation value as a sum of two terms, one associated with each outcome of a measurement of $T$. With $t = t_0 + dt$, the contributions to $\mathrm{Tr}[T\rho(t)]$ are, with $T_j = \langle j | T | j \rangle - t_0$,

$$ \begin{aligned} T_0 \langle 0 | \rho(t) | 0 \rangle &= \cos^2(\omega t/2) \frac{1}{\omega} (-\tan(\omega t_0/2)) \\ &= -\frac{1}{\omega} \left( \cos^2(\omega t_0/2) - \frac{\omega}{2} dt \sin(\omega t_0) + O(dt^2) \right) \tan(\omega t_0/2) \\ &= -\frac{1}{2\omega} \sin(\omega t_0) + dt \sin^2(\omega t_0/2) + O(dt^2), \end{aligned} \quad (125) $$

$$ \begin{aligned} T_1 \langle 1 | \rho(t) | 1 \rangle &= \sin^2(\omega t/2) \frac{1}{\omega} \frac{1}{\tan(\omega t_0/2)} \\ &= \frac{1}{\omega} \left( \sin^2(\omega t_0/2) + \frac{\omega}{2} dt \sin(\omega t_0) + O(dt^2) \right) \frac{1}{\tan(\omega t_0/2)} \\ &= \frac{1}{2\omega} \sin(\omega t_0) + dt \cos^2(\omega t_0/2) + O(dt^2). \end{aligned} \quad (126) $$

Indeed, $\mathrm{Tr}[T\rho(t)] = t_0 + T_0 \langle 0 | \rho(t) | 0 \rangle + T_1 \langle 1 | \rho(t) | 1 \rangle = t_0 + dt + O(dt^2)$. However, as $t_0 \to 0$, $t_0 \neq 0$, we see that the value $T_1$ diverges while the corresponding probability $\langle 1 | \rho(t_0) | 1 \rangle$ vanishes. It turns out that that large term times a tiny term conspire to provide just exactly the required difference in the expectation value so that we have $\mathrm{Tr}[T\rho(t_0 + dt)] \approx t_0 + dt$. In the regime where limited data is available, the outcome $|1\rangle$ is never observed, because it occurs too rarely. As a consequence, only the first outcome is observed and the reported estimate for the parameter, computed from the averages of the samples of the outcomes of $T$, is $t_0 - [\tan(\omega t_0/2)]/\omega$. This value does not depend on $dt$; therefore, the estimation procedure fails to accurately reveal the value of $dt$ to the desired accuracy $1/\omega^2$. The approach presented in this work aims to tackle settings such as the one above, where the estimation procedure must rely on a limited number of samples.

### III. OPTIMIZATION THROUGH CONVEX PROGRAMMING

In this section, we consider the optimized success probabilities and show that we can cast them into the form of convex semi-infinite problems (SIPs) [56, 133, 134]. These represent continuous analogues of semi-definite programs, which have to be discretized to be solved on a computer. We elaborate on this point in Section III E.

Throughout this section, we make use of the following standard forms of primal and dual semi-definite programs [17]:

$$ \begin{array}{ll} \text{maximize} & \mathrm{Tr}[AX] \\ \text{subject to} & X \ge 0, \\ & \Phi[X] \le B. \end{array} \qquad \begin{array}{ll} \text{minimize} & \mathrm{Tr}[BY] \\ \text{subject to} & Y \ge 0, \\ & \Phi^{\dagger}[Y] \ge A, \end{array} \quad (127) $$

where $A$ and $B$ are Hermitian operators and $\Phi$ is a Hermiticity-preserving linear map. The convex semi-infinite programs that we consider in this work have the form of these semi-definite programs, with either given tuple $(A, B, \Phi) \equiv (A(t), B(t), \Phi(t))$, the optimization variables $X \equiv X(t)$ and $Y \equiv Y(t)$, or both, being parameterized by $t \in \mathbb{R}$. As in the theory of semi-definite programs [58], the notions of (weak and strong) duality and Slater's conditions carry over to such convex SIPs [134, 135], and we make use these concept throughout in what follows.

#### A. Measurement optimization

It is quite straightforward that the optimal measurement in the Bayesian case can be determined using a convex program.
**Proposition 1** (Bayesian measurement optimization). For a given set of states $\rho(t)$ with prior distribution $\mu(t)$ and a fixed window function $w(\tau)$, the optimal success probability $\eta^*(w, \mu, \rho)$ defined in Eq. (15) can be computed using the convex problem

$$ \begin{array}{ll} \text{maximize} & \displaystyle \int dt \operatorname{Tr}[(w * [\mu \cdot \rho])(t)Q(t)] \\ \text{subject to} & Q(t) \ge 0, \hfill (128) \\ & \displaystyle \int dt Q(t) = \mathbb{I}. \end{array} $$

There is no duality gap and the associated dual program is

$$ \begin{array}{ll} \text{minimize} & \operatorname{Tr}[X] \\ \text{subject to} & X \ge 0, \hfill (129) \\ & X \ge (w * [\mu \cdot \rho])(t) \quad \forall t. \end{array} $$

Notably, the definition of the success probability arising from the dual coincides with a continuous version of the “least upper bound” for state discrimination [16] which was also shown to be optimal in this case [61].

Before proving Proposition 1, let us make the following definitions. For a function $A: \mathbb{R} \to P(\mathcal{H})$, $t \mapsto A(t)$, where $P(\mathcal{H})$ is the set of positive semi-definite operators acting on a Hilbert space $\mathcal{H}$, and for a POVM $\{Q(t) : t \in \mathbb{R}\}$, we let

$$ G(A, Q) := \int dt \operatorname{Tr}[Q(t)A(t)], \hfill (130) $$

$$ G_{\max}(A) := \sup_{\substack{Q(t) \ge 0 \\ \int dt Q(t) = \mathbb{I}}} G(A, Q). \hfill (131) $$

From this, we see that the Bayesian success probability is given by

$$ \eta^*(w, \mu, \rho) = G_{\max}(w * (\mu \cdot \rho)). \hfill (132) $$

The statement of Proposition 1 then follows from the following lemma about $G_{\max}$.

**Lemma 29.** For a function $A: \mathbb{R} \to P(\mathcal{H})$, $t \mapsto A(t)$, the function $G_{\max}(A)$ can be computed via a convex problem such that its dual formulation results in

$$ G_{\max}(A) = \inf\{\operatorname{Tr}[Y] : Y \ge 0, Y \ge A(t) \quad \forall t \in \mathbb{R}\} = \inf_{\substack{\sigma \ge 0 \\ \operatorname{Tr}[\sigma]=1}} \sup_{t \in \mathbb{R}} \lambda_{\max}(\sigma^{-\frac{1}{2}}A(t)\sigma^{-\frac{1}{2}}), \hfill (133) $$

where $\lambda_{\max}$ denotes the largest eigenvalue.

**Remark 30.** Note that, because $\lambda_{\max}(X) = \|X\|_{\infty}$ for all $X \in P(\mathcal{H})$, we equivalently have

$$ G_{\max}(A) = \inf_{\substack{\sigma \ge 0 \\ \operatorname{Tr}[\sigma]=1}} \sup_{t \in \mathbb{R}} \|\sigma^{-\frac{1}{2}} A(t) \sigma^{-\frac{1}{2}}\|_{\infty}. \hfill (134) $$

*Proof.* By comparing the definition of $G_{\max}(A)$ in (133) with the primal convex problem in (127), we immediately see that $G_{\max}(A)$ is characterized by a convex problem based on the following identifications:

$$ X := \int dt |t\rangle\langle t| \otimes Q(t), \hfill (135) $$

$$ A := \int dt |t\rangle\langle t| \otimes A(t), \hfill (136) $$

$$ \Phi[X] := \left( \int dt Q(t) - \int dt Q(t') \right), \hfill (137) $$

$$ B := \begin{pmatrix} \mathbb{I} \\ -\mathbb{I} \end{pmatrix}. \hfill (138) $$

Here, $\{|t\rangle\}_{t \in \mathbb{R}}$ refers to the (continuous) orthonormal basis of position-operator eigenstates, satisfying $\langle t|t' \rangle = \delta(t - t')$ for all $t, t' \in \mathbb{R}$, where $\delta(t - t')$ is the Dirac delta function evaluated on $t - t'$.