The Phase Ordering Problem for Quantum Circuit Compilation

通过利用量子力学定律，量子计算有可能让我们比传统计算机更快地执行任务。目前的设备有噪声，因此为容错量子计算机设计的算法不能可靠地执行。对执行这种算法所需资源的改进将使更大的任务能够在量子计算机上精确解决，使我们更接近量子优势。本文提出了程序设计语言理论和电路编译的研究方向，旨在为量子计算的研究和发展设计新的工具。尽管在开发新的量子算法和硬件方面取得了令人印象深刻的进展，但在实践中，量子程序仍然使用电路来定义，这类似于经典计算中的汇编代码。这不是设计大规模量子应用程序的明智方法，因为它阻止程序员以模块化、可重用的方式表达他们的想法。为了充分利用量子的优势，有必要发展经典量子规划的语义。Sam Staton教授提出的代数框架，利用线性类型理论表征了量子信息的不可克隆性，为实现经典量子编程语言奠定了良好的基础，该语言可以利用代数效应将局部经典计算与只允许线性使用资源的外部量子计算分离开来。这种分离将使开发更高级、更不容易出错的软件成为可能，更容易为编译器分析。虽然ZX-calculus已经开发出新的有效的重写规则来简化电路[2]，但是在如何选择和应用这些重写规则方面缺乏研究：许多关于电路编译的论文在没有利用现有重写规则的情况下提出了新的重写规则并将其组合成一个贪心例程。一般来说，图表编写是一种非合流操作，因此应用编译阶段的顺序会严重影响结果。同时，这一相序问题在经典编译领域得到了较为深入的研究[0]。我的计划是使用pauliopt，这是Stefano Gogioso博士和我在硕士论文期间开发的基于泡利小工具的库，作为实现我将在博士课程中开发的新优化例程的框架。作为起点，我将使用机器学习来找到给定电路的最佳编译阶段顺序。然后，我将合并其他相位小工具重写规则，例如蜘蛛巢恒等式，它被天真地应用于实现最先进的t计数减少。在我看来，开源软件的发展对量子计算领域至关重要，所以我提出算法的论文都附有实现的代码。[4,5]为了证明它们的功效和益处，在哲学博士课程中开发的技术将伴随着实施和实验。特别是，我将专注于将QML技术应用于NLP，这是我从工作和本科学习中获得的经验。在牛津提供的优秀资源和监督下，我相信我能够取得最先进的成果，推动量子计算领域的发展。我的项目属于EPSRC量子技术领域。

By leveraging the laws of quantum mechanics, quantum computing potentially allows us to perform tasks faster than a classical computer. Current devices are noisy, so algorithmsdesigned for fault-tolerant quantum computers cannot be reliably performed. Improvements made upon the resources required to execute such algorithms will enable larger tasks to beaccurately solved on a quantum computer, bringing us closer to quantum advantage. This proposal presents directions of research in programming language theory and circuit compilation, with the aim of designing new tools for quantum computing research and development.Although impressive progress has been made in developing new quantum algorithms and hardware, in practice quantum programs are still defined using circuits, which are akin to assembly code in classical computing. This is not a sensible way to design large-scale quantum applications, as it prevents the programmer from expressing their ideas in a modular, reusable manner. To fully take advantage of quantum advantage, it is necessary to develop semantics for classical-quantum programming. The algebraic framework proposed by Prof. Sam Staton [1], which characterises the unclonability of quantum information using linear type theory, is a good foundation for implementing a classical-quantum programming language which can use algebraic effects to separate the local classical computation from external quantum computation that permits only linear use of resources. This separation will enable the development of more advanced, less error-prone software that is easier to analyse for acompiler.Although ZX-calculus has enabled the development of new and effective rewrite rules for simplifying circuits [2], there is a lack of research in how to select and apply such rewriterules: many papers on circuit compilation propose new rewrite rules and combine them into a greedy routine without leveraging existing rewrite rules. In general, diagrammaticrewriting is a non-confluent operation, so the order in which the compilation phases are applied can severely impact the results. Meanwhile, this problem of phase ordering has beenmore thoroughly studied in the field of classical compilation [3]. My plan is to use pauliopt, a Pauli gadget based library developed by Dr. Stefano Gogioso and me during my master'sthesis, as a framework for implementing the new optimisation routines that I will develop over the course of the DPhil. As a starting point, I will use machine learning to find theoptimal compilation phase ordering of a given circuit. Then, I will incorporate other phase gadget rewrite rules such as the spider nest identities, which have been naively applied toachieve state-of-the-art T-count reduction.In my opinion, the development of open-source software is crucial to the field of quantum computing, so my papers that propose algorithms are accompanied with implemented code.[4, 5] To demonstrate their effcacy and benefits, the techniques developed over the course of the DPhil will be accompanied with implementation and experiments. In particular, Iwill focus on applying QML techniques to NLP, a field I have gained experience in from my work and undergraduate studies. With the excellent resources and supervision that Oxfordprovides, I believe I will be able to achieve state-of-the-art results and advance the field of quantum computing.My project falls within EPSRC Quantum Technologies area.