Numerical Simulations of Quantum Computers and Disordered Systems

University Of California-Santa Cruz, Santa Cruz CA

Investigators

Abstract

TECHNICAL SUMMARY This award supports computational and theoretical research and education applying the tools of statistical mechanics to questions on the overall expected performance of a quantum computer and to key conceptual questions on the nature of spin glasses. A major problem in quantum computing is whether an eventual quantum computer would be able to solve a broad range of problems more efficiently than a classical computer. The PI will investigate whether the time taken, the complexity, for the quantum adiabatic algorithm to solve an ?optimization" problem on a quantum computer varies as a power of the number of variables, N, or exponentially with N. The emphasis will be on the size dependence of the minimum gap as the control parameter in the quantum adiabatic algorithm is varied. In order to determine the complexity at large N, the PI plans to develop new algorithms which will allow simulations of larger sizes than in the earlier work, and also to modify the quantum models in order to make the asymptotic dependence appear for smaller sizes. The PI will investigate numerically, the most extensively studied type of system with disorder and frustration, the ?spin glass.? Spin glass physics applies to a wide range of problems in science. Analytical calculations are very hard; so much of what is known has come from simulations. The PI will investigate several key questions: (i) Is there a line of transitions, the ?Almeida-Thouless" line, in a magnetic field? (ii) What is the nature of transition in the Heisenberg spin glass? (iii) Is there an ?ideal glass transition" in structural glasses? Most of the work will actually be carried out on a model in one-dimension with interactions which, on average, fall off as a power of the distance. The advantages of this model are (i) that large sizes can be studied, and (ii) the model is analogous to a short-range model in a finite dimension, and changing the power is equivalent to changing the dimension of the short range model. Hence spin glass physics can, in effect, be studied over a wide range of dimensions by using this model. This proposal will support the education of students in developing state of the art algorithms for large-scale computer simulations. The research will enable them to pursue scientific careers in many related fields. Techniques used in the research will be incorporated into courses on computational physics offered to both undergraduate and graduate students. NON-TECHNICAL ABSTRACT This award supports computational and theoretical research and education applying the tools of statistical mechanics to questions on the overall expected performance of a quantum computer and to key conceptual questions on the nature of spin glasses. There is great excitement and experimental effort to determine whether a quantum computer can be made. A quantum computer would work through the preparation and manipulation of quantum mechanical states. It has been shown that for certain tasks, a quantum computer would be vastly faster than the fastest existing computers. But can they solve general problems faster than existing computers? The PI will apply computational techniques developed for the problems of Statistical Physics to understand if a proposed general purpose algorithm for a quantum computer executed on a quantum computer is more efficient than algorithms for a classical computer for large problems. This research speaks to the general performance one can expect from a quantum computer and may have impact on how the field of quantum computing evolves. The PI will also study ?spin glasses", which are archetypes for interacting systems with frustration ? systems where there is a strong competition between interactions. Spin glasses are important because ideas developed for them have applicability to a wide range of complex systems, such as combinatorial optimization problems in computer science, protein folding in biology, structural glasses ? ?window glass,? etc. Spin glasses are a convenient system in which to study this class of problems since they can be probed in fine detail in experiments by applying a magnetic field, and can be represented theoretically by models that succumb to computation. Understanding spin glasses will contribute to our understanding of a wide range of problems that cross disciplinary boundaries. This proposal will support the education of students in developing state of the art algorithms for large-scale computer simulations. The research will enable them to pursue scientific careers in many related fields. Techniques used in the research will be incorporated into courses on computational physics offered to both undergraduate and graduate students.