Optimizing Tensor Network Contraction Using Reinforcement Learning
- URL: http://arxiv.org/abs/2204.09052v1
- Date: Mon, 18 Apr 2022 21:45:13 GMT
- Title: Optimizing Tensor Network Contraction Using Reinforcement Learning
- Authors: Eli A. Meirom, Haggai Maron, Shie Mannor, Gal Chechik
- Abstract summary: 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.
- Score: 86.05566365115729
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
Related papers
- Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems.
This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization.
We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
arXiv Detail & Related papers (2024-07-08T22:02:39Z) - Tensor Quantum Programming [0.0]
We develop an algorithm that encodes Matrix Product Operators into quantum circuits with a depth that depends linearly on the number of qubits.
It demonstrates effectiveness on up to 50 qubits for several frequently encountered in differential equations, optimization problems, and quantum chemistry.
arXiv Detail & Related papers (2024-03-20T10:44:00Z) - Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem.
The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
arXiv Detail & Related papers (2023-04-18T11:57:15Z) - The Basis of Design Tools for Quantum Computing: Arrays, Decision
Diagrams, Tensor Networks, and ZX-Calculus [55.58528469973086]
Quantum computers promise to efficiently solve important problems classical computers never will.
A fully automated quantum software stack needs to be developed.
This work provides a look "under the hood" of today's tools and showcases how these means are utilized in them, e.g., for simulation, compilation, and verification of quantum circuits.
arXiv Detail & Related papers (2023-01-10T19:00:00Z) - Decoding surface codes with deep reinforcement learning and
probabilistic policy reuse [0.5999777817331317]
Current quantum hardware, also known as noisy intermediate-scale quantum computers (NISQ), are still unable to carry out computations faithfully.
Recent developments of machine learning (ML)-based techniques especially the reinforcement learning (RL) methods have been applied to the decoding problem.
We propose a continual reinforcement learning method to address these decoding challenges.
arXiv Detail & Related papers (2022-12-22T17:24:32Z) - Reservoir Computing via Quantum Recurrent Neural Networks [0.5999777817331317]
Existing VQC or QNN-based methods require significant computational resources to perform gradient-based optimization of quantum circuit parameters.
In this work, we approach sequential modeling by applying a reservoir computing (RC) framework to quantum recurrent neural networks (QRNN-RC)
Our numerical simulations show that the QRNN-RC can reach results comparable to fully trained QRNN models for several function approximation and time series tasks.
arXiv Detail & Related papers (2022-11-04T17:30:46Z) - Accelerating the training of single-layer binary neural networks using
the HHL quantum algorithm [58.720142291102135]
We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL)
This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
arXiv Detail & Related papers (2022-10-23T11:58:05Z) - Quantum Architecture Search via Continual Reinforcement Learning [0.0]
This paper proposes a machine learning-based method to construct quantum circuit architectures.
We present the Probabilistic Policy Reuse with deep Q-learning (PPR-DQL) framework to tackle this circuit design challenge.
arXiv Detail & Related papers (2021-12-10T19:07:56Z) - An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian
Simulation [55.41644538483948]
Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates.
We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions.
The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
arXiv Detail & Related papers (2021-08-06T19:38:03Z) - Space-efficient binary optimization for variational computing [68.8204255655161]
We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem.
We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
arXiv Detail & Related papers (2020-09-15T18:17:27Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.