Quantum Computational Complexity of Classical Statistical Mechanics

量子信息处理在经典统计力学背景下的计算优势在很大程度上仍然未知。这个建议是关于理解量子计算在硬经典统计力学问题中的作用。这将通过开发一个分类来完成，即伊辛自旋玻璃和波茨模型（统计力学中的关键模型）的实例适合快速量子模拟。预计这将直接导致对组合学、图论、纽结理论和拓扑学中相关问题的量子计算复杂性的理解。因此，这个建议旨在阐明经典和量子计算复杂性理论之间的边界，超越现有的Shors和Grovers算法的变体。两种不同的方法将被追求：（一）使用编码理论和一个量子算法的数论对象称为高斯和，和（ii）表示量子电路的代数对象称为二次签署的重量枚举。在这两种情况下，可以直接连接到Potts模型或Ising自旋玻璃模型的配分函数，这是已知的产生计算困难的问题。所追求的基本方法是根据它们的量子计算复杂性对这两个模型的实例进行分类。这将揭示量子计算的力量，并可能导致发现新的量子算法，这些算法优于经典算法。广泛的影响：该提案将促进量子计算的培训和学习。量子计算对从头算材料和药物设计具有巨大的影响潜力。该提案旨在阐明量子计算在模拟经典物理学方面的潜力，这可以通过为硬经典统计力学问题提供快速解决方案来造福社会，例如，在聚合物物理学和需要组合优化的领域。PI是南加州大学新成立的量子信息科学技术中心（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.