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.
