The complementary slackness condition can therefore be written as

$$ \sum_{\omega} e^{-i\omega t} \left( X \hat{Q}_{\omega} - \sum_{\delta} \hat{w}_{\delta} \hat{\psi}_{\delta} \hat{Q}_{\omega-\delta} \right) = 0. \qquad (623) $$

As we want the above to hold for all $t$, we expect this to require to hold independently for all frequencies, especially $\omega = 0$. This gives

$$ X \hat{Q}_0 = \sum_{\delta} \hat{w}_{\delta} \hat{\psi}_{\delta} \hat{Q}_{-\delta}. \qquad (624) $$

But, as we know that $Q$ is a valid POVM, we have that $\hat{Q}_0 = I/2\pi$, and hence we get a formula for $X$ given by

$$ \begin{aligned} X &= 2\pi \sum_{\delta} \hat{w}_{\delta} \hat{\psi}_{\delta} \hat{Q}_{-\delta} \\ &= \sum_{\delta} \hat{w}_{\delta} \hat{\psi}_{\delta} \hat{\psi}_{0}^{-\frac{1}{2}} \hat{\psi}_{-\delta} \hat{\psi}_{0}^{-\frac{1}{2}} \\ &= \sum_{\delta} \hat{w}_{\delta} \left( \sum_{\lambda} \psi_{\lambda} \psi_{\lambda-\delta}^{*} |\psi_{\lambda}\rangle\langle\psi_{\lambda-\delta}| \right) \left( \sum_{\lambda} \frac{1}{|\psi_{\lambda}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda}| \right) \left( \sum_{\lambda} \psi_{\lambda-\delta} \psi_{\lambda}^{*} |\psi_{\lambda-\delta}\rangle\langle\psi_{\lambda}| \right) \left( \sum_{\lambda} \frac{1}{|\psi_{\lambda}|} |\psi_{\lambda}\rangle\langle\psi_{\lambda}| \right) \\ &= \sum_{\delta} \hat{w}_{\delta} \sum_{\lambda} |\psi_{\lambda}| |\psi_{\lambda-\delta}| |\psi_{\lambda}\rangle\langle\psi_{\lambda}|. \end{aligned} \qquad (625) $$

We can immediately see that the dual value is correct, as

$$ \mathrm{Tr}[X] = \sum_{\delta} \hat{w}_{\delta} \sum_{\lambda} |\psi_{\lambda}| |\psi_{\lambda-\delta}|. \qquad (626) $$

It is left to be shown that $X$ and $\mu(t) = 1/2\pi$ constitute a feasible point of the dual, i.e., that

$$ X \geq \frac{1}{2\pi} (w * \psi)(t). \qquad (627) $$

Note that by construction, $X$ commutes with the Hamiltonian and is therefore invariant under time evolution, which means it is sufficient to check the above condition at $t = 0$, where it evaluates to

$$ X \geq \frac{1}{2\pi} \int d\tau w(\tau) \psi(\tau) = \sum_{\omega} \hat{w}_{\omega} \hat{\psi}_{\omega}, \qquad (628) $$

where we again used Parseval's theorem. We can then collect the hermitian conjugate terms to obtain

$$ \sum_{\omega \ge 0} \hat{w}_{\omega} \sum_{\lambda} (|\psi_{\lambda}|^2 |\psi_{\lambda-\omega}| + |\psi_{\lambda}|^2 |\psi_{\lambda+\omega}|) |\psi_{\lambda}\rangle\langle\psi_{\lambda}| \ge \sum_{\omega \ge 0} \hat{w}_{\omega} \sum_{\lambda} \psi_{\lambda} \psi_{\lambda-\omega}^{*} |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| + \psi_{\lambda} \psi_{\lambda+\omega}^{*} |\psi_{\lambda}\rangle\langle\psi_{\lambda+\omega}|, \qquad (629) $$

where we have used that $\hat{w}_{\omega} = \hat{w}_{-\omega}$ because it is a symmetric function. As $w$ is still arbitrary, this should hold for all $\omega$ independently. We can exploit that the sum runs over all $\lambda$, which allows us to replace $(\lambda, \lambda + \omega) \to (\lambda - \omega, \lambda)$ and obtain

