Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation

• URL: http://arxiv.org/abs/2004.10892v2
• Date: Fri, 1 May 2020 08:58:19 GMT
• Title: Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
• Authors: Roman Schutski, Dmitry Kolmakov, Taras Khakhulin, and Ivan Oseledets
• Abstract summary: We propose a parallel algorithm for the contraction of tensor networks using probabilistic models. We apply the resulting algorithm to the simulation of random quantum circuits.
• Score: 1.4416132811087747
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Tensor networks are the main building blocks in a wide variety of computational sciences, ranging from many-body theory and quantum computing to probability and machine learning. Here we propose a parallel algorithm for the contraction of tensor networks using probabilistic graphical models. Our approach is based on the heuristic solution of the $\mu$-treewidth deletion problem in graph theory. We apply the resulting algorithm to the simulation of random quantum circuits and discuss the extensions for general tensor network contractions.

Related papers

• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Circuit Simulation with Fast Tensor Decision Diagram [10.24745264727704]
  We present a novel open-source framework that harnesses tensor decision diagrams to eliminate overheads and achieve significant speedups. We introduce a new linear-complexity rank simplification algorithm, Tetris, and edge-centric data structures for tensor decision diagram operations.
  arXiv  Detail & Related papers  (2024-01-21T01:24:29Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions. The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix. We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
  arXiv  Detail & Related papers  (2023-04-12T18:10:47Z)
• Tensor Networks or Decision Diagrams? Guidelines for Classical Quantum Circuit Simulation [65.93830818469833]
  tensor networks and decision diagrams have independently been developed with differing perspectives, terminologies, and backgrounds in mind. We consider how these techniques approach classical quantum circuit simulation, and examine their (dis)similarities with regard to their most applicable abstraction level. We provide guidelines for when to better use tensor networks and when to better use decision diagrams in classical quantum circuit simulation.
  arXiv  Detail & Related papers  (2023-02-13T19:00:00Z)
• On the quantum simulation of complex networks [0.0]
  Continuous-time quantum walk algorithms assume that we can simulate the dynamics of quantum systems where the Hamiltonian is given by the adjacency matrix of the graph. We extend the state-of-the-art results on quantum simulation to graphs that contain a small number of hubs, but that are otherwise sparse.
  arXiv  Detail & Related papers  (2022-12-12T18:55:31Z)
• Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation [1.2704529528199062]
  One of the key problems in quantum circuit simulation is the construction of a contraction tree. We introduce a novel time algorithm for constructing an optimal contraction tree. We show that our method achieves superior results on a majority of tested quantum circuits.
  arXiv  Detail & Related papers  (2022-09-07T02:50:30Z)
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry [0.0]
  We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyper-optimization over the compression and contraction strategy itself to minimize error and cost.
  arXiv  Detail & Related papers  (2022-06-14T17:59:16Z)
• Optimizing Tensor Network Contraction Using Reinforcement Learning [86.05566365115729]
  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.
  arXiv  Detail & Related papers  (2022-04-18T21:45:13Z)
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams [72.03286471602073]
  We study the importance of the path that is chosen when simulating quantum circuits using decision diagrams. We propose an open-source framework that allows to investigate dedicated simulation paths.
  arXiv  Detail & Related papers  (2022-03-01T19:00:11Z)
• Simulation of Quantum Computing on Classical Supercomputers [23.350853237013578]
  We propose a scheme based on cutting edges of undirected graphs. This scheme cuts edges of undirected graphs with large tree width to obtain many undirected subgraphs. It can simulate 120-qubit 3-regular QAOA algorithm on 4096-core supercomputer.
  arXiv  Detail & Related papers  (2020-10-28T13:26:41Z)
• Efficient construction of tensor-network representations of many-body Gaussian states [59.94347858883343]
  We present a procedure to construct tensor-network representations of many-body Gaussian states efficiently and with a controllable error. These states include the ground and thermal states of bosonic and fermionic quadratic Hamiltonians, which are essential in the study of quantum many-body systems.
  arXiv  Detail & Related papers  (2020-08-12T11:30:23Z)

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.