Improved quantum data analysis

Abstract

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\le A_1,A_2,...,A_m\le 1$ such that $\mathrm{tr}(\rho A_i)\ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(\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)/{\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 $\tilde{O}(({\log }^{3}m)/{\epsilon }^2)$ samples.

References in corpus (6)

• The Spectra of Density Operators and the Kronecker Coefficients of the Symmetric Group
• The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes
• Entanglement is Necessary for Optimal Quantum Property Testing
• Sample efficient tomography via Pauli Measurements
• Robust quantum minimum finding with an application to hypothesis selection
• Sample optimal Quantum identity testing via Pauli Measurements

Cited by in corpus (3)

• Private learning implies quantum stability
• A Hierarchy for Replica Quantum Advantage
• Learning the closest product state