In order to obtain the dual convex problem, we simply determine the adjoint of the map $\Phi$, as defined by the relation

$$ \mathrm{Tr}[Y\Phi[X]] = \mathrm{Tr}[\Phi^{\dagger}[Y]X]. \qquad (139) $$

Now, because $B$ is block-diagonal, it suffices to let the dual variable be of the form

$$ Y = \begin{pmatrix} Y_1 & \\ & Y_2 \end{pmatrix}, \qquad (140) $$

such that $Y_1 \ge 0$ and $Y_2 \ge 0$. We then find that

$$ \begin{aligned} \mathrm{Tr}[Y\Phi[X]] &= \mathrm{Tr}\left[\begin{pmatrix} Y_1 & \\ & Y_2 \end{pmatrix} \left(\int dt \, Q(t) - \int dt \, Q(t)\right)\right] \quad (141) \\ &= \mathrm{Tr}\left[(Y_1 - Y_2) \left(\int dt \, Q(t)\right)\right] \\ &= \mathrm{Tr}\left[\left(\int dt \, |t\rangle\langle t| \otimes (Y_1 - Y_2)\right) \left(\int dt \, |t\rangle\langle t| \otimes Q(t)\right)\right], \end{aligned} $$

which means that we can identify $\Phi^{\dagger}[Y]$ as

$$ \Phi^{\dagger}[Y] = \int dt \, |t\rangle\langle t| \otimes (Y_1 - Y_2). \qquad (142) $$

The dual convex problem is thus

$$ \begin{array}{ll} \underset{\text{subject to}}{\begin{array}{l} \mathrm{Tr}[Y_1 - Y_2] \\ Y_1 \ge 0, Y_2 \ge 0, \end{array}} & (143) \\ \int dt \, |t\rangle\langle t| \otimes (Y_1 - Y_2) \ge \int dt \, |t\rangle\langle t| \otimes A(t). & \end{array} $$

Now, the final constraint implies that $Y_1 - Y_2 \ge A(t)$ for all $t$. Furthermore, because only $Y_1 - Y_2$ appears in the objective function and in the constraints, and because $A(t) \ge 0$ for all $t$, by a change of variable the dual optimization above simplifies to the optimization problem

$$ \begin{array}{ll} \underset{\text{subject to}}{\begin{array}{l} \mathrm{Tr}[Y] \\ Y \ge 0, \end{array}} & (144) \\ Y \ge A(t) \quad \forall t. & \end{array} $$

Finally, because strong duality holds, we have that the primal and dual convex problems have the same optimal value, which concludes the proof of the first equality in (133).

To prove the second equality in (133), we make another change of variable. For the convex problem in (144), we let $Y = x\sigma$, such that $x \ge 0$, $\sigma \ge 0$ and $\mathrm{Tr}[\sigma] = 1$. Then, $\mathrm{Tr}[Y] = x$, and the convex problem in (144) becomes

$$ \begin{array}{ll} \underset{\text{subject to}}{\begin{array}{l} x \\ x \ge 0, \end{array}} & (145) \\ x\sigma \ge A(t) \quad \forall t, \\ \sigma \ge 0, \mathrm{Tr}[\sigma] = 1. & \end{array} $$

Next, observe that we can restrict the optimization to density operators $\sigma$ that have full rank, such that the inequality $x\sigma \ge A(t)$ is equivalent to $x\mathbb{I} \ge \sigma^{-\frac{1}{2}}A(t)\sigma^{-\frac{1}{2}}$. Furthermore, because $\sigma^{-\frac{1}{2}}A(t)\sigma^{-\frac{1}{2}}$ is positive semi-definite for all $t$, optimizing with respect to $x \ge 0$ is equivalent to optimizing with respect to all $x \in \mathbb{R}$. Therefore, because

$$ \inf\{x : x \in \mathbb{R}, x\mathbb{I} \ge H\} = \lambda_{\max}(H), \qquad (146) $$

where $H$ is an arbitrary Hermitian operator and $\lambda_{\max}(H)$ is the largest eigenvalue of $H$, we find that the convex problem in (145) is equivalent to

$$ \begin{array}{ll} \underset{\text{subject to}}{\begin{array}{l} \mathrm{sup}_{t \in \mathbb{R}} \lambda_{\max}(\sigma^{-\frac{1}{2}}A(t)\sigma^{-\frac{1}{2}}) \\ \sigma \ge 0, \mathrm{Tr}[\sigma] = 1. \end{array}} & (147) \end{array} $$

This concludes the proof of the second equality in (133). □
We can also determine the optimal measurement in the minimax setting using a convex program.

**Proposition 2 (Minimax measurement optimization).** For a given set of states $\rho(t)$ and a fixed window function $w(\tau)$, the optimal minimax success probability $\bar{\eta}^*(w, \rho)$ defined in Definition 1 can be computed using the following convex program:

$$
\begin{array}{ll}
\text{maximize} & \eta \\
\text{subject to} & Q(t) \ge 0, \eta \in [0, 1], \\
& \int dt \, Q(t) = \mathbb{I}, \\
& \mathrm{Tr}[\rho(t)(w * Q)(t)] \ge \eta \quad \forall t.
\end{array}
\qquad (148)
$$

There is no duality gap and the associated dual program is

$$
\begin{array}{ll}
\text{minimize} & \mathrm{Tr}[X] \\
\text{subject to} & X \ge 0, \mu(t) \ge 0, \\
& \int dt \, \mu(t) = 1, \\
& X \ge \mu(t)(w * \rho)(t) \quad \forall t.
\end{array}
\qquad (149)
$$

*Proof.* Comparing the primal problem in (148) with the primal problem in the left-hand side of (127), we can make
the following identifications:

$$
X = \left( \eta \int dt |t\rangle\langle t| \otimes Q(t) \right), \qquad (150)
$$

$$
A = \begin{pmatrix} 1 \\ 0 \end{pmatrix}, \qquad (151)
$$

$$
\Phi[X] = \left( \int dt |t\rangle\langle t| (\eta - \mathrm{Tr}[\rho(t)(w * Q)(t)]) \int dt Q(t) - \int dt Q(t) \right), \quad (152)
$$

$$
B = \begin{pmatrix} 0 & \\ & -\mathbb{I} \end{pmatrix}. \tag{153}
$$

This establishes that the optimal minimax success probability is characterized by a convex problem.

Now, for the dual, because the operator $B$ defined above is block-diagonal, it suffices to let the dual variable be of
the form

$$
Y = \begin{pmatrix} \int dt \, \mu(t) |t\rangle\langle t| & \\ & Y_1 \\ & Y_2 \end{pmatrix}, \qquad (154)
$$

where $\mu(t) \ge 0$ for all $t$, and $Y_1, Y_2 \ge 0$. Then, the adjoint of the map $\Phi$ defined above is given by the relation

$$
\mathrm{Tr}[Y\Phi[X]] = \mathrm{Tr}[\Phi^{\dagger}[Y]X]. \qquad (155)
$$

In particular,

$$
\begin{align}
\mathrm{Tr}[Y\Phi[X]] &= \int dt \, \mu(t) (\eta - \mathrm{Tr}[\rho(t)(w*Q)(t)]) + \int dt \, \mathrm{Tr}[(Y_1 - Y_2)Q(t)] \tag{156} \\
&= \eta \int dt \, \mu(t) - \int dt \, \mu(t) \mathrm{Tr}[\rho(t)(w*Q)(t)] + \int dt \, \mathrm{Tr}[(Y_1 - Y_2)Q(t)]. \nonumber
\end{align}
$$

Now,

$$
\begin{align}
& \int dt \, \mu(t) \operatorname{Tr}[\rho(t)(w * Q)(t)] \tag{157} \\
&= \int dt \, dt' \operatorname{Tr}[\mu(t)\rho(t)w(t - t')Q(t)] \nonumber \\
&= \int dt' \operatorname{Tr}\left[(\int dt \, \mu(t)\rho(t)w(t - t')) Q(t')\right] \nonumber \\
&= \int dt' \operatorname{Tr}[(w * (\mu \cdot \rho))(t')Q(t')], \nonumber
\end{align}
$$
where to obtain the last line we have used the symmetry of the window function, i.e., $w(t-t') = w(t'-t)$. Therefore,

$$ \mathrm{Tr}[Y\Phi[X]] = \eta \int dt \, \mu(t) + \int dt \, \mathrm{Tr}[(Y_1 - Y_2 - (w * (\mu \cdot \rho))(t))Q(t)], \quad (158) $$

which implies that the adjoint of $\Phi$ is given by

$$ \Phi^{\dagger}[Y] = \left( \int dt \, \mu(t) \int dt \, |t\rangle\langle t| \otimes (Y_1 - Y_2 - (w * (\mu \cdot \rho))(t)) \right). \quad (159) $$

The dual convex problem is therefore

$$
\begin{array}{ll}
\text{minimize} & \mathrm{Tr}[Y_1 - Y_2] \\
\text{subject to} & Y_1 \ge 0, Y_2 \ge 0, \mu(t) \ge 0 \quad \forall t, \\
& \int dt \, \mu(t) \ge 1, \\
& \int dt \, |t\rangle\langle t| \otimes (Y_1 - Y_2 - (w * (\mu \cdot \rho))(t)) \ge 0.
\end{array}
\quad (160)
$$

The final constraint is equivalent to $Y_1 - Y_2 \ge (w * (\mu \cdot \rho))(t)$ for all $t$. Furthermore, because only $Y_1 - Y_2$ appears in the objective function and in the constraints, and because $(w * (\mu \cdot \rho))(t) \ge 0$ for all $t$, the convex problem above simplifies to the following:

$$
\begin{array}{ll}
\text{minimize} & \mathrm{Tr}[Y] \\
\text{subject to} & Y \ge 0, \mu(t) \ge 0 \quad \forall t, \\
& \int dt \, \mu(t) \ge 1, \\
& Y \ge (w * (\mu \cdot \rho))(t) \quad \forall t.
\end{array}
\quad (161)
$$

Finally, let us apply the complementary slackness condition [17] $\Phi^{\dagger}[Y]X = AX$. Based on the definitions above, this implies that $\eta \int dt \, \mu(t) = \eta$, i.e., $\int dt \, \mu(t) = 1$. Therefore, we obtain

$$
\begin{array}{ll}
\text{minimize} & \mathrm{Tr}[Y] \\
\text{subject to} & Y \ge 0, \mu(t) \ge 0 \quad \forall t, \\
& \int dt \, \mu(t) = 1, \\
& Y \ge (w * (\mu \cdot \rho))(t) \quad \forall t,
\end{array}
\quad (162)
$$

as claimed. It is straightforward to verify strong duality, so that the primal and dual programs have the same optimal value. $\square$

## B. Probe optimization

In certain applications, especially considering real experiments where capabilities can be limited or pre-existing experiments should be used, the optimization of a probe state for fixed measurement $Q(t)$ and encoding channel $N(t)$ needs to be considered. Note that fixing a measurement corresponds to fixing both the quantum part and the classical post-processing. In this case, the optimization takes a particularly simple form. Here, $\|\cdot\|_{\infty}$ denotes the infinity or spectral norm.

**Proposition 3 (Probe state optimization).** For a given set of encoding channels $N(t)$ with prior probabilities $\mu(t)$, a fixed measurement $Q(t)$ and a fixed window function $w(\tau)$, the optimal success probability optimized over all probe states is given by

$$ \eta^*(w, \mu, \mathcal{N}, Q) = \left\| \int d\mu(t) \mathcal{N}^{\dagger}(t) [(w * Q)(t)] \right\|_{\infty} \quad (163) $$

and is achieved for the pure eigenstate of the operator $\int d\mu(t) \mathcal{N}^{\dagger}(t) [(w * Q)(t)]$ corresponding to the largest eigenvalue. Similarly,

$$ \bar{\eta}^*(w, \mathcal{N}, Q) = \min_t \|\mathcal{N}^{\dagger}(t) [(w * Q)(t)]\|_{\infty}, \quad (164) $$

which is achieved for the pure eigenstate of the operator $\min_t \mathcal{N}^{\dagger}(t) [(w * Q)(t)]$ corresponding to the largest eigenvalue.
<figure><img src="image_12.png" /><figcaption>FIG. 10. Depiction of an adaptive procedure for estimating the parameter $t$ encoded in a quantum channel $\mathcal{N}(t)$. The number of uses of the channel here is $n = 4$.</figcaption></figure>

*Proof.* Writing out the objective of the optimization yields

$$ \begin{aligned} \eta(w, \mu, \mathcal{N}(\cdot)[\rho_0], Q) &= \int d\mu(t) \operatorname{Tr}[\mathcal{N}(t)[\rho_0](w * Q)(t)] \tag{165} \\ &= \operatorname{Tr}\left[\rho_0 \int d\mu(t) \mathcal{N}^{\dagger}(t)[(w * Q)(t)]\right] \end{aligned} $$

which is clearly maximized over quantum states $\rho_0$ for the largest eigenstate of $\int d\mu(t) \mathcal{N}^{\dagger}(t)[(w * Q)(t)]$, as the latter is a positive semi-definite operator by construction. This proves the statement for the Bayesian case. The minimax case follows straightforwardly by noting that taking the infimum over priors will yield the minimum. $\square$

From the above proposition, we learn that the optimal probe states can always be assumed to be pure states, mixed states can only be admissible if the operators in Eqs. (163) and (164) have a degenerate subspace corresponding to the largest eigenvalue.

### C. Optimization with respect to strategies with definite causal order

Typically, metrological problems are defined by a parametrized physical process modeled as a quantum channel $\mathcal{N}(t)$ and an optimal combination of probe state and measurement needs to be found to best extract the parameter $t$. This necessitates a joint optimization over both variables. Applying such an optimization naively, i.e., by optimizing over both variables in the expression

$$ \eta^*(w, \mu, \mathcal{N}) = \int d\mu(t) \operatorname{Tr}[\mathcal{N}(t)[\rho^0](w * Q)(t)], \qquad (166) $$

does not yield a semi-definite program, as it is quadratic in the variables $\rho^0$ and $Q(t)$. Another possible alternative would be to exploit the result of Proposition 3 which gives the optimal probe for any measurement, and optimize over the measurement, i.e.,

$$ \eta^*(w, \mu, \mathcal{N}) = \sup \left\{ \left\| \int d\mu(t) \mathcal{N}^{\dagger}(t) [(w * Q)(t)] \right\|_{\infty} \middle| Q(t) \ge 0, \int dt Q(t) = 1 \right\}. \qquad (167) $$

This, however, corresponds to maximizing a convex function, and hence is not a convex optimization problem.

The above arguments might suggest that performing a joint optimization is impossible; however, we can circumvent these obstacles by a change of perspective. This is because the repeated use of a quantum channel, possibly in an adaptive way as shown in Fig. 10, can be described by a quantum comb [20], also known as a quantum strategy [21]. In the following, we exploit the fact that the set of quantum combs is convex and formulate a convex problem for the joint optimization of probe state and measurement.

To see how this works, before describing the general case, let us consider the example described above, with an input state $\rho^0$ and a measurement $t \mapsto Q(t)$, both of which we wish to optimize jointly. This scenario corresponds to the adaptive strategy depicted in Fig. 10 with $n = 1$. The probability of the outcome $t'$ of the measurement, when the channel is $\mathcal{N}(t)$, is given by

$$ \operatorname{Tr}[Q_{RB}(t')\mathcal{N}_{A \to B}(t)[\rho_{RA}^0]], \qquad (168) $$

where $A$ and $B$ are the input and output systems, respectively, of the channel, and $R$ is a memory system of arbitrary dimension. Let us write the output state $\mathcal{N}_{A \to B}(t)[\rho_{RA}^0]$ in terms of the Choi representation $C_{AB}^{\mathcal{N}(t)}$ of $\mathcal{N}(t)$ as follows [17]:

$$ \mathcal{N}_{A \to B}(t)[\rho_{RA}^0] = \operatorname{Tr}_A[(\rho_{RA}^{T_A} \otimes \mathbb{I}_B)(\mathbb{I}_R \otimes C_{AB}^{\mathcal{N}(t)})]. \qquad (169) $$
<figure><img src="image_13.png" /><figcaption>FIG. 11. A general quantum comb with $n = 4$ elements. The input and output systems are $A_j$ and $B_j$, respectively, and the memory systems are $R_j$.</figcaption></figure>

Therefore, the probability in (168) can be written as $\mathrm{Tr}[P_{AB}^T(t')C_{AB}^{\mathcal{N}(t)}] \equiv P_{AB}(t') \star C_{AB}^{\mathcal{N}(t)}$, where the “★” refers to the link product [20] and

$$P_{AB}(t') := \mathrm{Tr}_R[(\rho_{RA}^0 \otimes \mathbb{I}_B)(\mathbb{I}_B \otimes Q_{RA}^{T_A}(t'))]. \quad (170)$$

Now, because $t \mapsto Q(t)$ is a POVM, we find that

$$\int dt P_{AB}(t) = \mathrm{Tr}_R[\rho_{RA}^0 \otimes \mathbb{I}_B]. \quad (171)$$

In other words, for every state-measurement pair $(\rho_{RA}^0, t \mapsto Q(t))$, we can construct a positive semi-definite operator $t \mapsto P_{AB}(t)$ such that $\int dt P_{AB}(t) = \sigma_A \otimes \mathbb{I}_B$ for some quantum state $\sigma_A$. The converse is also true [21] (Theorem 6), which implies that the optimal success probability, optimized with respect to both input probe state and measurement, can be obtained as the solution to the following convex problem (in the Bayesian setting):

$$
\begin{array}{ll}
\text{maximize} & \int dt \, \mu(t) \, \mathrm{Tr}[(w * P_{AB})(t) C_{AB}^{\mathcal{N}(t)}] \\
\text{subject to} & P_{AB}(t) \ge 0 \quad \forall t, \\
& \int dt \, P_{AB}(t) = \sigma_A \otimes \mathbb{I}_B, \\
& \sigma_A \ge 0, \mathrm{Tr}[\sigma_A] = 1,
\end{array}
\quad (172)
$$

where $t \mapsto \mu(t)$ is the prior probability density function. In the minimax setting, the optimal success probability can be obtained as the solution to the following convex problem:

$$
\begin{array}{ll}
\text{maximize} & \eta \\
\text{subject to} & \mathrm{Tr}[(w * P_{AB})(t) C_{AB}^{\mathcal{N}(t)}] \ge \eta \quad \forall t, \\
& \eta \in [0, 1], \\
& P_{AB}(t) \ge 0 \quad \forall t, \\
& \int dt P_{AB}(t) = \sigma_A \otimes \mathbb{I}_B, \\
& \sigma_A \ge 0, \mathrm{Tr}[\sigma_A] = 1.
\end{array}
\quad (173)
$$

We provide a formal proof of these results, in the general context of multiple adaptive uses of the channel $t \mapsto \mathcal{N}(t)$, in Propositions 4 and 5 below.

A general quantum comb of length $n = 4$ is shown in Fig. 11. The comb is simply a concatenation of quantum channels $\mathcal{E}^j$, with input systems $A_j$, output systems $B_j$, and memory systems $R_j$. We refer to the comb using the notation $\mathcal{E}^{[n]}$. It can be shown that the Choi representation $C_{A_1^{[n]} B_1^{[n]}}^{\mathcal{E}^{[n]}}$ of the comb satisfies the following constraints:

$$\mathrm{Tr}_{B_n} \left[ C_{A_1^n B_1^n}^{\mathcal{E}^{[n]}} \right] = C_{A_1^{n-1} B_1^{n-1}}^{\mathcal{E}^{[n-1]}} \otimes \mathbb{I}_{A_n}, \quad (174)$$

$$\mathrm{Tr}_{B_k} \left[ C_{A_k^n B_1^n}^{\mathcal{E}^{[k]}} \right] = C_{A_1^{k-1} B_1^{k-1}}^{\mathcal{E}^{[k-1]}} \otimes \mathbb{I}_{A_k} \quad \forall k \in \{2, 3, \dots, r-1\}, \quad (175)$$

$$\mathrm{Tr}_{B_1} \left[ C_{A_1 B_1}^{\mathcal{E}^{[1]}} \right] = \mathbb{I}_{A_1}. \quad (176)$$

These constraints tell us that by iteratively tracing out the output systems we obtain Choi representations of the same comb but with one fewer round each time. Conversely, every set $\{C_{A_1^{(k)} B_1^{(k)}}\}_{k=1}^n$ of positive semi-definite operators satisfying the constraints in (174)–(176) gives us Choi representations corresponding to a quantum comb with length $n$; see Ref. [21] (Theorem 6). Note that these operators do not give us the Choi representations of the channels $\mathcal{E}^j$
themselves, only the Choi representations of the combs obtained by concatenating the channels in the manner shown in Fig. 11.

Following Ref. [21], for every $n \in \{1, 2, \dots\}$, we define the set $S_n(A_1^n, B_1^n)$ as

$$ S_n(A_1^n, B_1^n) := \left\{ C_{A_1^n B_1^n}^{(n)} : C_{A_1^n B_1^n}^{(n)} \ge 0, \mathrm{Tr}_{B_k}[C_{A_1^k B_1^k}^{(k)}] = C_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_k}, C_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \ge 0 \ \forall k \in \{2, 3, \dots, n\}, \mathrm{Tr}_{B_1}[C_{A_1 B_1}^{(1)}] = \mathbb{I}_{A_1}, C_{A_1 B_1}^{(1)} \ge 0 \right\}. \quad (177) $$

In other words, $S_n(A_1^n, B_1^n)$ is the set of all Choi representations of length-$n$ quantum combs with input systems $A_1, A_2, \dots, A_n$ and output systems $B_1, B_2, \dots, B_n$. Similarly, for the set of combs consisting of quantum state preparation at the beginning, known as co-strategies (see the red comb in Fig. 10), we let

$$ \begin{aligned} \bar{S}_n(A_1^{n-1}, B_1^n) := & \left\{ C_{A_1^{n-1} B_1^n}^{(n)} : C_{A_1^{n-1} B_1^n}^{(n)} \ge 0, \mathrm{Tr}_{B_k}[C_{A_1^{k-1} B_1^k}^{(k)}] = C_{A_1^{k-2} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_{k-1}}, \right. \\ & \left. C_{A_1^{k-2} B_1^{k-1}}^{(k-1)} \ge 0 \ \forall k \in \{3, 4, \dots, n\}, \mathrm{Tr}_{B_2}[C_{A_1 B_1^2}^{(2)}] = C_{B_1}^{(1)} \otimes \mathbb{I}_{A_1}, C_{B_1}^{(1)} \ge 0, \mathrm{Tr}_{B_1}[C_{B_1}^{(1)}] = 1 \right\}. \end{aligned} \quad (178) $$

Now, returning to the parameter estimation problem, note that in Fig. 10, we have a concatenation of two combs: One corresponding to the strategy itself (in red), and the other corresponding to the channels $\mathcal{N}(t)$ containing the parameter to be estimated. The Choi representation of the latter is simply a tensor product

$$ C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}} = \bigotimes_{j=1}^{n} C_{A_j B_j}^{\mathcal{N}(t)}, \quad (179) $$

because the channel uses are independent of each other. Using this, we can obtain the optimal success probability as the following primal-dual pair of convex problems, concretely semi-infinite problems, in both the Bayesian and minimax settings. (We refer to Ref. [136] for a similar result.)

**Proposition 4** (Bayesian optimization of adaptive causal strategies). Let $C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}}$ be the Choi representation of the comb $\mathcal{N}(t)^{[n]}$ corresponding to $n$ uses of the paramterized quantum channel $t \mapsto \mathcal{N}(t)$, as shown in Fig. 10. Also, let $t \mapsto \mu(t)$ be a prior probability density function. Then, the optimal Bayesian strategy for estimating the parameter $t$ can be determined using the convex problem

$$ \begin{array}{ll} \text{maximize} & \displaystyle \int dt \, \mu(t) \operatorname{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}})(t)] \\ \text{subject to} & P_{A_1^n B_1^n}(t) \ge 0 \ \forall t, \\ & \displaystyle \int dt \, P_{A_1^n B_1^n}(t) = C_{A_1^n B_1^n}^{(n)} \otimes \mathbb{I}_{B_n}, \\ & C_{A_1^n B_1^n}^{(n)} \in \bar{S}_n(B_1^{n-1}, A_1^n), \end{array} \quad (180) $$

where the variable $C_{A_1^n B_1^n}^{(n)}$ represents a length-$n$ co-strategy quantum comb, excluding the measurement, (see the red comb in Fig. 10). The variables $P_{A_1^n B_1^n}(t)$ correspond to the measurement.

The convex program dual to the one above is

$$ \begin{array}{ll} \text{minimize} & \lambda \\ \text{subject to} & \lambda \ge 0, \\ & \lambda Y_{A_1^n B_1^n}^{(n)} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}})(t) \ \forall t, \\ & Y_{A_1^n B_1^n}^{(n)} \in S_n(A_1^n, B_1^n), \end{array} \quad (181) $$

where the optimization is with respect to $\lambda \ge 0$ and length-$n$ quantum combs represented by the operator $Y_{A_1^n B_1^n}^{(n)}$. Furthermore, strong duality holds, so that the primal and dual problems have the same optimal value.
*Proof.* Starting with the primal problem in (180), we can cast it into the standard form in (127) as

$$X = \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right) \oplus \left( \sum_{k=1}^n |k\rangle\langle k| \otimes C_{A_1^k B_1^{k-1}}^{(k)} \right), \quad (182)$$

$$A = \left( \int dt |t\rangle\langle t| \otimes \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}[n]})(t) \right) \oplus \left( \sum_{k=1}^n |k\rangle\langle k| \otimes 0 \right), \quad (183)$$

$$
\begin{align}
\Phi[X] &= |0,0\rangle\langle0,0| \otimes \left( \int dt P_{A_1^n B_1^n}(t) - C_{A_1^n B_1^{n-1}}^{(n)} \otimes \mathbb{I}_{B_n} \right) \nonumber \\
&\quad + |0,1\rangle\langle0,1| \otimes \left( - \int dt P_{A_1^n B_1^n}(t) + C_{A_1^n B_1^{n-1}}^{(n)} \otimes \mathbb{I}_{B_n} \right) \nonumber \\
&\quad + |1,0\rangle\langle1,0| \otimes \mathrm{Tr}_{A_1}[C_{A_1}^{(1)}] + |1,1\rangle\langle1,1| \otimes (-\mathrm{Tr}_{A_1}[C_{A_1}^{(1)}]) \nonumber \\
&\quad + \sum_{k=2}^n |k,0\rangle\langle k,0| \otimes \left( \mathrm{Tr}_{A_k}[C_{A_1^k B_1^{k-1}}^{(k)}] - C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}} \right) \nonumber \\
&\quad + \sum_{k=2}^n |k,1\rangle\langle k,1| \otimes \left( -\mathrm{Tr}_{A_k}[C_{A_1^k B_1^{k-1}}^{(k)}] + C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}} \right), \nonumber \\
B &= |0,0\rangle\langle0,0| \otimes 0 + |0,1\rangle\langle0,1| \otimes 0 + |1,0\rangle\langle1,0| \otimes 1 + |1,1\rangle\langle1,1| \otimes (-1) \tag{184} \\
&\quad + \sum_{k=2}^n |k,0\rangle\langle k,0| \otimes 0 + \sum_{k=2}^n |k,1\rangle\langle k,1| \otimes 0. \nonumber
\end{align}
$$

Now, without loss of generality, we can let the dual variable $Y$ have the block-diagonal form

$$Y = |0,0\rangle\langle0,0| \otimes Y_{A_1^n B_1^n}^{(1)} + |0,1\rangle\langle0,1| \otimes Y_{A_1^n B_1^n}^{(2)} + |1,0\rangle\langle1,0| \otimes \alpha + |1,1\rangle\langle1,1| \otimes \beta \\ + \sum_{k=2}^n |k,0\rangle\langle k,0| \otimes \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} + \sum_{k=2}^n |k,1\rangle\langle k,1| \otimes \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)} \quad (185)$$

From this, we obtain

$$
\begin{align}
\mathrm{Tr}[Y\Phi[X]] &= \mathrm{Tr}\left[\left(\int dt P_{A_1^n B_1^n}(t)\right) \left(Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)}\right)\right] \tag{186} \\
&\quad + \mathrm{Tr}\left[(C_{A_1^n B_1^{n-1}}^{(n)} \otimes \mathbb{I}_{B_n}) (-Y_{A_1^n B_1^n}^{(1)} + Y_{A_1^n B_1^n}^{(2)})\right] \nonumber \\
&\quad + \mathrm{Tr}_{A_1}[C_{A_1}^{(1)}](\alpha - \beta) \nonumber \\
&\quad + \sum_{k=2}^n \mathrm{Tr}\left[\mathrm{Tr}_{A_k}[C_{A_1^k B_1^{k-1}}^{(k)}] (\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)})\right] \nonumber \\
&\quad + \sum_{k=2}^n \mathrm{Tr}\left[(C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}}) (-\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} + \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)})\right] \nonumber \\
&= \mathrm{Tr}\left[\left(\int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t)\right) \left(\int dt |t\rangle\langle t| \otimes (Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)})\right)\right] \nonumber \\
&\quad + \mathrm{Tr}\left[C_{A_1}^{(1)}((\alpha - \beta)\mathbb{I}_{A_1} + \mathrm{Tr}_{B_1}[-\tilde{C}_{A_1 B_1}^{(2,0)} + \tilde{C}_{A_1 B_1}^{(2,1)}])\right] \nonumber \\
&\quad + \sum_{k=2}^{n-1} \mathrm{Tr}\left[C_{A_1^k B_1^{k-1}}^{(k)}\left(\left(\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}\right) \otimes \mathbb{I}_{A_k} + \mathrm{Tr}_{B_k}[-\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} + \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}]\right)\right] \nonumber \\
&\quad + \mathrm{Tr}\left[C_{A_1^{n-1} B_1^{n-1}}^{(n,0)}\left(\left(\tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,1)}\right) \otimes \mathbb{I}_{A_n} + \mathrm{Tr}_{B_n}[-Y_{A_1^n B_1^n}^{(1)} + Y_{A_1^n B_1^n}^{(2)}]\right)\right]. \nonumber
\end{align}
$$
This implies that