$$ \begin{aligned} \sum_{\lambda} |\psi_{\lambda}|^2 |\psi_{\lambda-\omega}|^2 |\psi_{\lambda}\rangle\langle\psi_{\lambda}| + |\psi_{\lambda-\omega}|^2 |\psi_{\lambda}|^2 |\psi_{\lambda-\omega}\rangle\langle\psi_{\lambda-\omega}| \ge \\ \sum_{\lambda} \psi_{\lambda} \psi_{\lambda-\omega}^{*} |\psi_{\lambda}\rangle\langle\psi_{\lambda-\omega}| + \psi_{\lambda-\omega} \psi_{\lambda}^{*} |\psi_{\lambda-\omega}\rangle\langle\psi_{\lambda}|. \end{aligned} \qquad (630) $$

We can write this as a sum over matrix-inequalities on the subspaces spanned by $|\psi_{\lambda}\rangle$ and $|\psi_{\lambda-\omega}\rangle$ to arrive at the final

$$ \sum_{\lambda} \left[ \begin{array}{cc} |\psi_{\lambda}|^2 |\psi_{\lambda-\omega}| & \psi_{\lambda}^{*} \psi_{\lambda-\omega} \\ \psi_{\lambda-\omega}^{*} \psi_{\lambda} & |\psi_{\lambda}|^2 |\psi_{\lambda-\omega}| \end{array} \right]_{\lambda, \lambda-\omega} \geq 0. \qquad (631) $$
Denoting now for brevity $a = \psi_{\lambda}^{*}\psi_{\lambda-\omega}$ we can chat the inequality by computing the characteristic polynomial

$$ \det \begin{bmatrix} |a| - \alpha & a \\ a^{*} & |a| - \alpha \end{bmatrix} = \alpha^2 - 2|a|\lambda = \alpha(\alpha - 2|a|) \quad (632) $$

which has the two non-negative roots $0$ and $2|a|$, which, together with the fact that a sum of positive semi-definite matrices is positive-semi-definite, concludes the proof that $X$ is indeed a feasible point of the dual and hence the pretty good measurement is optimal. □

We can exploit the optimality of the pretty good measurement together with the formula for the minimax success probability to optimize the probe state. If we define the vector $\psi = (|\psi_{\lambda_1}|, |\psi_{\lambda_2}|, \dots, |\psi_{\lambda_d}|)$ and the matrix $W_{\lambda,\lambda'} = \hat{w}_{\lambda-\lambda'}$, we can write the minimax success probability of Eq. (613) as a quadratic form $\bar{\eta} = \langle \psi, W\psi \rangle$. This implies that the optimal probe state is the solution of a quadratic program over the positive orthant

$$ \begin{array}{ll} \bar{\eta}^*(w, U(\phi)) = & \underset{\substack{\text{maximize} \\ \text{over} \\ \text{such that}}} \langle \psi, W\psi \rangle \\ & \psi_i \ge 0 \\ & \sum_{i=1}^d \psi_i^2 = 1. \end{array} \quad (633) $$

Programs of this form are in general NP-hard to solve in worst case complexity, but as the optimization is over $n \times n$ matrices where $n$ is the number of channel repetitions, we can still use numerical methods to solve this problem for large numbers of qubits, as direct simulation is not required. Note that the normalization condition for $\psi$ implies that

$$ \bar{\eta}^*(w, U(\phi)) \le \|W\|_{\infty}. \quad (634) $$

By the Perron-Frobenius theorem, this bound is tight if the matrix $W$ has only positive entries, which is only guaranteed if the Fourier transform of the window function is a non-negative function, which will most of the time not be the case.

Every candidate for the optimal probe state will allow us to determine a lower bound on $\bar{\eta}^*(w, U(\phi))$. One such candidate is a uniform superposition of energy eigenstates $\psi = (1/\sqrt{d}, 1/\sqrt{d}, \dots, 1/\sqrt{d})$. This will give a near optimal success probability in the limit where $1/n$ is large compared to the spectral width of the window. This can be seen by noting that in this limit the first order expansion of the Fourier transform is approximately constant

$$ \hat{w}_{\lambda} \approx \hat{w}_{0} \quad (635) $$

In this case, the success probability is dominated by the one-norm of the vector $\|\psi\|_1$:

