Optimal Layout Synthesis for Quantum Computing
Optimal Layout Synthesis for Quantum Computing
复制标题
量子计算的最优布局综合
DOI：
10.1145/3400302.3415620
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
J. Cong
中科院分区：
文献类型：
--
作者：
Daniel Bochen Tan;J. Cong
近年来见证了量子计算的快速发展。世界各地的研究人员都渴望运行越来越大的量子算法，这些算法承诺对任何经典算法都无法加速。但是，可用的量子计算机仍然波动且容易出错。因此，将量子程序转换以满足这些硬件限制的布局合成是实现量子计算的关键步骤。在本文中，我们提出了两个合成器，一个合成器，一个最佳和一个近似值，但几乎是最佳。尽管已经发布了一些解决此问题的最佳方法，但我们的最佳合成器探索了更大的解决方案空间，因此在更强的意义上是最佳的。此外，与某些领先的最佳方法相比，它将时间和空间复杂性成倍降低。成功的关键是将布局合成问题作为数学编程问题的更有效的时空编码。通过稍微更改我们的配方，我们获得了一个近似的合成器，该合成器更加有效，并且在额外的门成本方面胜过某些领先的启发式方法，最高可达100％，并且在一套全面的基准标准上，最高可达10倍程序和体系结构。对于一个名为QAOA的特定量子程序家族，该量子程序被认为是近期量子计算机的有前途的应用程序，我们通过考虑换向的考虑，进一步调整了近似合成器，最高可达到75％，高达65％与领先的QAOA研究中使用的工具相比，额外成本降低。
Recent years have witnessed the fast development of quantum computing. Researchers around the world are eager to run larger and larger quantum algorithms that promise speedups impossible to any classical algorithm. However, the available quantum computers are still volatile and error-prone. Thus, layout synthesis, which transforms quantum programs to meet these hardware limitations, is a crucial step in the realization of quantum computing. In this paper, we present two synthesizers, one optimal and one approximate but nearly optimal. Although a few optimal approaches to this problem have been published, our optimal synthesizer explores a larger solution space, thus is optimal in a stronger sense. In addition, it reduces time and space complexity exponentially compared to some leading optimal approaches. The key to this success is a more efficient spacetime-based variable encoding of the layout synthesis problem as a mathematical programming problem. By slightly changing our formulation, we arrive at an approximate synthesizer that is even more efficient and outperforms some leading heuristic approaches, in terms of additional gate cost, by up to 100%, and also fidelity by up to 10x on a comprehensive set of benchmark programs and architectures. For a specific family of quantum programs named QAOA, which is deemed to be a promising application for near-term quantum computers, we further adjust the approximate synthesizer by taking commutation into consideration, achieving up to 75% reduction in depth and up to 65% reduction in additional cost compared to the tool used in a leading QAOA study.