Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm

Abstract

Tensor network contractions are widely used in statistical physics, quantum computing, and computer science. We introduce a method to efficiently approximate tensor network contractions using low-rank approximations, where each intermediate tensor generated during the contractions is approximated as a low-rank binary tree tensor network. The proposed algorithm has the flexibility to incorporate a large portion of the environment when performing low-rank approximations, which can lead to high accuracy for a given rank. Here, the environment refers to the remaining set of tensors in the network, and low-rank approximations with larger environments can generally provide higher accuracy. For contracting tensor networks defined on lattices, the proposed algorithm can be viewed as a generalization of the standard boundary-based algorithms. In addition, the algorithm includes a cost-efficient density matrix algorithm for approximating a tensor network with a general graph structure into a tree structure, whose computational cost is asymptotically upper-bounded by that of the standard algorithm that uses canonicalization. Experimental results indicate that the proposed technique outperforms previously proposed approximate tensor network contraction algorithms for multiple problems in terms of both accuracy and efficiency.

References in corpus (41)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• The density-matrix renormalization group
• Efficient classical simulation of slightly entangled quantum computations
• A Practical Introduction to Tensor Networks: Matrix Product States and Projected Entangled Pair States
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Characterizing Quantum Supremacy in Near-Term Devices
• The ITensor Software Library for Tensor Network Calculations
• Time-evolution methods for matrix-product states
• Tensor renormalization group approach to 2D classical lattice models
• Classical simulation of quantum many-body systems with a tree tensor network
• Tensor networks for complex quantum systems
• Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
• Minimally Entangled Typical Thermal State Algorithms
• Tensor product methods and entanglement optimization for ab initio quantum chemistry
• Differentiable Programming Tensor Networks
• Algorithms for finite Projected Entangled Pair States
• What limits the simulation of quantum computers?
• Hyper-optimized tensor network contraction
• Efficient Tree Tensor Network States (TTNS) for Quantum Chemistry: Generalizations of the Density Matrix Renormalization Group Algorithm
• Unifying Projected Entangled Pair States contractions
• Compressing Graphs and Indexes with Recursive Graph Bisection
• Fork Tensor Product States - Efficient Three Orbital Real Time DMFT Solver
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Efficient Tensor Network ansatz for high-dimensional quantum many-body problems
• Tensor Network Contractions for #SAT
• Fast counting with tensor networks
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Tensor Networks contraction and the Belief Propagation algorithm
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• Comb tensor networks
• General tensor network decoding of 2D Pauli codes
• Adaptive-weighted tree tensor networks for disordered quantum many-body systems
• Simulating quantum circuits using tree tensor networks
• Understanding Generalization in Deep Learning via Tensor Methods
• Automatic Contraction of Unstructured Tensor Networks
• Efficient tensor network simulation of quantum many-body physics on sparse graphs
• Fast and Accurate Randomized Algorithms for Low-rank Tensor Decompositions
• On Stability of Tensor Networks and Canonical Forms
• Permutation Search of Tensor Network Structures via Local Sampling
• Cost-efficient Gaussian Tensor Network Embeddings for Tensor-structured Inputs

Cited by in corpus (2)

• Tensor networks for quantum computing
• Enhanced Krylov Methods for Molecular Hamiltonians: Reduced Memory Cost and Complexity Scaling via Tensor Hypercontraction