$$ \bar{\eta}^*(w, \psi) \approx \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}| \hat{w}_0 = \hat{w}_0 \|\psi\|_1^2. \quad (636) $$

This is only meant as an intuitive argument.

Let us make this more concise in the case of a $\delta$ window in the limit $\delta \to 0$. We can show the following proposition: **Proposition 40.** In the phase sensing example, for a rectangular window $w_{\delta}$ and a probe state $\psi(0)$, we have that

$$ \bar{\eta}^*(w, U(\phi)) \le \frac{\delta}{\pi} \left[ \mathrm{Tr}[\hat{\psi}_0^{\frac{1}{2}}]^2 - \frac{\delta^2}{2} \frac{2}{3} \mathrm{Var}_{\psi(0)}(H) + O(\delta^4) \right]. \quad (637) $$

*Proof.* We use the second order expansion

$$ \hat{w}_{\omega} = \frac{\sin \omega \delta}{\pi \omega} = \frac{\delta}{\pi} \left[ 1 - \frac{1}{2} \frac{\delta^2}{3} \omega^2 + O(\delta^4) \right]. \quad (638) $$

If we use this together with the formula for the success probability, where $\omega = \lambda - \lambda'$, we obtain

$$ \begin{align} \bar{\eta}^*(w, \psi) &= \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}| \hat{w}_{\lambda-\lambda'} \tag{639} \\ &= \frac{\delta}{\pi} \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}| \left[ 1 - \frac{1}{2} \frac{\delta^2}{3} \omega^2 + O(\delta^4) \right] \nonumber \\ &= \frac{\delta}{\pi} \left[ \|\psi\|_1^2 - \frac{1}{2} \frac{\delta^2}{3} \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}| (\lambda - \lambda')^2 + O(\delta^4) \right]. \nonumber \end{align} $$
The quadratic term can be recast into

