Optimizing Tensor Network Contraction Using Reinforcement Learning

Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik

Hall E #826

Keywords: [ APP: Physics ] [ DL: Graph Neural Networks ] [ OPT: Learning for Optimization ] [ RL: Deep RL ]

[ Abstract ]
[ Poster [ Paper PDF
Wed 20 Jul 3:30 p.m. PDT — 5:30 p.m. PDT
Spotlight presentation: Reinforcement Learning: Deep RL
Wed 20 Jul 7:30 a.m. PDT — 9 a.m. PDT


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.

Chat is not available.