Algorithms for Tensor Network Contraction Ordering
Contracting tensor networks is often computationally demanding. Well-designed contraction sequences can dramatically reduce the contraction cost. We explore the performance of simulated annealing and genetic algorithms, two common discrete optimization techniques, to this ordering problem. We benchmark their performance as well as that of the commonly-used greedy search on physically relevant tensor networks. Where computationally feasible, we also compare them with the optimal contraction sequence obtained by an exhaustive search. We find that the algorithms we consider consistently outperform a greedy search given equal computational resources, with an advantage that scales with tensor network size. We compare the obtained contraction sequences and identify signs of highly non-local optimization, with the more sophisticated algorithms sacrificing run-time early in the contraction for better overall performance.
Code (1)
Tasks
Tensor NetworksSimilar Papers 제목 키워드 기반
Optimizing Tensor Network Contraction Using Reinforcement Learning
Quantum Computing (QC) stands to revolutionize computing, but is currently still limited. To develop and test quantum algorithms today, quantum circuits are often simulated on classical computers. Simulating a complex qu…
Combinatorial Optimizationreinforcement-learningReinforcement LearningReinforcement Learning (RL)Learning to Rank Tensor Network Contraction Plans for GPU-Accelerated Quantum Circuit Simulation
Classical simulation remains essential for developing and validating quantum algorithms, but its cost grows rapidly with circuit size. Tensor-network contraction can reduce this cost by exploiting circuit structure, alth…
Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
Constrained counting is a fundamental problem in artificial intelligence. A promising new algebraic approach to constrained counting makes use of tensor networks, following a reduction from constrained counting to the pr…
Tensor NetworksDuality of Graphical Models and Tensor Networks
In this article we show the duality between tensor networks and undirected graphical models with discrete variables. We study tensor networks on hypergraphs, which we call tensor hypernetworks. We show that the tensor hy…
Tensor NetworksFast and Guaranteed Tensor Decomposition via Sketching
Tensor CANDECOMP/PARAFAC (CP) decomposition has wide applications in statistical learning of latent variable models and in data mining. In this paper, we propose fast and randomized tensor CP decomposition algorithms bas…
Tensor Decomposition