$$ 
\begin{aligned}
\sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}|(\lambda - \lambda')^2 &= \sum_{\lambda, \lambda'} |\psi_{\lambda}||\psi_{\lambda'}|(\lambda^2 + \lambda'^2 - 2\lambda\lambda') \\
&= 2\|\psi\|_1 \sum_{\lambda} |\psi_{\lambda}|\lambda^2 - 2\left(\sum_{\lambda} |\psi_{\lambda}|\lambda\right)^2 \\
&= 2\left(\mathrm{Tr}[\hat{\psi}_0^{\frac{1}{2}}]\mathrm{Tr}[H^2\hat{\psi}_0^{\frac{1}{2}}] - \mathrm{Tr}[H\hat{\psi}_0^{\frac{1}{2}}]^2\right).
\end{aligned} 
\quad (640) $$

Now, we show that the map

$$ V(X) = \mathrm{Tr}[X] \mathrm{Tr}[H^2 X] - \mathrm{Tr}[HX]^2 \quad (641) $$

is an operator monotone. We can rewrite it as

$$ V(X) = \frac{1}{2} \mathrm{Tr}[(H^2 \otimes \mathbb{I} + \mathbb{I} \otimes H^2 - 2H \otimes H)(X \otimes X)] \quad (642) $$

and can explicitly check the positivity of the operator by checking its action on an products of eigenstates of $H|\lambda\rangle = \lambda|\lambda\rangle$ given by

$$ 
\begin{aligned}
(H^2 \otimes \mathbb{I} + \mathbb{I} \otimes H^2 - 2H \otimes H)|\lambda\lambda'\rangle &= (\lambda^2 + \lambda'^2 - 2\lambda\lambda')|\lambda\lambda'\rangle \\
&= (\lambda - \lambda')^2|\lambda\lambda'\rangle.
\end{aligned} 
\quad (643) $$

We can then also use the facts that

$$ A \ge B \ge 0 \Rightarrow A \otimes A \ge B \otimes B, \quad (644) $$

$$ A \ge B \Rightarrow \mathrm{Tr}[MA] \ge \mathrm{Tr}[MB] \quad \text{for all } M \ge 0, \quad (645) $$

to conclude that

$$ A \ge B \Rightarrow V(A) \ge V(B). \quad (646) $$

Considering

$$ \mathbb{I} \ge \psi(0) \ge 0 \Rightarrow \hat{\psi}_0^{\frac{1}{2}} \ge \psi(0) \quad (647) $$

together with the operator monotonicity of $V(X)$ allows us to conclude that

$$ V(\hat{\psi}_0^{\frac{1}{2}}) \ge V(\psi(0)) = \mathrm{Var}(H). \quad (648) $$

Putting this back into the success probability we obtain

$$ 
\begin{aligned}
\bar{\eta}^*(w, \psi) &= \frac{\delta}{\pi} \left[ \|\psi\|_1^2 - \frac{\delta^2}{2} \frac{2}{3} V(\hat{\psi}_0^{\frac{1}{2}}) + O(\delta^4) \right] \\
&\le \frac{\delta}{\pi} \left[ \mathrm{Tr}[\hat{\psi}_0^{\frac{1}{2}}]^2 - \frac{\delta^2}{2} \frac{2}{3} \mathrm{Var}(H) + O(\delta^4) \right].
\end{aligned} 
\quad (649) $$

□

The above proposition implies that as long $\delta n \ll 1$, the uniform superposition probe state will work well.

## XII. MINIMAX ANALYSIS OF PHASE ESTIMATION

We now treat the practically important case of phase estimation. We consider without loss of generality a phase $t \in [-\pi, \pi]$ to be encoded via $U(t) = e^{-itH}$ for the Hamiltonian $H = \mathrm{diag}(0, 1)$. If we perform $n$ repetitions of the experiment, we encode with

$$ U^{\otimes n}(t) = e^{-it \sum_{i=1}^{n} H_i} \quad H_i = \mathbb{I}^{\otimes i-1} \otimes H \otimes \mathbb{I}^{\otimes n-i}. \quad (650) $$
The effective accessible spectrum is then

$$ \Lambda_n = \{0, 1, \dots, n\}. \tag{651} $$

In the following discussions, we always use the rectangular window function

$$ w_{\delta}(t) = \begin{cases} 1 & \text{if } |t| \le \delta \\ 0 & \text{else.} \end{cases} \tag{652} $$

We first give a proof of Theorem 25 of the main text, which establishes the asymptotic rate of the optimal probe for phase estimation on a spin chain.

*Proof of Theorem 25.* Slepian gives an asymptotic rate with which the largest eigenvalue of W approaches 1 as

$$ \begin{align} \bar{R}_{\text{par}}^* &= \log \left( 1 + \frac{2\sqrt{1 - \cos \delta}}{\sqrt{2} - \sqrt{1 - \cos \delta}} \right) \tag{653} \\ &= \log \left( \frac{\sqrt{2} + \sqrt{1 - \cos \delta}}{\sqrt{2} - \sqrt{1 - \cos \delta}} \right) \nonumber \\ &= \log \left( \frac{1 + \sin \frac{\delta}{2}}{1 - \sin \frac{\delta}{2}} \right). \nonumber \end{align} $$

A quick Taylor expansion yields the theorem statement. We do, however, still need to establish positivity of the associated eigenvector, the DPSS of zeroth order. To do so, we rely on another result of Slepian, namely that the DPSS of zeroth order also corresponds to the largest eigenvector of the tridiagonal matrix $\tilde{W}$ with entries

$$ \tilde{W}_{\lambda, \lambda'} = \begin{cases} \frac{\lambda(n+1-\lambda)}{2} & \text{for } \lambda' = \lambda - 1 \\ \left(\frac{n}{2} - \lambda\right)^2 \cos \delta & \text{for } \lambda' = \lambda \\ \frac{(\lambda+1)(n-\lambda)}{2} & \text{for } \lambda' = \lambda + 1 \\ 0 & \text{else.} \end{cases} \tag{654} $$

As $0 \le \lambda \le n$, the entries of this matrix are positive as long as $\delta \le \pi/2$ as required by the Theorem as well as being the only non-trivial parameter range. Because of the positive entries, we can apply the Perron-Frobenius theorem to conclude that the eigenvector associated to the largest eigenvalue – the DPSS of zeroth order – must be non-negative. $\square$

Next, we give a proof of Theorem 26 of the main text that establishes the minimax rate for a Gaussian probe. In the course of the proof, we will optimize the width of the Gaussian to have an optimal trade off between $\delta$ and $n$. Note that in the below proof, $\sigma$ refers to the standard deviation of the distribution of estimates, and is thus the inverse of the standard deviation of the probe state itself.

*Proof of Theorem 26.* Before we start the proof, we recall the Fourier transform

$$ f(t) = \sum_{\omega=-\infty}^{\infty} e^{-i\omega t} \hat{f}(\omega), \tag{655} $$

$$ \hat{f}(\omega) = \frac{1}{2\pi} \int_{-\pi}^{\pi} dt f(t) e^{i\omega t}. \tag{656} $$

We prove the statement by constructing a probe state that achieves the given asymptotic rate. Our target will be the construction of a probe state whose associated PGM fidelity function is a wrapped normal distribution

$$ f_{\sigma}(t) = \frac{1}{\sqrt{2\pi}\sigma} \sum_{k=-\infty}^{\infty} \exp \left( -\frac{1}{2} \left( \frac{t+2\pi k}{\sigma} \right)^2 \right) \tag{657} $$

with standard deviation $\sigma$. In the following, we use $\tilde{f}_{\sigma}(t)$ to denote an *unwrapped* normal distribution. Our aim is to let $\sigma$ vanish asymptotically in the number of repetitions $n$. Because the available frequencies of the Hamiltonian are $\Lambda_n = \{0, 1, \dots, n\}$, the Fourier transform of the actual PGM fidelity function must be supported on the frequencies
frequencies $\{-n, \dots, n\}$, which are all possible differences of frequencies in $\Lambda_n$. Our strategy will be to assume that we choose Fourier coefficients of the PGM fidelity function such that they are equal to our target in Eq. (657) on the frequencies $\{-n, \dots, n\}$ and zero outside. With this approximation, we will make an error, which we will see below. Then, we need to judiciously choose $\sigma$ so that we keep both the approximation error in check as well as making $\sigma$ as small as possible to fit most of the Gaussian into the window.

Let us first analyze the error we make when we approximate $f_\sigma(t)$ on frequencies from $-n$ to $n$. We denote this approximation to $f_\sigma$ as $f_\sigma^{\le n}$ so that $f_\sigma(t) = f_\sigma^{\le n} + f_\sigma^{>n}$. Note that $f_\sigma^{\le n}$ is still a properly normalized function as only $\hat{f}(0)$ contributes to the integral. The expected error probability for this probe is then

$$ 
\begin{aligned}
1 - \bar{\eta}_{\sigma} &= 1 - \int_{-\pi}^{\pi} dt \, w(t) f_{\sigma}^{\le n}(t) & (658) \\
&= 1 - \int_{-\pi}^{\pi} dt \, w(t) f_{\sigma}(t) + \int_{-\pi}^{\pi} dt \, w(t) f_{\sigma}^{>n}(t) \\
&= \int_{-\pi}^{\pi} dt \, f_{\sigma}(t) - \int_{-\delta}^{\delta} dt \, f_{\sigma}(t) + \int_{-\pi}^{\pi} dt \, w(t) f_{\sigma}^{>n}(t) \\
&= 2 \int_{\delta}^{\pi} dt \, f_{\sigma}(t) + \int_{-\pi}^{\pi} dt \, w(t) f_{\sigma}^{>n}(t) \\
&= 2 \int_{\delta}^{\pi} dt \, f_{\sigma}(t) + 2\pi \sum_{\omega=-\infty}^{\infty} \hat{w}(\omega) \hat{f}_{\sigma}^{>n}(\omega) \\
&= 2 \int_{\delta}^{\pi} dt \, f_{\sigma}(t) + 4\pi \sum_{\omega=n+1}^{\infty} \hat{w}(\omega) \hat{f}_{\sigma}(\omega),
\end{aligned}
$$

where we have used the definition of $w_\delta$ and Parseval's theorem, which for real-valued functions and our Fourier transform conventions reads

$$ \int_{-\pi}^{\pi} dt \, f(t)g(t) = 2\pi \sum_{\omega=-\infty}^{\infty} \hat{f}(\omega)\hat{g}(\omega). \qquad (659) $$

We just expanded the error in terms of two tails of $f_\sigma$, one in real space and one in frequency space. The next step is to choose $\sigma$ judiciously to balance the two tails to achieve a minimal error. The first tail is easy to treat,

$$ 
\begin{aligned}
2 \int_{\delta}^{\pi} dt \, f_{\sigma}(t) &= 2 \frac{1}{\sqrt{2\pi\sigma}} \sum_{k=-\infty}^{\infty} \int_{\delta}^{\pi} \exp \left( -\frac{1}{2} \left( \frac{t+2\pi k}{\sigma} \right)^2 \right) & (660) \\
&= 2 \frac{1}{\sqrt{2\pi\sigma}} \sum_{k=-\infty}^{\infty} \int_{\delta-2\pi k}^{\pi-2\pi k} \exp \left( -\frac{1}{2} \left( \frac{t}{\sigma} \right)^2 \right) \\
&\le 2 \frac{1}{\sqrt{2\pi\sigma}} \int_{\delta}^{\infty} \exp \left( -\frac{1}{2} \left( \frac{t}{\sigma} \right)^2 \right) \\
&\le 2 \int_{\delta}^{\infty} dt \, \tilde{f}_{\sigma}(t) \\
&= \operatorname{Erfc} \left( \frac{\delta}{\sqrt{2\sigma}} \right) \\
&\le \exp \left( -\frac{1}{2} \left( \frac{\delta}{\sigma} \right)^2 \right) \sqrt{\frac{2}{\pi}} \frac{\sigma}{\delta},
\end{aligned}
$$

where we have used the definition of the cumulative error function $x \mapsto \operatorname{Erfc}(x)$ and the standard tail bound. Note that the first inequality follows from the positivity of the normal distribution.

The second term will be treated in a comparable manner, however we have to be careful when relating the discrete summation to an integral. We will need the Fourier transforms of the involved functions, given by

$$ \hat{w}_{\delta}(\omega) = \frac{\sin \delta \omega}{\pi \omega} \le \frac{1}{\pi \omega}, \qquad (661) $$

$$ \hat{f}_{\sigma}(\omega) = \frac{1}{2\pi} \exp\left(-\frac{1}{2}(\sigma\omega)^2\right). \qquad (662) $$
We will apply the bound

$$4\pi \hat{w}_{\delta}(\omega) \hat{f}_{\sigma}(\omega) \leq \frac{2}{\pi\omega} \exp\left(-\frac{1}{2}(\sigma\omega)^2\right) \leq \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma\omega)^2\right), \qquad (663)$$

where the last inequality is valid for $\omega \geq 1$. In this approximation, we can use the integral approximation formula for positive and monotonically decreasing functions

$$\begin{aligned} 4\pi \sum_{\omega=n+1}^{\infty} \hat{w}(\omega) \hat{f}_{\sigma}(\omega) &\leq \sum_{\omega=n+1}^{\infty} \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma\omega)^2\right) \\ &\leq \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) + \frac{2}{\pi} \int_{n+1}^{\infty} d\omega \exp\left(-\frac{1}{2}(\sigma\omega)^2\right) \\ &\leq \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) + \frac{1}{\pi} \operatorname{Erfc}\left(\frac{(n+1)\sigma}{\sqrt{2}}\right) \\ &\leq \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) + \frac{1}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) \sqrt{\frac{2}{\pi}} \frac{1}{\sigma(n+1)} \\ &\equiv \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) \left[1 + \frac{1}{\sqrt{2\pi\sigma}}\right]. \end{aligned} \qquad (664)$$

