New insights in quantum algorithms and complexity

量子算法和复杂性的新见解

• 批准号: EP/L021005/1
• 负责人: Ashley Montanaro
• 金额: $ 107.19万
• 依托单位: University of Bristol
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2014
• 资助国家: 英国
• 起止时间: 2014 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FL021005%2F1
• 关键词: New; insights; quantum; algorithms; complexity

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.

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

项目成果

Average-Case Complexity Versus Approximate Simulation of Commuting Quantum Computations

• DOI: 10.1103/physrevlett.117.080501
• 发表时间: 2016-08-18
• 期刊: PHYSICAL REVIEW LETTERS
• 影响因子: 8.6
• 作者: Bremner, Michael J.;Montanaro, Ashley;Shepherd, Dan J.
• 通讯作者: Shepherd, Dan J.

Number of superclasses of four-qubit entangled states under the inductive entanglement classification

• DOI: 10.1103/physreva.95.022329
• 发表时间: 2017-02
• 期刊: Physical Review A
• 影响因子: 2.9
• 作者: Miriam Backens

Complexity Classification of Two-Qubit Commuting Hamiltonians

二量子位通勤哈密顿量的复杂性分类

• 发表时间: 2016
• 作者: Bouland A

A Simplified Stabilizer ZX-calculus

• DOI: 10.4204/eptcs.236.1
• 发表时间: 2016-02
• 作者: Miriam Backens;S. Perdrix;Quanlong Wang

Improved bounds on Fourier entropy and min-entropy

改进傅里叶熵和最小熵的界限

• DOI: 10.4230/lipics.stacs.2020.45
• 发表时间: 2020
• 期刊: Leibniz International Proceedings in Informatics, LIPIcs
• 作者: Arunachalam S.