Numerical Simulations of Quantum Computers and Disordered Systems

该奖项支持将统计力学工具应用于量子计算机的整体预期性能问题和自旋玻璃性质的关键概念问题的计算和理论研究和教育。量子计算的一个主要问题是最终的量子计算机是否能够比经典计算机更有效地解决广泛的问题。PI将调查是否所需的时间，复杂性，量子绝热算法来解决一个？量子计算机上的“优化”问题随变量数N的幂或随N呈指数变化。重点将是在量子绝热算法中的控制参数变化的最小间隙的大小依赖性。为了确定在大N的复杂性，PI计划开发新的算法，这将允许模拟更大的尺寸比在早期的工作，并修改量子模型，以使渐近依赖出现较小的sizes.The PI将调查数值，最广泛的研究类型的系统与混乱和挫折，？旋转玻璃。？自旋玻璃物理学适用于科学中的广泛问题。分析计算是非常困难的;我们所知道的很多东西都来自模拟。PI将调查几个关键问题：（i）是否存在过渡线？在磁场中的“阿尔梅达-无齿”线？(ii)海森堡自旋玻璃中跃迁的性质是什么？(iii)有没有？结构玻璃中的“理想玻璃化转变”？ 实际上，大部分工作都是在一维模型上进行的，其中的相互作用平均而言会随着距离的增加而下降。该模型的优点是（i）可以研究大尺寸，以及（ii）该模型类似于有限尺寸的短程模型，并且改变功率相当于改变短程模型的尺寸。因此，自旋玻璃物理可以，在效果上，通过使用这个模型在很宽的尺寸范围内进行研究。这一建议将支持学生的教育，在发展国家的最先进的算法，大规模的计算机模拟。这项研究将使他们能够在许多相关领域从事科学事业。研究中使用的技术将被纳入为本科生和研究生提供的计算物理课程。技术摘要该奖项支持将统计力学工具应用于量子计算机的整体预期性能问题和自旋玻璃性质的关键概念问题的计算和理论研究和教育。量子计算机是否能被制造出来量子计算机将通过准备和操纵量子力学状态来工作。研究表明，对于某些任务，量子计算机将比现有最快的计算机快得多。但它们能比现有的计算机更快地解决一般问题吗？PI将应用为统计物理问题开发的计算技术，以了解在量子计算机上执行的量子计算机通用算法是否比经典计算机的算法更有效。这项研究说明了人们可以从量子计算机中期望的一般性能，并可能对量子计算领域的发展产生影响。PI还将研究？旋转眼镜”，这是交互系统的原型与挫折？系统之间的相互作用存在着强烈的竞争。自旋玻璃之所以重要，是因为为它们开发的想法适用于广泛的复杂系统，例如计算机科学中的组合优化问题，生物学中的蛋白质折叠，结构玻璃？?窗玻璃，？自旋玻璃是研究这类问题的一个方便的系统，因为它们可以通过施加磁场在实验中进行详细的探测，并且可以通过屈服于计算的模型在理论上表示。了解自旋玻璃将有助于我们理解广泛的问题，跨学科的边界。这一建议将支持学生的教育，在发展国家的最先进的算法，大规模的计算机模拟。这项研究将使他们能够在许多相关领域从事科学事业。研究中使用的技术将被纳入为本科生和研究生提供的计算物理课程。

TECHNICAL SUMMARYThis 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 ABSTRACTThis 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.