论文标题
几何本地，浅量子电路的输出概率的准多项式时间近似
Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits
论文作者
论文摘要
我们提出了一种经典的算法，对于任何3D几何本地，多凝集的量子电路$ c $作用于$ n $ Qubits，以及任何位字符串$ x \ in \ in \ {0,1 \}^n $都可以计算数量$ | <x | c | c | c | c | c | c | c | c | c | c | c | c | 0^2 $ |准多项式时间。众所周知，将同样数量计算为$ 2^{ - n^2} $添加错误[mov20，kmm21]之内是$ \＃p $ -HARD。此问题的先前最著名的算法使用$ o（2^{n^{1/3}} \ text {poly}（1/ε））$时间将概率计算为添加性错误$ε$ [BGM20]。值得注意的是，[BGM20]论文包括一种限制在2D电路的估计任务的优雅多项式时间算法，该估计任务限于2D电路，该算法的新颖使用了1D矩阵产品状态状态（MPS），仔细量身定制了有关电路的2D几何形状。令人惊讶的是，尚不清楚可以在多项式时间内扩展这种MP的使用以解决3D电路的情况。这就提出了一个自然的问题，即3D问题的计算复杂性是否可能大大高于2D问题。在这项工作中，我们通过为3D案例展示一种准多项式时间算法来解决这个问题。为了超越以前已知的技术遇到的技术障碍，我们被迫采用一种新颖的方法。 我们的算法具有分裂和串联的结构，演示了如何通过相同问题类型的几个实例化近似所需数量，每种量子涉及量子数的一半，涉及量子数的一半。然后递归地应用此分裂步骤，将原始数量表示为越来越小的3d-local量子电路的加权组合。一个核心技术挑战是控制不同电路之间可能存在的纠缠而产生的相关性。
We present a classical algorithm that, for any 3D geometrically-local, polylogarithmic-depth quantum circuit $C$ acting on $n$ qubits, and any bit string $x\in\{0,1\}^n$, can compute the quantity $|< x |C|0^{\otimes n}>|^2$ to within any inverse-polynomial additive error in quasi-polynomial time. It is known that it is $\#P$-hard to compute this same quantity to within $2^{-n^2}$ additive error [Mov20, KMM21]. The previous best known algorithm for this problem used $O(2^{n^{1/3}}\text{poly}(1/ε))$ time to compute probabilities to within additive error $ε$ [BGM20]. Notably, the [BGM20] paper included an elegant polynomial time algorithm for this estimation task restricted to 2D circuits, which makes a novel use of 1D Matrix Product States (MPS) carefully tailored to the 2D geometry of the circuit in question. Surprisingly, it is not clear that it is possible to extend this use of MPS to address the case of 3D circuits in polynomial time. This raises a natural question as to whether the computational complexity of the 3D problem might be drastically higher than that of the 2D problem. In this work we address this question by exhibiting a quasi-polynomial time algorithm for the 3D case. In order to surpass the technical barriers encountered by previously known techniques we are forced to pursue a novel approach. Our algorithm has a Divide-and-Conquer structure, demonstrating how to approximate the desired quantity via several instantiations of the same problem type, each involving 3D-local circuits on about half the number of qubits as the original. This division step is then applied recursively, expressing the original quantity as a weighted combination of smaller and smaller 3D-local quantum circuits. A central technical challenge is to control correlations arising from entanglement that may exist between the different circuit ``pieces" produced this way.
