Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations

Abstract

We present a general method for approximately contracting tensor networks with an arbitrary connectivity. This enables us to release the computational power of tensor networks to wide use in inference and learning problems defined on general graphs. We show applications of our algorithm in graphical models, specifically on estimating free energy of spin glasses defined on various of graphs, where our method largely outperforms existing algorithms including the mean-field methods and the recently proposed neural-network-based methods. We further apply our method to the simulation of random quantum circuits, and demonstrate that, with a trade off of negligible truncation errors, our method is able to simulate large quantum circuits that are out of reach of the state-of-the-art simulation methods.

arXiv comment14 pages, 13 figures

References in corpus (37)

• Adam: A Method for Stochastic Optimization
• Auto-Encoding Variational Bayes
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group in the age of matrix product states
• An efficient, multiple range random walk algorithm to calculate the density of states
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• A Quantum Approximate Optimization Algorithm
• Efficient simulation of one-dimensional quantum many-body systems
• Pixel Recurrent Neural Networks
• NICE: Non-linear Independent Components Estimation
• Variational Inference with Normalizing Flows
• Characterizing Quantum Supremacy in Near-Term Devices
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• Density estimation using Real NVP
• Tensor renormalization group approach to 2D classical lattice models
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• The iTEBD algorithm beyond unitary evolution
• Simulating quantum computation by contracting tensor networks
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Coarse-graining renormalization by higher-order singular value decomposition
• Unsupervised Generative Modeling Using Matrix Product States
• Second Renormalization of Tensor-Network States
• Differentiable Programming Tensor Networks
• Solving Statistical Mechanics Using Variational Autoregressive Networks
• Efficient classical simulation of random shallow 2D quantum circuits
• Tree Tensor Networks for Generative Modeling
• Anisotropic Tensor Renormalization Group
• Classical Simulation of Quantum Supremacy Circuits
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Simulation of low-depth quantum circuits as complex undirected graphical models
• Classical Simulation of Intermediate-Size Quantum Circuits
• Fast counting with tensor networks
• An adaptive algorithm for quantum circuit simulation
• Compressing deep neural networks by matrix product operators
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Solving Statistical Mechanics on Sparse Graphs with Feedback Set Variational Autoregressive Networks
• Automatic Contraction of Unstructured Tensor Networks

Cited by in corpus (37)

• The ITensor Software Library for Tensor Network Calculations
• What limits the simulation of quantum computers?
• Efficient classical simulation of random shallow 2D quantum circuits
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
• Tropical Tensor Network for Ground States of Spin Glasses
• Riemannian geometry and automatic differentiation for optimization problems of quantum physics and quantum technologies
• Simulating the Sycamore quantum supremacy circuits
• Accurate simulation for finite projected entangled pair states in two dimensions
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Tensor networks for unsupervised machine learning
• From Tensor Network Quantum States to Tensorial Recurrent Neural Networks
• Gauging tensor networks with belief propagation
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• How to simulate quantum measurement without computing marginals
• Fast Simulation of High-Depth QAOA Circuits
• Simulating quantum circuits using tree tensor networks
• Tensor networks for quantum computing
• Boltzmann machines as two-dimensional tensor networks
• Simulation of quantum optics by coherent state decomposition
• Optimization schemes for unitary tensor-network circuit
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
• Collective Monte Carlo updates through tensor network renormalization
• Identification of topological phases using classically-optimized variational quantum eigensolver
• Qsun: an open-source platform towards practical quantum machine learning applications
• The resource theory of tensor networks
• Fermionic tensor network contraction for arbitrary geometries
• Improved real-space parallelizable matrix-product state compression and its application to unitary quantum dynamics simulation
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Scalable projected entangled-pair state representation of random quantum circuit states
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Reducing Computational Complexity of Tensor Contractions via Tensor-Train Networks
• Who can compete with quantum computers? Lecture notes on quantum inspired tensor networks computational techniques
• Integrating Neural Networks and Tensor Networks for Computing Free Energy