New directions in quantum algorithms

量子计算是建立在量子力学原理基础上的一种新的计算模式。令人兴奋的是，它为某些问题提供了比经典算法更快的算法。non-quantum)计算。例如，对于将大合数分解为其质因数的任务，认为没有有效的经典算法。这个问题在密码学中很重要。然而，确实存在一种有效的量子算法来完成这一任务（称为肖尔算法）。这个问题似乎包含了一些量子计算可以以经典计算无法使用的方式使用的结构。另一个重要的量子算法被称为格罗弗算法；令人惊讶的是，使用这种算法，量子计算机可以在搜索无序列表的基本任务中实现比经典计算机更快的速度。本研究的目的是基于这两种算法不同的原理开发新的量子算法，反过来提高我们对量子计算局限性的理解。该项目的具体目标是：1。将经典的启发式算法扩展到量子算法中，获得新的量子加速。绝大多数关于量子计算的研究都考虑了复杂性的最坏情况。该项目旨在开发平均优于经典算法的量子算法。这将大大增加量子计算机可以有效应用的问题范围。开创了优化问题不可逼近性的量子理论。众所周知，对于某些优化问题，标准计算机很难给出近似的答案。该项目将迈出将这一概念转化为量子计算的第一步，并将因此证明量子计算机能力的局限性。产生第一个有效的量子数据结构。该项目将研究量子态是否可以用作数据结构，以实现与经典数据结构相比减少空间的问题。大规模量子计算机尚未建成。然而，更好地了解这些机器的潜力既可以大大加快它们的发展，又可以为尝试在第一个地方建造它们提供额外的理由。这项研究旨在帮助产生这样一种理解。

Quantum computation is a new model of computing based on the principles of quantum mechanics. Excitingly, it offers the prospect of obtaining faster algorithms for certain problems than are possible in classical (ie. non-quantum) computation.As an example, it is believed that there exists no efficient classical algorithm for the task of decomposing a large composite number into its prime factors. This problem is important in cryptography. However, there does exist an efficient quantum algorithm for this task (known as Shor's algorithm). The problem appears to contain some structure that quantum computation can use in a way that classical computation cannot. Another important quantum algorithm is known as Grover's algorithm; surprisingly, using this algorithm a quantum computer can achieve a speed-up over classical computers in the basic task of searching an unsorted list.The aim of this research is to develop new quantum algorithms based on different principles to these two algorithms, and conversely to improve our understanding of the limitations of quantum computing. Specific goals of the project are:1. To obtain new quantum speed-ups by extending classical heuristics to quantum algorithms. The vast majority of research in quantum computing has considered worst-case measures of complexity. This project aims to develop quantum algorithms that outperform classical algorithms on average. This should vastly increase the range of problems to which quantum computers can be usefully applied.2. To initiate a quantum theory of inapproximability of optimisation problems. It is known that it is hard for standard computers to approximate the answer to certain optimisation problems. This project will take the first steps in translating this concept to quantum computation, and will thus prove limitations on the power of quantum computers.3. To produce the first efficient quantum data structures. This project will investigate the question of whether quantum states can be used as data structures to achieve a reduction in space compared to classical data structures.Large-scale quantum computers are yet to be built. However, a better understanding of the potential of these machines could both greatly accelerate their development, and give additional reasons for attempting to build them in the first place. This research aims to help produce such an understanding.