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)/epsilon(2)) samples of a d-dimensional state rho. That is, given observables 0 < A(1), A(2), ..., A(m) <= 1 such that tr(rho A(i)) >= 1/2 for at least one i, the algorithm finds j with tr(rho A(j)) >= 1/2 - epsilon. As a consequence, we obtain a Shadow Tomography algorithm requiring only <(O)over tilde>( (log(2) m) (log d) /epsilon(4)) samples, which simultaneously achieves the best known dependence on each parameter m, d, epsilon. This yields the same sample complexity for quantum Hypothesis Selection among m states; we also give an alternative Hypothesis Selection method using (O) over tilde((log(3) m)/epsilon(2)) samples.