Timezone: »

Optimizing Tensor Network Contraction Using Reinforcement Learning
eli meirom · Haggai Maron · Shie Mannor · Gal Chechik

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 enormous 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 improvement over state-of-the-art techniques in three varieties of circuits, including the largest scale networks used in contemporary QC.

Author Information

eli meirom (NVIDIA)
Haggai Maron (NVIDIA Research)

I am a Research Scientist at NVIDIA Research. My main fields of interest are machine learning, optimization, and shape analysis. More specifically, I am working on applying deep learning to irregular domains (e.g., graphs, point clouds, and surfaces) and graph/shape matching problems. I completed my Ph.D. in 2019 at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman.

Shie Mannor (Technion)
Gal Chechik (NVIDIA / Bar-Ilan University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors