Computational Complexity in Statistical and Quantum Physics

莫尔：这笔拨款的目的是探索物理学和计算机科学之间的接口。最近，这两个领域之间的互动越来越多，一个领域的方法和隐喻正在成功地应用到另一个领域。其中包括量子计算(量子力学可以帮助我们以新的方式进行计算的想法)，以及计算机科学中搜索问题的“相变”(从可解到不可解的急剧跳跃，就像从水到冰的物理跳跃一样)。具体地说，摩尔教授将利用这笔赠款研究并行量子算法，其中许多操作一次执行，以及优化问题中的相变，在优化问题中，我们试图以最小的成本找到满足许多约束的问题的解决方案。他还将继续研究需要多少计算努力来解决统计物理中的问题，或预测模拟的结果。

0071139Moore The purpose of this grant is to explore the interface betweenphysics and computer science. Recently there has been an increased amount of interaction between these two fields, in which methods and metaphors from one field are being successfully applied to the other. These include quantum computation (the idea that quantum mechanics can help us compute in new ways), and "phase transitions" in search problems from computer science (a sharp jump from solvability to unsolvability, not unlike the physical jump from water to ice). Specifically, Prof. Moore will use this grant to study parallelquantum algorithms, where many operations are carried out at once, and phase transitions in optimization problems, where we are trying to find solutions to a problem that satisfy many constraints at a minimum cost. He will also continue to study how much computational effort is needed to solve problems in statistical physics, or to predict the outcome of a simulation.