Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation

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.

arXiv comment11 pages, 12 figures

References in corpus (8)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Simulating quantum computation by contracting tensor networks
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Tensor network states and geometry
• 64-Qubit Quantum Circuit Simulation
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Faster identification of optimal contraction sequences for tensor networks
• An adaptive algorithm for quantum circuit simulation

Cited by in corpus (9)

• Computational advantage of quantum random sampling
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Classical Simulation of Quantum Supremacy Circuits
• Tropical Tensor Network for Ground States of Spin Glasses
• Simulating the Sycamore quantum supremacy circuits
• Simulating the quantum Fourier transform, Grover's algorithm, and the quantum counting algorithm with limited entanglement using tensor-networks
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo
• State of practice: evaluating GPU performance of state vector and tensor network methods
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations