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.