论文标题
学习量子阶段的最佳算法
Optimal algorithms for learning quantum phase states
论文作者
论文摘要
我们分析了学习$ n $ qubit量子阶段状态的复杂性。学位 - $ d $相位状态定义为所有$ 2^n $ basis vectors $ x $的叠加，其振幅与$（-1）^{f（x）} $成比例，其中$ f $是age-d $ d $ d $ boolean polorean polynomial to $ n $ variables。我们表明，如果我们允许纠缠的测量结果，则可以学习未知度的样本复杂性-D $相位状态为$θ（n^d）$，如果允许可分离的测量和$θ（n^{d-1}）$。我们的学习算法基于可分离的测量值具有运行时$ \ textsf {poly}（n）$（对于常数$ d $），并且非常适合近期示范，因为它仅需要Pauli $ x $ x $和$ z $ bases中的单品测量值。我们在样品复杂性上显示了具有复杂值振幅的通用相位状态的样品复杂性的相似界限。我们进一步考虑学习阶段指出$ f $具有稀疏 - $ s $，量-d $ in $ \ mathbb {f} _2 $表示（带有样本复杂性$ o（2^d sn）$），$ f $具有傅立叶 - $ $ t $（带有样品复杂性$ o（2^{2t} $），并学习$ o（2^{2t）$ - 噪声（带有样本复杂性$ O（n^{1+ \ varepsilon}）$）。这些学习算法为我们提供了学习Clifford层次结构和IQP〜电路的对角线单位的程序。
We analyze the complexity of learning $n$-qubit quantum phase states. A degree-$d$ phase state is defined as a superposition of all $2^n$ basis vectors $x$ with amplitudes proportional to $(-1)^{f(x)}$, where $f$ is a degree-$d$ Boolean polynomial over $n$ variables. We show that the sample complexity of learning an unknown degree-$d$ phase state is $Θ(n^d)$ if we allow separable measurements and $Θ(n^{d-1})$ if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime $\textsf{poly}(n)$ (for constant $d$) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli $X$ and $Z$ bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when $f$ has sparsity-$s$, degree-$d$ in its $\mathbb{F}_2$ representation (with sample complexity $O(2^d sn)$), $f$ has Fourier-degree-$t$ (with sample complexity $O(2^{2t})$), and learning quadratic phase states with $\varepsilon$-global depolarizing noise (with sample complexity $O(n^{1+\varepsilon})$). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.
