New insights in quantum algorithms and complexity

量子计算机是一种机器，它使用量子力学的神秘原理在某些任务中实现优于任何标准（“经典”）计算机的优势。大规模的量子计算机尚未建成;然而，国际社会目前正在努力这样做。为了理解量子计算的力量，也进行了许多理论工作，特别是，量子算法已经被开发用于某些问题，这些问题优于在经典计算机上运行的任何可能的算法。这些问题包括破解密码（例如作为互联网安全基础的RSA代码），某些数据库搜索问题，以及量子力学系统的有效模拟（应用包括药物化合物和新材料的设计）。量子计算研究如此迷人的一个原因是，除了具有这样的实际应用外，使我们对大自然有更深的认识。量子力学是宇宙的物理基础，理解量子计算机的功能就等于理解宇宙的计算能力。本项目旨在更深入地理解某些问题，这意味着存在一种有效的量子算法来解决这些问题。特别是，该项目将为量子计算机开发新的算法和协议，以获得与经典计算相比的显着效率提升。其中一些算法可以在不久的将来进行实验测试。该提案分为三个主题，第一个主题将寻找新的量子算法、通信协议和数据结构。例如，超高效的量子算法将被开发出来，用于确定一个物体是否具有某种属性，或者距离具有这种属性非常遥远。这种性质的一个问题是，通过只查看计算机之间随机选择的几个链接，来确定计算机网络是否连接或非常远离连接。到目前为止，人们已经很好地理解了哪些问题在经典计算机上可以快速解决。然而，量子计算机可能能够在解决这类问题时实现显着的加速。此外，还将利用量子漫步技术，开发出解决离散问题（如图形和编码）的有效算法，并最终解决是否存在比任何经典数据结构更有效的量子数据结构的问题。第二个主题是利用量子计算的思想来研究量子物理和量子化学问题的复杂性。一方面，新的量子算法将被开发出来，使量子计算机能够比经典算法更有效地解决这些领域的实际重要问题。另一方面，这一领域的某些问题的棘手性将得到证明，这将使从业者（如物理学家和化学家）能够确定他们想要解决的问题实际上在本质上是困难的。因此，即使没有大型量子计算机，量子计算的思想也是一个有用的工具。最后，第三个主题将开发新的基础数学技术，以解决前两个主题提出的难题。这些成果包括“超压缩性”理论的发展（该理论最近已成为理论计算机科学中许多重要成果的重要工具），以及新的数学技术，以找到量子计算能力的更严格界限。总而言之，这些成果将标志着我们对量子计算机能力的理解向前迈出了一大步。

A quantum computer is a machine built to use the mysterious principles of quantum mechanics to achieve an advantage in some task over any standard ("classical") computer. Large-scale quantum computers have not yet been built; however, an international effort is currently underway to do so. Much theoretical work has also been carried out to understand the power of quantum computation, and in particular, quantum algorithms have been developed for certain problems that outperform any possible algorithm running on a classical computer. These problems include breaking cryptographic codes (such as the RSA code which underlies Internet security), certain database search problems, and efficient simulation of quantum mechanical systems (with applications including design of medicinal compounds and novel materials).One reason that the study of quantum computing is so fascinating is that, as well as having practical applications like this, it enables us to obtain a deeper understanding of nature. As it appears that quantum mechanics is the physical theory on which our universe is based, understanding what a quantum computer can do is nothing less than understanding the computational power of the universe.This project aims to find a deeper understanding of what it is about certain problems which means that there is an efficient quantum algorithm to solve them. In particular, the project will develop new algorithms and protocols for quantum computers to obtain dramatic efficiency improvements over classical computation. Some of these algorithms could be tested experimentally in the near future. The proposal is divided into three themes.The first theme will find new quantum algorithms, communication protocols and data structures. For example, super-efficient quantum algorithms will be developed for determining whether an object has some property, or is very far away from having that property. One problem of this nature would be to determine whether a computer network is connected or very far from connected, by looking at only a few, randomly chosen, links between computers. It is by now fairly well understood which problems like this have fast solutions on a classical computer. However, quantum computers might be able to achieve dramatic speed-ups for certain problems of this type. Efficient algorithms for discrete problems (e.g. concerning graphs and codes) will also be developed using the exciting new technique known as quantum walks, and finally the question of whether there exist quantum data structures which are more efficient than any classical data structure will be attacked.In the second theme, ideas from quantum computing will be used to study the complexity of problems from quantum physics and quantum chemistry. On the one hand, new quantum algorithms will be developed that allow quantum computers to solve practically important problems from these fields more efficiently than is possible classically. On the other, intractability of certain problems in this area will be proven, which will enable practitioners (such as physicists and chemists) to determine when problems they want to solve are actually intrinsically hard. Ideas from quantum computing are thus a helpful tool even without having access to a large-scale quantum computer.Finally, the third theme will develop new underlying mathematical technology in order to solve the difficult problems thrown up by the first two themes. These include developments in the theory of "hypercontractivity", which has recently been an essential tool in many important results in theoretical computer science, and new mathematical techniques to find tighter bounds on the abilities of quantum computation.Taken together, these results will mark a significant leap forward in our understanding of the power of quantum computers.