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.

Source: arXiv.org:2011.10908

Volume: Volume 3

Published on: March 18, 2024

Accepted on: January 28, 2024

Submitted on: February 7, 2023

Keywords: Quantum Physics,Computer Science - Computational Complexity

Funding:

- Source : OpenAIRE Graph
*FET: Small: Foundations of Quantum State Learning and Testing*; Funder: National Science Foundation; Code: 1909310*Enabling Research for the Next Generation GW Detectors*; Funder: National Science Foundation; Code: 2110001

This page has been seen 195 times.

This article's PDF has been downloaded 120 times.