Applied Category Theory for Compilation of Quantum Algorithms

在密码学和量子化学等领域的重要应用中，量子计算的几种算法有望逐渐优于经典算法。然而，尽管最近取得了重大进展，但在有用的问题规模上执行这些算法所需的资源通常比当前可用的硬件高几个数量级。因此，这些算法的运行问题必须从两个不同的方向来解决：改进硬件以匹配所需的规格，改进算法的编译以减少资源需求。我建议使用范畴量子力学，以及一般的范畴理论，来对算法的编译进行推理，并开发理论和实践工具，以允许渐进优势的量子算法更快地在实际设备上运行，并且使用更少的资源。这具有巨大的潜在影响，因为获得现实生活中的量子优势可能会对几个问题领域产生革命性的影响。这种方法最近成功地使用了图形演算，如用于减少量子电路中的t和cnot计数的zx演算、原始量子位映射方法、容错程序的时空压缩和新量子纠错码的开发，但许多候选主题仍未探索。量子计算和相应的量子算法有两种广泛的机制：(a)近期所谓的噪声中尺度量子（NISQ）设备，其中硬件错误是主要的限制因素；(b)容错设备的长期目标，它利用使用大量量子比特或外来准粒子的纠错码来克服硬件错误。NISQ器件的量子位很少，往往存在连接性差、相干时间低和门保真度差的问题，尤其是纠缠门。因此，NISQ算法是变分的，将浅量子电路作为子程序在更大的经典循环中运行，以优化成本函数。虽然使用范畴量子力学对NISQ编译进行了一些改进，但NISQ算法往往是同质的和原始的，并且电路模型似乎大多是足够的。相比之下，在计划容错设备上的本地操作，如缺陷编织和晶格手术，使用范畴量子力学很好地表示，相关的计算模型与NISQ电路有很大不同。最昂贵的资源是非clifford状态，即使给定数百万物理量子位，运行一个完整的容错算法也可能需要几天的时间来处理相关的问题规模。这是编译工具开发的一个关键领域。现有的分类模型描述了使用外来准粒子的计算，这些模型应该被改进和扩展到一般的容错计算。本课题的研究与现代应用范畴论相一致，利用一元范畴和图解推理来描述复杂系统。该项目属于EPSRC量子技术研究领域。

Several algorithms for quantum computing can be expected to asymptotically outperform their classical counterparts for important applications in areas such as cryptography and quantum chemistry. However, despite significant recent advancements, the resources required to perform these algorithms at useful problem sizes are typically orders of magnitude above the available current hardware. Therefore, the problem of running these algorithms must be tackled from two different directions: the improvement of hardware to match the required specifications, and improved compilation of algorithms to reduce the resource requirements.I propose the use of categorical quantum mechanics, and category theory in general, to reason about compilation of algorithms, and to develop theoretical and practical tools to allow asymptotically advantageous quantum algorithms to run on real devices sooner and with fewer resources. This has large potential impact, as obtaining real-life quantum advantage would be potentially revolutionary for several problem domains. This approach has recently seen success using graphical calculi such as the ZX-calculus for reduction of T-and CNOT-counts in quantum circuits, original qubit-mapping methods, space-time compression of fault-tolerant programs and development of new quantum error correction codes, but many candidate topics remain unexplored.There are two broad regimes of quantum computing, and corresponding quantum algorithms: (a) near-term so-called noisy intermediate scale quantum (NISQ) devices, for which hardware errors are the primary limiting factors, and (b) the long-term goal of fault-tolerant devices, which leverage error correcting codes using large numbers of qubits or exotic quasiparticles to overcome hardware errors.NISQ devices have few qubits, which tend to suffer from poor connectivity, low coherence times and poor gate fidelities, particularly for entangling gates. As a result, NISQ algorithms are variational, running a shallow quantum circuit as a subroutine within a larger classical loop to optimise a cost function. While there have been some improvements made to NISQ compilation using categorical quantum mechanics, NISQ algorithms tend to be homogeneous and primitive, and the circuit model appears mostly sufficient.By contrast, native operations on planned fault-tolerant devices, such as defect braiding and lattice surgery, are well-represented using categorical quantum mechanics, and the relevant computational models differ substantially from NISQ circuits. The most expensive resources are non-Clifford states, and running a full fault-tolerant algorithm could be expected to take several days for relevant problem sizes, even given millions of physical qubits. This is a key area for the development of compilation tools. Existing categorical models describe computation using exotic quasiparticles, and these should be refined and extended for general fault-tolerant computation.The research on this topic aligns with modern applied category theory, leveraging monoidal categories and diagrammatic reasoning to describe complex systems. This project falls within the EPSRC Quantum Technologies research area.