Using Classical Shadow to predict quantum state's fidelity has nothing to do with the dimension of the density matrix?

Using classical shadow(or refer to this post for basic things about classical shadow), we can predict linear functions like $$Tr(O\hat{\rho})$$ with number of copies(referred paper): $$2\log(2M/\delta)*\frac{34}{\epsilon^2}||O-tr(O)/2^n||^2_{shadow}\tag{1}$$

If I want to measure the fidelity of quantum states, that is, if $$\rho$$ is pure state, and $$\hat{\rho}$$ is the actual state, and I want to predict the fidelity between $$\rho$$ and $$\hat{\rho}$$. The formula for this fidelity is $$Tr(\rho\hat{\rho})$$ which can easily be deduced from the definition of fidelity $$F(\rho,\sigma)=Tr\sqrt{\rho^{1/2}\sigma\rho^{1/2}}$$. And we can replace the $$O$$ in linear function $$Tr(O\hat{\rho})$$ with $$\rho$$, so we change the fidelity function into $$Tr(\rho\hat{\rho})$$, i.e., the quantum state fidelity.

And there is a result in this paper(referred paper), with eq. (S16) said that with some cased, we can realize $$||O-tr(O)/2^n||^2_{shadow}\le3Tr(O)^2$$, which should be $$3Tr(\rho)^2=3$$ in my case of predicting the fidelity. So now eq.(1) becomes: $$2\log(2M/\delta)*\frac{34}{\epsilon^2}*3$$ which has nothing to do with the dimension of quantum states? It seems really strange to me, so do I make some mistakes?

References

The point is that you estimate with additive precision, but your fidelity could be exponentially small. E.g. if the fidelity is $$10^{-8}$$, you need a much smaller error to resolve that compare to a fidelity of, say, 1/2. Thus, estimating with relative precision would be much better, but this would then mean that your sample complexity should scale with the dimension (in the worst case).
Moreover, I think the question is not really about shadow tomography. If $$\rho$$ is a pure state, then the fidelity is nothing but the Born probability in a projective measurement, say in the computational basis. So this is just estimating probabilities in disguise. Then, something like Hoeffding's inequality would give you an identical scaling in error and confidence level, namely $$N \geq \frac12\log(2/\delta) \varepsilon^{-2},$$ Note that this does not depend on the dimension! But still, this is only an additive estimate.
• +1. Hoeffdings inequality does recover roughly the same scaling if one assumes that the random variable $X=\text{tr}(O \hat{\rho})$ is bounded, but that the authors instead used a "median-of-means" estimator which just exchanges information about the bounds of $X$ for knowledge of $\text{Var}[X] \leq \lVert O \rVert_{shadow}$. But there's no significant difference in intuition about the concentration behavior. Oct 11 '21 at 16:42
• @Sherlock Additive error means that your estimate, say $\hat X$, is known to be at most $\varepsilon$ away from the true value $X$, i.e. $| \hat X - X | \leq \varepsilon$. In contrast, estimating with relative/multiplicative error means that $| \hat X - X | \leq \varepsilon |X|$. The second notion is clearly much stronger. Oct 20 '21 at 7:05
• Markus Heinrich I see. @forky40 If the author of the post's statement is correct, I can choose $O=\begin{pmatrix} 1&0\\0&0\end{pmatrix}$ to get $Tr(\rho O)=\rho_{11}$, and $O=\begin{pmatrix}0&0\\0&1\end{pmatrix}$ to get $\rho_{22}$, and choose $O=\sigma_x$ and $O=\sigma_y$ to get $\rho_{12}$ and $\rho_{21}$, which will only need Order of $\log d$ samples, with $d$ stands for the dimension of the density matrix. But as far as I know, doesn't the best full tomography needs $rand(\rho)d$? Oct 22 '21 at 6:24