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.