Quantum Computational Complexity of Classical Statistical Mechanics

量子信息处理在经典统计力学背景下的计算优势在很大程度上仍然是未知的。这一建议涉及在硬经典统计力学问题的背景下理解量子计算的力量。这将通过对伊辛自旋玻璃和波茨模型(统计力学中的关键模型)的哪些实例进行分类来实现这一点。预计这将直接导致对组合学、图论、纽结理论和拓扑学中相关问题的量子计算复杂性的理解。因此，这项提议旨在阐明经典和量子计算复杂性理论之间的边界，超越现有的Shors和Grover算法的变体。我们将寻求两种不同的方法：(I)使用编码理论和现有的量子算法来处理称为高斯和的数论对象，以及(Ii)利用称为二次带符号重量枚举数的代数对象来表示量子电路。在这两种情况下，都可以直接连接到Potts模型或Ising自旋玻璃模型的配分函数，这两种模型都会产生计算困难的问题。要追求的基本方法是根据它们的量子计算复杂性对这两个模型的实例进行分类。这将揭示量子计算的力量，并可能导致新的量子算法的发现，这些算法的性能优于经典的同类算法。广泛的影响：这项提议将促进量子计算方面的培训和学习。量子计算可能会对从头算材料和药物设计产生巨大影响。这项提议旨在阐明量子计算在模拟经典物理方面的潜力，它可以通过为硬经典统计力学问题提供快速解决方案来造福社会，例如在聚合物物理中出现的问题，以及需要组合优化的领域。国际和平协会是南加州大学新成立的量子信息科学与技术中心(CQIST)的主任，该中心将协调针对洛杉矶地区社会经济困难学生和天才学生的外联活动。它将在洛杉矶市中心的高中为科学教师建立一个大学总部。国家质检总局将通过出版出版物、定期召开系列会议和与新闻界接触等方式，传播本提案的研究成果。

The computational advantages of Quantum Information Processing in the context ofclassical statistical mechanics are still largely unknown. This proposal is concerned with understanding the power of quantum computation in the context of hard classical statistical mechanics problems. This will be done by developing a classification of which instances of the Ising Spin Glass and Potts models (key models in statistical mechanics) are amenable to fast quantum simulation. It is expected that this will lead directly to an understanding of the quantum computational complexity of related problems in combinatorics, graph theory, knot theory, and topology. Thus this proposal aims to shed light on the border between classical and quantum computational complexity theory, beyond the existing variants on Shors and Grovers algorithms. Two distinct approaches will be pursued: (i) The use of coding theory and an exisiting quantum algorithm for number-theoretic objects known as Gauss sums, and (ii) A representation of quantum circuits in terms of an algebraic object known as quadratically signed weight enumerators. In both cases a direct connection can be made to the partition function of the Potts model or the Ising Spin Glass model, whichare known to generate computationally hard problems. The basic approach to bepursued is to classify instances of these two models in terms of their quantumcomputational complexity. This will shed light on the power of quantum computation, and may lead to the discovery of new quantum algorithms which outperform their classical counterparts. Broad Impact: This proposal will promote training, and learning in quantum computation. Quantum computation has potential for dramatic impact on ab initio materials and drug design. This proposal aims to elucidate the potential of quantum computation in simulating classical physics, which can benefit society by providing fast solutions to hard classical statistical mechanics problems arising, e.g., in polymer physics, and fields requiring combinatorial optimization. The PI is the Directorof the newly formed Center for Quantum Information Science & Technology (CQIST) at USC, which will coordinate outreach activities aimed at socioeconomically challenged as well as gifted students in the Los Angeles area. It will build a University home base for science teachers at high schools in central Los Angeles. CQIST will disseminate the results of the research of this proposal, by means of publications, regular series of meetings, and contacts with the press.