QRewriting

基于模式匹配的量子电路重写框架

摘要 量子算法的实现依赖于根据底层量子处理器进行特定的量子编译。然而，在不同的物理设备中，有各种方法来物理实现量子比特并操纵这些量子比特。这些差异导致了不同的通信方法和连接拓扑，每个供应商都实现了自己的一组原始门。因此，量子电路必须重写或转换才能从一个平台移植到另一个平台。我们提出了一个基于模式匹配的量子电路重写框架，称为 QRewriting。它利用了一种使用符号序列的量子电路新表示。与使用有向无环图的传统方法不同，新的表示使我们能够轻松识别非连续出现但可简化的模式。然后，我们将模式匹配问题转换为寻找不同子序列的问题，并提出了一种基于多项式时间动态规划的模式匹配和替换算法。我们开发了一个用于基本优化的规则库，并将算术和 Toffoli 电路从常用的门集重写为 Surface-17 量子处理器支持的门集。与在 BIGD 基准上优化的最先进的量子电路优化框架 PaF 相比，QRewriting 进一步将深度和门数分别平均减少了 26.5% 和 17.4%。