Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation
Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation
复制标题
DOI：
10.1109/hpec55821.2022.9926353
复制
发表时间：
2022-09
期刊：
影响因子：
--
通讯作者：
Cameron Ibrahim;Danylo Lykov;Zichang He;Y. Alexeev;Ilya Safro
中科院分区：
文献类型：
--
作者：
Cameron Ibrahim;Danylo Lykov;Zichang He;Y. Alexeev;Ilya Safro
基于张量网络的量子电路模拟的关键问题之一是构造一个收缩树，使模拟的成本最小化，其中成本可以表示为模拟运行时间的代理操作的数量。同样的问题出现在各种应用领域，如组合科学计算，边缘化的概率图形模型，并解决约束满足问题。在本文中，我们减少了计算困难的部分，这个问题的一个图的线性排序，并演示了如何在这一领域的现有方法可以利用，以实现几个数量级优于现有的最先进的方法相同的运行时间。为此，我们引入了一种新的多项式时间算法，从给定的顺序构建一个最佳的收缩树。此外，我们介绍了一个快速和高品质的线性排序求解器，并证明其适用性作为一个启发式提供订单收缩树。最后，我们比较了我们的求解器与竞争的方法构建收缩树在量子电路模拟上的一组随机生成的量子近似优化算法最大切割电路，并表明我们的方法实现了上级结果对大多数测试的量子电路。复制：我们的源代码和数据可以在https://github.com/cameton/HPEC2022_ContractionTrees上找到。
One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees.