Quantum Circuit Simulation with Fast Tensor Decision Diagram
- URL: http://arxiv.org/abs/2401.11362v1
- Date: Sun, 21 Jan 2024 01:24:29 GMT
- Title: Quantum Circuit Simulation with Fast Tensor Decision Diagram
- Authors: Qirui Zhang, Mehdi Saligane, Hun-Seok Kim, David Blaauw, Georgios
Tzimpragos and Dennis Sylvester
- Abstract summary: 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.
- Score: 10.24745264727704
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Quantum circuit simulation is a challenging computational problem crucial for
quantum computing research and development. The predominant approaches in this
area center on tensor networks, prized for their better concurrency and less
computation than methods using full quantum vectors and matrices. However, even
with the advantages, array-based tensors can have significant redundancy. We
present a novel open-source framework that harnesses tensor decision diagrams
to eliminate overheads and achieve significant speedups over prior approaches.
On average, it delivers a speedup of 37$\times$ over Google's TensorNetwork
library on redundancy-rich circuits, and 25$\times$ and 144$\times$ over
quantum multi-valued decision diagram and prior tensor decision diagram
implementation, respectively, on Google random quantum circuits. To achieve
this, we introduce a new linear-complexity rank simplification algorithm,
Tetris, and edge-centric data structures for recursive tensor decision diagram
operations. Additionally, we explore the efficacy of tensor network contraction
ordering and optimizations from binary decision diagrams.
Related papers
- Limitations of tensor network approaches for optimization and sampling: A comparison against quantum and classical Ising machines [0.0]
We develop an algorithm to reveal the low-energy spectrum of Ising spin-glass systems with interaction graphs.
Our deterministic approach combines a branch-and-bound search strategy with an approximate calculation of marginals.
We benchmark our approach on random problems defined on Pegasus and Zephyr graphs with up to a few thousand spins.
arXiv Detail & Related papers (2024-11-25T14:35:14Z) - 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) - 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) - 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) - 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) - A quantum algorithm for training wide and deep classical neural networks [72.2614468437919]
We show that conditions amenable to classical trainability via gradient descent coincide with those necessary for efficiently solving quantum linear systems.
We numerically demonstrate that the MNIST image dataset satisfies such conditions.
We provide empirical evidence for $O(log n)$ training of a convolutional neural network with pooling.
arXiv Detail & Related papers (2021-07-19T23:41:03Z) - 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) - Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor
Network States Algorithm [0.0]
Algorithm is up to $2$ orders of magnitudes faster than Sch$ddottexto$dinger-Feynman algorithm.
We simulate larger random quantum circuits up to $104$ qubits, showing that this algorithm is an ideal tool to verify relatively shallow quantum circuits on near-term quantum computers.
arXiv Detail & Related papers (2020-11-05T02:20:56Z) - 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)
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.