Applied Category Theory for Compilation of Quantum Algorithms

量子算法编译的应用范畴论

• 批准号: 2426721
• 金额: --
• 依托单位: University of Oxford
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2020
• 资助国家: 英国
• 起止时间: 2020 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2426721
• 关键词: Applied; Category; Theory; Compilation; Quantum

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.

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