AF: Small: Classical Simulation of Quantum Algorithms and Approximation of Permanents

这项研究将开发新的计算方法来模拟量子力学系统，同时确定阻碍有效算法的基本障碍。 这些方法将被应用于模拟量子计算机和其他设备，这反过来将为具有实际重要性的硬计算问题提供新的算法范例。 量子计算机被认为可以解决任何传统计算机都无法解决的问题。 这些包括密码学问题，如大数分解，以及模拟具有多个自由度的量子系统。 这项研究将利用最近发现的量子力学和矩阵永久之间的联系。 与行列式一样，方阵的积和式也被定义为排列之和，只是没有符号。 但这是根本不同的。虽然行列式可以使用基本线性代数有效地计算，但计算永久性是最困难的计算问题之一，甚至被认为在量子计算机上是难以处理的。 然而，众所周知，任何将不变量近似到一定精度的方法，都会立即给出一种有效模拟任何量子算法的方法。 因此，该项目将通过研究永久量近似的算法复杂性，同时确定这种近似的复杂性理论障碍，开发模拟量子力学的新的经典随机方法。这项研究将揭示有关矩阵永久式及其与计算机科学和计算物理的关系的基本真理。它将提供新的下限和上限的永久和相关的数量，同时建立新的硬度计算和近似永久的结果。不变量的新界将为量子光学中的测量概率提供更深入的理论和算法理解。 该研究的数学部分将对量子信息论、组合数学、半定规划、多线性代数、算子理论等领域产生影响。反过来，这项研究将有助于我们从理论上理解经典和量子计算机的能力和局限性。

This research will develop new computational methods for simulating quantum mechanical systems, while identifying fundamental obstacles preventing efficient algorithms. These methods will be applied to simulating quantum computers and other devices, which in turn will provide new algorithmic paradigms for hard computational problems of practical importance. Quantum computers are known to solve problems that are believed to be intractable by any conventional computer. These include cryptographic problems such as factoring large numbers, as well as simulating quantum systems with many degrees of freedom. This research will utilize recently discovered connections between quantum mechanics and the matrix permanent. Like the determinant, the permanent of a square matrix is also defined as a sum over permutations, only without signs. But it is fundamentally different. While the determinant can be efficiently computed using basic linear algebra, computing the permanent is among the hardest computational problems, and is even believed to be intractable on a quantum computer. Nevertheless, it is known that any procedure for approximating permanents to a certain accuracy will immediately give a method for efficiently simulating any quantum algorithm. This project will thus develop new classical randomized methods for simulating quantum mechanics through the study of the algorithmic complexity of the approximations of permanents, while determining complexity-theoretic obstacles to such approximations. This research will uncover fundamental truths about matrix permanents and their relation to computer science and computational physics. It will provide new lower and upper bounds on the permanent and related quantities, while establishing new hardness results for computing and approximating permanents. The new bounds on permanents will provide deeper theoretical and algorithmic understandings of measurement probabilities in quantum optics. The mathematical part of this research will have impact on many areas such as quantum information theory, combinatorics, semidefinite programming, multilinear algebra, operator theory. In turn, this research will contribute to our theoretical understanding of the capabilities and limitations of computers, both classical and quantum.