$$
\begin{equation}
\begin{split}
\Phi^{\dagger}[Y] = \int dt |t\rangle\langle t| \otimes & (Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)}) \\
& \oplus ((\tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,1)}) \otimes \mathbb{I}_{A_n} + \mathrm{Tr}_{B_n} [-Y_{A_1^n B_1^n}^{(1)} + Y_{A_1^n B_1^n}^{(2)}]) \\
& \oplus \sum_{k=2}^{n-1} |k\rangle\langle k| \otimes ((\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}) \otimes \mathbb{I}_{A_k} + \mathrm{Tr}_{B_k} [-\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} + \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}]) \\
& \oplus ((\alpha - \beta)\mathbb{I}_{A_1} + \mathrm{Tr}_{B_1} [-\tilde{C}_{A_1 B_1}^{(2,0)} + \tilde{C}_{A_1 B_1}^{(2,1)}]).
\end{split}
\tag{187}
\end{equation}
$$

The dual problem is therefore

minimize $\alpha - \beta$

$$
\begin{align}
\text{subject to} \quad & \alpha \ge 0, \beta \ge 0, Y_{A_1^n B_1^n}^{(1)} \ge 0, Y_{A_1^n B_1^n}^{(2)} \ge 0, \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} \ge 0, \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)} \ge 0, k \in \{1, 2, \dots, n\}, \nonumber \\
& \mathrm{Tr}_{B_1} [\tilde{C}_{A_1 B_1}^{(2,0)} - \tilde{C}_{A_1 B_1}^{(2,1)}] \le (\alpha - \beta) \mathbb{I}_{A_1}, \nonumber \\
& \mathrm{Tr}_{B_k} [\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} - \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}] \le (\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}) \otimes \mathbb{I}_{A_k}, k \in \{2, 3, \dots, n-1\}, \tag{188} \\
& \mathrm{Tr}_{B_n} [Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)}] \le (\tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,1)}) \otimes \mathbb{I}_{A_n}, \nonumber \\
& Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t. \nonumber
\end{align}
$$

It is straightforward to verify that strong duality holds, which means that the primal and dual problems have the same optimal value.

Let us now make several simplifications to the dual optimization problem. We start with the following change of variables:

$$
\lambda \equiv \alpha - \beta, \tag{189}
$$

$$
Y_{A_1^k B_1^k}^{(k)} \equiv \tilde{C}_{A_1^k B_1^k}^{(k+1,0)} - \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}, \quad k \in \{1, 2, \dots, n-1\}, \qquad (190)
$$

$$
Y_{A_1^n B_1^n}^{(n)} \equiv Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)}. \tag{191}
$$

Then, because the operator $\mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t)$ is positive semi-definite for all $t$, we have that $Y_{A_1^n B_1^n}^{(n)}$ is positive semi-definite. Due to the second-last constraint in the above convex problem, this implies that $Y_{A_1^{n-1} B_1^{n-1}}^{(n-1)} \ge 0$, which in turn, from the third constraint in the convex problem above, implies that $Y_{A_1^k B_1^k}^{(k)} \ge 0$ for all $k \in \{1, 2, \dots, n-2\}$, such that finally $\lambda \ge 0$ is also implied. Therefore, the convex problem above simplifies to

$$
\text{minimize } \lambda
$$

$$
\begin{align}
\text{subject to} \quad & \lambda \ge 0, Y_{A_1^k B_1^k}^{(k)} \ge 0 \quad \forall k \in \{1, 2, \dots, n\}, \nonumber \\
& \mathrm{Tr}_{B_1}[Y_{A_1 B_1}^{(1)}] \le \lambda \mathbb{I}_{A_1}, \tag{192} \\
& \mathrm{Tr}_{B_k}[Y_{A_1^k B_1^k}^{(k)}] \le Y_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_k} \quad \forall k \in \{2, 3, \dots, n\}, \nonumber \\
& Y_{A_1^n B_1^n}^{(n)} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t. \nonumber
\end{align}
$$

Let us now argue that the inequality constraints $\mathrm{Tr}_{B_1}[Y_{A_1 B_1}^{(1)}] \le \lambda \mathbb{I}_{A_1}$ and $\mathrm{Tr}_{B_k}[Y_{A_1^k B_1^k}^{(k)}] \le Y_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_k}$, $k \in \{2, 3, \dots, n\}$, for every feasible set of variables, can be made into equality constraints, without changing the value $\lambda$ of the objective function. First, by adding an appropriate positive multiple of the identity to $Y_{A_1 B_1}^{(1)}$, we can obtain an operator $\tilde{Y}_{A_1 B_1}^{(1)} \ge 0$ such that $\tilde{Y}_{A_1 B_1}^{(1)} \ge Y_{A_1 B_1}^{(1)}$ and $\mathrm{Tr}_{B_1}[\tilde{Y}_{A_1 B_1}^{(1)}] = \lambda \mathbb{I}_{A_1}$. Now, because $\tilde{P} \ge P \Rightarrow \tilde{P} \otimes \mathbb{I} \ge P \otimes \mathbb{I}$ for all $P \ge 0$, we have that

$$
\tilde{Y}_{A_1 B_1}^{(1)} \otimes \mathbb{I}_{A_2} \geq Y_{A_1 B_1}^{(1)} \otimes \mathbb{I}_{A_1} \geq \mathrm{Tr}_{B_2}[Y_{A_1^2 B_1^2}^{(2)}]. \quad (193)
$$

This implies that there exists a $Q_{A_1^n B_1^n}^{(2)} \ge 0$ such that $\tilde{Y}_{A_1 B_1}^{(1)} \otimes \mathbb{I}_{A_2} = \mathrm{Tr}_{B_2}[Y_{A_1^2 B_1^2}^{(2)}] + Q_{A_1^n B_1^n}^{(2)}$. Letting

$$
R_{A_1^2 B_1^2}^{(2)} := Q_{A_1^2 B_1}^{(2)} \otimes \frac{\mathbb{I}_{B_2}}{d_{B_2}} \qquad (194)
$$
and $\tilde{Y}_{A_1^2 B_1^2}^{(2)} := Y_{A_1^2 B_1^2}^{(2)} + R_{A_1^2 B_1^2}^{(2)}$, we have that $\tilde{Y}_{A_1^2 B_1^2}^{(2)} \ge Y_{A_1^2 B_1^2}^{(2)}$ and $\mathrm{Tr}_{B_2}[\tilde{Y}_{A_1^2 B_1^2}^{(2)}] = \tilde{Y}_{A_1 B_1}^{(1)} \otimes \mathbb{I}_{A_1}$. We can proceed analogously for all $k \in \{3, 4, \dots, n\}$, defining new variables $\tilde{Y}_{A_1^k B_1^k}^{(k)}$ such that $\tilde{Y}_{A_1^k B_1^k}^{(k)} \ge Y_{A_1^k B_1^k}^{(k)}$ and $\mathrm{Tr}_{B_k}[\tilde{Y}_{A_1^k B_1^k}^{(k)}] = \tilde{Y}_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_k}$. In particular, for $k=n$, we obtain the constraint

$$ \tilde{Y}_{A_1^n B_1^n}^{(n)} \ge Y_{A_1^n B_1^n}^{(n)} \ge (w * C_{A_1^n B_1^n}^{\mathcal{N}[n]})(t) \quad (195) $$

for all $t$. With this change of variables, the value $\lambda$ of the objective function does not change. Therefore, we have shown that the convex problem above is equivalent to

$$
\begin{array}{ll}
\text{maximize} & \lambda \\
\text{subject to} & \lambda \ge 0, Y_{A_1^n B_1^n}^{(k)} \ge 0 \quad \forall k \in \{1, 2, \dots, n\}, \\
& \mathrm{Tr}_{B_1}[Y_{A_1 B_1}^{(1)}] = \lambda \mathbb{I}_{A_1}, \qquad (196) \\
& \mathrm{Tr}_{B_k}[Y_{A_1^n B_1^n}^{(k)}] = Y_{A_1^{k-1} B_1^{k-1}}^{(k-1)} \otimes \mathbb{I}_{A_k} \quad \forall k \in \{2, 3, \dots, n\}, \\
& Y_{A_1^n B_1^n}^{(n)} \ge \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}[n]})(t) \quad \forall t.
\end{array}
$$

Finally, let us make one more change of variables. Let $\tilde{Y}_{A_1^n B_1^n}^{(k)} = \frac{1}{\lambda} Y_{A_1^n B_1^n}^{(k)}$ for all $k \in \{1, 2, \dots, n\}$. Then, we find that $\mathrm{Tr}_{B_1}[\tilde{Y}_{A_1 B_1}^{(1)}] = \mathbb{I}_{A_1}$, $\mathrm{Tr}_{B_k}[\tilde{Y}_{A_1^n B_1^n}^{(k)}] = \tilde{Y}_{A_1^n B_1^n}^{(k-1)} \otimes \mathbb{I}_{A_k}$ for all $k \in \{2, 3, \dots, n\}$, and $\lambda Y_{A_1^n B_1^n}^{(n)} \ge \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}[n]})(t)$ for all $t$. To conclude, we have that $Y_{A_1^n B_1^n}^{(n)} \in S_n(A_1^n, B_1^n)$, based on the definition in (177), which gives us the desired dual problem. $\square$

**Proposition 5** (Minimax optimization of adaptive causal strategies). Let $C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}}$ be the Choi representation of the comb $\mathcal{N}(t)^{[n]}$ corresponding to $n$ uses of the paramterized quantum channel $t \mapsto \mathcal{N}(t)$, as shown in Fig. 10. Then, the optimal minimax strategy for estimating the parameter $t$ can be determined using the convex problem

$$
\begin{array}{ll}
\text{maximize} & \eta \\
\text{subject to} & \mathrm{Tr}[C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}} (w * P_{A_1^n B_1^n})(t)] \ge \eta \quad \forall t, \\
& \eta \ge 0, \\
& P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \\
& \int dt P_{A_1^n B_1^n}(t) = C_{A_1^n B_1^{n-1}}^{(n)} \otimes \mathbb{I}_{B_n}, \\
& C_{A_1^n B_1^{n-1}}^{(n)} \in \bar{S}_n(B_1^{n-1}, A_1^n),
\end{array}
\quad (197)
$$

where the variable $C_{A_1^n B_1^{n-1}}^{(n)}$ represents a length-n quantum comb, excluding the measurement, with a quantum state preparation at the beginning (see the red comb in Fig. 10). The variables $P_{A_1^n B_1^n}(t)$ correspond to the measurement. The convex program dual to the one above is

$$
\begin{array}{ll}
\text{minimize} & \lambda \\
\text{subject to} & \lambda \ge 0, \\
& \lambda Y_{A_1^n B_1^n}^{(n)} \ge \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}})(t) \quad \forall t, \qquad (198) \\
& Y_{A_1^n B_1^n}^{(n)} \in S_n(A_1^n, B_1^n), \\
& \mu(t) \ge 0 \quad \forall t, \quad \int dt \, \mu(t) = 1,
\end{array}
$$

where the optimization is with respect to $\lambda \ge 0$, probability density functions $\mu(t)$, and length-n quantum combs represented by the operator $Y_{A_1^n B_1^n}^{(n)}$. Furthermore, strong duality holds, so that the primal and dual programs have the same optimal value.

The convex problems in the above proposition are the continuous analogues of the semi-definite problems for multiple channel discrimination [20, 137, 138]. Notably, as with Proposition 2, the optimal minimax success probability can be obtained via optimization of the Bayesian success probability with respect to all possible priors.
*Proof.* The proof is analogous to the proof of Proposition 4, so we omit some of the details. First, upon inspection of the primal problem in (197), we find that it is of the standard form of the primal problem in (127), with

$$X = \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right) \oplus \left( \sum_{k=1}^n |k\rangle\langle k| \otimes C_{A_1^k B_1^{k-1}}^{(k)} \right) \oplus \eta, \quad (199)$$

$$A = \left( \int dt |t\rangle\langle t| \otimes 0 \right) \oplus \left( \sum_{k=1}^{n} |k\rangle\langle k| \otimes 0 \right) \oplus 0,$$

$$\begin{aligned} \Phi[X] = & \left( \int dt |t\rangle\langle t| \left( \eta - \operatorname{Tr} \left[ P_{A_1^n B_1^n}(t) (w * C_{A_1^n B_1^n}^{[n]})(t) \right] \right) \right) \\ & \oplus |0,0\rangle\langle 0,0| \otimes \left( \int dt P_{A_1^n B_1^n}(t) - C_{A_1^n B_1^{n-1}} \otimes \mathbb{I}_{B_n} \right) \\ & + |1,0\rangle\langle 1,0| \otimes \operatorname{Tr}_{A_1} [C_{A_1}^{(1)}] + |1,1\rangle\langle 1,1| \otimes (-\operatorname{Tr}_{A_1} [C_{A_1}^{(1)}]) \\ & + \sum_{k=2}^{n} |k,0\rangle\langle k,0| \otimes \left( \operatorname{Tr}_{A_k} [C_{A_1^k B_1^{k-1}}^{(k)}] - C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}} \right) \end{aligned} \quad (200)$$

$$+ \sum_{k=2}^{n} |k, 1\rangle\langle k, 1| \otimes \left( -\operatorname{Tr}_{A_k} [C_{A_1^k B_1^{k-1}}^{(k)}] + C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}} \right),$$

$$\begin{aligned} B = & 0 \oplus |0,0\rangle\langle 0,0| \otimes 0 + |0,1\rangle\langle 0,1| \otimes 0 + |1,0\rangle\langle 1,0| \otimes 1 + |1,1\rangle\langle 1,1| \otimes (-1) \\ & + \sum_{k=2}^{n} |k,0\rangle\langle k,0| \otimes 0 + \sum_{k=2}^{n} |k,1\rangle\langle k,1| \otimes 0. \end{aligned} \quad (201)$$

Now, without loss of generality, we can let the dual variable $Y$ have the following block-diagonal form:

$$Y = \left( \int dt \mu(t) |t\rangle\langle t| \right) \oplus |0,0\rangle\langle 0,0| \otimes Y_{A_1^n B_1^n}^{(1)} + |1,0\rangle\langle 0,1| \otimes Y_{A_1^n B_1^n}^{(2)} + |1,0\rangle\langle 1,0| \otimes \alpha + |1,1\rangle\langle 1,1| \otimes \beta \\ + \sum_{k=2}^{n} |k,0\rangle\langle k,0| \otimes \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} + \sum_{k=2}^{n} |k,1\rangle\langle k,1| \otimes \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}. \quad (202)$$

This implies that

$$\operatorname{Tr}[Y\Phi[X]] = \int dt \mu(t) (\eta - \operatorname{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{[n]})(t)]) \quad (203)$$

$$+ \operatorname{Tr} \left[ \left( \int dt P_{A_1^n B_1^n}(t) \right) \left( Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)} \right) \right] \quad (204)$$

$$+ \operatorname{Tr} \left[ \left( C_{A_1^n B_1^{n-1}}^{(n)} \otimes \mathbb{I}_{B_n} \right) \left( -Y_{A_1^n B_1^n}^{(n)} + Y_{A_1^n B_1^n}^{(2)} \right) \right]$$

$$+ \operatorname{Tr}_{A_1} [C_{A_1}^{(1)}] (\alpha - \beta)$$

$$+ \sum_{k=2}^{n} \operatorname{Tr} \left[ \operatorname{Tr}_{A_k} \left[ C_{A_1^k B_1^{k-1}}^{(k)} \right] \left( \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)} \right) \right]$$

$$+ \sum_{k=2}^{n} \operatorname{Tr} \left[ \left( C_{A_1^{k-1} B_1^{k-2}}^{(k-1)} \otimes \mathbb{I}_{B_{k-1}} \right) \left( -\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} + \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)} \right) \right]$$

$$= \operatorname{Tr} \left[ \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right) \left( \int dt |t\rangle\langle t| \otimes (Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)} - \mu(t)(w * C_{A_1^n B_1^n}^{[n]})(t)) \right) \right]$$

$$+ \operatorname{Tr} \left[ C_{A_1}^{(1)} \left( (\alpha - \beta) \mathbb{I}_{A_1} + \operatorname{Tr}_{B_1} [-\tilde{C}_{A_1 B_1}^{(2,0)} + \tilde{C}_{A_1 B_1}^{(2,1)}] \right) \right]$$

$$+ \sum_{k=2}^{n-1} \operatorname{Tr} \left[ C_{A_1^k B_1^{k-1}}^{(k)} \left( (\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}) \otimes \mathbb{I}_{A_k} + \operatorname{Tr}_{B_k} [-\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} + \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}] \right) \right]$$

$$+ \operatorname{Tr} \left[ C_{A_1^n B_1^{n-1}}^{(n)} \left( (\tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,1)}) \otimes \mathbb{I}_{A_n} + \operatorname{Tr}_{B_n} [-Y_{A_1^n B_1^n}^{(1)} + Y_{A_1^n B_1^n}^{(2)}] \right) \right],$$
which in turn implies that

$$
\begin{equation}
\begin{aligned}
\Phi^{\dagger}[Y] = & \left( \int dt |t\rangle\langle t| \otimes (Y_{A_1^B_1}^{(1)} - Y_{A_1^B_1}^{(2)} - \mu(t)(w * C_{A_1^B_1}^{\mathcal{N}^{[n]}})(t)) \right) \\
& \oplus \left( (\tilde{C}_{A_1^{n-1}B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1}B_1^{n-1}}^{(n,1)}) \otimes \mathbb{I}_{A_n} + \mathrm{Tr}_{B_n} [-Y_{A_1^B_1}^{(1)} + Y_{A_1^B_1}^{(2)}] \right) \\
& \oplus \sum_{k=2}^{n-1} |k\rangle\langle k| \otimes \left( (\tilde{C}_{A_1^{k-1}B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1}B_1^{k-1}}^{(k,1)}) \otimes \mathbb{I}_{A_k} + \mathrm{Tr}_{B_k} [-\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} + \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}] \right) \\
& \oplus ((\alpha - \beta)\mathbb{I}_{A_1} + \mathrm{Tr}_{B_1} [-\tilde{C}_{A_1 B_1}^{(2,0)} + \tilde{C}_{A_1 B_1}^{(2,1)}]) \\
& \oplus \left( \int dt \mu(t) \right).
\end{aligned}
\tag{205}
\end{equation}
$$

The inequality $\Phi^{\dagger}[Y] \ge A$, therefore, implies that the dual problem is given by

minimize $\alpha - \beta$

subject to $\alpha \ge 0, \beta \ge 0, Y_{A_1^n B_1^n}^{(1)} \ge 0, Y_{A_1^n B_1^n}^{(2)} \ge 0, \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} \ge 0, \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)} \ge 0 \ \forall k \in \{1, 2, \dots, n\}$,

$$
\begin{align}
& Y_{A_1^n B_1^n}^{(1)} - Y_{A_1^n B_1^n}^{(2)} - \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t, \nonumber \\
& (\tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,0)} - \tilde{C}_{A_1^{n-1} B_1^{n-1}}^{(n,1)}) \otimes \mathbb{I}_{A_n} + \mathrm{Tr}_{B_n} [-Y_{A_1^n B_1^n}^{(1)} + Y_{A_1^n B_1^n}^{(2)}] \ge 0, \tag{206} \\
& (\tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,0)} - \tilde{C}_{A_1^{k-1} B_1^{k-1}}^{(k,1)}) \otimes \mathbb{I}_{A_k} + \mathrm{Tr}_{B_k} [-\tilde{C}_{A_1^k B_1^k}^{(k+1,0)} + \tilde{C}_{A_1^k B_1^k}^{(k+1,1)}] \quad \forall k \in \{2, 3, \dots, n-1\}, \nonumber \\
& (\alpha - \beta)\mathbb{I}_{A_1} + \mathrm{Tr}_{B_1} [-\tilde{C}_{A_1 B_1}^{(2,0)} + \tilde{C}_{A_1 B_1}^{(2,1)}] \ge 0, \nonumber \\
& \int dt \, \mu(t) \ge 1, \mu(t) \ge 0 \quad \forall t. \nonumber
\end{align}
$$

Strong duality is straightforward to show, which implies that the optimal solution to this dual problem is equal to the optimal solution of the primal problem.

Next, by the complementary slackness condition $\Phi^{\dagger}[Y]X = AX$, we find that $\int dt \mu(t) = 1$. We can further simplify the dual problem above via change of variables, in exactly the same way as we did in the proof of Proposition 4. Doing so gives us the desired dual problem in the statement of the proposition. $\square$

### D. Optimization with respect to strategies with indefinite causal order

In the previous section, we considered sequential/adaptive quantum metrology protocols in which every use of the parameterized channel $t \mapsto \mathcal{N}(t)$ is causally ordered. Let us now consider a more general class of protocols, based on non-causal ordering of the channel uses. Following Refs. [139, 140], we define a general, non-causal strategy for $n$ uses of the channel $\mathcal{N}_{A \to B}(t)$ by operators $t \mapsto P_{A_1^n B_1^n}(t)$ such that $P_{A_1^n B_1^n}(t) \ge 0$ for all $t$, and $W_{A_1^n B_1^n} := \int dt P_{A_1^n B_1^n}(t)$ satisfies $\mathrm{Tr}[W_{A_1^n B_1^n}(C_{A_1 B_1}^{(1)} \otimes C_{A_2 B_2}^{(2)} \otimes \dots \otimes C_{A_n B_n}^{(n)})] = 1$ for all Choi representations $C_{A_k B_k}^{(k)}$ of quantum channels (i.e., Hermitian operators $C_{A_k B_k}^{(k)}$ satisfying $C_{A_k B_k}^{(k)} \ge 0$ and $\mathrm{Tr}_{B_k}[C_{A_k B_k}^{(k)}] = \mathbb{I}_{A_k}$). We let

$$
\mathcal{C}_n^{\text{prod}}(A_1^n, B_1^n) := \left\{ \bigotimes_{k=1}^n C_{A_k B_k}^{(k)} : C_{A_k B_k}^{(k)} \ge 0, \mathrm{Tr}_{B_k}[C_{A_k B_k}^{(k)}] = \mathbb{I}_{A_k}, k \in \{1, 2, \dots, n\} \right\} \quad (207)
$$

be the set of all tensor $n$-fold tensor products of Choi representations of quantum channel. Then, we define

$$
\mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n) := \{ W_{A_1^n B_1^n} : W_{A_1^n B_1^n} \ge 0, \mathrm{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}] = 1 \quad \forall Y_{A_1^n B_1^n} \in \mathcal{C}_n^{\text{prod}}(A_1^n, B_1^n) \} \quad (208)
$$

to be the set of all operators representing $n$-partite non-causal strategies. An explicit form for this set for arbitrary $n \in \{2, 3, \dots\}$ can be found in Ref. [141]. As an example, for $n = 2$,

$$
\mathcal{S}_2^{\text{ico}}(A_1^2, B_1^2) = \left\{ W_{A_1^2 B_1^2} : W_{A_1^2 B_1^2} \ge 0, \mathrm{Tr}[W_{A_1^2 B_1^2}] = d_{B_1} d_{B_2}, W_{A_1^2 B_1^2} = (\mathcal{R}_{B_1} + \mathcal{R}_{B_2} - \mathcal{R}_{B_1 B_2})(W_{A_1^2 B_1^2}), \right. \\
\left. \mathcal{R}_{A_1 B_1}(W_{A_1^2 B_1^2}) = \mathcal{R}_{A_1 B_1 B_2}(W_{A_1^2 B_1^2}), \mathcal{R}_{A_2 B_2}(W_{A_1^2 B_1^2}) = \mathcal{R}_{A_2 B_1 B_2}(W_{A_1^2 B_1^2}) \right\}, \quad (209)
$$

where $\mathcal{R}_A(X_{RA}) := \mathrm{Tr}_A[X_{RA}] \otimes \frac{\mathbb{I}_A}{d_A}$ is the completely depolarizing channel acting on a system $A$, which discards the state of the system $A$ and replaces it with the maximally-mixed state.
**Lemma 31.** For every $n \in \{2, 3, \dots\}$, it holds that

$$ \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n) = \left\{ W_{A_1^n B_1^n} : W_{A_1^n B_1^n} \ge 0, \text{Tr}[W_{A_1^n B_1^n} (C_{A_1 B_1}^{(1)} \otimes C_{A_2 B_2}^{(2)} \otimes \cdots \otimes C_{A_n B_n}^{(n)})] = 1, \right. \\ \left. C_{A_k B_k}^{(k)} \text{ Hermitian, } \text{Tr}_{B_k}[C_{A_k B_k}^{(k)}] = \mathbb{I}_{A_k}, k \in \{1, 2, \dots, n\} \right\}. \quad (210) $$

*Proof.* We follow the arguments presented in Ref. [141]. The inclusion “$\supseteq$” is clear. For the inclusion “$\subseteq$”, assume that $W_{A_1^n B_1^n} \in \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n)$. We now show that $\text{Tr}[W_{A_1^n B_1^n} (C_{A_1 B_1}^{(1)} \otimes \cdots \otimes C_{A_n B_n}^{(n)})] = 1$ for every collection $C_{A_1 B_1}^{(1)}, \dots, C_{A_n B_n}^{(n)}$ of Hermitian operators satisfying $\text{Tr}_{B_1}[C_{A_1 B_1}^{(1)}] = \mathbb{I}_{A_1}, \dots, \text{Tr}_{B_n}[C_{A_n B_n}^{(n)}] = \mathbb{I}_{A_n}$. To that end, note that for every such $C_{A_k B_k}^{(k)}$, there exists $\alpha_k \ge 0$ such that $C_{A_k B_k}^{(k)} + \alpha_k \frac{1}{d_{B_k}} \mathbb{I}_{A_k B_k} \ge 0$. Furthermore, we can decompose $C_{A_k B_k}^{(k)}$ as

$$ C_{A_k B_k}^{(k)} = (\alpha_k + 1) C_{A_k B_k}^{(k,0)} - \alpha_k C_{A_k B_k}^{(k,1)}, \quad (211) $$

$$ C_{A_k B_k}^{(k,0)} = \frac{1}{\alpha_k + 1} \left( C_{A_k B_k}^{(k)} + \alpha_k \frac{1}{d_{B_k}} \mathbb{I}_{A_k B_k} \right), \quad (212) $$

$$ C_{A_k B_k}^{(k,1)} = \frac{1}{d_{B_k}} \mathbb{I}_{A_k B_k}. \quad (213) $$

Observe that $C_{A_k B_k}^{(k,0)} \ge 0$, $C_{A_k B_k}^{(k,1)} \ge 0$, and $\text{Tr}_{B_k}[C_{A_k B_k}^{(k,0)}] = \text{Tr}_{B_k}[C_{A_k B_k}^{(k,1)}] = \mathbb{I}_{A_k}$. Then, we have

$$ \begin{aligned} \text{Tr}[W_{A_1^n B_1^n} (C_{A_1 B_1}^{(1)} \otimes \cdots \otimes C_{A_n B_n}^{(n)})] &= \sum_{x \in \{0,1\}^n} \left( \prod_{k=1}^n (\alpha_k + 1)^{x_k} (-\alpha_k)^{1-x_k} \right) \underbrace{\text{Tr} \left[ W_{A_1^n B_1^n} \otimes \prod_{k=1}^n C_{A_k B_k}^{(k,x)} \right]}_{=1 \quad \forall x \in \{0,1\}^n} \\ &= \sum_{x \in \{0,1\}^n} \left( \prod_{k=1}^n (\alpha_k + 1)^{x_k} (-\alpha_k)^{1-x_k} \right) \\ &= \prod_{k=1}^n (-\alpha_k + \alpha_k + 1) \\ &= 1, \end{aligned} \quad (214) $$

which implies the desired result, because the operator $W_{A_1^n B_1^n} \in \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n)$ was arbitrary. $\square$

Let

$$ \tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n) := \left\{ \bigotimes_{k=1}^n C_{A_k B_k}^{(k)} : C_{A_k B_k}^{(k)} \text{ Hermitian, } \text{Tr}_{B_k}[C_{A_k B_k}^{(k)}] = \mathbb{I}_{A_k}, k \in \{1, 2, \dots, n\} \right\}. \quad (215) $$

Lemma 31 tells us that

$$ \begin{aligned} \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n) &= \{ W_{A_1^n B_1^n} : W_{A_1^n B_1^n} \ge 0, \text{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}] = 1 \quad \forall Y_{A_1^n B_1^n} \in \tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n) \} \\ &= \{ W_{A_1^n B_1^n} : W_{A_1^n B_1^n} \ge 0, \text{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}] = 1 \quad \forall Y_{A_1^n B_1^n} \in \text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n)) \}, \end{aligned} \quad (216) $$

where $\text{aff}(\mathcal{S}) := \{ \sum_i x_i s_i : s_i \in \mathcal{S}, x_i \in \mathbb{R}, \sum_i x_i = 1 \}$ denotes the affine hull of a set $\mathcal{S}$.

**Proposition 32** (Bayesian optimization of non-causal strategies). Let $C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}}$ be the Choi representation of the comb $\mathcal{N}(t)^{[n]}$ corresponding to n uses of the parameterized quantum channel $t \mapsto \mathcal{N}(t)$. Also, let $t \mapsto \mu(t)$ be a prior probability density function. Then, the optimal non-causal Bayesian strategy for estimating the parameter $t$ can be determined using the convex problem

$$ \begin{array}{ll} \text{maximize} & \int dt \, \mu(t) \text{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}})(t)] \\ \text{subject to} & P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \\ & \int dt \, P_{A_1^n B_1^n}(t) \in \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n). \end{array} \quad (217) $$
The dual problem, which has the same optimal value as the primal problem above, is

$$
\begin{align}
\text{minimize} \quad & \lambda \nonumber \\
\text{subject to} \quad & \lambda Y_{A_1^n B_1^n} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t, \tag{218} \\
& Y_{A_1^n B_1^n} \in \tilde{S}_n^{\text{NS}}(A_1^n, B_1^n), \nonumber
\end{align}
$$

where $\tilde{S}_n^{\text{NS}}(A_1^n, B_1^n)$ is the set of all Choi representations of n-partite Hermiticity-preserving non-signaling superoperators with input systems $A_1, \dots, A_n$ and output systems $B_1, \dots, B_n$, defined as [142, 143]