Putting both upper bounds together, we see that

$$1 - \bar{\eta}_{\sigma} \leq \exp\left(-\frac{1}{2}\left(\frac{\delta}{\sigma}\right)^2\right) \sqrt{\frac{2}{\pi}} \frac{\sigma}{\delta} + \frac{2}{\pi} \exp\left(-\frac{1}{2}(\sigma(n+1))^2\right) \left[1 + \frac{1}{\sqrt{2\pi\sigma}}\right]. \qquad (665)$$

In practice, the error will be dominated by the larger exponent, so we can optimize it by making both exponents equal, i.e., choosing $\sigma$ such that

$$\frac{\delta}{\sigma} = \sigma(n+1) \Leftrightarrow \sigma = \sqrt{\frac{\delta}{n+1}}, \qquad (666)$$

in which case we have that

$$1 - \bar{\eta}_{\sigma} \leq \exp\left(-\frac{\delta(n+1)}{2}\right) \left\{ \sqrt{\frac{2}{\pi}} \sqrt{\frac{1}{\delta(n+1)}} + \frac{2}{\pi} \left[ 1 + \frac{1}{\sqrt{2\pi}} \sqrt{\frac{n+1}{\delta}} \right] \right\}. \qquad (667)$$

The asymptotic rate of the above quantity is $\delta/2$ as claimed in the theorem statement.

To round off the proof of the theorem, we need to show that the desired fidelity function can actually be realized. Note that the PGM fidelity function fulfills

$$f(t) = |p(t)|^2 \qquad (668)$$

where the Fourier transform of $t \mapsto p(t)$ has coefficients

$$\hat{p}(\omega) = \frac{1}{\sqrt{2\pi}} |\psi_{\omega}|. \qquad (669)$$

The Fourier transform is such that

$$\hat{f}(\omega) = (\hat{p} * \hat{p}^*)(\omega). \qquad (670)$$

Here $\hat{p}^*(\omega) = \hat{p}(-\omega)$ is a time reversed version of $\hat{p}$ which coincides with the complex conjugate when $p(t)$ is real-valued as we will choose below.

As the weights $|\psi_{\omega}|$ need to correspond to a valid quantum state and $\omega \in \{0, 1, \dots, n\}$, we require that

$$\hat{p}(\omega) \geq 0 \quad \text{and} \quad \sum_{\omega=0}^{n} \hat{p}(\omega)^2 = \frac{1}{2\pi}. \qquad (671)$$
We also note that shifting the support of the Fourier transform of $p(\tau)$ only introduces a phase. We will therefore consider the Fourier transform to be supported on the interval $\{-n/2, \dots, n/2\}$.

As we let $\sigma \to 0$, we can work with the unwrapped Gaussian instead of the wrapped Gaussian which will significantly simplify our calculations. Formally, this is

$$ \frac{f_{\sigma}(t)}{\tilde{f}_{\sigma}(t)} \le C \qquad (672) $$

for some $C$ that can be chosen arbitrarily close to 1 for appropriately large $n$. As we want to construct $f_{\sigma}(t)$, we can exploit the fact that

$$ \tilde{f}_{\sigma}(t) = (\tilde{f}_{\sigma\sqrt{2}}(t))^2 \qquad (673) $$

and choose

$$ p(t) = \tilde{f}_{\sigma\sqrt{2}}^{\le n/2}(t). \qquad (674) $$

By approximating this expression, we make an error that we need to correct for through re-normalization, the factor of which is given by

$$ \begin{aligned} \frac{\mathcal{N}}{2\pi} &= \frac{1}{4\pi^2} \sum_{\omega=-n/2}^{n/2} \exp(-\frac{1}{2}(\sigma\omega)^2) && (675) \\ &= \frac{1}{2\pi} - \frac{1}{2\pi^2} \sum_{\omega=n/2}^{\infty} \exp(-\frac{1}{2}(\sigma\omega)^2). \end{aligned} $$

We see that the right term is again the tail of the Gaussian in frequency space which becomes arbitrarily small for $n \to \infty$. We therefore know that there exists an $n$ such that $1/2 \le \mathcal{N} \le 1$. This means the actual probe we will use is given by

$$ \hat{p}(\omega) = \mathcal{N}^{-1} \hat{f}_{\sigma\sqrt{2}}^{\le n}(\omega), \qquad (676) $$

$$ \psi_{\omega} = \sqrt{2\pi}\mathcal{N}^{-1}\hat{f}_{\sigma\sqrt{2}}^{\le n}(\omega). \qquad (677) $$

The correction factor, as well as the error of approximating the wrapped Gaussian with the unwrapped Gaussian is bounded and will thus not contribute to the asymptotic rate. This concludes the proof. $\square$

Next, we will discuss the constant factor of the Heisenberg scaling of the Gaussian probe and give a proof of Theorem 27 of the main text.

*Argument for Observation 27.* We use the same setting as in the above proof of Theorem 26. We start from Eq. (667) and set

$$ \delta = \frac{\alpha}{n+1} \qquad (678) $$

to obtain

$$ 1 - \bar{\eta} \le \frac{2}{\pi} e^{-\frac{\alpha}{2}} \left( 1 + \sqrt{\frac{1}{\alpha}} \left[ \sqrt{\frac{\pi}{2}} + \sqrt{\frac{1}{2\pi}}(n+1) \right] \right) \qquad (679) $$

