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.