# Optimizing Tensor Network Contraction Using Reinforcement Learning

arXiv: https://arxiv.org/abs/2204.09052 · HTML: https://mlsanity.com/paper/2204.09052/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 46 references that are in the map.
- First posted on arXiv 18 Apr 2022.

## Builds on (most cited first, 22 of 22)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [From Local Structures to Size Generalization in Graph Neural Networks](https://mlsanity.com/paper/2010.08853/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case](https://mlsanity.com/paper/1910.07421/) (2019)
- [Supervised Learning with Quantum-Inspired Tensor Networks](https://mlsanity.com/paper/1605.05775/) (2016)
- [Solving a New 3D Bin Packing Problem with Deep Reinforcement Learning Method](https://mlsanity.com/paper/1708.05930/) (2017)
- [Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2010.05313/) (2020)
- [Quantum Computing: A Taxonomy, Systematic Review and Future Directions](https://mlsanity.com/paper/2010.15559/) (2020)
- [No-Regret Reinforcement Learning with Heavy-Tailed Rewards](https://mlsanity.com/paper/2102.12769/) (2021)
- [A Survey on Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2008.12248/) (2020)
- [k-way Hypergraph Partitioning via n-Level Recursive Bisection](https://mlsanity.com/paper/1511.03137/) (2015)
- [Algorithms for Tensor Network Contraction Ordering](https://mlsanity.com/paper/2001.08063/) (2020)

## Built on by (most cited first, 5 of 5)

- [Domain-Aware Tensor Network Structure Search](https://mlsanity.com/paper/2505.23537/) (2025)
- [Intrinsically motivated graph exploration using network theories of human curiosity](https://mlsanity.com/paper/2307.04962/) (2023)
- [Sampling-Based Decomposition Algorithms for Arbitrary Tensor Networks](https://mlsanity.com/paper/2210.03828/) (2022)
- [Combining Local Symmetry Exploitation and Reinforcement Learning for Optimised Probabilistic Inference -- A Work In Progress](https://mlsanity.com/paper/2503.08786/) (2025)
- [Algorithmic algorithm development with LLMs: A Case Study on LLM-Usage for Contraction Order Optimization in Tensor Networks](https://mlsanity.com/paper/2606.01975/) (2026)

## Abstract (arXiv)

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 quantum circuit requires computing the contraction of a large network of tensors. The order (path) of contraction can have a drastic effect on the computing cost, but finding an efficient order is a challenging combinatorial optimization problem. We propose a Reinforcement Learning (RL) approach combined with Graph Neural Networks (GNN) to address the contraction ordering problem. The problem is extremely challenging due to the huge search space, the heavy-tailed reward distribution, and the challenging credit assignment. We show how a carefully implemented RL-agent that uses a GNN as the basic policy construct can address these challenges and obtain significant improvements over state-of-the-art techniques in three varieties of circuits, including the largest scale networks used in contemporary QC.