$$ = \frac{2}{\pi} \exp \left( -\frac{\alpha}{2} + O(\log \alpha) + O(\log n) \right). \qquad (680) $$

Rearranging then yields

$$ 2 \log \frac{2}{\pi(1 - \bar{\eta})} \ge \alpha + O(\log \alpha) + O(\log n) \qquad (681) $$

which implies the Observation. $\square$
A. Chernoff bound and entanglement advantage

In the previous section, we have shown that the optimal rate for the phase sensing problem is lower-bounded by $\delta/2$ in the case of an entangled probe. In this section, we also provide an upper bound on the best rate that can be achieved with tensor power inputs. We can exploit the upper bound on the asymptotic rate for the tensor power case derived in Theorem 27 to establish the following theorem.

**Theorem 41.** The optimal minimax rate for tensor power inputs for the phase sensing problem is upper-bounded by

$$ \bar{R}_{\text{iid}}^*(w_\delta, U(t)) \leq -\log \cos^2(\delta) = \delta^2 + O(\delta^4). \quad (682) $$

We can, therefore, guarantee a quadratic advantage over the i.i.d. case through the use of entanglement.

*Proof.* We know from Theorem 27 that we need to bound the Chernoff coefficient, which for pure quantum states relates to the fidelity according to

$$ \begin{aligned} C(\psi(t), \psi(t+2\delta)) &= -\log \min_{0 \le s \le 1} \mathrm{Tr}[\psi(t)^s \psi(t+2\delta)^{1-s}] \\ &= -\log \mathrm{Tr}[\psi(t)\psi(t+2\delta)] \\ &= -\log |\langle\psi(t)|\psi(t+2\delta)\rangle|^2. \end{aligned} \quad (683) $$

Note that due to the covariance property it is sufficient to study the fidelity for $t = 0$. As for our setting, we have used a single qubit as our building block we can expand

$$ \begin{aligned} |\langle\psi(0)|\psi(2\delta)\rangle|^2 &= ||\psi_0|^2 + e^{-i2\delta} |\psi_1|^2|^2 \\ &= |\psi_0|^4 + |\psi_1|^4 + 2|\psi_0|^2|\psi_1|^2 \cos \delta \\ &= (|\psi_0|^2 + |\psi_1|^2)^2 - 2(1 - \cos 2\delta)|\psi_0|^2|\psi_1|^2 \\ &= 1 - 2(1 - \cos 2\delta)|\psi_0|^2|\psi_1|^2. \end{aligned} \quad (684) $$

For the best protocol, this quantity has to be as small as possible, hence the optimal probe has $|\psi_0|^2 = |\psi_1|^2 = 1/2$. Therefore, for the optimal probe state

$$ |\langle\psi(0)|\psi(2\delta)\rangle|^2 = 1 - \frac{1}{2}(1 - \cos 2\delta) = \cos^2(\delta). \quad (685) $$

We conclude by the Taylor expansion of $-\log \cos^2(\delta)$.

□

B. Additional numerics

In this section, we present additional numerical results for the minimax analysis of phase estimation performed in Section XI of the main text.
<figure><img src="image_19.png" /></figure>

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

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

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

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

<figure><img src="image_24.png" /><figcaption>FIG. 12. Optimal error probability of quantum metrology that can be guaranteed for any prior distribution for different probes in the phase estimation scenario for different values of the target tolerance $\bar{\delta}$. We compare a generalized GHZ state (Eq. (95), red), an tensor power of plus states (green), the Holland-Burnett state (Eq. (96), orange), the Gaussian state (Eq. (99), yellow) and the optimal state (Eq. (93), blue).</figcaption></figure>
<figure><img src="image_25.png" /></figure>

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

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

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

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

<figure><img src="image_30.png" /><figcaption>FIG. 13. Optimal tolerance of quantum metrology that can be guaranteed for any prior distribution for different probes in the phase estimation scenario for different values of the target success probability $\bar{\eta}$. We compare a generalized GHZ state (Eq. (95), red), an tensor power of plus states (green), the Holland-Burnett state (Eq. (96), orange), the Gaussian state (Eq. (99), yellow) and the optimal state (Eq. (93), blue).</figcaption></figure>