论文标题
改进的量子数据分析
Improved quantum data analysis
论文作者
论文摘要
我们在量子数据分析中提供了一些基本例程的更多样本效率版本，以及更简单的证明。特别是，我们提供了一种量子“阈值搜索”算法，该算法仅需要$ o（（（\ log^2 m）/ε^2）$ d $二维状态$ρ$的$样本。也就是说，可以观察到$ 0 \ le a_1，a_2，...，a_m \ le 1 $ 1 $，以至于$ \ mathrm {tr}（ρa_i）（ρa_i）\ ge 1/2 $至少一个$ i $，algorithm找到$ j $ with $ j $，带有$ \ nathrm {tr}（tr}（tr}（ρa_j_ pe ge 1/2-）结果，我们获得了一个阴影层析成像算法，仅需要$ \ tilde {o}（（（\ log^2 m）（\ log d d）/ε^4）$样本，同时可以实现每个参数$ m $，$ d $，$ d $，$ d $，$ε$。这产生了相同的样本复杂性，用于$ m $状态之间的量子假设选择；我们还使用$ \ tilde {o}（（（\ log^3 m）/ε^2）$样本提供了一种替代假设选择方法。
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 \le A_1, A_2, ..., A_m \le 1$ such that $\mathrm{tr}(ρA_i) \ge 1/2$ for at least one $i$, the algorithm finds $j$ with $\mathrm{tr}(ρA_j) \ge 1/2-ε$. As a consequence, we obtain a Shadow Tomography algorithm requiring only $\tilde{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 $\tilde{O}((\log^3 m)/ε^2)$ samples.
