EMT/QIS: Physics Based Approaches to Quantum Algorithms

量子计算位于计算机科学和物理学的交叉点，是一种有前途的新兴技术。 量子算法利用了传统计算机无法利用的量子效应。有一些引人注目的例子表明，在量子计算机上运行的量子算法将优于任何尝试相同任务的经典计算机。 这些包括寻找一个数的素因子，搜索一个无序列表，并确定谁赢得了比赛。 新算法的发现是这一领域发展的关键。 研究人员希望开发新的算法，并研究某些已知算法的性能，这些算法的运行时间尚未确定。 希望是继续开发物理学和传统算法设计中使用的技术之间富有成效的协同作用。这里的研究将在计算机科学和物理学领域之间架起桥梁，寻找新的算法，并加深我们对量子加速背后的物理学的理解。 大规模量子计算机的发展将改变计算世界，这项研究试图帮助开发这样一台机器。 要研究的主题包括量子行走算法，算法评估琼斯多项式和其他相关的数量，以及密码协议的不可伪造的身份。 绝热算法将使用矩阵乘积状态分析器以及通过大规模数值模拟来研究，并且该算法的容错性也将被研究。

Quantum computation lies at the intersection of computer science and physics and is a promising emerging technology. Quantum algorithms take advantage of quantum effects not available to conventional computers. There are striking examples where a quantum algorithm, running on a quantum computer, would outperform any classical computer attempting the same task. These include finding the prime factors of a number, searching an unordered list and determining who wins a game. The discovery of new algorithms is key to the growth of this field. The investigators hope to develop new algorithms as well as study the performance of certain known algorithms whose run time is not yet established. The hope is to continue to develop a fruitful synergy between techniques used in physics and conventional algorithm design. The research here would bridge the fields of computer science and physics looking for new algorithms as well as deepening our understanding of the physics which underlies the quantum speedups. The development of a large scale functioning quantum computer would change the world of computation and this research attempts to aid the effort to develop such a machine. The topics to be investigated include quantum walk algorithms, algorithms for evaluating the Jones polynomial and other related quantities, as well as cryptographic protocols for unforgeable identification. The adiabatic algorithm will be studied using a Matrix Product State ansatz as well as by large scale numerical simulation and the fault tolerance of this algorithm will also be investigated.