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 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.
