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

Question

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

Predicting Many Properties of a Quantum System from Very Few Measurements Eq.(S13)

Answer 1

Without really checking your arguments, there is a fundamental reason why the scaling could be fine, but it is still not strange at all.

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.