New directions in quantum algorithms

量子计算是基于量子力学原理的一种新的计算模式。令人兴奋的是，它为某些问题提供了比经典(即。例如，人们认为，对于将一个大的复合数分解成它的素数因子的任务，没有有效的经典算法。这个问题在密码学中很重要。然而，对于这项任务，确实存在一种有效的量子算法(称为肖尔算法)。这个问题似乎包含一些量子计算可以使用的结构，而经典计算则不能。另一种重要的量子算法是Grover算法；令人惊讶的是，使用该算法，量子计算机在搜索未排序列表的基本任务中可以实现比经典计算机更快的速度。本研究的目的是基于不同于这两种算法的原理开发新的量子算法，并反过来提高我们对量子计算局限性的理解。该项目的具体目标是：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.