Improved quantum data analysis

We provide more sample-efficient versions of some basic routines in quantum data analysis, along with simpler proofs. Particularly, we give a quantum “Threshold Search” algorithm that requires only $O(({\log }^{2}m)\mathrm{/}{ϵ}^2)$ samples of a $d$-dimensional state $\rho$. That is, given observables $0 \le A_1, A_2, …, A_m \le 1$suchthat$$\mathrm{t}\mathrm{r}$(\rho A_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $$\mathrm{t}\mathrm{r}$(\rho A_j) \ge 1/2-\epsilon$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{O}(({\log }^{2}m)(\log d)\mathrm{/}{ϵ}^4)$ samples, which simultaneously achieves the best known dependence on each parameter $m$, $d$, $ϵ$. This yields the same sample complexity for quantum Hypothesis Selection among $m$ states; we also give an alternative Hypothesis Selection method using $\tilde{O}(({\log }^{3}m)\mathrm{/}{ϵ}^2)$ samples.