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.
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.
Quantum computers use the counter-intuitive behavior of quantum mechanics (the theory of nature which describes very small objects like atoms) to try to perform certain computations more efficiently than would be possible on a normal (classical) computer. While it has not yet been possible to build a quantum computer which could solve large problems (because it is very difficult to prevent external "noise" from eliminating the delicate quantum effects which give rise to the speed up) there is a lot of theoretical interest in determining which problems an eventual quantum computer could solve efficiently. In this project I have investigated whether a quantum computer could efficiently solve "optimization" problems, in which one has to find the maximum (or minimum) value of a function of many variables. These have a wide range of application in science, engineering and industry. Examples are image recognition, of great interest, for example, to Google, and efficient scheduling, which is of interest to NASA who wants to optimize the activity of the Mars Rover. Both of these problems can be formulated as optimization problems, and Google and NASA are interested in using quantum algorithms to solve them. However, during the project, I and collaborators found that a simple application of the algorithm proposed to solve optimization problems on a quantum computer does not lead to a faster solution than would be found on a classical computer, at least for the various problem we looked at. Many systems in nature evolve very slowly in time. An example is window glass in which the atoms do not form a periodic array as in a crystal but rather have an amorphous structure which can "flow' over astronomical times. Various magnetic systems, which can be studied more conveniently, also show behavior which varies very slowly with time as the temperature is lowered. A theoretical problem of interest is whether the time for the system to reach its equilibrium state (i.e. a state which no longer evolves with time), called the relaxation time, actually diverges at a certain temperature or whether the relaxation time smoothly increases as the temperature is lowered, eventually becoming longer than the time over which measurements can be performed but never actually diverging. A theory predicting a truly infinite relaxation time for the magnetic systems was developed a long time ago by Almeida and Thouless, but we only know, for sure, that it is correct for a very special model system, rather far removed from the real world. During this project, I and collaborators carried out numerical simulations on a magnetic system corresponding to the real world of three dimensions. We did not find a sharp transition where the relaxation time diverges.
