Exploration of the timeliness and value of Quantum Algorithms

最近在开发量子计算（QC）硬件方面取得了重大进展。现在的主要挑战是开发算法，为现实世界的最终用户应用程序开放这种硬件的应用程序。当我们考虑未来的量子计算设备（例如，大规模，容错系统）时，以及当我们询问未来5-10年可用硬件的可能性时，这都是正确的。这个项目将涉及偏微分方程的量子算法的发展，特别是计算流体动力学。我们将与AWE的科学家直接合作，测试我们为相关问题开发的新算法，并将它们与现有的经典计算方法进行比较。当前最重要的挑战之一是，在现有HPC基础设施上使用的算法不能直接在量子计算机上使用。相反，在选择与程序相关的任务时，我们必须设计利用QC独特操作机制的算法。从广义上看，开发量子计算机应用程序有两种方法：1)大规模容错设备的软件。在这里，算法设计是硬件无关的。可以证明，这些机器将比经典的高性能计算有优势，至少对于某些类型的线性微分方程。然而，这种硬件的开发可能需要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.