Simulation Paths for Quantum Circuit Simulation with Decision Diagrams

• URL: http://arxiv.org/abs/2203.00703v2
• Date: Tue, 6 Sep 2022 18:00:08 GMT
• Title: Simulation Paths for Quantum Circuit Simulation with Decision Diagrams
• Authors: Lukas Burgholzer, Alexander Ploier and Robert Wille
• Abstract summary: 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.
• Score: 72.03286471602073
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Simulating quantum circuits on classical computers is a notoriously hard, yet increasingly important task for the development and testing of quantum algorithms. In order to alleviate this inherent complexity, efficient data structures and methods such as tensor networks and decision diagrams have been proposed. However, their efficiency heavily depends on the order in which the individual computations are performed. For tensor networks the order is defined by so-called contraction plans and a plethora of methods has been developed to determine suitable plans. On the other hand, simulation based on decision diagrams is mostly conducted in a straight-forward, i.e., sequential, fashion thus far. In this work, we study the importance of the path that is chosen when simulating quantum circuits using decision diagrams and show, conceptually and experimentally, that choosing the right simulation path can make a vast difference in the efficiency of classical simulations using decision diagrams. We propose an open-source framework (available at github.com/cda-tum/ddsim) that not only allows to investigate dedicated simulation paths, but also to re-use existing findings, e.g., obtained from determining contraction plans for tensor networks. Experimental evaluations show that translating strategies from the domain of tensor networks may yield speedups of several factors compared to the state of the art. Furthermore, we design a dedicated simulation path heuristic that allows to improve the performance even further -- frequently yielding speedups of several orders of magnitude. Finally, we provide an extensive discussion on what can be learned from tensor networks and what cannot.

Related papers

• 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)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  We propose Grab-UCB, a graph- kernel multi-arms bandit algorithm to learn online the optimal source placement in large scale networks. We describe the network processes with an adaptive graph dictionary model, which typically leads to sparse spectral representations. We derive the performance guarantees that depend on network parameters, which further influence the learning curve of the sequential decision strategy.
  arXiv  Detail & Related papers  (2023-07-07T15:03:42Z)
• 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)
• 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)
• 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)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• 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)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19: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.