Exploration of the timeliness and value of Quantum Algorithms

最近在开发量子计算（QC）硬件方面取得了重大进展。现在的一个主要挑战是开发算法，为现实世界的最终用户应用程序打开这种硬件的应用程序。当我们考虑未来的量子计算设备（例如，大规模容错系统），以及当我们询问未来5-10年可用硬件的可能性时。该项目将涉及偏微分方程的量子算法的发展，特别是计算流体动力学。我们将与AWE的科学家直接合作，测试我们为相关问题开发的新算法，并将其与现有的经典计算方法进行基准测试。当前最重要的挑战之一是，现有HPC基础设施上使用的算法无法直接用于量子计算机。相反，选择与程序相关的任务，我们必须设计算法，利用QC独特的操作机制。从广义上讲，有两种方法可以开发量子计算机的应用程序：1）用于大规模容错设备的软件。这里，算法设计是硬件不可知的。可以证明，这些机器将具有优于经典HPC的优势，至少对于某些类别的线性微分方程。然而，开发这种硬件的时间可能需要10-15年，或者更长的时间来实现线性方程2）用于近期机器的软件，它利用了硬件实现的特定属性。这些特殊用途的机器有几种不同的形式，在文献中称为量子模拟器，量子退火器或噪声中间尺度量子（NISQ）计算机。优势证明往往是启发式的。但它们提供了在短得多的范围内（在未来5-10年内）产生影响的潜力。此外，所展示的启发式算法有时可以在经典硬件上运行，提供了量子启发的加速比现有的经典算法。一个很好的例子是物流优化新算法的开发（例如，路由和流量）。我们的目标是探索这些方法中的每一种来开发量子软件来求解特定类别的偏微分方程。我们将确定最有前途的方法，以及是否可以通过开发量子启发的经典算法来实现近期收益。该项目的具体目标是-确定有可能在量子计算机上加速解决的问题-开发算法来解决这些问题，在近期或长期内使用QC，同时也测试这些问题的量子启发经典算法-比较计算成本与现有的（经典）方法，寻找潜在的量子优势确定最有前途的算法和范围，在什么时间尺度上量子计算可能会对相应的领域产生影响。学生将直接参与开发量子算法，并开发其实现的经典模拟，以及量子启发的经典算法的实现。

There has been substantial recent progress in developing hardware for quantum computing (QC). A major challenge now is to develop algorithms that open applications of this hardware for real-world end-user applications. This is true both when we consider future quantum computing devices (e.g., large-scale, fault-tolerant systems), and also when we ask what is possible with hardware available in the next 5-10 years. This project will involve the development of quantum algorithms for partial differential equations, especially computational fluid dynamics. We will work in direct collaboration with scientists from AWE to test novel algorithms we develop for classes of relevant problems, and benchmark them against existing classical computing methods.One of the most important current challenges is that algorithms used on existing HPC infrastructure cannot be used directly on a quantum computer. Instead, choosing the tasks relevant to the programme we must design algorithms that take advantage of the unique operating mechanisms of QC. Broadly seen, there are two approaches to developing applications for quantum computers:1) Software for large-scale, fault tolerant devices. Here, the algorithm design is hardware-agnostic. It can be proven that these machines will have an advantage over classical HPC, at least for certain classes of linear differential equation. However, the timescale for development of this hardware might be 10-15 years away, or longer for large-scale implementation of linear equations2) Software for near-term machines, which takes advantage of specific properties of the hardware implementations. These special-purpose machines come in several distinct forms, referred to in the literature as Quantum Simulators, Quantum Annealers, or Noisy Intermediate-Scale Quantum (NISQ) computers. Proof of advantage tends to be heuristic. But they offer the potential for impact on a much shorter scale (within the next 5-10 years). In addition, the heuristic algorithms that are demonstrated can sometimes be run on classical hardware, offering a quantum-inspired speedup over existing classical algorithms. A good example has been the development of new algorithms for logistics optimization (e.g., of routing and traffic flows).We aim to explore each of these approaches for developing quantum software to solve specific classes of partial differential equations. We will identify the most promising way, and also whether near-term gains might be achieved by developing quantum-inspired classical algorithms.The specific objectives of this project are to- Identify problems that have the potential to be solved with a speed-up on a quantum computer- Develop algorithms to solve these problems with QC in the near or long term, while also testing quantum-inspired classical algorithms for these problems- Compare the computational cost to existing (classical) methods, looking to identify the potential for a quantum advantage - Identify the most promising algorithms and scope on what timescales quantum computing is likely to have an impact on the corresponding area.The student will be directly involved in developing quantum algorithms, and developing classical simulations of their implementations, as well as implementations of quantum-inspired classical algorithms.