Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem
Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem
复制标题
PAC 模型中学习量子通道的高效算法示例和近似状态判别问题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Han
中科院分区：
文献类型：
--
作者：
Kai;Han
我们通过将经典函数的概念推广到量子过程，定义了emph问题，将PAC（可能近似正确的）学习模型推广到量子世界{PAC学习量子过程}，并研究其样本复杂度。在PAC学习量子过程的问题中，我们想要学习一个 $epsilon$-未知量子过程的近似 $c^*$ 从一个已知的有限概念类 $C$ 有概率地 $1-delta$ 使用样本 ${(x_1,c^*(x_1)),(x_2,c^*(x_2)),dots}$，其中 ${x_1,x_2, dots}$ 计算基态是从未知分布中采样的吗 $D$ 和 ${c^*(x_1),c^*(x_2),dots}$ （可能混合）量子态输出由 $c^*$。恒定输入下pac -学习量子过程的特殊情况可归结为一个自然问题，我们将其命名为近似状态判别，其中我们给定未知量子态的副本 $c^*$ 从一个已知的有限集合 $C$，我们想用概率来学习 $1-delta$ 一个 $epsilon$-近似 $c^*$ 只有很少的副本 $c^*$ 尽可能。我们证明了PAC学习量子过程的问题可以用 $$Oleft(frac{log|C| + log(1/ delta)} { epsilon^2}
ight)$$ 当输出是纯状态和 $$Oleft(frac{log^3 |C|(log |C|+log(1/ delta))} { epsilon^2}
ight)$$ 采样，如果输出可以混合。我们的研究结果的一些含义是，我们可以在多项式样本中pac - learning一个多项式大小的量子电路，并且即使在概念类大小的情况下，也可以在多项式样本中解决近似状态判别问题 $|C|$ 在量子比特的数量上是指数级的，比全态断层扫描有指数级的改进。
We generalize the PAC (probably approximately correct) learning model to the quantum world by generalizing the concepts from classical functions to quantum processes, defining the problem of emph{PAC learning quantum process}, and study its sample complexity. In the problem of PAC learning quantum process, we want to learn an $epsilon$-approximate of an unknown quantum process $c^*$ from a known finite concept class $C$ with probability $1-delta$ using samples ${(x_1,c^*(x_1)),(x_2,c^*(x_2)),dots}$, where ${x_1,x_2, dots}$ are computational basis states sampled from an unknown distribution $D$ and ${c^*(x_1),c^*(x_2),dots}$ are the (possibly mixed) quantum states outputted by $c^*$. The special case of PAC-learning quantum process under constant input reduces to a natural problem which we named as approximate state discrimination, where we are given copies of an unknown quantum state $c^*$ from an known finite set $C$, and we want to learn with probability $1-delta$ an $epsilon$-approximate of $c^*$ with as few copies of $c^*$ as possible. We show that the problem of PAC learning quantum process can be solved with $$Oleft(frac{log|C| + log(1/ delta)} { epsilon^2}
ight)$$ samples when the outputs are pure states and $$Oleft(frac{log^3 |C|(log |C|+log(1/ delta))} { epsilon^2}
ight)$$ samples if the outputs can be mixed. Some implications of our results are that we can PAC-learn a polynomial sized quantum circuit in polynomial samples and approximate state discrimination can be solved in polynomial samples even when concept class size $|C|$ is exponential in the number of qubits, an exponentially improvement over a full state tomography.