用多项式时间学习浅层量子电路生成的未知态，可高效判断态的复杂度。
Learning quantum states prepared by shallow circuits in polynomial time
- 从局部密度矩阵重构全局量子态，实现高效学习。
- 对常数深度电路，算法运行时间多项式；对polylog深度，为准多项式。
- 适用于检测量子态是否具有低或高电路复杂度，适合量子复杂度研究者。
我们提出一个多项式时间算法，给定由未知常数深度电路 $U$ 作用于 $|0^n angle$ 生成的未知量子态 $| heta angle = U|0^n angle$，该算法能学习出一个常数深度量子电路来重建此态。当 $U$ 的深度为 $ ext{polylog}(n)$ 时，算法运行时间为准多项式。核心创新是一种通用且高效的方案，可从局部约化密度矩阵重构全局态 $| heta angle$。作为应用，我们给出了一个高效算法，用于判断晶格上的未知量子态是否具有低或高量子电路复杂度。
原文摘要 · Abstract (English)
We give a polynomial time algorithm that, given copies of an unknown quantum state $\vertψ\rangle=U\vert 0^n\rangle$ that is prepared by an unknown constant depth circuit $U$ on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares $\vertψ\rangle$. The algorithm extends to the case when the depth of $U$ is $\mathrm{polylog}(n)$, with a quasi-polynomial run-time. The key new idea is a simple and general procedure that efficiently reconstructs the global state $\vertψ\rangle$ from its local reduced density matrices. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。