Quantum Computational Complexity of Spin Glasses
Abstract
While it is in some sense natural that quantum systems are efficient at simulating one another, a less natural question is the efficient simulation of classical systems on quantum computers (QCs). This question was first raised, and partly answered by the PI in the context of Ising spin glasses (an ensemble of classical spin-1/2's with fixed random interactions). Recently, there has been further interest in classical physics simulations on QCs in the context of hydrodynamics, chaos, and knot theory, which has a deep connection to classical statistical mechanics. The purpose of this project is to quantify the computational complexity of the canonical problem of classical statistical mechanics: computation of the classical partition function. We have approached this problem using the Potts model and Ising spin glasses, which are known to give rise to a rich class of hard computational problems. Indeed, instances of spin glass and Potts model problems have been shown to be NP-hard, and have been mapped to problems in graph and knot theory. An "instance" of the spin glass problem refers here to a particular choice of (i) graph describing the spin glass (spins with q=2 states are located on the vertices, interactions on the edges), and (ii) distribution of interactions. An instance of the Potts model refers to a choice of a graph on whose vertices reside spins with q>1 (q an integer) states. In certain limits of particularly simple graphs and distributions these problems are analytically solvable, while in other limits they are computationally hard; hence by "tuning" the graph and distribution one may expect to traverse a "landscape of hardness", whose quantum computational complexity we are exploring.
Document Details
- Document Type
- Technical Report
- Publication Date
- Mar 19, 2011
- Accession Number
- ADA545157
Entities
People
- Daniel Lidar
Organizations
- University of Southern California