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 )/є 2 ) samples of a d -dimensional state ρ. That is, given observables 0 ≤ A 1 , A 2 , …, A m ≤ 1 such that (ρ A i ) ≥ 1/2 for at least one i , the algorithm finds j with (ρ A j ) ≥ 1/2−є. As a consequence, we obtain a Shadow Tomography algorithm requiring only O ((log 2 m )(log d )/є 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 O ((log 3 m )/є 2 ) samples.

Authors

• Costin Badescu
• Ryan O'Donnell

Keywords

• quantum sample complexity
• shadow tomography