Applied Category Theory for Compilation of Quantum Algorithms

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.