论文标题
高斯消除与贪婪的方法，用于合成线性可逆电路
Gaussian Elimination versus Greedy Methods for the Synthesis of Linear Reversible Circuits
论文作者
论文摘要
线性可逆电路代表了可逆电路的子类，其中许多应用在量子计算中。这些电路可以通过经典计算机有效地模拟，它们的大小在多个量子位上是多项式界限的，这使它们成为部署有效方法以降低计算成本的良好候选者。我们提出了一种新算法，用于通过使用高斯消除算法的优化版本与调谐的LU分解来合成任何线性可逆操作员。我们还提高了纯粹贪婪方法的可伸缩性。总体而言，在随机操作员上，我们的算法改善了特定问题范围的最先进方法：自定义高斯消除算法为大型问题大小（n> 150）提供了最佳结果，纯粹的贪婪方法可提供准最佳结果，而当n <30时，我们可以在n <30中降低c nections n <30。重要性（T计数，T-Depth）尽可能低。
Linear reversible circuits represent a subclass of reversible circuits with many applications in quantum computing. These circuits can be efficiently simulated by classical computers and their size is polynomially bounded by the number of qubits, making them a good candidate to deploy efficient methods to reduce computational costs. We propose a new algorithm for synthesizing any linear reversible operator by using an optimized version of the Gaussian elimination algorithm coupled with a tuned LU factorization. We also improve the scalability of purely greedy methods. Overall, on random operators, our algorithms improve the state-of-the-art methods for specific ranges of problem sizes: the custom Gaussian elimination algorithm provides the best results for large problem sizes (n > 150) while the purely greedy methods provide quasi optimal results when n < 30. On a benchmark of reversible functions, we manage to significantly reduce the CNOT count and the depth of the circuit while keeping other metrics of importance (T-count, T-depth) as low as possible.