$$
\tilde{S}_n^{\text{NS}}(A_1^n, B_1^n) := \{ Y_{A_1^n B_1^n} : Y_{A_1^n B_1^n} \text{ Hermitian, } \text{Tr}_{B_K}[Y_{A_1^n B_1^n}] = \mathbb{I}_{A_K} \otimes Y'_{A_K B_K}, Y'_{A_K B_K} \ge 0, K \subseteq \{1, 2, \dots, n\} \}. \quad (219)
$$

Here, $B_K$ denotes the $B$ systems labeled by the subset $K$, and $\bar{K}$ denotes the complement of $K$.

Proof. Using (216), we can write the primal problem as

$$
\begin{align}
\text{maximize} \quad & \int dt \, \mu(t) \operatorname{Tr}[P_{A_1^n B_1^n}(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t)] \notag \\
\text{subject to} \quad & P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \notag \\
& W_{A_1^n B_1^n} = \int dt \, P_{A_1^n B_1^n}(t), \tag{220} \\
& \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}] = 1 \quad \forall Y_{A_1^n B_1^n} \in \operatorname{aff}(\tilde{C}_n^{\operatorname{prod}}(A_1^n, B_1^n)). \notag
\end{align}
$$

Now, let us pick a basis $\{Y_{A_1^n B_1^n}^j\}_j$ for the affine space $\operatorname{aff}(\tilde{C}_n^{\operatorname{prod}}(A_1^n, B_1^n))$. With this, the infinite number of constraints in the final line of the above convex problem can be made into a finite number of constraints, such that the primal problem can be formulated as

$$
\begin{align}
\text{maximize} \quad & \int dt \, \mu(t) \operatorname{Tr}[P_{A_1^n B_1^n}(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t)] \notag \\
\text{subject to} \quad & P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \notag \\
& W_{A_1^n B_1^n} = \int dt \, P_{A_1^n B_1^n}(t), \tag{221} \\
& \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] = 1 \quad \forall j. \notag
\end{align}
$$

We can now cast this into the standard form (127) of a primal problem. Specifically, we have

$$
X = \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t), \tag{222}
$$

$$
A = \int dt |t\rangle\langle t| \otimes \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t), \quad (223)
$$

$$
\Phi[X] = \sum_j \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] |j\rangle\langle j| \oplus \sum_j (-\operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j]) |j\rangle\langle j|, \quad (224)
$$

$$
B = \sum_j |j\rangle\langle j| \oplus \sum_j (-1)^j |j\rangle\langle j|. \tag{225}
$$

Now, for the dual variable, we can take it to be of the form $Y = \sum_j \alpha_j |j\rangle\langle j| \oplus \sum_j \beta_j |j\rangle\langle j|$, where $\alpha_j \ge 0$ and $\beta_j \ge 0$ for all $j$. From this, it is straightforward to show that

$$
\mathrm{Tr}[Y\Phi[X]] = \mathrm{Tr} \left[ \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right) \left( \int dt |t\rangle\langle t| \otimes \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j \right) \right], \quad (226)
$$

so that

$$
\Phi^{\dagger}[Y] = \int dt |t\rangle\langle t| \otimes \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j . \quad (227)
$$

The dual problem is therefore

$$
\begin{align}
\text{minimize} \quad & \sum_j (\alpha_j - \beta_j) \nonumber \\
\text{subject to} \quad & \alpha_j \ge 0, \beta_j \ge 0 \quad \forall j, \nonumber \\
& \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t. \tag{228}
\end{align}
$$
Strong duality is straightforward to verify, which means that this dual problem has the same optimal value as the primal problem. Now, let $\lambda = \sum_j (\alpha_j - \beta_j)$. Then, $\lambda \in \mathbb{R}$ and

$$ \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j = \lambda \sum_j \frac{\alpha_j - \beta_j}{\lambda} Y_{A_1^n B_1^n}^j = \lambda Y_{A_1^n B_1^n}, \quad (229) $$

where $Y_{A_1^n B_1^n} \in \text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n))$. We thus conclude that the dual problem is given by

$$
\begin{array}{ll}
\text{minimize} & \lambda \\
\text{subject to} & \lambda Y_{A_1^n B_1^n} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t, \qquad (230) \\
& Y_{A_1^n B_1^n} \in \text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n)).
\end{array}
$$

Finally, we use Ref. [142] (Theorem 14), which implies that $\text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n)) = \tilde{\mathcal{S}}_n^{\text{NS}}(A_1^n, B_1^n)$, completing the proof. $\square$

**Proposition 33** (Minimax optimization of non-causal strategies). Let $C_{A_1^n B_1^n}^{\mathcal{N}(t)^{[n]}}$ be the Choi representation of the comb $\mathcal{N}(t)^{[n]}$ corresponding to n uses of the parameterized quantum channel $t \mapsto \mathcal{N}(t)$. Then, the optimal non-causal minimax strategy for estimating the parameter $t$ can be determined using the convex problem

$$
\begin{array}{ll}
\text{maximize} & \eta \\
\text{subject to} & \text{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t)] \ge \eta \quad \forall t, \\
& \eta \ge 0, \\
& P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \\
& \int dt P_{A_1^n B_1^n}(t) \in \mathcal{S}_n^{\text{ico}}(A_1^n, B_1^n).
\end{array}
\qquad (231)
$$

The dual problem, which has the same optimal value as the primal problem above, is

$$
\begin{array}{ll}
\text{minimize} & \lambda \\
\text{subject to} & \lambda Y_{A_1^n B_1^n} \ge \mu(t) (w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t) \quad \forall t, \qquad (232) \\
& Y_{A_1^n B_1^n} \in \text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n)), \\
& \mu(t) \ge 0, \quad \int dt \mu(t) = 1.
\end{array}
$$

*Proof.* We proceed similarly to the proof of Proposition 32. By picking a basis $\{Y_{A_1^n B_1^n}^j\}_{j}$ for $\text{aff}(\tilde{\mathcal{C}}_n^{\text{prod}}(A_1^n, B_1^n))$, we can write the primal problem as

$$
\begin{array}{ll}
\text{maximize} & \eta \\
\text{subject to} & \text{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]}})(t)] \ge \eta \quad \forall t, \\
& \eta \ge 0, \\
& P_{A_1^n B_1^n}(t) \ge 0 \quad \forall t, \\
& W_{A_1^n B_1^n} = \int dt P_{A_1^n B_1^n}(t), \\
& \text{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] = 1 \quad \forall j.
\end{array}
\qquad (233)
$$
We can then cast this into the standard form (127) as

$$X = \eta \oplus \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right), \qquad (234)$$

$$A = 1 \oplus \left( \int dt |t\rangle\langle t| \otimes 0 \right), \qquad (235)$$

$$\begin{aligned} \Phi[X] = & \left( \int dt |t\rangle\langle t| \otimes (\eta - \operatorname{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]})}(t)]) \right) \\ & \oplus \left( \sum_j \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] |j\rangle\langle j| \right) \\ & \oplus \left( \sum_j (-\operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j]) |j\rangle\langle j| \right), \end{aligned} \qquad (236)$$

$$B = \left( \int dt |t\rangle\langle t| \otimes 0 \right) \oplus \left( \sum_j |j\rangle\langle j| \right) \oplus ((-1)|j\rangle\langle j|). \qquad (237)$$

Then, letting the dual variable $Y$ be

$$Y = \left( \int dt |t\rangle\langle t|\mu(t) \right) \oplus \left( \sum_j |j\rangle\langle j|\alpha_j \right) \oplus \left( \sum_j |j\rangle\langle j|\beta_j \right), \qquad (238)$$

with $\mu(t) \ge 0$ for all $t$ and $\alpha_j \ge 0$, $\beta_j \ge 0$ for all $j$, we obtain

$$\begin{aligned} \operatorname{Tr}[Y\Phi[X]] = & \int dt \mu(t) (\eta - \operatorname{Tr}[P_{A_1^n B_1^n}(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]})}(t)]) \\ & + \sum_j \alpha_j \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] - \sum_j \beta_j \operatorname{Tr}[W_{A_1^n B_1^n} Y_{A_1^n B_1^n}^j] \end{aligned} \qquad (239)$$

$$= \eta \int dt \mu(t) \\ + \operatorname{Tr} \left[ \left( \int dt |t\rangle\langle t| \otimes P_{A_1^n B_1^n}(t) \right) \left( \int dt |t\rangle\langle t| \otimes \left( \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j - \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]})}(t) \right) \right) \right]. \qquad (240)$$

This implies that

$$\Phi^{\dagger}[Y] = \left( \int dt \mu(t) \right) \oplus \left( \int dt |t\rangle\langle t| \otimes \left( \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j - \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]})}(t) \right) \right). \qquad (241)$$

The dual problem is therefore

$$\begin{array}{ll} \text{minimize} & \sum_j \alpha_j - \beta_j \\ \text{subject to} & \alpha_j \ge 0, \beta_j \ge 0 \quad \forall j, \mu(t) \ge 0 \quad \forall t, \\ & \int dt \mu(t) \ge 1, \sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j \ge \mu(t)(w * C_{A_1^n B_1^n}^{\mathcal{N}^{[n]})}(t) \quad \forall t. \end{array} \qquad (242)$$

Strong duality is straightforward to show, which means that this dual problem has the same optimal value as the primal problem.

Now, the complementary slackness condition $\Phi^{\dagger}[Y]X = AX$ implies that $\int dt \mu(t) = 1$. Furthermore, letting $\lambda \equiv \sum_j \alpha_j - \beta_j$, we find that

$$\sum_j (\alpha_j - \beta_j) Y_{A_1^n B_1^n}^j = \lambda \sum_j \frac{\alpha_j - \beta_j}{\lambda} Y_{A_1^n B_1^n}^j = \lambda Y_{A_1^n B_1^n}, \quad Y_{A_1^n B_1^n} \in \operatorname{aff}(\tilde{\mathbb{C}}_n^{\operatorname{prod}}(A_1^n, B_1^n)). \qquad (243)$$

With these simplifications, along with Ref. [142] (Theorem 14), which states that $\operatorname{aff}(\tilde{\mathbb{C}}_n^{\operatorname{prod}}(A_1^n, B_1^n)) = \tilde{\mathbb{S}}_n^{\mathrm{NS}}(A_1^n, B_1^n)$, we obtain the desired dual problem. $\square$
The convex programs presented in Propositions 32 and 33 are continuous analogues of the SDPs in Refs. [140, 144] for channel discrimination using strategies without causal ordering of the channel uses.

E. Numerical implementation

The optimization programs presented in the preceding sections typically involve continuous objects, both in the inputs to the problem as well as in the optimization variables. As optimization over these quantities is not readily available in numerical solvers, we have to discretize the problems for actual implementation. This means, we need to choose a number of points in the discretization which we denote with $k$. We then replace any function $f(t)$ with a vector of discrete values $(f_\ell)_{\ell=1}^k$ corresponding to points in time $(t_\ell)_{\ell=1}^k$.

Typically, $t$ varies only in a finite interval $[0, T]$. In this case, the most straightforward way to discretize is to fix a number of discretization steps $k$ and choose time points that are evenly spaced in time, i.e., $t_\ell = \ell T/k$. We then replace the time-varying quantity $f(t)$ with the average over the preceding interval in the discretization as

$$f_{\ell} = \frac{k}{T} \int_{t_{\ell-1}}^{t_{\ell}} dt f(t), \qquad (244)$$

where we use the convention that $t_0 = 0$. This corresponds to replacing $f(t)$ with a piece-wise constant function

$$f(t) \rightarrow \sum_{\ell=1}^{k} f_{\ell} \chi[t_{\ell-1} < t \leq t_{\ell}], \qquad (245)$$

where $\chi$ denotes an indicator function which takes the value one if the argument is true and zero otherwise. As an example, we give the discretized version of the convex program of Proposition 1. The objective of said program is given by

$$\int dt d\tau w(t - \tau) \mathrm{Tr}[\mu(t)\rho(t)Q(\tau)]. \qquad (246)$$

We now replace all functions by their piece-wise approximations, to obtain

$$\sum_{\ell=1}^{k} \sum_{m=1}^{k} \sum_{p=1}^{k} w_p \mathrm{Tr}[\mu_{\ell} \rho_{\ell} Q_m] \int dt d\tau \chi[t_{\ell-1} < t \leq t_{\ell}] \chi[t_{p-1} < t - \tau \leq t_p] \chi[t_{m-1} < \tau \leq t_m] \qquad (247) \\ = \sum_{\ell=1}^{k} \sum_{m=1}^{k} \sum_{p=1}^{k} w_{\ell-m} \chi[1 \leq \ell - m \leq k] \mathrm{Tr}[\mu_{\ell} \rho_{\ell} Q_m] \left(\frac{T}{k}\right)^2 \\ = \sum_{\ell=1}^{k} \sum_{m=\max(1, \ell-k)}^{\min(k, \ell-1)} w_{\ell-m} \mathrm{Tr}[\mu_{\ell} \rho_{\ell} Q_m] \left(\frac{T}{k}\right)^2 .$$

The discretized version of the convex problem would thus be

$$\begin{align} \eta^*(w, \mu, \rho) &\approx \eta^*((w_\ell), (\mu_\ell), (\rho_\ell)) \tag{248} \\ &= \underset{\text{such that}}{\text{maximize}} \left(\frac{T}{k}\right)^2 \sum_{\ell=1}^k \sum_{m=\max(1, \ell-k)}^{\min(k, \ell-1)} w_{\ell-m} \mathrm{Tr}[\mu_\ell \rho_\ell Q_m] \nonumber \\ &= \sum_\ell Q_\ell \geq 0 \text{ for all } \ell \nonumber \\ &= \sum_\ell Q_\ell = \mathbb{I}. \nonumber \end{align}$$

In this case, the sum over $m$ denotes a discrete convolution. Under the assumption of periodic boundary conditions, this convolution would be changed to wrap around the interval which would yield a simpler expression.

The other possibility, namely the case in which $t$ can take arbitrary values on the real line, makes sense only if we have access to a prior $\mu(t)$. This case can be treated in a similar manner, but the discretization is not uniform anymore. Instead, one can choose regions $R_\ell \subset \mathbb{R}$ of equal measure $\mu(R_\ell) = 1/k$ for all $\ell$. In this way, we are replacing the measure over values of $t$ with a uniform measure over the choice of region $R_\ell$. For each such region we replace the function value with its average over the region, i.e., a piece-wise approximation

$$f(t) \approx \sum_{\ell=1}^{k} f_{\ell} \chi[t \in R_{\ell}], \qquad f_{\ell} = \frac{1}{|R_{\ell}|} \int_{R_{\ell}} dt f(t) \qquad (249)$$
such that

$$ \int d\mu(t) f(t) \approx \frac{1}{k} \sum_{\ell=1}^{k} f_{\ell}. \qquad (250) $$

Ideally, one would like to do away with the discretization completely. To do so, one could consider an expansion of the optimization variable, for example the measurement,

$$ Q(t) = \sum_{\omega} \hat{Q}_{\omega} \phi_{\omega}(t), \qquad (251) $$

for some set of functions $\phi_\omega$. Typical choices, like the Fourier basis, however do not work, as the positive semi-definiteness constraint $Q(t) \ge 0$ is very difficult to enforce. It is an intriguing direction for future research if we can use bases of non-negative functions [145] to get around this limitation.

## F. Discretizing the success probability

In this section we will discuss how to discretize and formalize the POVM optimization problem in Proposition 7 in order to obtain mathematically formal statements. Recall that it was given by

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

Here we will focus on the Bayesian case for simplicity, as the minimax case is completely analogous. First, we note that to be formally correct in its formulations it is necessary to restrict the continuous-parameter POVMs we optimize over to make sense of the optimization and maximum above. Here, we will consider two natural possible restrictions: first, to POVMs that are Lipschitz with respect to the operator norm with a Lipschitz constant $C_\delta$, i.e. for all $t, t'$:

