Quantum Computational Complexity of Classical Statistical Mechanics

University Of Southern California, Los Angeles CA

Investigators

Abstract

The computational advantages of Quantum Information Processing in the context of classical 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, which are known to generate computationally hard problems. The basic approach to be pursued is to classify instances of these two models in terms of their quantum computational 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 Director of 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.