Quantum Computational Complexity of Classical Statistical Mechanics

经典统计力学的量子计算复杂性

• 批准号: 0802678
• 负责人: Daniel Lidar
• 金额: --
• 依托单位: University of Southern California
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-08-01 至 2011-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0802678&HistoricalAwards=false
• 关键词: Quantum; Computational; Complexity; Classical; Statistical

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.

量子信息处理的计算优势仍然在很大程度上未知。该提案与在硬经典统计力学问题的背景下了解量子计算的力量有关。这将通过开发一个分类来完成，该分类可以通过哪些旋转玻璃和POTTS模型（统计力学中的关键模型）进行快速量子模拟。预计这将直接导致对组合学，图理论，结理论和拓扑中相关问题的量子计算复杂性的理解。因此，该提案旨在阐明经典计算复杂性理论之间的边界，除了在海岸和Grovers算法上的现有变体之外。将采用两种不同的方法：（i）使用编码理论和一种被称为高斯总和的数字理论对象的量子算法的使用，以及（ii）用代数对象表示量子电路的表示，称为四倍体签名的权重枚举者。在这两种情况下，都可以与Potts模型或Ising Spin Glass模型的分区功能进行直接连接，该模型已知会产生计算上的硬性问题。提出的基本方法是根据量子计算的复杂性对这两个模型的实例进行分类。这将阐明量子计算的功能，并可能导致发现新的量子算法，这些算法的表现优于其经典对应物。广泛的影响：该建议将促进培训和量子计算中的学习。量子计算具有对从头算材料和药物设计产生巨大影响的潜力。该提案旨在阐明量子计算在模拟古典物理学中的潜力，该物理学可以通过为硬性经典统计力学问题提供快速解决方案而受益，例如在聚合物物理学和需要组合优化的领域。 PI是USC新成立的量子信息科学技术中心（CQIST）的主任，该中心将协调针对社会经济挑战的外展活动以及洛杉矶地区的有天赋的学生。它将在洛杉矶中部高中的科学老师建立大学主场。 CQIST将通过出版物，常规会议以及与新闻界的联系来传播该提案的研究结果。