Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation

• URL: http://arxiv.org/abs/2209.02895v1
• Date: Wed, 7 Sep 2022 02:50:30 GMT
• Title: Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation
• Authors: Cameron Ibrahim, Danylo Lykov, Zichang He, Yuri Alexeev, Ilya Safro
• Abstract summary: 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.
• Score: 1.2704529528199062
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: One of the key problems in tensor network based quantum circuit simulation is the construction of a contraction tree which minimizes the cost of the simulation, where the cost can be expressed in the number of operations as a proxy for the simulation running time. This same problem arises in a variety of application areas, such as combinatorial scientific computing, marginalization in probabilistic graphical models, and solving constraint satisfaction problems. In this paper, we reduce the computationally hard portion of this problem to one of graph linear ordering, and demonstrate how existing approaches in this area can be utilized to achieve results up to several orders of magnitude better than existing state of the art methods for the same running time. To do so, we introduce a novel polynomial time algorithm for constructing an optimal contraction tree from a given order. Furthermore, we introduce a fast and high quality linear ordering solver, and demonstrate its applicability as a heuristic for providing orderings for contraction trees. Finally, we compare our solver with competing methods for constructing contraction trees in quantum circuit simulation on a collection of randomly generated Quantum Approximate Optimization Algorithm Max Cut circuits and show that our method achieves superior results on a majority of tested quantum circuits. Reproducibility: Our source code and data are available at https://github.com/cameton/HPEC2022_ContractionTrees.

Related papers

• Fast classical simulation of quantum circuits via parametric rewriting in the ZX-calculus [0.0]
  We show that it is possible to perform the final stage of classical simulation quickly utilising a high degree of GPU parallelism. We demonstrate speedups upwards of 100x for certain classical simulation tasks vs. the non-parametric approach.
  arXiv  Detail & Related papers  (2024-03-11T14:44:59Z)
• Hybrid discrete-continuous compilation of trapped-ion quantum circuits with deep reinforcement learning [1.7087507417780985]
  We show that we can significantly reduce the size of relevant quantum circuits for trapped-ion computing. Our framework can also be applied to an experimental setup whose goal is to reproduce an unknown unitary process.
  arXiv  Detail & Related papers  (2023-07-12T14:55:28Z)
• 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)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• 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)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• 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)
• Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation [1.4416132811087747]
  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.
  arXiv  Detail & Related papers  (2020-04-22T23:00:42Z)
• Hyper-optimized tensor network contraction [0.0]
  We implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems.
  arXiv  Detail & Related papers  (2020-02-05T19:00:00Z)

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.