Near-term quantum computing for solving hard industrial optimisation problems

优化和约束满足问题在工业中无处不在，从安排时间表等简单任务到布置电信网络或高性能集成电路等极具挑战性的任务。像这样的问题与需要搜索指数级的许多潜在解决方案以找到最佳可能的解决方案相关联。找到更好的优化问题解决方案可以实现多种结果，如降低包裹交付的运输成本和增加蜂窝网络的容量。然而，尽管理论家和实践者多年来一直在努力，这些问题对标准计算机来说仍然是非常具有挑战性的。自20世纪90年代以来，人们就知道量子计算机可以比标准计算机更快地解决优化问题。例如，Grover著名的量子搜索算法可以解决优化问题，其运行时间可以像经典非结构化搜索的运行时间的平方根一样扩展。然而，这种方法和其他用于解决优化问题的方法只适用于长期的容错量子计算，这就提出了一个问题，即量子计算机是否可以在不久的将来应用于优化问题，使它们能够释放相关的价值。在这个项目中，我们将确定近期门模型量子计算解决优化问题的潜力。项目合作伙伴英国电信将确定特别适合量子计算机解决的问题，特别是在电信网络优化领域。项目合作伙伴Phasecraft将为这些问题和相关问题设计和实现量子算法，这些算法将在项目合作伙伴Rigetti开发的尖端量子硬件上执行和评估。该项目结果的商业可行性将通过与解决优化问题的领先经典方法进行比较来评估。我们的工作将建立在之前InnovateUK资助的可行性研究的结果基础上，该研究探索了容错量子计算机解决与电信网络相关的长期优化问题的潜力，但没有在真实的硬件上实现近期算法。我们将举办一个创新研讨会，针对那些优化问题与其业务相关的领先组织，确定哪些问题最有希望通过量子计算解决，并展示该项目的结果。我们希望该项目将提供一个解决优化问题的量子解决方案，在真实的量子硬件上进行演示，并为现实世界的问题提供一个清晰的路线图。

Optimisation and constraint satisfaction problems are ubiquitous in industry, ranging from straightforward tasks such as arranging a timetable to exceptionally challenging ones such as laying out a telecommunications network or a high-performance integrated circuit. Problems like this are associated with the need to search over exponentially many potential solutions to find the best possible solution. Finding better solutions to optimisation problems could enable outcomes as diverse as reducing shipping costs for package deliveries and increasing the capacity of cellular networks. Yet these problems remain exceptionally challenging for standard computers, despite many years of effort from theorists and practitioners.It has been known since the 1990s that quantum computers could solve optimisation problems significantly more quickly than standard computers. For example, Grover's famous quantum search algorithm can solve optimisation problems with a runtime that scales like the square root of the runtime of classical unstructured search. However, this approach and others for solving optimisation problems are suitable only for long-term, fault-tolerant quantum computing, raising the question of whether quantum computers can be applied to optimisation problems in the near future, enabling them to unlock the associated value.In this project we will determine the potential for near-term gate-model quantum computing to solve optimisation problems. Project partner BT will identify problems, in particular in the domain of telecoms network optimisation, that are particularly suited to being solved by quantum computers. Project partner Phasecraft will design and implement quantum algorithms for these and related problems, which will be executed and evaluated on cutting-edge quantum hardware developed by project partner Rigetti. Commercial feasibility of the results of the project will be evaluated by comparing against leading classical approaches for solving optimisation problems.Our work will build on the results of a previous InnovateUK funded feasibility study, which explored the potential for fault-tolerant quantum computers to solve optimisation problems relevant to telecom networks in the long term, but did not implement near-term algorithms on real hardware.We will hold an innovation workshop targeted at leading organisations for whom optimisation problems are relevant to their businesses, to determine which problems are the most promising to be addressed by quantum computing and to present the results of the project. We expect that the project will deliver a quantum solution for solving optimisation problems, demonstrated on real quantum hardware, as well as a clear roadmap for applicability to real-world problems.