Timezone: »
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.
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)
-
2022 Poster: Optimizing Tensor Network Contraction Using Reinforcement Learning »
Wed. Jul 20th through Thu the 21st Room Hall E #826
More from the Same Authors
-
2022 : P20: Learning to Reason about and to Act on Cascading Events »
Eli Meirom -
2023 Poster: Auxiliary Learning as an Asymmetric Bargaining Game »
Aviv Shamsian · Aviv Navon · Neta Glazer · Kenji Kawaguchi · Gal Chechik · Ethan Fetaya -
2023 Poster: Representation-Driven Reinforcement Learning »
Ofir Nabati · Guy Tennenholtz · Shie Mannor -
2023 Poster: Learning to Initiate and Reason in Event-Driven Cascading Processes »
Yuval Atzmon · Eli Meirom · Shie Mannor · Gal Chechik -
2023 Poster: Equivariant Polynomials for Graph Neural Networks »
Omri Puny · Derek Lim · Bobak T Kiani · Haggai Maron · Yaron Lipman -
2023 Poster: Equivariant Architectures for Learning in Deep Weight Spaces »
Aviv Navon · Aviv Shamsian · Idan Achituve · Ethan Fetaya · Gal Chechik · Haggai Maron -
2023 Poster: PPG Reloaded: An Empirical Study on What Matters in Phasic Policy Gradient »
Kaixin Wang · Zhou Daquan · Jiashi Feng · Shie Mannor -
2023 Poster: Learning Hidden Markov Models When the Locations of Missing Observations are Unknown »
BINYAMIN PERETS · Mark Kozdoba · Shie Mannor -
2023 Poster: Reward-Mixing MDPs with Few Contexts are Learnable »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2023 Poster: Graph Positional Encoding via Random Feature Propagation »
Moshe Eliasof · Fabrizio Frasca · Beatrice Bevilacqua · Eran Treister · Gal Chechik · Haggai Maron -
2023 Oral: Equivariant Polynomials for Graph Neural Networks »
Omri Puny · Derek Lim · Bobak T Kiani · Haggai Maron · Yaron Lipman -
2023 Oral: Equivariant Architectures for Learning in Deep Weight Spaces »
Aviv Navon · Aviv Shamsian · Idan Achituve · Ethan Fetaya · Gal Chechik · Haggai Maron -
2022 Poster: Actor-Critic based Improper Reinforcement Learning »
Mohammadi Zaki · Avi Mohan · Aditya Gopalan · Shie Mannor -
2022 Poster: The Geometry of Robust Value Functions »
Kaixin Wang · Navdeep Kumar · Kuangqi Zhou · Bryan Hooi · Jiashi Feng · Shie Mannor -
2022 Spotlight: The Geometry of Robust Value Functions »
Kaixin Wang · Navdeep Kumar · Kuangqi Zhou · Bryan Hooi · Jiashi Feng · Shie Mannor -
2022 Spotlight: Actor-Critic based Improper Reinforcement Learning »
Mohammadi Zaki · Avi Mohan · Aditya Gopalan · Shie Mannor -
2022 Poster: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Poster: Multi-Task Learning as a Bargaining Game »
Aviv Navon · Aviv Shamsian · Idan Achituve · Haggai Maron · Kenji Kawaguchi · Gal Chechik · Ethan Fetaya -
2022 Spotlight: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms »
Jeongyeol Kwon · Yonathan Efroni · Constantine Caramanis · Shie Mannor -
2022 Spotlight: Multi-Task Learning as a Bargaining Game »
Aviv Navon · Aviv Shamsian · Idan Achituve · Haggai Maron · Kenji Kawaguchi · Gal Chechik · Ethan Fetaya -
2021 : Invited Speaker: Shie Mannor: Lenient Regret »
Shie Mannor -
2021 Poster: GP-Tree: A Gaussian Process Classifier for Few-Shot Incremental Learning »
Idan Achituve · Aviv Navon · Yochai Yemini · Gal Chechik · Ethan Fetaya -
2021 Spotlight: GP-Tree: A Gaussian Process Classifier for Few-Shot Incremental Learning »
Idan Achituve · Aviv Navon · Yochai Yemini · Gal Chechik · Ethan Fetaya -
2021 Poster: Personalized Federated Learning using Hypernetworks »
Aviv Shamsian · Aviv Navon · Ethan Fetaya · Gal Chechik -
2021 Spotlight: Personalized Federated Learning using Hypernetworks »
Aviv Shamsian · Aviv Navon · Ethan Fetaya · Gal Chechik -
2021 Poster: Compositional Video Synthesis with Action Graphs »
Amir Bar · Roi Herzig · Xiaolong Wang · Anna Rohrbach · Gal Chechik · Trevor Darrell · Amir Globerson -
2021 Spotlight: Compositional Video Synthesis with Action Graphs »
Amir Bar · Roi Herzig · Xiaolong Wang · Anna Rohrbach · Gal Chechik · Trevor Darrell · Amir Globerson -
2021 Poster: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2021 Poster: From Local Structures to Size Generalization in Graph Neural Networks »
Gilad Yehudai · Ethan Fetaya · Eli Meirom · Gal Chechik · Haggai Maron -
2021 Spotlight: Controlling Graph Dynamics with Reinforcement Learning and Graph Neural Networks »
Eli Meirom · Haggai Maron · Shie Mannor · Gal Chechik -
2021 Spotlight: From Local Structures to Size Generalization in Graph Neural Networks »
Gilad Yehudai · Ethan Fetaya · Eli Meirom · Gal Chechik · Haggai Maron -
2020 Poster: On Learning Sets of Symmetric Elements »
Haggai Maron · Or Litany · Gal Chechik · Ethan Fetaya -
2020 Poster: Learning Algebraic Multigrid Using Graph Neural Networks »
Ilay Luz · Meirav Galun · Haggai Maron · Ronen Basri · Irad Yavneh -
2018 Poster: Beyond the One-Step Greedy Approach in Reinforcement Learning »
Yonathan Efroni · Gal Dalal · Bruno Scherrer · Shie Mannor -
2018 Oral: Beyond the One-Step Greedy Approach in Reinforcement Learning »
Yonathan Efroni · Gal Dalal · Bruno Scherrer · Shie Mannor -
2017 Workshop: Lifelong Learning: A Reinforcement Learning Approach »
Sarath Chandar · Balaraman Ravindran · Daniel J. Mankowitz · Shie Mannor · Tom Zahavy -
2017 Poster: Consistent On-Line Off-Policy Evaluation »
Assaf Hallak · Shie Mannor -
2017 Talk: Consistent On-Line Off-Policy Evaluation »
Assaf Hallak · Shie Mannor -
2017 Poster: End-to-End Differentiable Adversarial Imitation Learning »
Nir Baram · Oron Anschel · Itai Caspi · Shie Mannor -
2017 Talk: End-to-End Differentiable Adversarial Imitation Learning »
Nir Baram · Oron Anschel · Itai Caspi · Shie Mannor