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 𝑂((log 2 𝑚)/𝜖 2 ) samples of a 𝑑-dimensional state 𝜌. That is, given observables 0 ≤ 𝐴 1 , 𝐴 2 , . . . , 𝐴 𝑚 ≤ 1 such that tr(𝜌𝐴 𝑖 ) ≥ 1/2 for at least one 𝑖, the algorithm finds 𝑗 with tr(𝜌𝐴 𝑗 ) ≥ 1/2 -𝜖. As a consequence, we obtain a Shadow Tomography algorithm requiring only 𝑂((log 2 𝑚)(log 𝑑)/𝜖 4 ) samples, which simultaneously achieves the best known dependence on each parameter 𝑚, 𝑑, 𝜖. This yields the same sample complexity for quantum Hypothesis Selection among 𝑚 states; we also give an alternative Hypothesis Selection method using 𝑂((log 3 𝑚)/𝜖 2 ) samples.