$$ \|Q(t) - Q(t')\|_{\infty} \le C_{\delta}|t - t'|. \qquad (253) $$

We choose to make the Lipschitz constant depend explicitly on $\delta$ to emphasize that, as $\delta \to 0$, it is also necessary to make $C_\delta \to +\infty$ to make sure we are optimizing over POVMs that are sufficiently sensitive to distinguish the underlying states. Indeed, if we want the POVMs to distinguish states that are $\delta$ apart it is necessary that $\|Q(t) - Q(t')\|_{\infty} = \Omega(1)$ for $|t - t'|$ of order $\delta$. Note that the set of Lipschitz POVMs is a compact, convex subset with respect to the operator norm, and that the success probability is a linear functional of the parametrized POVM. Thus, the max in Eq. (252) is justified, as it is attained. Another natural variation is to consider the set of continuous POVMs. As we let $C_\delta \to +\infty$ we can approximate any continuous function by a Lipschitz function, so this can be seen as a limiting case of the previous problem.

We now discuss how to discretize the problem in Eq. (252) and show convergence. For the setting of Lipschitz POVMs we will also obtain quantitative statements. To obtain such statements, we will assume that the curve of states $\rho(t)$ is Lipschitz with respect to the trace distance, i.e. for all $t, t'$:

$$ \|\rho(t) - \rho(t')\|_{1} \le C_{\rho}|t - t'|. \qquad (254) $$

We further need to discretize the set of possible measures $\mu$. We will assume here that $\mu$ has compact support and periodic boundary conditions, but the general case can be considered by considering a sequence of measures with compact support $\mu_n$ that approximate $\mu$.

We will pick a discretization parameter $\Delta$ satisfying $1 > \delta > \Delta > 0$ such that $\delta/\Delta \in \mathbb{N}$ and consider a discretization of the image of $\rho(t)$, i.e. on the level of states. Let $T = |\operatorname{supp}(\mu)|$ be the size of the support of $\mu$. We will discretize it into $N = \lceil T\Delta^{-1} \rceil$ points $\{t_1, t_2, \dots, t_N\}$ that are $\Delta$ apart. Furthermore, we will call $T_i = [t_i - \Delta/2, t_i + \Delta/2]$. Given the $t_i$ and $\delta$, we will call

$$ N_{\delta}(i) := \{j \mid |t_i - t_j| \le \delta\}. \qquad (255) $$

We then consider the following semidefinite program for a given parameter $\delta$, which gives the maximal success
probability for this window function:

$$ \text{maximize} \quad \sum_{i=1}^{N} \mu(T_i) \sum_{j \in N_{\delta}(i)} \text{Tr} [Q_j \rho(t_i)] \qquad (256) $$

subject to $Q_i \ge 0$,

$$ \sum_{i=1}^{N} Q_i = \mathbb{I}, $$

$$ \|Q_i - Q_{i+1}\|_{\infty} \le C_{\delta}\Delta \quad \text{for all } i $$

The semidefinite program in Eq. (256) can be solved in time that is polynomial in $N$ and the dimension of the states $\rho(t)$, and, as the number of constraints is linear in $\Delta^{-1}$, the complexity will also depend polynomially on $\Delta^{-1}$. Note further that the operator norm constraint can be recast as the linear matrix inequality $-C_{\delta}\Delta \le Q_i - Q_{i+1} \le C_{\delta}\Delta$, so it is a valid SDP constraint.

Of course, the central question is how fast the value of the above SDP converges to that of Eq. (252). Before we prove the convergence, let us give some Lemmas:

**Lemma 34.** Let $\Delta$ be a discretization parameter satisfying $1 > \delta > \Delta > 0$, $T = |\text{supp}(\mu)|$ be the size of the support of $\mu$. Consider a discretization of the image of $\rho(t)$ into $N = \lceil T\Delta^{-1} \rceil$ points $\{t_1, t_2, \dots, t_N\}$ points that are $\Delta$ apart given by $\rho(t_i)$. Furthermore, we will call $T_i = [t_i - \Delta/2, t_i + \Delta/2]$. Further, assume that the curve of states is Lipschitz continuous:

$$ \|\rho(t_1) - \rho(t_2)\|_1 \le C_{\rho}|t_1 - t_2|. \qquad (257) $$

Then we have:

$$ \left\| \left( \int_{T_i} d\mu(t) \rho(t) \right) - \mu(T_i) \rho(t_i) \right\|_1 \le C_{\rho} \Delta \mu(T_i). \qquad (258) $$

Proof. Note that:

$$ \left( \int_{T_i} dt \, \mu(t) \rho(t) \right) - \mu(T_i) \rho(t_i) = \int_{T_i} dt \, \mu(t) (\rho(t) - \rho(t_i)). \qquad (259) $$

Thus, by the triangle inequality,

$$ \left\| \left( \int_{T_i} d\mu(t) \rho(t) \right) - \mu(T_i) \rho(t_i) \right\|_1 \le \int_{T_i} d\mu(t) \|\rho(t) - \rho(t_i)\|_1. \qquad (260) $$

By the Lipschitz condition in Eq. (258) and our choice of $t_i$ we have that

$$ \|\rho(t) - \rho(t_i)\|_1 \le C_{\rho}|t - t_i|. \qquad (261) $$

Inserting this bound in Eq. (260) we get that:

$$ \int_{T_i} d\mu(t) \|\rho(t) - \rho(t_i)\|_1 \le C_{\rho} \int_{T_i} d\mu(t) |t - t_i| \le C_{\rho} \Delta \mu(T_i), \qquad (262) $$

which proves the claim.

**Lemma 35.** Let $\Delta$ be a discretization parameter satisfying $1 > \delta > \Delta > 0$, $T = |\text{supp}(\mu)|$ be the size of the support of $\mu$. Let $\{Q(t)\}$ be a continuous POVM that is Lipschitz with respect to the operator norm, i.e.

$$ \|Q(t_1) - Q(t_2)\|_{\infty} \le C_{\delta}|t_1 - t_2|. \qquad (263) $$

Consider the following discretization of the POVM:

$$ Q_i = \int_{T_i} dt Q(t). \qquad (264) $$
Then for all $1 \le i < T$:

$$ \|Q_{i+1} - Q_i\|_{\infty} \le C_{\delta}\Delta^2 \qquad (265) $$

and for all $t \in T_i$ we have

$$ \left\| \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds Q(s) - \sum_{j \in N_{\delta}(i)} Q_j \right\|_{\infty} \le C_{\delta} \Delta \delta. \qquad (266) $$

Proof. Let us start by proving Eq. (265). Note that:

$$ Q_{i+1} - Q_i = \int_{T_i} ds Q(s + \Delta) - Q(s). \qquad (267) $$

By a triangle inequality followed by our Lipschitz condition we have:

$$ \|Q_{i+1} - Q_i\|_{\infty} \le \int_{T_i} ds \|Q(s + \Delta) - Q(s)\|_{\infty} \le C_{\delta}\Delta \int_{T_i} ds = C_{\delta}\Delta^2. \qquad (268) $$

Let us now prove Eq. (266) in a similar manner. We have that:

$$ \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds Q(s) - \sum_{j \in N_{\delta}(i)} Q_j = \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds [Q(s) - Q(s + t_i - t)], \qquad (269) $$

where we used the fact that $\delta/\Delta \in \mathbb{N}$. Thus,

$$ \left\| \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds [Q(s) - Q(s + t_i - t)] \right\|_{\infty} \le \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds \|Q(s) - Q(s + t_i - t)\|_{\infty} \qquad (270) $$

$$ \le C_{\delta}|t_i - t| \int_{t-\frac{\delta}{2}}^{t+\frac{\delta}{2}} ds \qquad (271) $$

$$ \le C_{\delta}\delta\Delta. \qquad (272) $$

□

Our strategy will now consist in showing that the above discretization {$Q_i$} of a continuous POVM gives a feasible point of the SDP in Eq. (256) whose value does not change significantly from that of its continuous-time counterpart.

**Proposition 36.** Under the same conditions as in Lemmas 34 and 35 we have that:

$$ \left| \int dt \operatorname{Tr}[(w_{\delta} * [\mu \cdot \rho])(t)Q(t)] - \sum_{i} \mu(T_i) \sum_{j \in N_{\delta}(i)} \operatorname{Tr}[Q_j \rho(t_i)] \right| \le C_{\delta} \delta \Delta + C_{\rho} \Delta. \qquad (273) $$

Proof. We will proceed by showing the statement on each interval $T_i$. We have:

$$ \int_{T_i} dt \operatorname{Tr}[(w_{\delta} * [\mu \cdot \rho])(t)Q(t)] - \mu(T_i) \sum_{j \in N_{\delta}(i)} \operatorname{Tr}[Q_j \rho(t_i)] \\ = \int_{T_i} d\mu(t) \left\{ \operatorname{Tr}[\rho(t)(w_{\delta} * Q)(t)] - \sum_{j \in N_{\delta}(i)} \operatorname{Tr}[Q_j \rho(t_i)] \right\}. \qquad (274) $$

First, note that as $Q(t)$ is a POVM, $\|(w_{\delta} * Q)(t)\|_{\infty} \le 1$. Thus, by Hölder's inequality:

$$ \int_{T_i} d\mu(t) \operatorname{Tr}[(\rho(t) - \rho(t_i))(w_{\delta} * Q)(t)] \le \int_{T_i} d\mu(t) \|\rho(t) - \rho(t_i)\|_{1} \|(w_{\delta} * Q)(t)\|_{\infty} \qquad (275) $$

$$ \le \mu(T_i)C_{\rho}\Delta, \qquad (276) $$
where we used Lemma 34 to bound the 1-norm. From this we conclude that:

$$ \left| \int_{T_i} dt \, \mu(t) \left\{ \mathrm{Tr}[\rho(t)(w_\delta * Q)(t)] - \sum_{j \in N_\delta(i)} \mathrm{Tr}[Q_j \rho(t_i)] \right\} \right| \qquad (277) $$

$$ = \left| \int_{T_i} d\mu(t) \left\{ \mathrm{Tr}[\rho(t) - \rho(t_i)](w_\delta * Q)(t) + \mathrm{Tr}\left[\rho(t_i) \left( (w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j \right) \right] \right\} \right| \qquad (278) $$

$$ \leq \mu(T_i) C_\rho \Delta + \left| \int_{T_i} d\mu(t) \mathrm{Tr} \left[ \rho(t_i) \left( (w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j \right) \right] \right| \qquad (279) $$

Let us now estimate the second term in the RHS of the last equation. Again applying a combination of Hölder and triangle inequalities,

$$ \left| \int_{T_i} d\mu(t) \left\{ \mathrm{Tr} \left[ \rho(t_i) \left( (w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j \right) \right] \right\} \right| \le \int_{T_i} d\mu(t) \|\rho(t_i)\|_1 \|(w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j\|_\infty \qquad (280) $$

By Lemma 35 we have that:

$$ \int_{T_i} d\mu(t) \|(w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j\|_\infty \le \mu(T_i) \delta \Delta C_\delta \qquad (281) $$

We conclude that

$$ \left| \int_{T_i} d\mu(t) \left\{ \mathrm{Tr}[\rho(t)(w_\delta * Q)(t)] - \sum_{j \in N_\delta(i)} \mathrm{Tr}[Q_j \rho(t_i)] \right\} \right| \le \mu(T_i)(\delta \Delta C_\delta + C_\rho \Delta). \qquad (282) $$

An application of the triangle inequality and summing over all $i$ yields the claim. $\square$

The proof above shows how, given one feasible POVM for the continuous-time version of the metrology problem, it is possible to construct a feasible POVM for the discretization without significantly changing the success probability as long as $\Delta$ is small enough.

We now present the other direction: given one feasible point of the discretized problem, we construct a continuous-time version thereof that is Lipschitz-continuous and whose success probability does not differ significantly from the original value.

Given a feasible POVM of the SDP in Eq. (256), $\{Q_i\}$, we define the continuous POVM $Q(t)$ by linear interpolation, i.e., for some $t = pt_i + (1-p)t_{i+1}$ as

$$ Q(t) := pQ_i + (1-p)Q_{i+1}. \qquad (283) $$

We will now show that this is indeed a POVM and that it is Lipschitz:

**Lemma 37.** Let $\{Q_i\}$ be a family of POVMs such that:

$$ \|Q_i - Q_{i+1}\|_{\infty} \le C_{\delta}\Delta \qquad (284) $$

and define $Q(t)$ as in Eq. (283). Then $Q(t)$ is a POVM and

$$ \|Q(s_1) - Q(s_2)\|_{\infty} \le C_{\delta}\Delta |s_1 - s_2|. \qquad (285) $$

Furthermore, for $t \in T_i$,

$$ \|(w_\delta * Q)(t) - \sum_{j \in N_\delta(i)} Q_j\| \le C_\delta \delta \Delta. \qquad (286) $$
*Proof.* Note that we have that:

$$ \int_{T_i} dt Q(t) = \int_{0}^{1} dp (pQ_i + (1-p)Q_{i+1}) = \frac{1}{2}(Q_i + Q_{i+1}). \qquad (287) $$

summing over all $i$ (recall the periodic boundary conditions) we see that

$$ \int dt Q(t) = \mathbb{I}. \qquad (288) $$

The fact that $Q(t)$ is positive semi-definite is obvious, as it is point-wise the convex combination of positive semi-definite operators, which shows that it is indeed a POVM. Let us now show Eq. (285). For $s_1, s_2 \in T_i$ we have that:

$$ Q(s_1) - Q(s_2) = (s_1 - s_2)(Q_i - Q_{i+1}). \qquad (289) $$

The claim follows by using the Lipschitz continuity of the $Q_i$. For $s_1, s_2$ in different intervals, say $s_1 \in T_{i_1}, s_2 \in T_{i_2}$ we apply the same argument to the sequence of points $s_1, i_1 + 1, i_1 + 1, i_1 + 2, \dots, i_2, s_2$. To show Eq. (286) we can follow the same route as for Eq. (266), as we have already established that the POVM is Lipschitz. $\square$

Now we have constructed a candidate for a feasible point of the continuous-time problem given a feasible point of the discrete problem. We will show below that the value they achieve is also close, which will lead us to conclude that the discretized and the continuous problems have comparable values for small enough values of $\Delta$.

**Proposition 38.** For given $\delta, C_\delta > 0$ and $\Delta < \delta, < 1$, let $\eta_\delta$ be the value of Eq. (252) when restricted to POVMs that are Lipschitz with Lipschitz constant at most $C_\delta$. Furthermore, assume that $\rho(t)$ is Lipschitz with constant $C_\rho$. Then the value of the SDP in Eq. (256), $\eta_{\delta,\Delta}$, satisfies:

$$ |\eta_{\delta} - \eta_{\delta,\Delta}| \le (C_{\rho} + C_{\delta})\Delta. \qquad (290) $$

*Proof.* It follows from Proposition 36 that, starting from the continuous version of the problem, we can construct a feasible point of the SDP whose success probability differs by at most $(C_\rho + C_\delta)\Delta$. This gives $\eta_\delta < \eta_{\delta,\Delta} - (C_\rho + C_\delta)\Delta$. On the other hand, Lemma 37 shows how to construct a continuous-time Lipschitz POVM from a feasible point of the SDP whose success probability will differ by at most $(C_\rho + C_\delta)\Delta$. This follows from Eq. (286) and similar reasoning as in Proposition 36. In a nutshell, we first approximate $(w_\delta * Q)(t)$ by $\sum_{j \in N_i(\delta)} Q_j$ on each interval $T_i$. Then we approximate the averaged states on each interval by $\rho(t_i)$. This gives $\eta_\Delta < \eta_\delta - (C_\rho + C_\delta)\Delta$, which yields the claim. $\square$

We can then obtain the convergence to continuous POVMs from the last statement:

**Corollary 39.** For given $\delta, C_\delta > 0$ and $\Delta < \delta$, let $\eta_{\delta,\Delta}$ be the value of Eq. (252) when restricted to POVMs that are Lipschitz with Lipschitz constant at most $C_\delta$ and $\eta$ when only requiring continuity. Furthermore, assume that $\rho(t)$ is Lipschitz with constant $C_\rho$. Then we have:

$$ \eta = \lim_{C_\delta \to \infty} \lim_{\Delta \to 0} \eta_{\delta, \Delta}. \qquad (291) $$

*Proof.* The statement follows from the fact that, by the Stone-Weierstrass theorem, any continuous function can be approximated arbitrarily well by Lipschitz functions. Thus, we can find a sequence of Lipschitz POVMs (with possibly diverging Lipschitz constant) that approximates the target POVM. In turn, these will be approximate arbitrarily well by the discretized SDP as we let $\tau \to 0$ by Proposition 38. This gives the statement. $\square$

It would be interesting to obtain statements about the Lipschitz constant of good POVMs for the metrology task to get more quantitative statements even in the continuous case. Indeed, one intuitively expects that it should not be too advantageous to have POVMs that vary significantly faster than the states $\rho(t)$ themselves. Thus, we leave to future work to investigate if we can always take $C_\delta = \mathcal{O}(C_\rho)$ to obtain a good approximation.
# IV. RELATION TO ENTROPY MEASURES

## A. Max-entropy radius

We can generalize an argument of Ref. [16] that gives an alternative characterization of the success probability in terms of the max-relative entropy [66] as

$$D_{\max}(X \| Y) = \log \inf\{\gamma | X \le \gamma Y\} = \log \lambda_{\max}(Y^{-\frac{1}{2}}XY^{-\frac{1}{2}}) = \log \|Y^{-\frac{1}{2}}XY^{-\frac{1}{2}}\|_{\infty}, \quad (292)$$

for X and Y positive semi-definite and $\text{supp}(X) \subseteq \text{supp}(Y)$, where $\|\cdot\|_{\infty}$ is the operator norm and the last equality holds because $Y^{-\frac{1}{2}}XY^{-\frac{1}{2}}$ is positive semi-definite. Indeed, we have the following corollary of Proposition 1.

**Corollary 6 (Max-entropy radius).** For a given set of states $\rho(t)$ with prior distribution $\mu(t)$, we define its max-relative entropy radius with respect to the window function $w(t)$ as

$$r_{\max}(w, \mu, \rho) = \inf_{\sigma} \sup_{t} D_{\max}((w * [\mu \cdot \rho])(t) \|\sigma), \quad (293)$$

where we optimize over arbitrary quantum states $\sigma$. We have that

$$r_{\max}(w, \mu, \rho) = \log \eta^*(w, \mu, \rho). \quad (294)$$

*Proof.* This follows immediately from Proposition 1, (132), and Lemma 29. □

The above corollary implies the following upper bound on the success probability **Corollary 7.** For any state $\sigma$, we have that

$$\eta^*(w, \mu, \rho) \le \exp \sup_t D_{\max}((w * [\mu\rho])(t) \|\sigma). \quad (295)$$

## B. Conditional min-entropy

We can also relate the Bayesian success probability $\eta^*(w, \mu, \rho)$ to the conditional min-entropy [65], which is defined as

$$H_{\min}(A | B)_{\rho} := - \inf_{\substack{\sigma_B \ge 0 \\ \text{Tr}[\sigma_B]=1}} D_{\max}(\rho_{AB} \| \mathbb{I}_A \otimes \sigma_B), \quad (296)$$

for arbitrary positive semi-definite operators $\rho_{AB}$, where $D_{\max}$ is defined in (292).

**Corollary 40.** For a given set of states $\rho(t)$ with prior distribution $\mu(t)$, and a window function $w$, the optimal success probability $\eta^*(w, \mu, \rho)$ is given by

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

where $P_{TS}$ is the classical-quantum operator [46]

$$P_{TS} := \int dt |t\rangle\langle t|_T \otimes (w * [\mu \cdot \rho])(t)_S. \quad (298)$$

*Proof.* This is a straightforward consequence of definitions. Using the definition of $D_{\max}$ in (292), we have that, for all states $\sigma_S$,

$$\begin{align}
D_{\max}(P_{TS} \| \mathbb{I}_T \otimes \sigma_S) &= \log \left\| \sigma_S^{-\frac{1}{2}} P_{TS} \sigma_S^{-\frac{1}{2}} \right\|_{\infty} \tag{299} \\
&= \left\| \int dt |t\rangle\langle t| \otimes \sigma_S^{-\frac{1}{2}} (w * [\mu \cdot \rho_S])(t) \sigma_S^{-\frac{1}{2}} \right\|_{\infty} \nonumber \\
&= \sup_t \left\| \sigma_S^{-\frac{1}{2}} (w * [\mu \cdot \rho])(t) \sigma_S^{-\frac{1}{2}} \right\|_{\infty} \nonumber \\
&= \sup_t D_{\max}((w * [\mu \cdot \rho])(t) \|\sigma). \nonumber
\end{align}$$

Therefore,

$$\inf_{\substack{\sigma_S \ge 0 \\ \text{Tr}[\sigma_S]=1}} D_{\max}(P_{TS} \| \mathbb{I}_T \otimes \sigma_S) = \inf_{\substack{\sigma \ge 0 \\ \text{Tr}[\sigma]=1}} \sup_t D_{\max}((w * [\mu \cdot \rho])(t) \| \sigma) = \log \eta^*(w, \mu, \rho), \quad (300)$$

which implies the desired result, where for the last equality we have used Corollary 6. □
# V. PROPERTIES OF THE PROPOSED QUANTIFIERS

In this section, we outline some properties of the proposed quantities.

## A. Properties of the unoptimized quantifiers

In this section, we outline some properties of the Bayesian success probability $\eta$ and the minimax success probability $\bar{\eta}$. We first establish that the Bayesian success probability is continuous in all arguments:

**Proposition 8 (Continuity properties of the Bayesian success probability).** *The Bayesian success probability $\eta$ has continuity*

(i) in the window function as

$$|\eta(w, \mu, \rho, Q) - \eta(w', \mu, \rho, Q)| \le \|w - w'\|_{\infty}, \qquad (301)$$

(ii) in the measure as

$$|\eta(w, \mu, \rho, Q) - \eta(w, \mu', \rho, Q)| \le \frac{1}{2} \|\mu - \mu'\|_{1}, \qquad (302)$$

(iii) in the state set as

$$|\eta(w, \mu, \rho, Q) - \eta(w, \mu, \rho', Q)| \le \int d\mu(t) \|\rho(t) - \rho'(t)\|_{1} \le \max_{t} \|\rho(t) - \rho'(t)\|_{1}, \qquad (303)$$

(iv) jointly in measure and state set as

$$|\eta(w, \mu, \rho, Q) - \eta(w, \mu', \rho', Q)| \le \int dt \|\mu(t)\rho(t) - \mu'(t)\rho'(t)\|_{1}, \qquad (304)$$

(v) in the measurement as

$$\begin{aligned} |\eta(w, \mu, \rho, Q) - \eta(w, \mu, \rho, Q')| & \le \int d\mu(t) \left\| \int d\tau w(t-\tau) [Q(\tau) - Q'(\tau)] \right\|_{\infty} \\ & \le \left( \int d\tau w(\tau) \right) \max_{t} \|Q(t) - Q'(t)\|_{\infty}. \end{aligned} \qquad (305)$$

*Proof.* The properties are shown as follows.

(i) follows because

$$\begin{aligned} |\eta(w, \mu, \rho, Q) - \eta(w', \mu, \rho, Q)| &= \left| \int d\mu(t) d\tau [w(\tau) - w'(\tau)] \operatorname{Tr}[Q(t-\tau)\rho(t)] \right| \\ &= \int d\tau [w(\tau) - w'(\tau)] \int d\mu(t) \operatorname{Tr}[Q(t-\tau)\rho(t)] \\ &\le \int d\tau |w(\tau) - w'(\tau)| \int d\mu(t) \operatorname{Tr}[Q(t-\tau)\rho(t)] \\ &\le \left( \max_{t} |w(t) - w'(t)| \right) \int d\tau d\mu(t) \operatorname{Tr}[Q(t-\tau)\rho(t)] \\ &= \|w - w'\|_{\infty}. \end{aligned} \qquad (306)$$

(ii) follows from the change of measure inequality [146],

$$\mathbb{E}_{\mu(t)}[\phi(t)] \le \mathbb{E}_{\mu'(t)}[\phi(t)] + \frac{1}{2} \|\mu - \mu'\|_{1}, \qquad (307)$$

which is valid if $0 \le \phi(t) \le 1$ when we note that

$$\eta(w, \mu, \rho, Q) = \mathbb{E}_{\mu} \{ \operatorname{Tr}[\rho(t)(w * Q)(t)] \} \qquad (308)$$

is exactly of that form. The statement follows by symmetrizing through exchange of $\mu$ and $\mu'$.
(iii) directly follows from item (iv).

(iv) follows from the short rearrangement

$$ \begin{aligned} |\eta(w, \mu, \rho, Q) - \eta(w, \mu', \rho', Q)| &= \left| \int dt \, d\tau \, w(t-\tau) \operatorname{Tr}[Q(\tau)[\mu(t)\rho(t) - \mu'(t)\rho'(t)]] \right| \\ &= \left| \int dt \, \operatorname{Tr} \left[ \left( \int d\tau \, w(t-\tau)Q(\tau) \right) [\mu(t)\rho(t) - \mu'(t)\rho'(t)] \right] \right| \\ &\le \left| \int dt \, \operatorname{Tr} [\mu(t)\rho(t) - \mu'(t)\rho'(t)] \right| \\ &\le \int dt \, \|\mu(t)\rho(t) - \mu'(t)\rho'(t)\|_{1}, \end{aligned} \quad (309) $$

where we have used the matrix Hölder inequality and exploited the fact that $\int d\tau w(t-\tau)Q(\tau) \le bI$ because $Q(\tau)$ is a POVM.

(v) follows from

$$ \begin{aligned} |\eta(w, \mu, \rho, Q) - \eta(w, \mu, \rho, Q')| &= \left| \int d\mu(t) d\tau w(t-\tau) \operatorname{Tr}[Q(\tau) - Q'(\tau)] \rho(t) \right| \\ &= \left| \int d\mu(t) \operatorname{Tr} \left[ \rho(t) \left( \int d\tau w(t-\tau) [Q(\tau) - Q'(\tau)] \right) \right] \right| \\ &\le \int d\mu(t) \left\| \int d\tau w(t-\tau) [Q(\tau) - Q'(\tau)] \right\|_{\infty} \\ &\le \max_{t} \left\| \int d\tau w(t-\tau) [Q(\tau) - Q'(\tau)] \right\|_{\infty} \\ &\le \left( \int d\tau w(\tau) \right) \max_{t} \|Q(t) - Q'(t)\|_{\infty}, \end{aligned} \quad (310) $$

where we have used the matrix Hölder inequality.

□

We can exploit the linearity and positivity of the success probability in its arguments to establish majorization-type statements as follows.

**Proposition 9 (Majorization properties of the Bayesian success probability).** The Bayesian success probability $\eta$ has the following majorization properties:

(i) Let $w_-(t)$ and $w_+(t)$ be two functions such that $w_-(t) \le w(t) \le w_+(t)$ for all $t$. Then

$$ \eta(w_-, \mu, \rho, Q) \le \eta(w, \mu, \rho, Q) \le \eta(w_+, \mu, \rho, Q). \quad (311) $$

(ii) Let $g_-(t)X_-(t)$ and $g_+(t)X_+(t)$ be sets of operators such that $g_-(t)X_-(t) \le \mu(t)\rho(t) \le g_+(t)X_+(t)$ for all $t$. Then

$$ \eta(w, g_-, X_-, Q) \le \eta(w, \mu, \rho, Q) \le \eta(w, g_+, X_+, Q). \quad (312) $$

This directly implies similar statements when only measure or states are changed.

(iii) Let $X_-(t)$ and $X_+(t)$ be sets of operators such that $X_-(t) \le Q(t) \le X_+(t)$ for all $t$. Then

$$ \eta(w, \mu, \rho, X_-) \le \eta(w, \mu, \rho, Q) \le \eta(w, \mu, \rho, X_+). \quad (313) $$

*Proof.* The properties directly follow from the linearity of $\eta$ in its arguments and the fact that the arguments which are not bounded above and below are non-negative. □

The minimax success probability also has comparable properties, some of which are inherited from the Bayesian success probability:
**Proposition 10** (Continuity properties of the minimax success probability). The minimax success probability $\bar{\eta}$ has continuity

(i) in the window function

$$|\bar{\eta}(w, \rho, Q) - \bar{\eta}(w', \rho, Q)| \le \|w - w'\|_{\infty}, \qquad (314)$$

(ii) in the state set

$$|\bar{\eta}(w, \rho, Q) - \bar{\eta}(w, \rho', Q)| \le \max_t \|\rho(t) - \rho'(t)\|_1, \qquad (315)$$

(ii) in the measurement

$$|\bar{\eta}(w, \rho, Q) - \bar{\eta}(w, \rho, Q')| \le \left( \int d\tau w(\tau) \right) \max_t \|Q(t) - Q'(t)\|_{\infty}. \qquad (316)$$

*Proof.* The properties are shown as follows.

(i) Follows from the calculation

$$\begin{aligned}
\bar{\eta}(w, \rho, Q) &= \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)\rho(t)] && (317) \\
&= \min_t \int d\tau [w(t-\tau) + w'(t-\tau) - w'(t-\tau)] \operatorname{Tr}[Q(\tau)\rho(t)] \\
&\le \min_t \int d\tau w'(t-\tau) \operatorname{Tr}[Q(\tau)\rho(t)] + \max_t \int d\tau [w(t-\tau) - w'(t-\tau)] \operatorname{Tr}[Q(\tau)\rho(t)] \\
&\le \bar{\eta}(w', \rho, Q) + \max_t \{w(t-\tau) - w'(t-\tau)\} \\
&\le \bar{\eta}(w', \rho, Q) + \max_t |w(t-\tau) - w'(t-\tau)| \\
&= \bar{\eta}(w', \rho, Q) + \|w - w'\|_{\infty},
\end{aligned}$$

where we have exploited the inequality $\min_t f(t) + g(t) \le \min_t f(t) + \max_t g(t)$ as well as the fact that

$$\int d\tau g(t-\tau)Q(\tau) \le \max_t g(t)\mathbb{I}, \qquad (318)$$

because $Q(\tau)$ is a POVM and the matrix Hölder inequality. The statement is then obtained by symmetrizing, via exchange of $w$ and $w'$.

(ii) follows from the short rearrangement

$$\begin{aligned}
\bar{\eta}(w, \rho, Q) &= \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)\rho(t)] && (319) \\
&= \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)[\rho(t) - \rho'(t) + \rho'(t)]] \\
&\le \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)\rho'(t)] + \max_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)[\rho(t) - \rho'(t)]] \\
&= \bar{\eta}(w, \rho', Q) + \max_t \operatorname{Tr} \left[ \left( \int d\tau w(t-\tau) Q(\tau) \right) [\rho(t) - \rho'(t)] \right] \\
&\le \bar{\eta}(w, \rho', Q) + \max_t \operatorname{Tr} [\rho(t) - \rho'(t)] \\
&\le \bar{\eta}(w, \rho', Q) + \max_t \|\rho(t) - \rho'(t)\|_1,
\end{aligned}$$

where we have exploited the inequality $\min_t f(t) + g(t) \le \min_t f(t) + \max_t g(t)$ as well as

$$\int d\tau w(t-\tau)Q(\tau) \le \mathbb{I}, \qquad (320)$$

because $Q(\tau)$ is a POVM and the matrix Hölder inequality. The statement is then obtained by symmetrizing via exchange of $\rho$ and $\rho'$.
(iii) follows similarly as

$$
\begin{align}
\bar{\eta}(w, \rho, Q) &= \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q(\tau)\rho(t)] \tag{321} \\
&= \min_t \int d\tau w(t-\tau) \operatorname{Tr}[[Q(\tau) - Q'(\tau) + Q'(\tau)]\rho(t)] \nonumber \\
&\le \min_t \int d\tau w(t-\tau) \operatorname{Tr}[Q'(\tau)\rho(t)] + \max_t \int d\tau w(t-\tau) \operatorname{Tr}[[Q(\tau) - Q'(\tau)]\rho(t)] \nonumber \\
&= \bar{\eta}(w, \rho, Q') + \max_t \operatorname{Tr}\left[\left[\left(\int d\tau w(t-\tau)Q(\tau)\right) - \left(\int d\tau w(t-\tau)Q'(\tau)\right)\right]\rho(t)\right] \nonumber \\
&\le \bar{\eta}(w, \rho, Q') + \max_t \left\|\int d\tau w(t-\tau) [Q(\tau) - Q'(\tau)]\right\|_{\infty} \nonumber \\
&\le \bar{\eta}(w, \rho, Q') + \left(\int d\tau w(\tau)\right) \max_t \|Q(\tau) - Q'(\tau)\|_{\infty} \nonumber
\end{align}
$$

where we have exploited the inequality $\min_t f(t) + g(t) \le \min_t f(t) + \max_t g(t)$ as well as the fact that $\int d\tau w(t-\tau)Q(\tau) \le I$ because $Q(\tau)$ is a POVM and the matrix Hölder inequality. The statement is then obtained by symmetrizing via exchange of $\rho$ and $\rho'$.

(ii) directly follows from the same argument as (i) when we note that

$$
\mathrm{Tr}[Q(\tau)\rho_{-}(t)] \leq \mathrm{Tr}[Q(\tau)\rho(t)] \leq \mathrm{Tr}[Q(\tau)\rho_{+}(t)], \quad (322)
$$

and hence the same ordering holds for the minimum.

(iii) directly follows from the same argument as (i) when we note that

$$
\mathrm{Tr}[Q_{-}(\tau)\rho(t)] \leq \mathrm{Tr}[Q(\tau)\rho(t)] \leq \mathrm{Tr}[Q_{+}(\tau)\rho(t)]. \quad (323)
$$

and hence the same ordering holds for the minimum.

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

Note that some of these continuity bounds are necessarily loose as the other parameters could be chosen in a
particularly pathological way.

The minimax success probability has majorization properties similar to the ones of the Bayesian success probability:

**Proposition 11 (Majorization properties of the minimax success probability).** The minimax success probability $\bar{\eta}$ has the following majorization properties:

(i) Let $w_-(t)$ and $w_+(t)$ be two functions such that $w_-(t) \le w(t) \le w_+(t)$ for all $t$. Then

$$
\bar{\eta}(w_{-}, \rho, Q) \leq \bar{\eta}(w, \rho, Q) \leq \bar{\eta}(w_{+}, \rho, Q). \tag{324}
$$

(ii) Let $X_-(t)$ and $X_+(t)$ be sets of operators such that $X_-(t) \le \rho(t) \le X_+(t)$ for all $t$. Then

$$
\bar{\eta}(w, X_{-}, Q) \leq \bar{\eta}(w, \rho, Q) \leq \bar{\eta}(w, X_{+}, Q). \quad (325)
$$

(iii) Let $X_-(t)$ and $X_+(t)$ be sets of operators such that $X_-(t) \le Q(t) \le X_+(t)$ for all $t$. Then

$$
\bar{\eta}(w, \rho, X_{-}) \leq \bar{\eta}(w, \rho, Q) \leq \bar{\eta}(w, \rho, X_{+}). \quad (326)
$$

Additionally, it has

(iv) monotonicity in the state set:

$$
\{\rho'(t)\}_t \subseteq \{\rho(t)\}_t \Rightarrow \bar{\eta}(w, \rho, Q) \le \bar{\eta}(w, \rho', Q). \quad (327)
$$

*Proof.* The properties directly follow from the fact that $\bar{\eta}$ is the result of a minimization of a linear function and the fact that the arguments which are not bounded above and below are non-negative. Item (iv) follows from the simple observation that the set of all measures over $\{\rho(t)\}_t$ includes all measures over $\{\rho'(t)\}_t$ and hence the optimization is bound to yield a higher value. $\square$
## B. Properties of the optimized quantities

As outcomes of a convex optimization, the optimized quantities fulfill convexity in the remaining parameters:

**Proposition 12 (Convexity).** The optimized Bayesian success probabilities $\eta^*(w, \mu, \rho)$, $\eta^*(w, \mu, \mathcal{N}, Q)$ and $\eta^*(w, \mu, \mathcal{N})$ are convex in all arguments and especially fulfill a triangle inequality in the window function.

*Proof.* The convexity of the Bayesian quantities is a direct consequence of linearity and the fact that

$$ \sup_Q f(Q) + g(Q) \le \sup_Q f(Q) + \sup_Q g(Q). \qquad (328) $$

The triangle inequality in the window function follows similarly.

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

The optimized probabilities also fulfill a type of data processing inequality:

**Proposition 13 (Data processing).** The optimized Bayesian success probabilities obey the following data-processing inequalities

$$ \eta^*(w, \mu, \mathcal{N}[\rho(\cdot)]) \le \eta^*(w, \mu, \rho(\cdot)), \qquad (329) $$

$$ \eta^*(w, \mu, \mathcal{N}(\cdot) \circ A, Q) \le \eta^*(w, \mu, \mathcal{N}(\cdot), Q), \qquad (330) $$

$$ \eta^*(w, \mu, B \circ \mathcal{N}(\cdot) \circ A) \le \eta^*(w, \mu, \mathcal{N}(\cdot)), \qquad (331) $$

which directly imply similar statements for the optimized minimax success probabilities

$$ \bar{\eta}^*(w, \mathcal{N}[\rho(\cdot)]) \le \bar{\eta}^*(w, \rho(\cdot)), \qquad (332) $$

$$ \bar{\eta}^*(w, \mathcal{N}(\cdot) \circ A, Q) \le \bar{\eta}^*(w, \mathcal{N}(\cdot), Q), \qquad (333) $$

$$ \bar{\eta}^*(w, B \circ \mathcal{N}(\cdot) \circ A) \le \bar{\eta}^*(w, \mathcal{N}(\cdot)), \qquad (334) $$

*Proof.* Denote with $\mathcal{Q}$ the set of all POVMs and with $\mathcal{N}[\mathcal{Q}]$ its image under a quantum channel $\mathcal{N}$. We note that for all quantum channels, we have that $\mathcal{N}^{\dagger}[\mathcal{Q}] \subseteq \mathcal{Q}$ due to the CPTP property of $\mathcal{N}$, which implies that $\mathcal{N}^{\dagger}$ is completely positive and unital. Then, we find

$$ \eta^*(w, \mu, \mathcal{N}[\rho(\cdot)]) = \sup_{Q(t) \in \mathcal{Q}} \int d\mu(t) d\tau w(t-\tau) \mathrm{Tr}[\mathcal{N}[\rho(t)]Q(\tau)] \qquad (335) $$

$$ = \sup_{Q(t) \in \mathcal{Q}} \int d\mu(t) d\tau w(t-\tau) \mathrm{Tr}[\rho(t)\mathcal{N}^{\dagger}[Q(\tau)]] $$

$$ = \sup_{Q'(t) \in \mathcal{N}^{\dagger}[\mathcal{Q}]} \int d\mu(t) d\tau w(t-\tau) \mathrm{Tr}[\rho(t)Q'(\tau)] $$

$$ \le \sup_{Q'(t) \in \mathcal{Q}} \int d\mu(t) d\tau w(t-\tau) \mathrm{Tr}[\rho(t)Q'(\tau)] $$

$$ = \eta^*(w, \mu, \rho(\cdot)), $$

where we have used the fact that a value optimized over a subset can never exceed the value of the fully optimized case. The minimax result is implied as the Bayesian statement holds independently of the prior. Similar arguments give rise to the statements for optimization over input states and joint optimization of probe and measurement. $\square$

## C. Subdivision trick

We now prove the subdivision trick of the main text.

*Proof of Lemma 6.* The proof follows a similar idea as the proof outlined for the reduction of multi-hypothesis testing to the binary case in Ref. [16]. We consider the case in which, additionally to the (unknown) state $\rho(t)$ with $t$ sampled according to $\mu(t)$, an oracle supplies us the information that $t$ lies in a certain interval $I_{t'}$ where the oracle samples $t'$ uniformly from $I_{t'}$, i.e., it uniformly randomly samples one of the intervals of size $T$ containing $t$. With this additional information available, we can restrict our attention to the interval $I_{t'}$ and perform a Bayesian update of our prior
which means we now deal with $\mu|_{I_{t'}}$. We can then perform the optimal strategy for this prior. As the additional information can only improve our estimate, we obtain

$$ \eta^*(\delta, \rho, \mu) \leq \int d\mu(t) \int dt' \mathbb{P}[t' | t] \eta^*(\delta, \rho, \mu|_{I_{t'}}) \quad (336) $$

$$ = \int d\mu(t) \int dt' \frac{1}{T} \chi[t' \in I_t] \eta^*(\delta, \rho, \mu|_{I_{t'}}) \quad (337) $$

$$ = \int d\mu(t) \int dt' \frac{1}{T} \chi[t \in I_{t'}] \eta^*(\delta, \rho, \mu|_{I_{t'}}) \quad (338) $$

$$ = \frac{1}{T} \int dt' \mu(I_{t'}) \eta^*(\delta, \rho, \mu|_{I_{t'}}). \quad (339) $$

Renaming $t'$ to $t$ yields the first statement of the lemma. The second statement follows by bounding $\eta^*(\delta, \rho, \mu|_{I_{t'}})$ by its maximum over $t'$ and recognizing that

$$ \frac{1}{T} \int dt' \mu(I_{t'}) = \frac{1}{T} \int dt' \int_{I_{t'}} dt \, \mu(t) \quad (340) $$

$$ = \frac{1}{T} \int dt' \int dt \, \mu(t) \chi[|t - t'| \le T/2] \quad (341) $$

$$ = \frac{1}{T} \int dt \, \mu(t) T \quad (342) $$

$$ = 1. \quad (343) $$

□

## VI. OPTIMAL POST-PROCESSING WITH FIXED MEASUREMENT

In this section, we give additional content relative to Section III B of the main text. There, it was established in Eq. (33) that the success probability for the smoothed maximum a posteriori estimate relates to the function infinite norm of the smoothed posterior probability:

$$ \eta(\delta, \mu, \rho, Q_{M, \tau_{\text{SMAP}}^*}) = \int d\nu(\lambda) \max_{\tau} (w_{\delta} * P(\cdot | \lambda))(\tau) \quad (344) $$

$$ = \int d\nu(\lambda) \|w_{\delta} * P(\cdot | \lambda)\|_{\infty}. \quad (345) $$

The connection to the infinity norm allows us to derive some simple upper bounds by applying Young's convolution inequality [147]:

**Lemma 14.** *The success probability of the smoothed maximum a posteriori estimate obeys the upper bound*

$$ \eta(w, \mu, \rho, Q_{M, \tau_{\text{SMAP}}^*}) \le \|w\|_p \int d\nu(\lambda) \|P(\cdot | \lambda)\|_q \quad (345) $$

for all $1/p + 1/q = 1$.

The above inequality immediately trivializes when choosing $p = \infty$, $q = 1$ but yields a non-trivial upper bound otherwise. This can be useful, when for example an upper bound on the likelihood is known.

A particularly interesting property of the smoothed maximum a posteriori estimate, of which we will use a discrete analogue later to relate metrology to binary hypothesis testing, is the following bound on contributions to the error for the $\delta$ window, which makes the dependence on the window size explicit:

**Lemma 15.** *For any interval $I$ of cardinality $|I| \le 2\delta$, define its $\delta$-complement as*

$$ \bar{I}^{\delta} := \{t \mid \text{there exists } t' \in I \text{ such that } |t - t'| > 2\delta\}. \quad (346) $$

Then, for any interval $I$ outside the smoothed maximum a posteriori interval, i.e., any interval contributing to the error, we have that

$$ \int_I dt P(t | \lambda) \le \int_{\bar{I}^\delta} dt P(t | \lambda) \quad (347) $$

for all $\lambda$.
*Proof.* Let us denote the smoothed maximum a posteriori interval as $I^* = [\tau_{\text{SMAP}}^*(\lambda) - \delta, \tau_{\text{SMAP}}^*(\lambda) + \delta]$. Then, by definition of the smoothed maximum a posteriori estimate, we have that

$$ \int_J dt P(t | \lambda) \le \int_{I^*} dt P(t | \lambda) \qquad (348) $$

for all compact intervals $J$ of cardinality $|J| = 2\delta$. We can exploit this and optimize over all intervals $J$ that contain the target interval $I$ to obtain

$$ \int_I dt P(t | \lambda) \le \inf_{J: |J|=2\delta, I \subseteq J} \int_{I^* \setminus J} dt P(t | \lambda), \qquad (349) $$

where we implicitly made use of the assumption that $I$ lies outside of $I^*$, i.e., that $I \cap I^* = \emptyset$. By construction, $\bar{I}^\delta$ is the complement of the union of all possible $J$ of cardinality $2\delta$ that contain $I$, which is exactly what we achieve as well on the right hand side by choosing the smallest interval $I^* \setminus J$, making the interval achieving the optimization a subinterval of $\bar{I}^\delta$. Extending the integration to all of $\bar{I}^\delta$ yields the statement of the lemma. $\square$

The further study of upper and lower bounds for the smoothed maximum a posteriori strategy would be a promising direction for future research, especially to relate to concepts of classical statistics.

# VII. RELATION TO HYPOTHESIS TESTING

## A. Multi-hypothesis testing as a special case of metrology

The notions introduced above can be considered as a continuous generalization of the discrete multi-hypothesis testing problem for quantum states and quantum channels, respectively. In the multi-hypothesis testing problem for quantum states, one is given a set of states $\{\rho_i\}_{i=1}^m$ – in the Bayesian setting with associated prior probabilities $\{p_i\}_{i=1}^m$ – and is tasked to find a measurement given by POVM effects $\{Q_i\}_{i=1}^m$ that maximizes the success probability [16, 17]

$$ P_s(\{p_i \rho_i\}_{i=1}^m) = \sup_{\{Q_i\}_{i=1}^m} \sum_{i=1}^m p_i \operatorname{Tr}[\rho_i Q_i]. \qquad (350) $$

In a similar way, one can define the associated minimax multi-hypothesis testing problem where we desired to find a measurement

$$ \bar{P}_s(\{\rho_i\}_{i=1}^m) = \sup_{\{Q_i\}_{i=1}^m} \min \operatorname{Tr}[\rho_i Q_i] \qquad (351) $$

with optimal worst-case performance. The *hypothesis testing* has in the binary case already been solved by Helstrom and Holevo [62, 148]. In particular, the optimal success probability has been determined by them in seminal work to be

$$ P_s(p\rho_1, (1-p)\rho_2) = \frac{1}{2} + \frac{1}{2}\|p\rho_1 - (1-p)\rho_2\|_1, \qquad (352) $$

where $\|\cdot\|_1$ denotes the trace or nuclear norm. In general, it is known that [65]

$$ P_s(\{p_i \rho_i\}_{i=1}^m) = 2^{-H_{\min}(X|B)_{\rho}}, \qquad (353) $$

where $H_{\min}(X|B) = -\inf_{\sigma_B \ge 0, \text{Tr}[\sigma_B]=1} D_{\max}(\rho_{XB} \| \mathbb{I}_X \otimes \sigma_B)$ is the conditional min-entropy and $\rho_{XB} = \sum_{i=1}^m p_i |i\rangle\langle i| \otimes \rho_i$. It has been shown in Ref. [15] that the asymptotic rates for the Bayesian and minimax multi-hypothesis testing problem coincide and are given by the minimal pairwise Chernoff divergence

$$ \bar{R}(\{\rho_i\}_{i=1}^m) = \lim_{n \to \infty} \frac{1}{n} \log(1 - \bar{P}_s(\{\rho_i\}_{i=1}^m)) = - \log \min_{i \neq j \ 0 \le s \le 1} \min \operatorname{Tr}[\rho_i^s \rho_j^{1-s}]. \qquad (354) $$

It now becomes clear that our notion of success for quantum metrology encompasses the quantum multi-hypothesis testing problem when we consider the following metrological problem that embeds a multi-hypothesis testing problem. Consider the following prior over states,

$$ \mu(t) = \sum_{i=1}^{m} p_i \delta(t - i), \qquad (355) $$
together with any parametrized state $\rho(t)$ such that $\rho(i) = \rho_i$ and a window function

$$w_{1/3}(t) = \begin{cases} 1 & \text{if } |t| \le 1/3 \\ 0 & \text{else.} \end{cases} \qquad (356)$$

It is obvious that

$$\eta^*(w_{1/3}, \mu, \rho) = P_s(\{p_i \rho_i\}_{i=1}^m). \qquad (357)$$

Later in this manuscript, we make use of this property to derive upper bounds on the metrological success probability from binary state discrimination.

In a similar way, we can consider the problem of multi-hypothesis testing for quantum channels. In this case, a discrete set of quantum channels $\{\mathcal{N}_i\}_{i=1}^m$, possibly again with prior probabilities $\{p_i\}_{i=1}^m$, is given and the optimal experimental prescription for distinguishing between these quantum channels is to be found. In the single-copy case, we need to find an input state $\rho_0$ and a measurement $\{Q_i\}_{i=1}^m$ that maximizes the success probability

$$P_s(\{p_i \mathcal{N}_i\}_{i=1}^m) = \sup_{\rho_0, \{Q_i\}_{i=1}^m} \sum_{i=1}^{m} p_i \operatorname{Tr}[\mathcal{N}_i[\rho_0]Q_i]. \qquad (358)$$

Using again the prior $\mu(t)$ of Eq. (355) together with any parametrized channel $\mathcal{N}(t)$ such that $\mathcal{N}(i) = \mathcal{N}_i$ and the window function $w_{1/3}$ of Eq. (356), we see that the success probability is given by the corresponding metrological success probability:

$$\eta^*(w_{1/3}, \mu, \mathcal{N}) = P_s(\{p_i \mathcal{N}_i\}_{i=1}^m). \qquad (359)$$

As we outlined in the preceding section, in the setting where multiple copies are available, there are different possible ways of using the quantum channel in question, corresponding to the i.i.d. case where the same input state is used repetitively, the separable case where only separable states are used as inputs, the parallel case where an entangled state is prepared and fed through the quantum channel and the adaptive case where a quantum comb is used. The success probabilities we defined in these cases naturally generalize the same notions available in the multi-hypothesis testing problem for channels.

## B. Upper bound on success probability from multi-hypothesis testing

In this section, we prove Theorem 10 of the main text and discuss its extensions to arbitrary window functions and quantum channels.

**Theorem 16.** For a given window function $w$, fix any set $S = \{(\lambda, s)\}$ of prior probabilities $\lambda \ge 0$ and shifts $s \in \mathbb{R}$ such that $\sum_{\lambda \in S} \lambda = 1$. Then, for a state set $\rho(t)$, possibly with prior $\mu(t)$, we have the upper bounds

$$\eta^*(w, \mu, \rho) \le K \int dt P_s^*(\{\lambda \mu(t+s)\rho(t+s)\}_{(\lambda,s) \in S}), \qquad (360)$$

$$\bar{\eta}^*(w, \rho) \le K \inf_t \bar{P}_s^*(\{\rho(t+s)\}_{s \in S}), \qquad (361)$$

where we introduced the constant

$$K := \sup_t \left\{ \sum_{s \in S} w(t+s) \right\}, \qquad (362)$$

which measures the overlap of the windows for the different shifts.

*Proof.* First, we recall the definition of the optimal multi-hypothesis testing success probability for a set of operators $\{A_i\}$:

$$P_s^*(\{A_i\}) := \sup_{\substack{0 \le Q_i \le \mathbb{I} \\ \sum_i Q_i = \mathbb{I}}} \sum_i \operatorname{Tr}[A_i Q_i]. \qquad (363)$$
We exploit that we can shift the time axis of the integration that computes the success probability arbitrarily, to observe that

$$ \eta(w, \mu, \rho, Q) = \sum_{(\lambda, s) \in S} \int dt \, \lambda \operatorname{Tr}[\mu(t+s)\rho(t+s)(w*Q)(t+s)]. \quad (364) $$

Using the definition of K given in the theorem statement, we see that defining the operators

$$ Q_s(t) := \frac{1}{K} (w * Q)(t+s) \quad (365) $$

yields a valid sub-normalized POVM for all t as

$$ \begin{align} \sum_{s \in S} Q_s(t) &= \frac{1}{K} \sum_{s \in S} (w * Q)(t+s) \tag{366} \\ &\le \frac{1}{K} \left( \left[ \sum_{s \in S} w(\cdot + s) \right] * Q \right) (t) \nonumber \\ &\le \frac{1}{K} (K * Q)(t) \nonumber \\ &= (1 * Q)(t) \nonumber \\ &= \mathbb{I}. \nonumber \end{align} $$

This means that the operators {$Q_s$}$_{s \in S}$ can serve as a candidate POVM in the optimization that computes $P_s(\{\lambda \mu(t+s)\rho(t+s)\}_{(\lambda,s) \in S})$, and hence

$$ \eta(w, \mu, \rho, Q) \le K \int dt P_s^*(\{\lambda \mu(t+s)\rho(t+s)\}_{(\lambda,s) \in S}) \quad (367) $$

which implies the first statement of the theorem as the upper bound is independent of the chosen POVM $Q(t)$.

The minimax statement is derived in a similar fashion, observing that we can also apply the time shifting trick to obtain

$$ \begin{align} \bar{\eta}(w, \rho, Q) &= \sum_{(\lambda, s) \in S} \lambda \inf_t \operatorname{Tr}[\rho(t+s)(w * Q)(t+s)] \tag{368} \\ &\le \inf_t \sum_{(\lambda, s) \in S} \lambda \operatorname{Tr}[\rho(t+s)(w * Q)(t+s)]. \nonumber \end{align} $$

Here, we again make the argument that the {$Q_s$}$_{s \in S}$ form a candidate POVM and then optimize over all possible $\lambda$ to obtain the theorem statement. □

Note that if $K$ in the above theorem is larger than the inverse success probability, then the bound becomes vacuous. This means, as the success probability asymptotically approaches 1, any bound that should work asymptotically must have $K = 1$. Let us now prove the Theorem from the main text:

*Proof of Theorem 10.* In the case of a rectangular window with tolerance $\delta$, we have that as long as $|s - s'| > 2\delta$ for any two shifts in $S$, that the rectangular windows do not overlap. Therefore, under the assumptions of Theorem 10, we have that $K = 1$ and the statement therefore directly follows from Theorem 16. □

Next, we present a corollary of Theorem 16 that extends the statement to metrology protocols defined with respect to channels. In this setting, the success probability is defined as a joint optimization over the input state and the POVM, possibly using an ancillary system:

$$ P_s^*(\{p_i, \mathcal{N}_i\}) := \sup \left\{ \sum_i p_i \operatorname{Tr}[(\mathbb{I} \otimes \mathcal{N}_i)[\rho_0]Q_i] \mid \rho_0 \ge 0, \operatorname{Tr}[\rho_0] = 1, 0 \le Q_i \le \mathbb{I}, \sum_i Q_i = \mathbb{I} \right\}. \quad (369) $$

The minimax success probability is defined analogously by optimizing the minimum over $i$. With these notions in place, we obtain the following statement:
**Corollary 17** (Upper bound on success probability). For a given window function $w$, fix any set $S = \{(\lambda, s)\}$ of prior probabilities $\lambda \ge 0$ and shifts $s \in \mathbb{R}$ such that $\sum_{\lambda \in S} \lambda = 1$. Then, for a channel set $\mathcal{N}(t)$, possibly with prior $\mu(t)$, we have the upper bounds

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

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

where the constant $K$ is defined in Eq. (362).

*Proof.* Theorem 16 is valid for any set of states, which means it also applies when $\rho(t) = (\mathbb{I} \otimes \mathcal{N}(t))[\rho_0]$ for the optimal probe state $\rho_0$. The fact that the optimal success probability for discriminating quantum channels is obtained by optimizing over $\rho_0$ and $Q(t)$ implies the corollary. $\square$

Similar statements are readily obtained for adaptive discrimination of multiple channel copies and other variants of the channel metrology task.

### C. Upper bound via binary hypothesis testing

In this section, we will derive some bounds using tools from symmetric hypothesis testing. Our first step is to derive a quantum analog of a Bretagnolle-Huber inequality (see e.g., Ref. [149])

**Theorem 18** (Binary hypothesis testing lower bound). Let $\rho$ and $\sigma$ be two quantum states and $0 \le \lambda \le 1$ a prior probability. Then, the optimal binary hypothesis testing error can be bounded from below via the fidelity as

$$ P_e^*(\lambda\rho, (1-\lambda)\sigma) \ge \lambda(1-\lambda)F(\rho, \sigma)^2 = \lambda(1-\lambda)\exp(-\tilde{D}_{1/2}(\rho \| \sigma)), \quad (372) $$

where $\tilde{D}_\alpha$ denotes the sandwiched Rényi-relative entropy.

*Proof.* We employ a strategy similar to the proof of Lemma 17 of Ref. [150] (compare also the proof of an analogue classical result in Ref. [149]). To this end, we denote with $A = \lambda\rho$ and $B = (1-\lambda)\sigma$ and write the optimal hypothesis testing success and error probabilities as

$$ P_s^*(A, B) = \mathrm{Tr}[A\Pi_A] + \mathrm{Tr}[B\Pi_B], \quad (373) $$

$$ P_e^*(A, B) = \mathrm{Tr}[A\Pi_B] + \mathrm{Tr}[B\Pi_A], \quad (374) $$

where $\Pi_A$ and $\Pi_B = \mathbb{I} - \Pi_A$ are the optimal POVM effects. Then, we define a CPTP map

$$ \Lambda(X \oplus Y) = \mathrm{Tr}[X\Pi_A \oplus Y\Pi_B] \oplus \mathrm{Tr}[X\Pi_B \oplus Y\Pi_A] \quad (375) $$

such that

$$ \Lambda(A \oplus B) = P_s^*(A, B) \oplus P_e^*(A, B), \quad (376) $$

$$ \Lambda(B \oplus A) = P_e^*(A, B) \oplus P_s^*(A, B). \quad (377) $$

The data-processing property of the fidelity implies that

$$ F(A \oplus B, B \oplus A) = 2\sqrt{\lambda(1-\lambda)}F(\rho, \sigma) \le F(\Lambda[A \oplus B], \Lambda[B \oplus A]) = 2\sqrt{P_s^*(A, B)P_e^*(A, B)}. \quad (378) $$

Using $P_s^*(A, B) \le 1$ and the definition of the sandwiched Rényi relative entropy then yields the statement of the Theorem. $\square$

We can use the above theorem to deduce the following lower bound for metrology:

**Theorem 19** (Two-point error probability lower bound). For a given tolerance $\delta$ and a set of states $\rho(t)$, we have the lower bound

$$ 1 - \bar{\eta}(\bar{\delta}, \rho) \ge \frac{1}{4} \exp \left( - \inf_{|t-t'| \ge 2\bar{\delta}} D_{1/2}(\rho(t) \| \rho(t')) \right) \quad (379) $$

on the minimax success probability.
*Proof.* We start from the upper bound on the minimax success probability derived in Theorem 10. Applied to a single time shift, it especially implies that

$$ \bar{\eta}(\delta, \rho) \leq \inf_t \bar{P}_s^*(\rho(t), \rho(t+2\delta)). \qquad (380) $$

This is equivalent to a lower bound on the minimax error

$$ 1 - \bar{\eta}(\delta, \rho) \geq \sup_t \bar{P}_e^*(\rho(t), \rho(t+2\delta)). \qquad (381) $$

For the sake of simplicity, we will lower bound the optimal minimax error with the one obtained from a uniform prior, i.e.

$$ 1 - \bar{\eta}(\delta, \rho) \geq \sup_{|t-t'|>2\delta} P_e^* \left( \frac{1}{2}\rho(t), \frac{1}{2}\rho(t') \right). \qquad (382) $$

Now, applying Theorem 18 yields

$$ 1 - \bar{\eta}(\delta, \rho) \geq \frac{1}{4} \sup_{|t-t'|>2\delta} F(\rho(t), \rho(t'))^2 \qquad (383) $$

$$ = \frac{1}{4} \exp \left( - \inf_{|t-t'|>2\delta} \tilde{D}_{1/2}(\rho(t) \| \rho(t')) \right) \qquad (384) $$

$$ \geq \frac{1}{4} \exp \left( - \inf_{t} \tilde{D}_{1/2}(\rho(t) \| \rho(t+2\delta)) \right). \qquad (385) $$

□

Corollary 12 of the main text follows immediately.

## D. Upper bound on the success probability from asymmetric hypothesis testing

We can use similar reasoning as in the derivation of Theorem 10 to obtain a lower bound that makes use of asymmetric hypothesis testing. In asymmetric (binary) hypothesis testing, the goal is to determine a measurement {$M, \mathbb{I} - M$} that distinguishes between two hypothesis $\rho$ and $\sigma$, such that the so-called type-II error $\text{Tr}[M\sigma]$ is minimized while maintaining an upper bound of $\epsilon \in [0, 1]$ on the type-I error probability $\text{Tr}[(\mathbb{I} - M)\rho]$. In particular, the optimal type-II error probability is given by [17]

$$ \beta_{\epsilon}(\rho \| \sigma) = \inf\{\text{Tr}[M\sigma] : 0 \le M \le \mathbb{I}, \text{Tr}[M\rho] \ge 1 - \epsilon\}. \qquad (386) $$

The hypothesis testing relative entropy is then defined to be the optimal type-II error exponent, namely,

$$ D_{\text{h}}^{\eta}(\rho \| \sigma) = - \log \beta_{1-\eta}(\rho \| \sigma), \qquad (387) $$

for $\eta \in [0, 1]$.

We can establish the following theorem:

**Theorem 41** (Asymmetric hypothesis testing bound). For a given tolerance $\delta$, fix any set of shifts $S = \{s\}$ such that $|s| > 2\delta$ and for all distinct $s, s' \in S$ we have that $|s - s'| > 2\delta$. Then, for a state set $\rho(t)$ with prior $\mu(t)$ we have the upper bound

$$ \eta(\delta, \rho, \mu, Q) \leq 1 - \int d\mu(t) \sum_{s \in S} \beta_{\text{h}}^{H(t+s)}(\rho(t+s) \| \rho(t)), $$

where we defined the shorthand

$$ H(t) := \text{Tr}[(w_{\delta} * Q)(t)\rho(t)]. \qquad (388) $$

In the minimax case, we have that for all $\bar{\eta} \le \bar{\eta}^*(\delta, \rho)$ that

$$ \bar{\eta}^*(\delta, \rho) \leq 1 - \max_t \sum_{s \in S} \beta_{\text{h}}^{\bar{\eta}}(\rho(t+s) \| \rho(t)). $$
An advantage of this bound is that the asymptotic behavior of the asymmetric hypothesis testing error is better understood than the asymptotics of the symmetric hypothesis testing error and that especially the second-order asymptotics are known.

*Proof.* Our strategy consists of using $(w * Q)(t)$ as a candidate POVM effect for the asymmetric hypothesis test. We first treat the minimax case, where the error probability can be expressed as

$$1 - \bar{\eta}(\delta, \rho, Q) = \max_t \mathrm{Tr}[(\bar{w} * Q)(t)\rho(t)], \qquad (389)$$

where $\bar{w}(t) = 1 - w(t)$ can be seen as the complement of the window function. We now make use of the fact that the set $S$ is defined such that we have $\bar{w}(t) \ge \sum_{s \in S} w(t + s)$ and hence

$$1 - \bar{\eta}(\delta, \rho, Q) \ge \max_t \sum_{s \in S} \mathrm{Tr}[(w(\cdot + s) * Q)(t)\rho(t)] \qquad (390)$$

As the POVM effect $(w * Q)(t + s)$ achieves $\mathrm{Tr}[(w * Q)(t + s)\rho(t + s)] \ge \bar{\eta}(\delta, \rho)$ by definition of the minimax success probability it is a candidate for a binary hypothesis testing and hence

$$1 - \bar{\eta}(\delta, \rho, Q) \ge \max_t \sum_{s \in S} \beta_h^{\bar{\eta}(\delta, \rho)} (\rho(t + s) \| \rho(t)). \qquad (391)$$

The claimed statement follows from the monotonicity of the asymmetric hypothesis testing error and by optimizing the left hand side over the POVM $Q$. For the Bayesian case, we introduce the notation

$$\bar{\eta}(t) := \mathrm{Tr}[(w * Q)(t)\rho(t)] \qquad (392)$$

such that $\bar{\eta} = \min_t \bar{\eta}(t)$ and $\eta = \int d\mu(t) \bar{\eta}(t)$. Now, we can use the exact similar reasoning as above and write

$$1 - \bar{\eta}(t) = \mathrm{Tr}[(\bar{w} * Q)(t)\rho(t)] \qquad (393)$$

$$\ge \sum_{s \in S} \beta_h^{\bar{\eta}(t+s)} (\rho(t+s) \| \rho(t)), \qquad (394)$$

where the only difference is that the argument of the asymmetric hypothesis test is now a function of $t$. We therefore obtain

$$\eta \le 1 - \int d\mu(t) \sum_{s \in S} \beta_h^{\bar{\eta}(t+s)} (\rho(t+s) \| \rho(t)). \qquad (395)$$

□

## E. Fano-type bounds for quantum multi-hypothesis testing

In this section we derive some bounds for quantum multi-hypothesis testing.

We first establish an analogue of Fano's inequality for quantum multi-hypothesis testing. To this end, we need two lemmas. The first establishes the behavior of the relative entropy under a direct sum:

**Lemma 20 (Relative entropy and direct sum).** We have the identity

$$D\left(\bigoplus_{i=1}^{M} \mu_i \rho_i \middle\| \bigoplus_{i=1}^{M} \nu_i \sigma_i\right) = D(\mu \| \nu) + \sum_{i=1}^{M} \mu_i D(\rho_i \| \sigma_i). \qquad (396)$$
Proof. The proof is a straightforward algebraic manipulation based off the additivity of the matrix logarithm,

$$D\left(\bigoplus_{i=1}^{M} \mu_i \rho_i \middle\| \bigoplus_{i=1}^{M} \nu_i \sigma_i\right) = \sum_{i=1}^{M} D(\mu_i \rho_i \| \nu_i \sigma_i) \quad (397)$$

$$= \sum_{i=1}^{M} \mathrm{Tr}[\mu_i \rho_i \{\log(\mu_i \rho_i) - \log(\nu_i \sigma_i)\}] \quad (398)$$

$$= \sum_{i=1}^{M} \mathrm{Tr}[\mu_i \rho_i \{\log(\rho_i) - \log(\sigma_i) + \log(\mu_i) - \log(\nu_i)\}] \quad (399)$$

$$= \sum_{i=1}^{M} \mu_i \mathrm{Tr}[\rho_i \{\log(\rho_i) - \log(\sigma_i)\}] + \sum_{i=1}^{M} \mu_i \{\log(\mu_i) - \log(\sigma_i)\} \quad (400)$$

$$= D(\mu \| \nu) + \sum_{i=1}^{M} \mu_i D(\rho_i \| \sigma_i). \quad (401)$$

□

The second lemma we need concerns the optimization of the above expression over the prior probabilities $\mu_i$.

**Lemma 42** (Relative-entropy regularized expectation value). Choosing $\mu_i \propto \nu_i e^{-x_i}$ and subsequently normalizing yields

$$\inf_{\mu} \left\{ D(\mu \| \nu) + \sum_{i=1}^{M} \mu_i x_i \right\} = - \log \sum_{i=1}^{M} \nu_i e^{-x_i}. \quad (402)$$

Proof. We first expand the expression as

$$D(\mu \| \nu) + \sum_{i=1}^{M} \mu_i x_i = \sum_{i=1}^{M} \mu_i \left( x_i + \log \frac{\mu_i}{\nu_i} \right) \quad (403)$$

and perform Lagrange optimization under the restriction $\sum_{i=1}^{M} \mu_i = 1$. The Lagrange function is given by

$$L(\mu, \lambda) = \sum_{i=1}^{M} \mu_i \left( x_i + \log \frac{\mu_i}{\nu_i} \right) + \lambda \left( 1 - \sum_{i=1}^{M} \mu_i \right). \quad (404)$$

The Karush-Kuhn-Tucker conditions enforce that $\partial_i L(\mu, \lambda) = 0$ for all $i$, i.e.

$$\partial_i L(\mu, \lambda) = x_i + 1 + \log \frac{\mu_i}{\nu_i} - \lambda = 0. \quad (405)$$

We thus set

$$\mu_i = \nu_i \exp(\lambda - 1 - x_i) \propto \nu_i e^{-x_i}. \quad (406)$$

The constant $\lambda$ is implicitly chosen such that the above is normalized, which yields

$$\mu_i = \left( \sum_{j=1}^{M} \nu_j e^{-x_j} \right)^{-1} \nu_i e^{-x_i}. \quad (407)$$

The value of the optimization problem is then

$$\begin{align}
\sum_{i=1}^{M} \mu_i \left( x_i + \log \frac{\mu_i}{\nu_i} \right) &= \sum_{i=1}^{M} \mu_i \left( x_i + \log \left( \sum_{j=1}^{M} \nu_j e^{-x_j} \right)^{-1} e^{-x_i} \right) \tag{408} \\
&= \sum_{i=1}^{M} \mu_i \left( -\log \sum_{j=1}^{M} \nu_j e^{-x_j} \right) \nonumber \\
&= -\log \sum_{j=1}^{M} \nu_j e^{-x_j}, \nonumber
\end{align}$$
as claimed.

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

We are now ready to prove the Fano-type bound:

**Theorem 21** (Fano-type bound for quantum multi-hypothesis testing). Let {$\mu_i\rho_i$}$_{i=1}^M$ be a quantum multi-hypothesis testing problem. For any reference state $\sigma$, the error probability obeys

$$ -\log P_e^* (\{\mu_i \rho_i\}_{i=1}^M) \le \frac{M}{M-1} \left( h(1/M) + D(\mu \| u) + \sum_{i=1}^M \mu_i D(\rho_i \| \sigma) \right), \quad (409) $$

where $u$ is the uniform distribution over $M$ elements and $h$ is the binary entropy function. Optimizing over $\mu$ yields the following bound on the minimax error probability:

$$ -\log \bar{P}_e^* (\{\rho_i\}_{i=1}^M) \le \frac{M}{M-1} \left( h(1/M) - \log \frac{1}{M} \sum_{i=1}^M e^{-D(\rho_i \| \sigma)} \right). \quad (410) $$

*Proof.* We will combine three ingredients to obtain the result. First, a result of Vazquez-Vilar that relates the multi-hypothesis testing error to an asymmetric hypothesis test [151]

$$ \begin{aligned} P_e^* (\{\mu_i \rho_i\}_{i=1}^M) &= \max_{\sigma} \beta_h^{1-1/M} \left( \bigoplus_{i=1}^M \mu_i \rho_i \left\| \frac{1}{M} \sigma^{\oplus M} \right. \right) && (411) \\ &= \exp \left( - \min_{\sigma} D_h^{1-1/M} \left( \bigoplus_{i=1}^M \mu_i \rho_i \left\| \frac{1}{M} \sigma^{\oplus M} \right. \right) \right), \end{aligned} $$

where $D_h^\eta$ is the hypothesis testing relative entropy with success probability $\eta$. Next, we use the standard bound

$$ D_h^\eta (\rho \| \sigma) \le \frac{1}{\eta} (D(\rho \| \sigma) + h(1 - \eta)) \quad (412) $$

that relates the hypothesis testing relative entropy to the regular relative entropy [17]. The final ingredient is Lemma 20. Putting everything together yields that for all $\sigma$,

$$ \begin{aligned} -\log P_e^* (\{\mu_i \rho_i\}_{i=1}^M) &\le D_h^{1-1/M} \left( \bigoplus_{i=1}^M \mu_i \rho_i \left\| \frac{1}{M} \sigma^{\oplus M} \right. \right) && (413) \\ &\le \frac{M}{M-1} \left[ D \left( \bigoplus_{i=1}^M \mu_i \rho_i \left\| \frac{1}{M} \sigma^{\oplus M} \right. \right) + h(1/M) \right] \\ &= \frac{M}{M-1} \left[ D(\mu \| u) + \sum_{i=1}^M \mu_i D(\rho_i \| \sigma) + h(1/M) \right] \end{aligned} $$

as claimed. The result on the minimax success probability follows by minimizing the above bound over $\mu$, with the resulting bound obtained via Lemma 42 using $x_i = D(\rho_i \| \sigma)$ and $\nu_i = 1/M$. □

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

Usually, in the literature for lower bounds in quantum information science (see, e.g., Ref. [152]), Fano's inequality is used in a different form, namely the one that bounds the mutual information of a quantum channel. The mutual information in turn is bounded by the Holevo information of an ensemble of quantum states, usually taken to be a uniform mixture of the multi-hypothesis testing states. We recover a similar argument from the above bound by using a uniform distribution as the candidate for the minimax optimization and the expected state as the candidate state $\sigma = \sum_{i=1}^M \mu_i \rho_i$, in which case the average relative entropy is exactly the Holevo information of the ensemble {$\mu_i\rho_i$}$_{i=1}^M$

$$ \begin{aligned} \sum_{i=1}^M \mu_i D \left( \rho_i \left\| \sum_{j=1}^M \mu_j \rho_j \right. \right) &= \sum_{i=1}^M \mu_i \operatorname{Tr} \left[ \rho_i \left( \log \rho_i - \log \sum_{j=1}^M \mu_j \rho_j \right) \right] && (414) \\ &= S \left( \sum_{i=1}^M \mu_i \rho_i \right) - \sum_{i=1}^M \mu_i S(\rho_i) \\ &= \chi(\{\mu_i \rho_i\}_{i=1}^M). \end{aligned} $$
We note that the major improvement over this strategy is the logarithmic dependence on the hypothesis testing error, which, however, comes at the cost of a missing cross-dependence between the Holevo information and the number of samples. We can phrase this as the following corollary:

**Corollary 22 (Fano-type bound with Holevo information).** Let {$\rho_i$}$_{i=1}^M$ be a quantum multi-hypothesis testing problem. We have the following bound on the minimax error probability:

$$- \log \bar{P}_e^* (\{\rho_i\}_{i=1}^M) \le \frac{M}{M-1} \left( h(1/M) + \chi \left( \left\{ \frac{1}{M} \rho_i \right\}_{i=1}^M \right) \right), \quad (415)$$

where $\chi$ is the Holevo information of an ensemble of quantum states.

We can also use a similar strategy as in the proof of Theorem 18 to obtain a multi-hypothesis testing lower bound involving the fidelity. Let us extend the fidelity to mixtures of states as follows:

$$F(\{\mu_i \rho_i\}_{i=1}^M, \{\nu_i \sigma_i\}_{i=1}^M) := F\left(\bigoplus_{i=1}^M \mu_i \rho_i, \bigoplus_{i=1}^M \nu_i \sigma_i\right) = \sum_{i=1}^M \sqrt{\mu_i \nu_i} F(\rho_i, \sigma_i). \quad (416)$$

We can then establish the following lower bound:

**Theorem 23 (Multi-hypothesis testing lower bound).** Let {$\rho_i$}$_{i=1}^M$ and $\sigma$ be quantum states and {$\mu_i$}$_{i=1}^M$ be prior probabilities. We define

$$F_{\text{avg}} := F(\{\mu_i \rho_i\}_{i=1}^M, \{\sigma/M\}_{i=1}^M) \quad (417)$$

and obtain the lower bound

$$P_e^*(\{\mu_i \rho_i\}) \ge \frac{M}{M-1} \left( F_{\text{avg}} - \sqrt{\frac{1}{M}} \right)^2 \ge \left( F_{\text{avg}} - \sqrt{\frac{1}{M}} \right)^2. \quad (418)$$

The bound is valid in the regime where $F_{\text{avg}} \ge \sqrt{1/M}$.

*Proof.* We employ a strategy similar to the proof of Theorem 18. To this end, we denote with $A_i = \mu_i \rho_i$ and $X = \frac{1}{M}\sigma$. We can write the optimal hypothesis testing success and error probabilities as

$$P_s^*(\{A_i\}) = \sum_{i=1}^{M} \mathrm{Tr}[A_i \Pi_i] \quad (419)$$

$$P_e^*(\{A_i\}) = \sum_{i=1}^{M} \mathrm{Tr}[A_i(\mathbb{I} - \Pi_i)] \quad (420)$$

where {$\Pi_i$}$_{i=1}^M$ are the optimal POVM effects. Then, we define a CPTP map

$$\Lambda \left( \bigoplus_{i=1}^{M} Y_i \right) = \mathrm{Tr} \left[ \left( \bigoplus_{i=1}^{M} Y_i \right) \left( \bigoplus_{i=1}^{M} \Pi_i \right) \right] \oplus \mathrm{Tr} \left[ \left( \bigoplus_{i=1}^{M} Y_i \right) \left( \bigoplus_{i=1}^{M} \mathbb{I} - \Pi_i \right) \right] \quad (421)$$

such that

$$\Lambda \left( \bigoplus_{i=1}^{M} A_i \right) = P_s^*(\{A_i\}) \oplus P_e^*(\{A_i\}) \quad (422)$$

$$\Lambda(X^{\oplus M}) = \mathrm{Tr}[X] \oplus (M-1) \mathrm{Tr}[X] = \frac{1}{M} \oplus \frac{M-1}{M}. \quad (423)$$

We can now again use the data-processing property of the fidelity. To this end, we observe that

$$F\left(\bigoplus_{i=1}^{M} A_i, X^{\oplus M}\right) = F_{\text{avg}}. \quad (424)$$
Now, applying the channel $\Lambda$ yields

$$ F\left(\bigoplus_{i=1}^{M} A_i, X^{\oplus M}\right) \le F\left(\Lambda\left[\bigoplus_{i=1}^{M} A_i\right], \Lambda\left[X^{\oplus M}\right]\right) \qquad (425) \\ = \sqrt{\frac{1}{M} P_s^*\left(\{\mu_i \rho_i\}\right)} + \sqrt{\frac{M-1}{M} P_e^*\left(\{\mu_i \rho_i\}\right)} $$

We now apply the bound $P_s^*\left(\{\mu_i \rho_i\}\right) \le 1$, rearrange and square to obtain the first Theorem statement. The validity range arises from the fact that the left hand side must remain non-negative for this to be sensible. $\square$

## F. Further bounds

Similarly to our argument for Theorem 23 above, which applied to quantum multi-hypothesis testing, we can do the same natively for quantum metrology. It involves the extension of the fidelity to parametrized quantum states defined as

$$ F(\mu(t)\rho(t), \nu(t)\sigma(t)) := \int dt \sqrt{\mu(t)\nu(t)} F(\rho(t), \sigma(t)). \qquad (426) $$

We obtain the following result:

**Theorem 24** (Metrology error lower bound). Let $\rho(t)$ a set of states with prior $\mu(t)$ supported on a compact interval of size $T$. Let $\sigma$ be a reference state. We define the random guessing probability $\kappa := 2\delta/T$ and a measure of average fidelity as

$$ F_{\text{avg}} := F(\mu(t)\rho(t), \sigma/T). \qquad (427) $$

With these definitions, the optimal Bayesian error probability can be lower bounded as

$$ 1 - \eta^*(\delta, \rho, \mu) \ge \frac{1}{1 - \kappa} (F_{\text{avg}} - \sqrt{\kappa})^2 \ge (F_{\text{avg}} - \sqrt{\kappa})^2. \qquad (428) $$

The bound is valid in the regime where $F_{\text{avg}} \ge \sqrt{\kappa}$.

**Proof.** We employ a strategy similar to the proof of Theorem 18. The Bayesian success probability is given by

$$ \eta(\delta, \rho, \mu, Q) = \int dt \operatorname{Tr}[\mu(t)\rho(t)(w_{\delta} * Q)(t)]. \qquad (429) $$

We can now see a set of states with prior as an operator-valued measure $\mu(t)\rho(t)$ with the trace map given as $\int dt \operatorname{Tr}[\cdot]$.
In this sense, we can define a CPTP map

$$ \Lambda(O(t)) = \left\{ \int dt \operatorname{Tr}[O(t)(w_{\delta} * Q)(t)] \right\} \oplus \left\{ \int dt \operatorname{Tr}[O(t)([1 - w_{\delta}] * Q)(t)] \right\} \qquad (430) $$

such that

$$ \Lambda(\mu(t)\rho(t)) = \eta \oplus 1 - \eta \qquad (431) $$

$$ \Lambda\left(\frac{\sigma}{T}\right) = \frac{2\delta}{T} \oplus \frac{T - 2\delta}{T} = \kappa \oplus 1 - \kappa, \qquad (432) $$

where we introduced the random guessing probability $\kappa := 2\delta/T$. Our results will be formulated in terms of sandwiched Rényi relative entropy of order 1/2,

$$ \tilde{D}_{1/2}(\rho \| \sigma) = -\frac{1}{2} \log \tilde{Q}_{1/2}(\rho \| \sigma) \qquad (433) $$

$$ = -\frac{1}{2} \log \operatorname{Tr}[(\sigma^{1/2} \rho \sigma^{1/2})^{1/2}] \qquad (434) $$

$$ = - \log F(\rho, \sigma), \qquad (435) $$
essentially the log-fidelity. Using the data-processing relation of the fidelity, we obtain a relation to the Bayesian success probability

$$
\begin{align}
F\left(\mu(t)\rho(t), \frac{\sigma}{\sqrt{t}}\right) &\le F(\eta \oplus 1 - \eta, \kappa \oplus 1 - \kappa) \tag{436} \\
&= \sqrt{\eta\kappa} + \sqrt{(1-\eta)(1-\kappa)} \nonumber \\
&\le \sqrt{\kappa} + \sqrt{(1-\eta)(1-\kappa)}. \nonumber
\end{align}
$$

Combining the two preceding results allows us to deduce

$$
1 - \eta \geq \frac{1}{1 - \kappa} (F_{\text{avg}} - \sqrt{\kappa})^2. \qquad (437)
$$

as long as

$$
F_{\text{avg}} \geq \sqrt{\kappa}. \tag{438}
$$

□

Another possibility to get a metrology bound is to use the Fano-type bounds we derived before. Going along this path gives the following theorem:

**Theorem 25.** *Fix a sub-interval of size $T = 4k\delta$ for $k \in \mathbb{N}$. We set $M = 2k + 1$ and have that*

$$
\begin{equation}
- \log 1 - \bar{\eta}^*(\delta, \rho) \le \tag{439}
\begin{aligned}[t]
& \max_t \frac{M}{M-1} \left( h\left(\frac{1}{M}\right) - \log \frac{1}{M} \sum_{l=-k}^{k} e^{-D(\rho(t+2\delta l) \| \rho(t))} \right).
\end{aligned}
\end{equation}
$$

*Proof.* We first use the subdivision trick of Lemma 6 to establish the following lower bound relating to a subinterval $I = [t - T/2, t + T/2]$ of size $T = 4k\delta$ centered around $t$:

$$
1 - \bar{\eta}^*(\delta, \rho) \geq \max_t \{1 - \bar{\eta}^*(\delta, \rho|_I)\}, \quad (440)
$$

where $\rho|_I$ is the restriction of $\rho(t)$ to $t \in I$. Next, we apply Theorem 10 to the above, choosing a set of states
$\{\rho_l = \rho(t + 2\delta l)\}_{l=-k}^k$ that fulfill the condition that the associated times are at least $2\delta$ apart. This gives

$$
1 - \bar{\eta}^*(\delta, \rho) \geq \max_t \bar{P}_e^*(\{\rho_l = \rho(t + 2\delta l)\}_{l=-k}^k). \quad (441)
$$

We then apply the above Theorem 21 with the reference state $\sigma = \rho(t)$ to obtain the statement of the Theorem. $\square$

G. Upper bound on asymptotic rate

Theorem 16 allows us to get bounds on the asymptotic rate for quantum metrology from the corresponding upper bounds for binary hypothesis testing. These bounds rely on the fact that the asymptotic rate for multi-hypothesis testing is given by the smallest quantum Chernoff divergence [14]

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

among two states that are to be tested [15]. To be able to establish such bounds, we first need the bound of Theorem 16 not to be vacuous which corresponds to enforcing $K = 1$, as the success probability asymptotically approaches 1, but $K$ is independent of the number of copies of the state that are used. As a further ingredient to establish the bounds on the asymptotic rate, we need the following Lemma that generalizes Laplace’s method in a way relevant to our work.

**Lemma 26 (Laplace principle).** Let $\mu(t)$ be a probability measure on $\mathbb{R}$ and $f(t)$ a bounded measurable function. The essential infimum with respect to $\mu(t)$ is defined as

$$
\inf_{\mu(t)} \text{ess} \, \text{inf} \, f(t) := \sup \{b \in \mathbb{R} \mid \mu(\{f(t) < b\}) = 0\}. \quad (443)
$$

We have that

$$
- \lim_{n \to \infty} \frac{1}{n} \log \int d\mu(t) e^{-nf(t)} = \inf_{\mu(t)} \text{ess} \, \text{inf} \, f(t). \quad (444)
$$
*Proof.* We assume without loss of generality that

$$f^* = \underset{\mu(t)}{\operatorname{ess\inf}} f(t) = \sup \{b \in \mathbb{R} \mid \mu(\{f(t) < b\}) = 0\} = 0, \qquad (445)$$

as we can otherwise consider the function $f - f^*$. First, note that

$$\frac{1}{n} \log \int d\mu(t) e^{-nf(t)} \le 0, \qquad (446)$$

as $e^{-nf(t)} \le 1$ almost everywhere. Thus,

$$\limsup_{n \to \infty} \frac{1}{n} \log \int d\mu(t) e^{-nf(t)} \le 0. \qquad (447)$$

By the definition of the essential minimum, for every $\epsilon > 0$ we have that there exists a $\delta > 0$ such that

$$\mu(\{f(t) < \epsilon\}) \ge \delta. \qquad (448)$$

From this, we obtain that for all $n$

$$\int d\mu(t) e^{-nf(t)} \ge e^{-n\epsilon}\delta. \qquad (449)$$

Taking the log and dividing by $n$ we obtain:

$$\frac{1}{n} \log \left( \int d\mu(t) e^{-nf(t)} \right) \ge -\epsilon + \frac{\log(\delta)}{n}. \qquad (450)$$

Taking the $\liminf$ of both sides we obtain that

$$\liminf_{n \to \infty} \frac{1}{n} \log \left( \int d\mu(t) e^{-nf(t)} \right) \ge -\epsilon. \qquad (451)$$

As $\epsilon > 0$ was arbitrary, we conclude that

$$\liminf_{n \to \infty} \frac{1}{n} \log \left( \int d\mu(t) e^{-nf(t)} \right) \ge 0. \qquad (452)$$

The claim then follows by combining Eq. (452) with Eq. (447). $\square$

We are now equipped to show that Theorem 16 implies the following bound on the asymptotic rate.

**Theorem 27** (Upper bound on asymptotic rate). For a given window function $w$, state set $\rho(t)$ and possibly a prior $\mu(t)$ that has non-vanishing support on the parameter domain, the Bayesian and the minimax rate obey the upper bounds

$$\overline{R}^*(w, \rho) \le R^*(w, \mu, \rho) \le \inf \left\{ C(\rho(t), \rho(t')) \mid t, t': \sup_x \{w(t+x) + w(t'+x)\} = 1 \right\}. \qquad (453)$$

*Proof.* Let us first recall the definition of the asymptotic Bayesian rate

$$R^*(w, \mu, \rho) = \lim_{n \to \infty} -\frac{1}{n} \log (1 - \eta^*(w, \mu, \rho^{\otimes n})). \qquad (454)$$

We will apply Theorem 16 for a set $S = \{(1/2, 0), (1/2, s)\}$ where $s$ is chosen such that the constant $K$ is equal to 1, i.e., such that the shifted windows do not overlap. In the case of binary discrimination, we can make use of the Helstrom formula

$$P_s^*(A, B) = \frac{1}{2} \operatorname{Tr}[A + B] + \frac{1}{2} \|A - B\|_1. \qquad (455)$$
The Theorem then implies the following lower bound on the error:

$$ 
\begin{aligned}
1 - \eta^*(w, \mu, \rho^{\otimes n}) &\ge 1 - \int dt P_s^* \left( \frac{1}{2}\mu(t)\rho^{\otimes n}(t), \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right) \tag{456} \\
&= 1 - \frac{1}{2} \left( \int dt \operatorname{Tr} \left[ \frac{1}{2}\mu(t)\rho^{\otimes n}(t) + \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right] + \left\| \frac{1}{2}\mu(t)\rho^{\otimes n}(t) + \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right\|_1 \right) \\
&= \frac{1}{2} \left( \int dt \operatorname{Tr} \left[ \frac{1}{2}\mu(t)\rho^{\otimes n}(t) + \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right] - \left\| \frac{1}{2}\mu(t)\rho^{\otimes n}(t) + \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right\|_1 \right) \\
&= \int dt P_e^* \left( \frac{1}{2}\mu(t)\rho^{\otimes n}(t), \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right),
\end{aligned}
$$

where we have used the fact that

$$ \int dt \operatorname{Tr} \left[ \frac{1}{2}\mu(t)\rho^{\otimes n}(t) + \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right] = 1. \qquad (457) $$

We can now make use of the fact that the asymptotic scaling of the error probability for binary hypothesis tests is known [153]. We only have to take care of the additional measures $\mu(t)$ and $\mu(t+s)$ that appear in the expression we look at. For the sense of brevity, we do not reproduce the whole proof of Theorem 2.2 of Ref. [153] but we just note that using the relation $\min\{ab, cd\} \ge \min\{a, c\} \min\{b, d\}$ for non-negative real numbers $a, b, c, d$ after Eq. (12) of Ref. [153] implies that

$$ P_e^* \left( \frac{1}{2}\mu(t)\rho^{\otimes n}(t), \frac{1}{2}\mu(t+s)\rho^{\otimes n}(t+s) \right) \ge \frac{1}{2} \min(\mu(t), \mu(t+s)) \exp(-n(C(\rho(t), \rho(t+s)) + o(1))). \quad (458) $$

Therefore,

$$ 1 - \eta^*(w, \mu, \rho^{\otimes n}) \ge \frac{1}{2} \int dt \min\{\mu(t), \mu(t+s)\} \exp(-n(C(\rho(t), \rho(t+s)) + o(1))). \quad (459) $$

For the next step, we define $\nu(t) = \min\{\mu(t), \mu(t+s)\}$ and have that $\int dt \nu(t) = c > 0$ by the assumptions of the theorem statement. With this at hand, we have that $\nu(t)/c$ is a proper measure so that

$$ \lim_{n \to \infty} -\frac{1}{n} \log(1 - \eta^*(w, \mu, \rho^{\otimes n})) \le \lim_{n \to \infty} -\frac{1}{n} \log \frac{c}{2} \int \frac{d\nu(t)}{c} \exp(-nC(\rho(t), \rho(t+s)) \exp(-o(n))). \quad (460) $$

We can asymptotically take care of the $o(n)$ term by adding $-n\epsilon$ with an arbitrary $\epsilon > 0$ to the exponent and then apply Lemma 26 to obtain

$$ 
\begin{aligned}
\lim_{n \to \infty} -\frac{1}{n} \log(1 - \eta^*(w, \mu, \rho^{\otimes n})) &\le \lim_{\epsilon \to 0} \lim_{n \to \infty} -\frac{1}{n} \log \int \frac{d\nu(t)}{c} \exp(-n[C(\rho(t), \rho(t+s) + \epsilon)] \\
&= \lim_{\epsilon \to 0} \inf_{\nu(t)} C(\rho(t), \rho(t+s) + \epsilon) \\
&= \inf_{\nu(t)} C(\rho(t), \rho(t+s)).
\end{aligned}
\quad (461) $$

In the above statement, the prior enters only through defining the support of $\nu(t)$, which by virtue of the assumptions of the theorem is the full support of the domain of the metrological problem which we left implicit. This means that asymptotic rate bound applies both to the Bayesian and the minimax case. The theorem statement follows by writing $s = t - t'$ and the condition $\sup_x\{w(t+s) + w(t'+s)\} = 1$ enforces $K = 1$ as desired. $\square$

The statement of Theorem 13 in the main text follows straightforwardly by noting that the condition on $t$ and $t'$ reduces to $|t - t'| > 2\delta$ for the rectangular window with tolerance $\delta$.

## H. Relation to Wigner-Yanase-Dyson information

Under continuity assumptions, the most similar states – and thus the states that are hardest to distinguish from each other – are the ones that are close in time. In the case of a rectangular window with very small tolerance $\delta$ we
thus expect the rate to be limited by the states that are 2δ-close. In this case, we can expand the Chernoff divergence as [154]

$$C(\rho(t), \rho(t + 2\delta)) = \frac{1}{2}\delta^2\mathcal{I}(t) + O(\delta^3), \qquad (462)$$

where $\mathcal{I}(t)$ is the Wigner-Yanase-Dyson information. We can alternatively define it through the affinity of quantum states

$$A(\rho, \sigma) = \mathrm{Tr}[\rho^{1/2}\sigma^{1/2}], \qquad (463)$$

such that

$$A(\rho(t), \rho(t + 2\delta)) = 1 - \frac{1}{4}\delta^2\mathcal{I}(t) + O(\delta^3). \qquad (464)$$

Compare this to the Bures fidelity, which expands into the quantum Fisher information $\mathcal{F}(t)$ as

$$F(\rho(t), \rho(t + 2\delta)) = \|\rho(t)^{1/2}\rho(t + 2\delta)^{1/2}\|_1 = 1 - \frac{1}{2}\delta^2\mathcal{F}(t) + O(\delta^3). \qquad (465)$$

For small $\delta$, we thus expect the asymptotic rate to be bounded by

$$\bar{R}^*(w_\delta, \rho) \le \frac{1}{2}\delta^2 \min_t \mathcal{I}(t). \qquad (466)$$

As the Wigner-Yanase-Dyson information is always smaller than the Bogoliubov-Kubo-Mori information associated to the quantum relative entropy, this is tighter than the characterization given by Hayashi in Eq. (71) of Ref. [43].

## I. Lower bound on success probability

In this section, we will establish a lower bound on the success probability. Such lower bounds are obtained by exhibiting a POVM $Q(\tau)$ for which we can guarantee a certain performance. In our case, we will assume a suitable measurement $\{M(\lambda)\}$ has already been chosen and we then compute guarantees for the smoothed maximum a posteriori strategy introduced in Section VI. Our bounds allow us to reduce the problem to the hardest binary hypothesis testing problem for two states $\rho(t)$ and $\rho(t')$ that can never be in the same window. We use our bounds to establish a lower bound on the asymptotic rate for the $\delta$ window and show that it matches the upper bound of Theorem 27 for commuting states. We conjecture that a suitable lower bound can be derived in the general case as well and sketch a possible direction to do so.

To establish a lower bound on the success probability – or equivalently an upper bound on the error – we will discretize the problem in question, establish the bound in the discrete case and then lift the result again to the continuous case by taking the appropriate limits. To this end, we will first establish the discrete version of the success probability:

$$\eta^*(W, \{\rho_i\}, \{p_i\}) := \sup_{\{Q_j\}} \sum_i \sum_j W_{i,j} p_i \mathrm{Tr}[\rho_i Q_j]. \qquad (467)$$

The first argument is a matrix $W$ that takes the role of the window function, whereas the other arguments are a collection of quantum states and a collection of prior probabilities. With this notation settled, we can establish the following lemma that establishes a lower bound through a specific discretization:

**Lemma 28 (Lower bound through discretization).** For a given window function $w$, state set $\rho(t)$ and prior $\mu(t)$, we define a discretization with respect to a set of mutually disjoint intervals $\{T_i\}_{i=1}^N$ as

$$p_i := \mu(T_i), \quad \rho_i := \frac{1}{p_i} \int_{T_i} d\mu(t) \rho(t), \quad W_{i,j} := \inf_{t_i \in T_i, t_j \in T_j} w(t - t'). \qquad (468)$$

Then, we have that

$$\eta^*(w, \rho, \mu) \ge \eta^*(W, \{\rho_i\}_{i=1}^N, \{p_i\}_{i=1}^N). \qquad (469)$$
Proof. As a first step, we can obtain a lower bound on the success probability by restricting the optimization over all POVMs $Q(\tau)$ to discrete POVMs $Q(t) = \sum_{j=1}^{N} \delta(t - t_j)Q_j$ associated to predictions $t_j \in T_j$. This yields

$$ \eta^*(\delta, \rho, \mu) = \sup_{Q(\tau)} \int d\mu(t) d\tau w(t-\tau) \mathrm{Tr}[\rho(t)Q(\tau)] \quad (470) \\ \ge \sup_{\{Q_j\}} \sum_j \int d\mu(t) w(t-t_j) \mathrm{Tr}[\rho(t)Q_j]. $$

Next, we split the integration over $t$ into integrals over the intervals $T_i$ and exploit the definition of $W_{i,j}$ as a lower bound. The statement of the lemma follows from collecting the resulting terms

$$ \begin{aligned} \eta^*(\delta, \rho, \mu) &\ge \sup_{\{Q_j\}} \sum_{i=1}^{N} \sum_j \int_{T_i} d\mu(t) w(t-t_j) \mathrm{Tr}[\rho(t)Q_j] \quad (471) \\ &\ge \sup_{\{Q_j\}} \sum_{i=1}^{N} \sum_{j=1}^{N} \int_{T_i} d\mu(t) W_{i,j} \mathrm{Tr}[\rho(t)Q_j] \\ &= \sup_{\{Q_j\}} \sum_{i=1}^{N} \sum_{j=1}^{N} p_i W_{i,j} \mathrm{Tr}[\rho_i Q_j] \\ &= \eta^*(w, \{\rho_i\}_{i=1}^N, \{p_i\}_{i=1}^N). \end{aligned} $$

□

Our next step is to provide a bound for the discrete problem that achieves a reduction to binary hypothesis testing. We will now define the discrete analogues of the smoothed maximum a posteriori estimation strategy of Section VI. For a given measurement $\{M(\lambda)\}$, we define the discrete likelihood function

$$ \Lambda(\lambda | i) := \mathrm{Tr}[\rho_i M(\lambda)]. \quad (472) $$

Analogously to Section III B, we also define the marginal probability of observing $\lambda$ as

$$ \nu(\lambda) = \sum_{i=1}^{N} p_i \Lambda_i(\lambda) \quad (473) $$

such that the discrete posterior distribution is given by

$$ P(i | \lambda) = \frac{p_i \Lambda(\lambda | i)}{\nu(\lambda)}. \quad (474) $$

The discrete likelihood function corresponds to a state

$$ \Lambda(\lambda | i) \Leftrightarrow \Lambda(i) := \int d\lambda |\lambda\rangle\langle\lambda| \Lambda(\lambda | i) = \frac{1}{p_i} \int d\nu(\lambda) |\lambda\rangle\langle\lambda| P(i | \lambda) \quad (475) $$

that captures the conditional distribution of measurement outcomes conditioned on the underlying state being $\rho_i$. A given strategy $\tau^*(\lambda)$ induces a POVM

$$ Q_j = \int d\lambda M(\lambda) \chi[\tau^*(\lambda) = j]. \quad (476) $$

The discrete success probability for that strategy is then

$$ \begin{aligned} \eta(w, \{\rho_i\}_{i=1}^N, \{p_i\}_{i=1}^N, \{Q_j\}_{j=1}^N) &= \int d\lambda \sum_{i=1}^N \sum_{j=1}^N p_i W_{i,j} \mathrm{Tr}[\rho_i M(\lambda)] \chi[\tau^*(\lambda) = j] \quad (477) \\ &= \int d\lambda \sum_{i=1}^N \sum_{j=1}^N W_{i,j} p_i \Lambda(\lambda | i) \chi[\tau^*(\lambda) = j] \\ &= \int d\lambda \sum_{i=1}^N \sum_{j=1}^N W_{i,j} \nu(\lambda) P(i | \lambda) \chi[\tau^*(\lambda) = j]. \end{aligned} $$
The smoothed maximum a posteriori estimation strategy corresponds to

$$ \tau_{\text{SMAP}}^{*}(\lambda) = \underset{1 \le i \le N}{\operatorname{argmax}} \sum_{j=1}^{N} W_{i,j} P(j | \lambda). \qquad (478) $$

The smoothed maximum a posteriori estimation strategy allows us to derive the following proposition that relates the error to binary hypothesis testing of the output distributions of a fixed measurement for any window which takes only values in 0 and 1, like the $\delta$ window.

**Proposition 29** (Error bound in the discrete case). For a given discrete set of states $\{\rho_i\}_{i=1}^N$ with prior probabilities $\{p_i\}_{i=1}^N$ and a window matrix $W$ with entries that are either 0 or 1, we have that the posterior states $\{\Upsilon_i\}_{i=1}^N$ provide the upper bound

$$ \sum_{i=1}^{N} p_i - \eta^*(W, \{\rho_i\}_{i=1}^N, \{p_i\}_{i=1}^N) \le N^2 \max_{\exists k: W_{i,k} = W_{j,k}=1} P_e(p_i \Lambda(i), p_j \Lambda(j)). \quad (479) $$

The condition on the indices $i$ and $j$ means we optimize over all states that cannot be in the same window at the same time.

*Proof.* By the construction of our measurement, we know that for all $i$

$$ \sum_{j=1}^{N} W_{i,j} P(j | \lambda) \le \sum_{j=1}^{N} W_{\tau^*(\lambda)} P(j | \lambda). \quad (480) $$

We can reformulate this by introducing a neighborhood of an index $i$, $K(i) := \{j | W_{i,j} = 1\}$, as

$$ \sum_{j \in K(i)} P(j | \lambda) \le \sum_{j \in K(\tau^*(\lambda))} P(j | \lambda), \quad (481) $$

where we implicitly made use of the fact that $W_{i,j}$ can be only either zero or one by assumption. We will denote the complement of a neighborhood as $\bar{K} = [N] \setminus K$. Note that the total error of our construction will be

$$ \sum_{i=1}^{N} p_i - \eta(W, \{\rho_i\}_{i=1}^N, \{p_i\}_{i=1}^N, \{Q_j\}) = \int d\nu(\lambda) \sum_{i \in \bar{K}(\tau^*(\lambda))} P(i | \lambda). \quad (482) $$

The first key observation we can draw from the above is that for any neighborhood $K(k)$ that contains $i$, we have that

$$ P(i | \lambda) \le \sum_{j \in K(\tau^*(\lambda))} P(j | \lambda) - \sum_{l \in K(k)} P(l | \lambda). \quad (483) $$

This upper bound will be non-trivial for any $i \in \bar{K}(\tau^*(\lambda))$. We can remove the overlapping terms in the upper bound to obtain the following inequality which holds for all $i \in \bar{K}(\tau^*(\lambda))$ and all $k$ such that for $i \in K(k)$,

$$ P(i | \lambda) \le \sum_{j \in K(\tau^*(\lambda) \setminus K(k))} P(j | \lambda). \quad (484) $$

Hence, we can conclude that if we define the union of all neighborhoods that contain $i$ as $U(i) := \bigcup\{K(k) | i \in K(k)\}$, we have that

$$ P(i | \lambda) \le \sum_{j \notin U(i)} P(j | \lambda). \quad (485) $$

The next crucial step in our derivation is to observe that the above immediately implies

$$ P(i | \lambda) \le \sum_{j \notin U(i)} \min\{P(i | \lambda), P(j | \lambda)\} \quad (486) $$
for all likelihood values that contribute to the error of the smoothed maximum a posteriori estimate. We can thus bound the total error as

$$
\begin{align}
\sum_{i=1}^{N} p_i - \eta(W, \{\rho_i\}_{i=1}^{N}, \{p_i\}_{i=1}^{N}, \{Q_j\}) &= \int d\nu(\lambda) \sum_{i \in \bar{K}(\tau^*(\lambda))} P(i | \lambda) \tag{487} \\
&\le \int d\nu(\lambda) \sum_{i \in \bar{K}(\tau^*(\lambda))} \sum_{j \notin U(i)} \min\{P(i | \lambda), P(j | \lambda)\} \nonumber \\
&\le \int d\nu(\lambda) \sum_{i=1}^{N} \sum_{j \notin U(i)} \min\{P(i | \lambda), P(j | \lambda)\} \nonumber \\
&= \sum_{i=1}^{N} \sum_{j \notin U(i)} \int d\nu(\lambda) \min\{P(i | \lambda), P(j | \lambda)\} \nonumber \\
&= \sum_{i=1}^{N} \sum_{j \notin U(i)} P_e(p_i \Lambda(i), p_j \Lambda(j)) \nonumber \\
&\le N^2 \max_{\substack{1 \le i, j \le N \\ j \notin U(i)}} P_e(p_i \Lambda(i), p_j \Lambda(j)). \nonumber
\end{align}
$$

The first equality is the error under the smoothed maximum a posteriori strategy, the first inequality is Eq. (486), the second inequality – a further crucial step – extends the summation over $i$ to include all possible indices. The second equality exchanges the order of integration and summation and the third equality compares to Eq. (475) and recognizes the term $\int d\nu(\lambda) \min\{P(i|\lambda), P(j|\lambda)\}$ as the minimum attainable error when discriminating the classical states $\Lambda(i)$ and $\Lambda(j)$ with prior probabilities $p_i$ and $p_j$. The final inequality bounds the sum via the maximum. The statement of the proposition follows by recognizing that $j \notin U(i)$ is equivalent to $\exists k: W_{i,k} = W_{jl} = 1$. $\square$

Let us now turn to the $\delta$ window and lift this proposition to a bound in the continuous case. To this end, recall the following definitions: We have the likelihood function

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

capturing the conditional distribution of measurement outcomes $\lambda$ for a given ground truth $t$, the associated likelihood state

$$ \Lambda(t) := \int d\lambda |\lambda\rangle\langle\lambda| \Lambda(\lambda | t), \quad (489) $$

and the marginal distribution of measurement outcomes and the posterior distribution:

$$ \nu(\lambda) := \int d\mu(t) \mathrm{Tr}[\rho(t)M(\lambda)] \quad (490) $$

$$ P(t | \lambda) := \frac{\mu(t)}{\nu(\lambda)} \Lambda(\lambda | t). \quad (491) $$

With these definitions at hand, we can establish the following proposition pertaining to a rectangular window function:

**Proposition 30.** Assume a rectangular window with fixed tolerance $\delta$, state set $\rho(t)$ with prior $\mu(t)$ and a fixed measurement $M(\lambda)$. We can then take any given compact interval $T$ and discretize it into $N \in \mathbb{N}$ equally sized sub-intervals of size $\Delta = |T|/N$. We define a smoothed state as

$$ \Upsilon^{\Delta}(t) := \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \, \mu(t + \tau) \Lambda(t + \tau). \quad (492) $$

Then, we have the bound

$$ \mu(T) - \eta^*(\delta, \rho, \mu) \le |T|N \max_{\substack{t,t' \in T \\ |t-t'| > 2(\delta-\Delta)}} P_e(\Upsilon^\Delta(t), \Upsilon^\Delta(t')). \quad (493) $$
Proof. Let us use the discretization introduced in Lemma 28 for a set of mutually disjoint intervals $T_i$ of cardinality bounded as $|T_i| \le \Delta$ such that $T = \bigcup_{i=1}^N T_i$ where $N = [T/\Delta]$. We combine the discretization lower bound of Lemma 28 with Proposition 29. Recall that the discretization involves the definitions

$$p_i = \mu(T_i) \qquad (494)$$

$$\rho_i = \frac{1}{p_i} \int_{T_i} d\mu(t) \rho(t). \qquad (495)$$

Subsequent application of Proposition 29 then gives the bound

$$\mu(T) - \eta^*(\delta, \rho, \mu) \le N^2 \max_{\substack{1 \le i,j \le N \\ \exists k: W_{i,k} = W_{j,k} = 1}} P_e(p_i \Lambda(i), p_j \Lambda(j)), \qquad (496)$$

where we have used $\sum_{i=1}^N p_i = \mu(T)$ and, for $t_i$ the midpoint of $T_i$, we have that

$$\begin{align*}
p_i \Lambda(i) &= p_i \int d\lambda |\lambda\rangle\langle\lambda| \operatorname{Tr}[\rho_i M(\lambda)] \tag{497} \\
&= p_i \int d\lambda |\lambda\rangle\langle\lambda| \operatorname{Tr}\left[\frac{1}{p_i} \int_{T_i} d\mu(t) \rho(t) M(\lambda)\right] \\
&= \int d\lambda |\lambda\rangle\langle\lambda| \int_{T_i} d\mu(t) \Lambda(\lambda |t) \\
&= \int_{T_i} d\mu(t) \Lambda(t) \\
&= \Delta \Upsilon^\Delta(t).
\end{align*}$$

Hence,

$$\mu(T) - \eta^*(\delta, \rho, \mu) \le \Delta N^2 \max_{\substack{1 \le i,j \le N \\ \exists k: W_{i,k} = W_{j,k} = 1}} P_e(\Upsilon^\Delta(t_i), \Upsilon^\Delta(t_j)). \qquad (498)$$

To bring this inequality to its final form, we revisit the definition of $W_{i,k}$ for the $\delta$ window

$$\begin{align*}
W_{i,k} &= \inf_{\substack{t'_i \in T_i \\ t'_k \in T_k}} w(t'_i - t'_k) \tag{499} \\
&= \inf_{\substack{t'_i \in T_i \\ t'_k \in T_k}} \chi[|t'_i - t'_k| \le \delta] \\
&= \inf_{-\Delta/2 \le \epsilon, \epsilon' \le \Delta/2} \chi[|t_i - t_k + \epsilon - \epsilon'| \le \delta] \\
&= \chi[|t_i - t_k| \le \delta - \Delta],
\end{align*}$$

where we recall that $t_i$ and $t_k$ are the midpoints of $T_i$ and $T_k$, respectively. The condition that there should not be a $k$ such that $W_{i,k}$ and $W_{j,k}$ are one at the same time thus translates to

$$\exists k: W_{i,k} = W_{j,k} = 1 \Leftrightarrow |t_i - t_j| > 2(\delta - \Delta). \qquad (500)$$

We, therefore, have

$$\begin{align*}
\mu(T) - \eta^*(\delta, \rho, \mu) &\le \Delta N^2 \max_{\substack{1 \le i,j \le N \\ |t_i - t_j| > 2(\delta - \Delta)}} P_e(\Upsilon^\Delta(t_i), \Upsilon^\Delta(t_j)) \\
&\le \Delta N^2 \sup_{\substack{t, t' \in T \\ |t - t'| > 2(\delta - \Delta)}} P_e(\Upsilon^\Delta(t), \Upsilon^\Delta(t')),
\end{align*}$$

where the second inequality follows from the fact that we can always extend the optimization in the maximum to also include points that are not the midpoints of the discretization intervals. The statement of the proposition follows from $\Delta = |T|/N$. $\square$
We will now use the above proposition to get a lower bound on the asymptotic rate for the $\delta$ window. We consider the case of a defined sequence of measurements $\{M^{(n)}\}$ for $n \in \mathbb{N}$. We denote the channel that maps states to their output distributions over $\lambda$ as

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

This sequence achieves the rate

$$ R^*(\rho, \sigma, \{M^{(n)}(\lambda)\}) := - \lim_{n \to \infty} \frac{1}{n} \log P_e^*(\mathcal{M}^{(n)}[\rho^{\otimes n}], \mathcal{M}^{(n)}[\sigma^{\otimes n}]) \quad (502) $$

for binary state discrimination. With this notation in place, we can now proceed with the proof of Theorem 14 of the main text:

*Proof of Theorem 14.* We will use Proposition 30 and choose an interval $T = [-T_0, T_0]$, and a number of discretization intervals $N \in \mathbb{N}$ such that $\Delta = 2T_0/N < \delta$. We actually have to choose $\Delta$ much smaller than that as will become apparent later. In our case, the likelihood state is given by

$$ \Lambda^{(n)}(t) = \mathcal{M}^{(n)}[\rho^{\otimes n}(t)] \quad (503) $$

and its smoothed counterpart by

$$ \Upsilon^{\Delta,(n)}(t) = \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \, \mu(t+\tau)\Lambda^{(n)}(t+\tau). \quad (504) $$

The upper bound on the error obtained from Proposition 30 then takes the form

$$ \mu([-T_0, T_0]) - \eta^*(\delta, \rho^{\otimes n}, \mu) \le 2T_0 N \sup_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2(\delta-\Delta)}} P_e(\Upsilon^{\Delta,(n)}(t), \Upsilon^{\Delta,(n)}(t')). \quad (505) $$

We will introduce the smoothed state set and measure as

$$ \mu^{\Delta}(t) := \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \, \mu(t+\tau) = \frac{1}{\Delta} \mu([t-\Delta/2, t+\Delta/2]), \quad (506) $$

$$ \rho^{\Delta,(n)} = \frac{1}{\mu([t-\Delta/2, t+\Delta/2])} \int_{-\Delta/2}^{\Delta/2} d\tau \, \mu(t) \rho^{\otimes n}(t). \quad (507) $$

With these notions, we have that

$$ \begin{aligned} \Upsilon^{\Delta,(n)}(t) &= \mathcal{M}^{(n)} \left[ \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \, \mu(t+\tau) \rho^{\otimes n}(t+\tau) \right] \\ &= \mathcal{M}^{(n)}[\mu^{\Delta}(t) \rho^{\Delta,(n)}(t)]. \end{aligned} \quad (508) $$

For technical reasons, we will need a full rank state in the following derivations. We therefore introduce the perturbed state set

$$ \rho_{\gamma}(t) := (1 - \gamma)\rho(t) + \gamma\omega, \quad (509) $$

where $0 < \gamma < 1$ and $\omega$ is the maximally mixed state. We will use $\rho_{\gamma}^{\Delta,(n)}(t)$ to denote the associated smoothed state sets analogously defined as in Eq. (507). We can use the upper bound

$$ \rho(t) \le \frac{1}{1-\gamma} \rho_{\gamma}(t) \Rightarrow \rho^{\otimes n}(t) \le e^{n \log(1/(1-\gamma))} \rho_{\gamma}^{\otimes n}(t). \quad (510) $$

The state $\rho^{\Delta,(n)}$ appearing in the upper bound of Eq. (505) is a mixture of i.i.d. states, but for our purposes we need an i.i.d. state. We therefore use the chain of inequalities

$$ \rho^{\Delta,(n)}(t) \le e^{n \log(1/(1-\gamma))} \rho_{\gamma}^{\Delta,(n)}(t) \le e^{n[\log(1/(1-\gamma)) + D_{\max}^{T_0,\Delta,\gamma}]} [\rho_{\gamma}^{\Delta}(t)]^{\otimes n}, \quad (511) $$
where we have introduced the quantity

$$D_{\max}^{T_0, \Delta, \gamma} := \sup_{-T_0 \le t \le T_0} \sup_{-\Delta/2 \le \tau \le \Delta/2} D_{\max}(\rho_{\gamma}(t+\tau), \rho_{\gamma}^{\Delta}(t)). \quad (512)$$

We have thus reduced from the state $\rho^{\Delta,(n)}(t)$ to the state $[\rho_{\gamma}^{\Delta}(t)]^{\otimes n}$ at the cost of a correction to the asymptotic rate given by $\log(1/(1-\gamma)) + D_{\max}^{T_0,\Delta,\gamma}$, as becomes apparent from the following chain of inequalities:

$$\mu([-T_0, T_0]) - \eta^*(\delta, \rho^{\otimes n}, \mu) \quad (513)$$

$$ \begin{align*} & \le 2T_0 N \sup_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2(\delta-\Delta)}} P_e(\mathcal{M}^{(n)}[\mu^\Delta(t)\rho^{\Delta,(n)}(t)], \mathcal{M}^{(n)}[\mu^\Delta(t')\rho^{\Delta,(n)}(t')]) \\ & \le 2T_0 N \sup_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2(\delta-\Delta)}} e^{n[\log(1/(1-\gamma)) + D_{\max}^{T_0,\Delta,\gamma}]} P_e(\mathcal{M}^{(n)}[\mu^\Delta(t)[\rho_\gamma^\Delta(t)]^{\otimes n}], \mathcal{M}^{(n)}[\mu^\Delta(t')[\rho_\gamma^\Delta(t')]^{\otimes n}]) \\ & \le 2T_0 N \sup_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2(\delta-\Delta)}} e^{n[\log(1/(1-\gamma)) + D_{\max}^{T_0,\Delta,\gamma}]} \max\{\mu^\Delta(t), \mu^\Delta(t')\} P_e(\mathcal{M}^{(n)}[[\rho^\Delta(t)]^{\otimes n}], \mathcal{M}^{(n)}[[\rho^\Delta(t')]^{\otimes n}]) \\ & \le 2T_0 N \sup_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2(\delta-\Delta)}} e^{n[\log(1/(1-\gamma)) + D_{\max}^{T_0,\Delta,\gamma}]} P_e(\mathcal{M}^{(n)}[[\rho^\Delta(t')]^{\otimes n}], \mathcal{M}^{(n)}[[\rho^\Delta(t')]^{\otimes n}]). \end{align*} $$

The first inequality is Eq. (505), the second inequality uses the facts that for the optimal binary hypothesis testing error we have that $A \le A'$, $B \le B'$ implies that $P_e^*(A, B) \le P_e^*(A', B')$ as well as that $P_e^*(\alpha A, \alpha B) = \alpha P_e^*(A, B)$. Both of these facts are readily observable from the Helstrom formula and the convex problem formulation of the hypothesis testing error. The third inequality extracts the measure via maximization and the fourth inequality upper-bounds the maximum of the smoothed measures by one. We can conclude that the asymptotic rate of approaching $\mu([-T_0, T_0])$ is thus at least

$$- \lim_{n \to \infty} \log[\mu([-T_0, T_0]) - \eta^*(\delta, \rho^{\otimes n}, \mu)] \ge \inf_{|t-t'| > 2(\delta-\Delta)} R(\rho_{\gamma}^{\Delta}(t), \rho_{\gamma}^{\Delta}(t'), \{M^{(n)}\}) - \log(1/(1-\gamma)) - D_{\max}^{T_0, \Delta, \gamma}. \quad (514)$$

Having established this bound, we now desire to let the number of discretization steps $N \to \infty$ and thus $\Delta \to 0$. By assumption, $t \mapsto \rho(t)$ is a continuous function and hence

$$ \begin{align} \lim_{\Delta \to 0} \|\rho_{\gamma}(t) - \rho_{\gamma}^{\Delta}(t)\| &= (1-\gamma) \lim_{\Delta \to 0} \|\rho(t) - \rho^{\Delta}(t)\| \tag{515} \\ &= (1-\gamma) \lim_{\Delta \to 0} \left\| \rho(t) - \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \rho(t+\tau) \right\| \nonumber \\ &= (1-\gamma) \lim_{\Delta \to 0} \frac{1}{\Delta} \left\| \int_{-\Delta/2}^{\Delta/2} \rho(t) - \rho(t+\tau) \right\| \nonumber \\ &\le \lim_{\Delta \to 0} \max_{-\Delta/2 \le \tau \le \Delta/2} \|\rho(t) - \rho(t+\tau)\| \nonumber \\ &= 0. \nonumber \end{align} $$

This implies that

$$\lim_{\Delta \to 0} R(\rho_{\gamma}^{\Delta}(t), \rho_{\gamma}^{\Delta}(t'), \{M^{(n)}\}) = R(\rho_{\gamma}(t), \rho_{\gamma}(t'), \{M^{(n)}\}) \quad (516)$$

as $R$ is a continuous function in the first two arguments with respect to the trace norm by the uniform limit theorem as it is a composition of continuous functions.

To wrap up our proof, we also show that the quantity $D_{\max}^{T_0,\Delta,\gamma}$ vanishes. To do so, we rely on the formulation of the max-relative entropy that involves the pseudoinverse:

$$D_{\max}(\rho_{\gamma}(t+\delta), \rho_{\gamma}^{\Delta}(t)) = \log \|\rho_{\gamma}(t+\delta)\rho_{\gamma}^{\Delta}(t)^{+}\|_{\infty}. \quad (517)$$

We can then make use of some results on the perturbation theory of the pseudoinverse. Namely, that if $\text{rank}(A) = \text{rank}(A+X)$ and $\|X\|_{\infty} < 1/\|A^{+}\|_{\infty}$, we have that [155]

$$ \begin{align} \|A^+ - (A+X)^+\|_{\infty} &\le 3 \|A^+\|_{\infty} \|(A+X)^+\|_{\infty} \|X\|_{\infty} \tag{518} \\ &\le 3 \frac{\|A^+\|_{\infty}^2 \|X\|_{\infty}}{1 - \|A^+\|_{\infty} \|X\|_{\infty}}. \nonumber \end{align} $$
In our case, we would like to show that $A+X = \rho_{\gamma}^{\Delta}(t)^{+}$ is not too far from $A = \rho_{\gamma}(t+\delta)^{+}$. As we perturbed all states with the maximally mixed state, we know that $\rho_{\gamma}^{\Delta}(t)$ and $\rho_{\gamma}(t+\delta)$ both have full rank, fulfilling the first requirement of the above result. Next, we use a similar argument as in Eq. (515) to establish that as long as $|\delta| \le \Delta/2$

$$ \begin{aligned} \lim_{\Delta \to 0} \|\rho_{\gamma}(t+\delta) - \rho_{\gamma}^{\Delta}(t)\| &= (1-\gamma) \lim_{\Delta \to 0} \|\rho(t+\delta) - \rho^{\Delta}(t)\| \\ &\le \lim_{\Delta \to 0} \left\| \rho(t+\delta) - \frac{1}{\Delta} \int_{-\Delta/2}^{\Delta/2} d\tau \, \rho(t+\tau) \right\| \\ &= \lim_{\Delta \to 0} \frac{1}{\Delta} \left\| \int_{-\Delta/2}^{\Delta/2} d\tau \, \rho(t+\delta) - \rho(t+\tau) \right\| \\ &\le \lim_{\Delta \to 0} \max_{-\Delta/2 \le \tau \le \Delta/2} \|\rho(t+\delta) - \rho(t+\tau)\| \\ &= 0, \end{aligned} \quad (519) $$

by continuity. This implies that we can make $\|\rho_{\gamma}^{\Delta}(t) - \rho_{\gamma}(t+\delta)\|_{\infty}$ arbitrarily small when decreasing $\Delta$. This especially means that we can make fulfill the second requirement of the above result on the magnitude of the perturbation. This is because for sufficiently small $\gamma$, we have that $1/\|\rho_{\gamma}(t+\delta)^{+}\|_{\infty} = O(1/\gamma)$ which is independent of $\Delta$. Hence, there exists a sufficiently small $\Delta$ such that we can apply the result. This allows us to conclude

$$ \begin{aligned} \lim_{\Delta \to 0} D_{\max}(\rho_{\gamma}(t+\delta), \rho_{\gamma}^{\Delta}(t)) &= \lim_{\Delta \to 0} \log \|\rho_{\gamma}(t+\delta)\rho_{\gamma}^{\Delta}(t)^{+}\|_{\infty} \quad (520) \\ &= \lim_{\Delta \to 0} \log \|\rho_{\gamma}(t+\delta)[\rho_{\gamma}^{\Delta}(t)^{+} - \rho_{\gamma}(t+\delta)^{+} + \rho_{\gamma}(t+\delta)^{+}]\|_{\infty} \\ &\le \lim_{\Delta \to 0} \log (\|\rho_{\gamma}(t+\delta)\rho_{\gamma}(t+\delta)^{+}\|_{\infty} + \|\rho_{\gamma}(t+\delta)[\rho_{\gamma}^{\Delta}(t)^{+} - \rho_{\gamma}(t+\delta)^{+}]\|_{\infty}) \\ &\le \lim_{\Delta \to 0} \log (1 + \|\rho_{\gamma}(t+\delta)\|_{\infty} \|[\rho_{\gamma}^{\Delta}(t)^{+} - \rho_{\gamma}(t+\delta)^{+}]\|_{\infty}) \\ &\le \lim_{\Delta \to 0} \log (1 + \|\rho_{\gamma}^{\Delta}(t)^{+} - \rho_{\gamma}(t+\delta)^{+}\|_{\infty}) \\ &\le \lim_{\Delta \to 0} \|[\rho_{\gamma}^{\Delta}(t)^{+} - \rho_{\gamma}(t+\delta)^{+}]\|_{\infty} \\ &\le \lim_{\Delta \to 0} 3 \frac{\|\rho_{\gamma}(t+\delta)^{+}\|_{\infty}^{2} \|\rho_{\gamma}^{\Delta}(t) - \rho_{\gamma}(t+\delta)\|_{\infty}}{1 - \|\rho_{\gamma}(t+\delta)^{+}\|_{\infty} \|\rho_{\gamma}^{\Delta}(t) - \rho_{\gamma}(t+\delta)\|_{\infty}} \\ &= 0. \end{aligned} $$

The last line follows by choosing $\Delta$ sufficiently small. This immediately implies the desired relation

$$ \lim_{\Delta \to 0} D_{\max}^{T_0, \Delta, \gamma} = 0. \quad (521) $$

and we obtain that

$$ - \lim_{n \to \infty} \log[\mu([-T_0, T_0]) - \eta^*(\delta, \rho^{\otimes n}, \mu)] \ge \inf_{\substack{-T_0 \le t, t' \le T_0 \\ |t-t'| > 2\delta}} R(\rho_{\gamma}(t), \rho_{\gamma}(t'), \{M^{(n)}\}) - \log(1/(1-\gamma)). \quad (522) $$

Finally, we let $\gamma \to 0$ and $T_0 \to \infty$, which recovers the theorem statement. $\square$

Looking at the structure of the above proofs, we see that Open Problem 5 could be solved if there exists a measurement $M(\lambda)$ such that in the discrete setting the pairwise discrimination error of the outcome distributions $\{\Lambda_i = M[\rho_i]\}_{i=1}^N$ fulfills

$$ \max_{\substack{1 \le i, j \le N \\ \exists k: W_{i,k} = W_{j,k} = 1}} P_e(p_i \Lambda_i, p_j \Lambda_j) \le C \max_{\substack{1 \le i, j \le N, \\ \exists k: W_{i,k} = W_{j,k} = 1}} \min_{0 \le s \le 1} \mathrm{Tr}[\rho_i^s \rho_j^{1-s}], \quad (523) $$

where the constant $C$ can be polynomial in the number of discrete states and the dimension of the underlying system, as i.i.d. states live in the symmetric subspace.
VIII. OPTIMAL TOLERANCE

In this section, we will focus our attention on the rectangular window with tolerance $\delta$. Until now, we have analyzed the problem of finding and optimizing the success probability we can guarantee for a fixed window size $\delta$. It is however also operationally meaningful to ask the reverse question: How small can we make the window tolerance $\delta$ while keeping the probability of success constant? This is especially interesting, as this quantity compares more naturally to the usual quantifiers in quantum metrology, namely the standard deviation.

We defined the success probability of a metrology protocol over states $\rho(t)$ with prior $\mu(t)$ as a quantity dependent on $\delta$ as $\eta(\delta) = \eta(\delta, \mu, \rho, Q)$. In the same spirit, we now define the optimal tolerance (as in the main text) as

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

If the function $\eta(\delta, \mu, \rho, Q)$ is injective in $\delta$, this is functionally equivalent to the inverse of this function seen as a map from $\delta$ to $\eta$. Contrary to $\eta$, the quantity $\delta$ cannot be written as a semi-definite program, because the dependence of $\eta$ onto $\delta$ is non-linear. The associated minimax quantities are defined likewise.

We can learn something about the relation between $\eta$ and $\delta$ by performing a Taylor expansion:

**Proposition 31** (Limit for smooth POVMs). For a rectangular window with small tolerance $\delta$, a set of states $\rho(t)$, possibly with prior $\mu(t)$ and a fixed smooth POVM $Q(\tau)$, we have that

$$ \eta(\delta, \mu, \rho, Q) = 2\delta \int d\mu(t) \operatorname{Tr}[\rho(t)Q(t)] + O(\delta^3), \qquad (525) $$

$$ \bar{\eta}(\delta, \rho, Q) = 2\delta \min_t \operatorname{Tr}[\rho(t)Q(t)] + O(\delta^3). \qquad (526) $$

*Proof.* A simple Taylor expansion of $Q$ around $Q(t)$ gives

$$ Q(t + \tau) = Q(t) + \tau \dot{Q}(t) + \frac{1}{2} \tau^2 \ddot{Q}(t) + O(\tau^3). \qquad (527) $$

Integrating this from $-\delta$ to $\delta$ yields

$$ \int_{-\delta}^{\delta} d\tau Q(t + \tau) = 2\delta Q(t) + \frac{1}{3}\delta^3 \ddot{Q}(t) + O(\delta^4). \qquad (528) $$

As

$$ \eta(\delta, \mu, \rho, Q) = \int d\mu(t) \int_{-\delta}^{\delta} d\tau \operatorname{Tr}[\rho(t)Q(t+\tau)], \qquad (529) $$

the statement of the proposition in the Bayesian case follows. The minimax case is also evident when recognizing that we just have to take a minimum of the same expression. $\square$

The above proposition highlights that in the limit of small $\delta$, the optimal POVM is independent of $\delta$, at least if we optimize over smooth POVMs only. We can also use it to give a simple proof of Proposition 28 of the main text:

*Proof of Proposition 28.* The formula for the derivative $\partial_{\delta}\eta$ at $\delta = 0$ can be readily read off the result of Proposition 31, the statement then follows by applying the formula for the first derivative of the inverse function. $\square$

A. Lower bounds via asymmetric hypothesis testing

In this section, we provide lower bounds on the size of the window function in terms of asymmetric hypothesis testing. We refer to Section VIID for a brief description of asymmetric hypothesis testing.

**Theorem 32.** For a given window function $w$ and set of states $\rho(t)$, we have for every quantum state $\sigma$ and constant $0 < \eta_0 \le \bar{\eta}^*(w, \rho)$ that

$$ \int dt w(t) \ge \int dt \beta_{1-\eta_0}(\rho(t)\|\sigma). \qquad (530) $$
**Proof.** By duality of semi-definite problems, it holds that the optimal type-II error probability defined in (386) can be expressed as [17]

$$ \beta_{\epsilon}(\rho\|\sigma) = \sup\{\mu(1-\epsilon) - \text{Tr}[X] : \mu \ge 0, X \ge 0, \mu\rho \le \sigma + X\}. \quad (531) $$

Define $\bar{\mu}(t)$, $\bar{X}(t)$ to be the optimal candidates in this convex problem, such that $\bar{\mu}(t)\rho(t) \le \sigma + \bar{X}(t)$ and $\beta_{1-\eta_0}(\rho(t)\|\sigma) = \bar{\mu}(t)\eta_0 - \text{Tr}[\bar{X}(t)]$. The strategy of the proof is to find dual candidates in the convex program for $\bar{\eta}^*(w, \rho)$ in (149).

Let $\nu = [\int dt \bar{\mu}(t)]^{-1}$ and let $\mu(t) = \nu\bar{\mu}(t)$, and observe that $\int dt \mu(t) = 1$. Let

$$ \delta = \frac{1}{2} \int dt w(t). \quad (532) $$

For any $t' \in \mathbb{R}$, we find

$$ \begin{aligned} \int dt \mu(t) w(t-t') \rho(t) &= \nu \int dt w(t-t') \bar{\mu}(t) \rho(t) \quad (533) \\ &\le \nu \int dt w(t-t') [\sigma + \bar{X}(t)] \\ &\le 2\nu\delta\sigma + \nu \int dt \bar{X}(t), \end{aligned} $$

where for the second term in the last line we have used the fact that $w(t-t') \le 1$. Defining

$$ X = 2\nu\delta\sigma + \nu \int dt \bar{X}(t) \quad (534) $$

thus ensures that

$$ \int dt \mu(t) w(t-t') \rho(t) \le X. \quad (535) $$

Therefore, $\mu(t)$ and $X$ are feasible candidates in the dual problem for $\bar{\eta}^*(w, \rho)$. The objective value attained by this choice of variables directly gives us an upper bound on the optimal value $\bar{\eta}^*(w, \rho)$, i.e.,

$$ \bar{\eta}^*(w, \rho) \le \text{Tr}[X] = 2\nu\delta + \nu \int dt \text{Tr}[\bar{X}(t)]. \quad (536) $$

The second term of (536) is

$$ \begin{aligned} \nu \int dt \operatorname{Tr}[\bar{X}(t)] &= \nu \int dt (\bar{\mu}(t)\eta_0 - \beta_{1-\eta_0}(\rho(t)\|\sigma)) \\ &= \eta_0 - \nu \int dt \beta_{1-\eta_0}(\rho(t)\|\sigma), \end{aligned} \quad (537) $$

where the first equality follows from the properties of the optimal candidates in the convex problem defining hypothesis testing entropy, and the second by the definition of $\nu$. Plugging this into Eq. (536), and recalling that $\eta_0 \le \bar{\eta}^*(w, \rho)$, we find

$$ \eta_0 \le \bar{\eta}^*(w, \rho) \le \eta_0 + \nu \left[ 2\delta - \int dt \beta_{1-\eta_0}(\rho(t)\|\sigma) \right], \quad (538) $$

which implies that

$$ \nu \left[ 2\delta - \int dt \beta_{1-\eta_0}(\rho(t)\|\sigma) \right] \ge 0. \quad (539) $$

Finally, because $\nu \ge 0$, we obtain

$$ 2\delta \ge \int dt \beta_{1-\eta_0}(\rho(t)\|\sigma). \quad (540) $$

This proves the claim, recalling the definition of $\delta$ in Eq. (532). $\square$

<figure><img src="image_18.png" /></figure>
Alternatively, the theorem states that for any $0 < \eta_0 \le 1$, any attempt to use a window function that is not as wide as prescribed by (530) will result in a success probability $\bar{\eta}^*(w, \rho)$ that is less than $\eta_0$. The left hand side of (530) is a measure of the width of the window function.

We can now give the proof of the asymptotic lower bound of Theorem 36 from the main text. For this, we need the famous Laplace's method which we use in the following simplified version (see, e.g., Ref. [156]):

**Lemma 33 (Laplace's method).** Let $\phi(x)$ be a twice continuous differentiable function such that it has a unique minimum $\phi(x_0) = 0$. Then, for any interval $I$ that contains $x_0$ in its interior, we have that

$$ \int_I dx \exp(-n\phi(x)) = \sqrt{\frac{2\pi}{n\phi''(x_0)}} + O(n^{-3/2}). \quad (541) $$

We can now prove the desired statement:

Using a $\delta$ window and a suitably chosen state $\sigma$ we can obtain the following corollary.

**Corollary 34.** For a rectangular window function with tolerance $\delta$ and a state set $\rho(t)$, we have for any $\eta_0 \le \bar{\eta}^*(w_\delta, \rho)$ that

$$ \delta \ge \frac{1}{2} \int dt \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t'))) \ge \sup_{\delta'>0} \delta' \sup_t \inf_{|t-t'|\le 2\delta'} \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (542) $$

*Proof.* As Theorem 32 holds for any state, we can also choose any $\rho(t')$. We therefore have

$$ 2\delta \ge \int dt \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (543) $$

We can now go further and restrict the integration to any interval $T$ of size $|T| = 2\delta'$ that contains $t'$ and maximize over these intervals:

$$ 2\delta \ge \sup_{|T|=2\delta' \ t' \in T} \int_T dt \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (544) $$

We can now lower-bound the integral by the lower-bound of the integrand over the interval to obtain

$$ 2\delta \ge 2\delta' \sup_{|T|=2\delta' \ t' \in T} \inf_{t' \in T} \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (545) $$

As $t'$ has been arbitrary, we can instead just optimize over $T$ as well to obtain

$$ 2\delta \ge 2\delta' \sup_{|T|=2\delta' \ t' \in T} \sup_{t \in T} \inf \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (546) $$

As $t$ and $t'$ have to lie in the same interval, we have that

$$ 2\delta \ge 2\delta' \sup_t \inf_{|t-t'|\le 2\delta'} \exp(-D_h^{\eta_0}(\rho(t)\|\rho(t))). \quad (547) $$

The statement of the Corollary follows by optimizing over $\delta'$ and dividing by 2. $\square$

The above result allows us to exploit Laplace's method and the relation of the hypothesis testing relative entropy with the sandwiched Rényi relative entropies of Eq. (64) to get an asymptotic bound. We will use Laplace's method in the following simplified version (see, e.g., Ref. [156]):

**Lemma 35 (Laplace's method).** Let $\phi(x)$ be a twice continuous differentiable function such that it has a unique minimum $\phi(x_0) = 0$. Then, for any interval $I$ that contains $x_0$ in its interior, we have that

$$ \int_I dx \exp(-n\phi(x)) = \sqrt{\frac{2\pi}{n\phi''(x_0)}} + O(n^{-3/2}). \quad (548) $$
The asymptotic behavior of the hypothesis testing bound is dominated by the hypothesis testing relative entropy of states close in time. In this case, the information measure induced by the sandwiched Rényi relative entropy [6] becomes relevant. We denote it by $\tilde{\mathcal{I}}_\alpha(t)$ and it is implicitly defined via [157]

$$ \tilde{D}_{\alpha}(\rho(t) \| \rho(t+\delta)) = \frac{\alpha}{2} \delta^2 \tilde{\mathcal{I}}_{\alpha}(t) + O(\delta^3). \qquad (549) $$

We obtain the following asymptotic result that reproduces the scaling of the standard quantum limit:

**Proposition 36 (Asymptotic lower bound).** For all $\alpha > 1$, the optimal minimax tolerance for a given minimax success probability $\bar{\eta}$ obeys the inequality

$$ \bar{\delta}^*(\bar{\eta}, \rho^{\otimes n}) \geq \frac{1}{2} \bar{\eta}^{\frac{\alpha}{\alpha-1}} \sqrt{\frac{2\pi}{\alpha n \tilde{\mathcal{I}}_\alpha}} + O\left(\frac{1}{n^{3/2}}\right) \qquad (550) $$

where

$$ \tilde{\mathcal{I}}_{\alpha} := \min_{t} \tilde{\mathcal{I}}_{\alpha}(\rho(t)). \qquad (551) $$

As Theorem 18, the above theorem visibly reminds us of the Quantum Cramér-Rao in the scaling of $n$, but the dependence on $\bar{\eta}$ is inferior.

*Proof.* We start from Proposition 28. To obtain a lower bound, we employ the standard upper bound

$$ D_{\text{h}}^{\eta_0}(\rho \| \sigma) \leq \tilde{D}_{\alpha}(\rho \| \sigma) + \frac{\alpha}{\alpha-1} \log \frac{1}{\eta_0} \qquad (552) $$

on the hypothesis testing relative entropy via the sandwiched Rényi relative entropies [17], which holds for $1 < \alpha < \infty$. We now set $\sigma = \rho^{\otimes n}(t')$ for some $t'$ to be determined later. Exploiting the additivity of the sandwiched Rényi relative entropy, we obtain

$$ \begin{aligned} \bar{\delta}(\bar{\eta}, \rho^{\otimes n}) &\geq \frac{1}{2} \int dt \exp \left( -n \tilde{D}_{\alpha}(\rho(t) \| \rho(t')) - \frac{\alpha}{\alpha-1} \log \frac{1}{\bar{\eta}} \right) \\ &= \frac{1}{2} \bar{\eta}^{\frac{\alpha}{\alpha-1}} \int dt \exp \left( -n \tilde{D}_{\alpha}(\rho(t) \| \rho(t')) \right). \end{aligned} \qquad (553) $$

The integral on the right hand side can be evaluated by a simple application of Laplace's method as given in Lemma 35, recognizing that $\tilde{D}_\alpha(\rho(t)\|\rho(t'))$ achieves its minimum for $t = t'$, yielding

$$ \bar{\delta}(\bar{\eta}, \rho^{\otimes n}) \geq \frac{1}{2} \bar{\eta}^{\frac{\alpha}{\alpha-1}} \sqrt{\frac{2\pi}{n \tilde{D}_{\alpha}''(t')}} + O(n^{-3/2}), \qquad (554) $$

where we have denoted

$$ \tilde{D}_{\alpha}''(t') = \left. \frac{\partial^2}{\partial \Delta^2} \tilde{D}_{\alpha}(\rho(t' + \Delta) \| \rho(t')) \right|_{\Delta=0}. \qquad (555) $$

The second order expansion of the sandwiched Rényi relative entropy was studied in Ref. [157]. We have that

$$ \tilde{D}_{\alpha}''(t') = \alpha \tilde{\mathcal{I}}_{\alpha}(t'), \qquad (556) $$

where $\tilde{\mathcal{I}}_\alpha$ interpolates between the Bogoliubov-Kubo-Mori (BKM) information in the limit $\alpha \to 1$ and other information measures. The associated Petz function is given by

$$ f_{\alpha}(t) = (\alpha - 1) \frac{t^{1/\alpha}}{1 - t^{(1-\alpha)/\alpha}}. \qquad (557) $$

Optimizing over $t'$ yields $\tilde{\mathcal{I}}_\alpha := \min_{t'} \tilde{\mathcal{I}}_\alpha(t')$. Putting this into the bound then gives

$$ \bar{\delta}(\bar{\eta}, \rho^{\otimes n}) \geq \frac{1}{2} \bar{\eta}^{\frac{\alpha}{\alpha-1}} \sqrt{\frac{2\pi}{n\alpha \tilde{\mathcal{I}}_{\alpha}}} + O(n^{-3/2}). \qquad (558) $$

□
## B. Lower bound via symmetric hypothesis testing

In this section, we will give the proof of the non-asymptotic Cramér-Rao like bound presented in Theorem 18 of the main text.

*Proof of Theorem 18.* Our derivation starts from Corollary 12, which states that

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

Using the fact that the sandwiched Rényi relative entropy of order 1/2 is given by

$$\tilde{D}_{\frac{1}{2}}(\rho \| \sigma) = -\frac{1}{2} \log F(\rho, \sigma) \quad (560)$$

and choosing $t' = t + 2\delta$, we obtain

$$\log \frac{1}{4(1 - \bar{\eta})} \leq 4 \inf_t \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t + 2\delta)), \quad (561)$$

as we can readily compare to Eq. (66) of the main text. Our desire is now to determine the scale of $\delta$ that we are allowed to choose. To this end, we perform a Taylor expansion of $\tilde{D}_{\frac{1}{2}}$:

$$\tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t + \tau)) = \sum_{k=2}^{\infty} \frac{f_k \tau^k}{k!} \quad (562)$$

$$= \frac{1}{2} f_2(t) \tau^2 + \frac{1}{6} f_3(t) \tau^3 + \frac{1}{24} f_4(t) \tau^4 + \dots \quad (563)$$

We assume that the Taylor expansion is valid in a radius of convergence $|\tau| < R(t)$. The coefficients $f_k(t)$ are given by

$$f_k(t) := \left. \frac{\partial^k}{\partial \tau^k} \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t + \tau)) \right|_{\tau=0}. \quad (564)$$

As the quantum Fisher information can be defined via [6]

$$\mathcal{F}(t) := -2 \left. \frac{\partial^2}{\partial \tau^2} F(\rho(t), \rho(t+\tau))^2 \right|_{\tau=0}, \quad (565)$$

we have that – as, for example discussed in Appendix C of Ref. [6] –

$$f_2(t) = -\frac{1}{2} \left. \frac{\partial^2}{\partial \tau^2} \log F(\rho(t), \rho(t+\tau)) \right|_{\tau=0} \quad (566)$$

$$= -\frac{1}{4} \left. \frac{\partial^2}{\partial \tau^2} \log F(\rho(t), \rho(t+\tau))^2 \right|_{\tau=0} \quad (567)$$

$$= -\frac{1}{4} \left( \left. \frac{\partial}{\partial F} \log(F) \right|_{F=1} \right) \left( \left. \frac{\partial^2}{\partial \tau^2} F(\rho(t), \rho(t+\tau))^2 \right|_{\tau=0} \right) \quad (568)$$

$$= \frac{1}{8} \mathcal{F}(t). \quad (569)$$

We note that the higher derivatives of the sandwiched Rényi relative entropy do not coincide anymore with the higher derivatives of the fidelity up to a constant. Having established the relation between the leading terms of the expansions of fidelity and the sandwiched Rényi relative entropy, we can now turn to the actual scale of $\delta$. As was made intuitive in the main text, for i.i.d. copies we are able to asymptotically choose $\delta = O(1/\sqrt{f_2}) = O(1/\sqrt{\mathcal{F}})$, the same scaling we expect from the quantum Cramér-Rao bound. We will thus make the ansatz

$$\tau = 2\delta = \frac{\gamma(t)}{\sqrt{f_2(t)}} \quad (570)$$
in Eq. (562). In this case, we have

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

To obtain a general upper bound for this expression, we define the constant

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

such that we can bound the fractions $f_p(t)/f_2^{p/2}(t)$ in Eq. (571) as

$$ \tilde{D}_{\frac{1}{2}}(\rho(t) \| \rho(t+\tau)) \le \frac{1}{2}\gamma^2(t) + \frac{1}{3!}q(t)\gamma^3(t) + \frac{1}{4!}q^2(t)\gamma^4(t) + \dots \quad (573) $$

$$ = \frac{1}{q^2(t)} \left( e^{q(t)\gamma(t)} - 1 - q(t)\gamma(t) \right). \quad (574) $$

We now insert this bound into Eq. (561) to obtain

$$ \frac{1}{4} \log \frac{1}{4(1-\bar{\eta})} \le \frac{1}{q^2(t)} \left( e^{q(t)\gamma(t)} - 1 - q(t)\gamma(t) \right). \quad (575) $$

We observe that the right hand side is always non-negative and that this only gives a nontrivial bound if $\bar{\eta} > 3/4$, similarly to Corollary 12. We will henceforth assume that this condition is met. Substituting the left hand side as $a = -\log(4(1-\bar{\eta}))/4$, we can now solve the above for equality using Mathematica

Solve[
  { (Exp[q\[Gamma]] - 1 - q\[Gamma]) / q^2 == a, q > 0 },
  \[Gamma]
]

to obtain

$$ \gamma_+(t) = -\frac{1}{q(t)} \left[ 1 + a q^2(t) + W_k(-e^{-1-a q^2(t)}) \right], \quad (576) $$

where $W_k(x)$ is the product logarithm function, i.e., the solution of $we^w = x$. The integer $k$ identifies the corresponding branch, in our case $k = -1$ is relevant because the argument $-e^{-1-aq^2(t)}$ lies between $-1/e$ and $0$. $\gamma_+(t)$ identifies the smallest admissible $\gamma$ we can take to still satisfy Corollary 12 for fixed reference time $t$. We can now continue to place bounds on $\gamma_+(t)$. To do so, we exploit the results of Ref. [158] that show that

$$ -1 - \sqrt{2u} - u < W_{-1}(-e^{-u-1}) < -1 - \sqrt{2u} - \frac{2}{3}u. \quad (577) $$

Identifying $u = aq^2(t)$ and inserting into Eq. (576) yields

$$ \sqrt{2a} - \frac{1}{3}aq(t) < \gamma_+(t) < \sqrt{2a}. \quad (578) $$

Substituting $a = -\log(4(1-\bar{\eta}))/4$ then gives

$$ \sqrt{\frac{1}{2} \log \frac{1}{4(1-\bar{\eta})} - \frac{q(t)}{12}} \log \frac{1}{4(1-\bar{\eta})} < \gamma_+(t) < \sqrt{\frac{1}{2} \log \frac{1}{4(1-\bar{\eta})}}. \quad (579) $$

We now use the fact that we chose $2\delta(t) = \gamma(t)/\sqrt{f_2(t)}$ and $f_2(t) = \mathcal{F}(t)/8$ to deduce

$$ \bar{\delta}(\bar{\eta}, \rho) \ge \sup_t \frac{1}{2} \frac{\gamma_+(t)}{\sqrt{f_2(t)}} \quad (580) $$

$$ = \sup_t \frac{\sqrt{2\gamma_+(t)}}{\sqrt{\mathcal{F}(t)}}. \quad (581) $$
To obtain the Theorem statement, we define

$$q := \sup_t q(t). \tag{582}$$

The coefficient $\Gamma(t) := \sqrt{2\gamma(t)}$ now fulfills the inequality

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

This holds especially for the $t$ achieving $\inf_t \mathcal{F}(t)$ in Eq. (580) and as such completes the Theorem statement. □

## IX. OPTIMAL SAMPLE COMPLEXITY

In this section, we provide supplementary material for Section VIII of the main text.

*Proof of Corollary 20.* Theorem 18 states that

$$\bar{\delta}(\bar{\eta}, \rho) \ge \frac{\Gamma}{\sqrt{\inf_t \mathcal{F}(t)}}, \tag{584}$$

where

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

We thus have the lower bound

$$\bar{\delta}(\bar{\eta}, \rho) \ge \frac{\sqrt{\log \frac{1}{4(1-\bar{\eta})}}}{\sqrt{\inf_t \mathcal{F}(t)}} - \frac{\frac{q}{6\sqrt{2}} \log \frac{1}{4(1-\bar{\eta})}}{\sqrt{\inf_t \mathcal{F}(t)}}. \tag{586}$$

Inserting the assumptions of the Corollary then establishes the scalings

$$\bar{\delta}(\bar{\eta}, \rho) \ge O(n^{-\frac{\alpha}{2}}) \sqrt{\log \frac{1}{4(1-\bar{\eta})}} - o(1)O(n^{-\frac{\alpha}{2}}) \log \frac{1}{4(1-\bar{\eta})}. \tag{587}$$

After rearranging, we have

$$O(n^{\frac{\alpha}{2}}) \ge \frac{\sqrt{\log \frac{1}{4(1-\bar{\eta})}}}{\bar{\delta}(\bar{\eta}, \rho)} - \frac{o(1) \log \frac{1}{4(1-\bar{\eta})}}{\bar{\delta}(\bar{\eta}, \rho)}, \tag{588}$$

which means that

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

as desired. □

## X. BEYOND UNIVARIATE METROLOGY

In the case of arbitrary parameter spaces, let us consider a parameters $x$ from a set $\mathcal{X}$ over which the prior distribution $\mu$ is defined such that $x \mapsto \rho(x)$. We assume that $\mathcal{X}$ is equipped with a distance measure $d(x, y)$ that is not necessarily symmetric. In this case, the definition of the Bayesian success probability becomes

$$\eta(w, \mu, \rho) = \int_{\mathcal{X}} d\mu(x) \int_{\mathcal{X}} dy w(d(x, y)) \mathrm{Tr}[\rho(x)Q(y)]. \tag{590}$$
Likewise, the minimax success probability is given by

$$ \bar{\eta}(w, \mu, \rho) = \inf_{x \in \mathcal{X}} \int_{\mathcal{X}} dy w(d(x, y)) \mathrm{Tr}[\rho(x)Q(y)]. \quad (591) $$

In this definition, we associate any parameter $x$ the accepting POVM effect

$$ \tilde{Q}_w(x) := \int_{\mathcal{X}} dy w(d(x, y))Q(y), \quad (592) $$

which takes the role of $(w * Q)(t)$ in the univariate case. To see how our results extend in this realm, we introduce a generalization of Theorem 16. For it, we only need the further notion of a *space-preserving transformation*:

**Definition 43 (Space-preserving transformation).** We call a transformation $\mathcal{T}: \mathcal{X} \to \mathcal{X}$ space-preserving if it is invertible and $\mathcal{T}[\mathcal{X}] = \mathcal{X}$.

We now give a generalization of Theorem 16 which in turn generalizes Theorem 10 of the main text:

**Theorem 37.** For a given parameter space $\mathcal{X}$ with distance function $d$ and window function $w$, fix any set $S = \{(\lambda, \mathcal{T})\}$ of prior probabilities $\lambda \ge 0$ and space-preserving transformations $\mathcal{T}$ such that $\sum_{\lambda \in S} \lambda = 1$. Then, for a state set $\rho(x)$, possibly with prior $\mu(x)$, we have the upper bounds

$$ \eta^*(w, \mu, \rho) \le K \int_{\mathcal{X}} dx P_s^* (\{\lambda \mu(\mathcal{T}[x])\rho(\mathcal{T}[x])\}_{(\lambda, \mathcal{T}) \in S}), \quad (593) $$

$$ \bar{\eta}^*(w, \rho) \le K \inf_{x \in \mathcal{X}} \bar{P}_s^* (\{\rho(\mathcal{T}[x])\}_{\mathcal{T} \in S}), \quad (594) $$

where we have introduced the constant

$$ K := \sup_{x,y \in \mathcal{X}} \left\{ \sum_{\mathcal{T} \in S} w(d(\mathcal{T}[x], y)) \right\}, \quad (595) $$

which measures the overlap of the windows for the different transformations.

*Proof.* First, we recall the definition of the optimal multi-hypothesis testing success probability for a set of operators $\{A_i\}$:

$$ P_s^*(\{A_i\}) := \sup_{\substack{0 \le Q_i \le \mathbb{I} \\ \sum_i Q_i = \mathbb{I}}} \sum_i \mathrm{Tr}[A_i Q_i]. \quad (596) $$

We exploit that the transformations are space-preserving and we can thus transform the domain of integration that computes the success probability arbitrarily, to observe that

$$ \eta(\delta, \mu, \rho, Q) = \sum_{(\lambda, \mathcal{T}) \in S} \int_{\mathcal{X}} dx \, \lambda \mathrm{Tr}[\mu(\mathcal{T}[x])\rho(\mathcal{T}[x])\tilde{Q}_w(\mathcal{T}[x])]. \quad (597) $$

Using the definition of $K$ given in the theorem statement, we see that defining the operators

$$ \bar{Q}_{\mathcal{T}}(x) := \frac{1}{K} \tilde{Q}_w(\mathcal{T}[x]) \quad (598) $$

yields a valid sub-normalized POVM for all $x$ as

$$ \begin{align} \sum_{\mathcal{T} \in S} \bar{Q}_{\mathcal{T}}(x) &= \frac{1}{K} \sum_{\mathcal{T} \in S} \tilde{Q}_w(\mathcal{T}[x]) \tag{599} \\ &= \frac{1}{K} \sum_{\mathcal{T} \in S} \int_{\mathcal{X}} dy w(d(\mathcal{T}[x], y))Q(y) \nonumber \\ &= \frac{1}{K} \int_{\mathcal{X}} dy \left( \sum_{\mathcal{T} \in S} w(d(\mathcal{T}[x], y)) \right) Q(y) \nonumber \\ &\le \frac{1}{K} \int_{\mathcal{X}} dy KQ(y) \nonumber \\ &\le \mathbb{I}. \nonumber \end{align} $$
This means that the operators {$\overline{Q}_{\mathcal{T}}(x)}_{\mathcal{T}\in\mathcal{S}}$ can serve as a candidate POVM in the optimization that computes $P_s(\{\lambda \mu(\mathcal{T}[x])\rho(\mathcal{T}[x])\}_{(\lambda,\mathcal{T})\in\mathcal{S}})$, and hence

$$ \eta(w, \mu, \rho, Q) \le K \int dt P_s^*(\{\lambda \mu(\mathcal{T}[x])\rho(\mathcal{T}[x])\}_{(\lambda, \mathcal{T}) \in \mathcal{S}}) \quad (600) $$

which implies the first statement of the theorem as the upper bound is independent of the chosen POVM $Q(y)$.

The minimax statement is derived in a similar fashion, observing that we can also apply the transformation trick to obtain

$$ \begin{aligned} \bar{\eta}(w, \rho, Q) &= \sum_{(\lambda, \mathcal{T}) \in \mathcal{S}} \lambda \inf_{x \in \mathcal{X}} \mathrm{Tr}[\rho(\mathcal{T}[x]) \tilde{Q}_w(\mathcal{T}[x])] && (601) \\ &\le \inf_{x \in \mathcal{X}} \sum_{(\lambda, \mathcal{X}) \in \mathcal{S}} \lambda \mathrm{Tr}[\rho(\mathcal{T}[x]) \tilde{Q}_w(\mathcal{T}[x])] . \end{aligned} $$

Here, we again make the argument that the {$\overline{Q}_{\mathcal{T}}(x)}_{\mathcal{T}\in\mathcal{S}}$ form a candidate POVM and then optimize over all possible $\lambda$ to obtain the theorem statement. $\square$

Note that if $K$ in the above theorem is larger than the inverse success probability, then the bound becomes vacuous. This means, as the success probability asymptotically approaches 1, any bound that should work asymptotically must have $K = 1$. Let us now turn to the practically important task of the rectangular window with tolerance $\delta$: We can define a distance ball around a points as

$$ \mathcal{B}_{\delta}(x) := \{y \in \mathcal{X} \mid d(x, y) \le \delta\}. \quad (602) $$

In this case, the definition of the accepting POVM effect becomes

$$ \tilde{Q}_{\delta}(x) := \int_{\mathcal{B}_{\delta}(x)} dy Q(y). \quad (603) $$

The transformation that ensure that different balls do not overlap and hence $K = 1$ are the ones that make sure that for all $x, y \in \mathcal{X}$ there is at most one among the {$\mathcal{T}[x]}$ such that $d(\mathcal{T}[x], y) \le \delta$. In other words, if we define the union of all balls of size $\delta$ around $x$ as

$$ \mathcal{U}_{\delta}(x) := \bigcup \{\mathcal{B}_{\delta}(y) \mid x \in \mathcal{B}_{\delta}(y)\}, \quad (604) $$

then

$$ K = 1 \Leftrightarrow \text{ for all } x \in \mathcal{X}, \mathcal{T} \in \mathcal{S}: x \notin \mathcal{U}_{\delta}(\mathcal{T}[x]). \quad (605) $$

This is analogous to the notion that metrology is as hard as distinguishing two points that are at least $2\delta$ apart in the univariate case. For very small $\delta$, one expects that $\mathcal{U}_{\delta}(x) \approx \mathcal{B}_{2\delta}(x)$.

We can cast the above reasoning into a corollary that can be seen as an analogue of Le Cam's two-point method:

**Corollary 38 (Generalized two-point method).** For a given parameter space $\mathcal{X}$ with distance function $d$ and given tolerance $\delta$, we have that

$$ \bar{\eta}^*(\delta, \rho) \le \inf_{\substack{x, y \in \mathcal{X} \\ y \notin \mathcal{U}_{\delta}(x)}} \bar{P}_s^*(\rho(x), \rho(y)). \quad (606) $$

# XI. THE COVARIANT CASE: PURE HAMILTONIAN EVOLUTION

In this section, we initiate the analytical study of the minimax success probability in a group-covariant setting. We consider a set of states $|\psi(t)\rangle$ generated by unitary evolution of a pure initial state $|\psi\rangle$ under a Hamiltonian $H$ reflecting closed system quantum mechanical evolution, i.e.

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

To ensure the group structure, $H$ must have eigenvalues such that all differences between eigenvalues are integer, 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 write

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

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

$$|\psi(t)\rangle = \sum_{\lambda} \psi_{\lambda} e^{-it\lambda} |\psi_{\lambda}\rangle \qquad (609)$$

and

$$ \begin{aligned} \psi(t) &= |\psi(t)\rangle\langle\psi(t)| \tag{610} \\ &= \sum_{\lambda, \lambda'} \psi_{\lambda} \psi_{\lambda'}^* e^{-i\omega(t-\lambda-\lambda')} |\psi_{\lambda}\rangle\langle\psi_{\lambda'}| \\ &= \sum_{\omega} e^{-i\omega t} \sum_{\lambda} \psi_{\lambda} \psi_{\lambda-\omega}^* |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| \\ &= \sum_{\omega} e^{-i\omega t} \hat{\psi}_{\omega}, \end{aligned} $$

where we have made use of $\psi(t)$ to denote the density matrix associated with the state $|\psi(t)\rangle$ and $\hat{\psi}_{\omega}$ are the coefficients of its Fourier transform given by

$$\hat{\psi}_{\omega} = \frac{1}{2\pi} \int dt e^{-i\omega t} \psi(t). \qquad (611)$$

In this setting, we can identify the optimal measurement strategy for any window function.

**Theorem 39 (PGM is minimax optimal).** For a state set $\rho(t)$ given by a pure initial 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 (PGM)

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

achieves the optimal minimax success probability for any window function $w(\tau)$. The minimax success probability is given by

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

where $\hat{w}_{\omega}$ is the Fourier transform of $w(\tau)$ at frequency $\omega$.

*Proof.* The pretty good measurement is by definition a valid POVM and thus a feasible point for the primal problem given in Proposition 2. The associated success probability is now independent of $t$, and we can thus let go of the minimum, to get

$$ \begin{aligned} \bar{\eta}_{\text{PGM}} &= \min_t \operatorname{Tr}[\psi(t)(w * Q_{\text{PGM}})(t)] \tag{614} \\ &= \min_t \int d\tau \operatorname{Tr}[\psi(t)w(\tau)Q(t-\tau)] \\ &= \int d\tau \operatorname{Tr}[\psi(0)w(\tau)Q_{\text{PGM}}(-\tau)] \\ &= \int d\tau \operatorname{Tr}[\psi(0)w(\tau)Q_{\text{PGM}}(\tau)] \\ &= \int d\tau w(\tau)f(\tau), \end{aligned} $$
where we have used the symmetry of $\tau$ and the fact that we integrate over a cyclic interval. Now, if we look closely at the definition of the pretty good measurement and compare to Eq. (611), we see that

$$R = 2\pi \hat{\psi}_0 = 2\pi \sum_{\lambda} |\psi_{\lambda}|^2 |\psi_{\lambda}\rangle\langle\psi_{\lambda}|, \qquad (615)$$

which in turn implies that

$$R^{-1/2} = \frac{1}{\sqrt{2\pi}} \sum_{\lambda} \frac{1}{|\psi_{\lambda}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda}|. \qquad (616)$$

We can now use this to complete the POVM elements

$$\begin{aligned} Q(t) &= \frac{1}{2\pi} \left( \sum_{\lambda} \frac{1}{|\psi_{\lambda}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda}| \right) \left( \sum_{\omega} e^{-i\omega t} \sum_{\lambda} \psi_{\lambda} \psi_{\lambda-\omega}^* |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| \right) \left( \sum_{\lambda} \frac{1}{|\psi_{\lambda}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda}| \right) \\ &= \frac{1}{2\pi} \sum_{\omega} e^{-i\omega t} \sum_{\lambda} \frac{\psi_{\lambda} \psi_{\lambda-\omega}^*}{|\psi_{\lambda}| |\psi_{\lambda-\omega}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| \end{aligned} \qquad (617)$$

and evaluate $\bar{\eta}_{\text{PGM}}$ via

$$\begin{aligned} f(\tau) &= \text{Tr}[\psi(0)Q_{\text{PGM}}(\tau)] \\ &= \frac{1}{2\pi} \sum_{\omega} e^{-i\omega\tau} \text{Tr} \left\{ \left( \sum_{\lambda, \lambda'} \psi_{\lambda} \psi_{\lambda'}^* |\psi_{\lambda}\rangle\langle\psi_{\lambda'}| \right) \left( \sum_{\lambda} \frac{\psi_{\lambda} \psi_{\lambda-\omega}^*}{|\psi_{\lambda}| |\psi_{\lambda-\omega}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| \right) \right\} \\ &= \sum_{\omega} e^{-i\omega\tau} \sum_{\lambda} \frac{|\psi_{\lambda}| |\psi_{\lambda-\omega}|}{2\pi} \\ &= \sum_{\omega} e^{-i\omega\tau} \hat{f}_{\omega}. \end{aligned} \qquad (618)$$

With this, we can Parseval's theorem to determine

$$\begin{aligned} \bar{\eta}_{\text{PGM}} &= \int d\tau w(\tau) f(\tau) \\ &= 2\pi \sum_{\omega} \hat{w}_{\omega} \hat{f}_{\omega} \\ &= \sum_{\omega} \hat{w}_{\omega} \sum_{\lambda} |\psi_{\lambda}| |\psi_{\lambda-\omega}| \\ &= \sum_{\lambda, \lambda'} |\psi_{\lambda}| |\psi_{\lambda'}| \hat{w}_{\lambda-\lambda'} \end{aligned} \qquad (619)$$

as claimed in the theorem statement. Note that we can also see $f(\tau) = |p(\tau)|^2$ where

$$p(\tau) = \frac{1}{\sqrt{2\pi}} \sum_{\lambda} e^{-i\lambda\tau} |\psi_{\lambda}|. \qquad (620)$$

To show the optimality of the PGM, we use complementary slackness and give a feasible point of the dual. First, we use $\mu(t) = 1/2\pi$ as the dual prior. The only non-trivial complementary slackness condition then is

$$XQ(t) = \frac{1}{2\pi}(w * \psi)(t)Q(t). \qquad (621)$$

We first expand the right hand side in the frequency picture, using the duality of multiplication and convolution under the Fourier transform,

$$(w * \psi)(t)Q(t) = \sum_{\omega} e^{-i\omega t} \sum_{\delta} \hat{w}_{\delta} \hat{\psi}_{\delta} \hat{Q}_{\omega-\delta}. \qquad (622)$$