Hyper-optimized approximate contraction of tensor networks with arbitrary geometry

Abstract

Tensor network contraction is central to problems ranging from many-body physics to computer science. We describe how to approximate tensor network contraction through bond compression on arbitrary graphs. In particular, we introduce a hyper-optimization over the compression and contraction strategy itself to minimize error and cost. We demonstrate that our protocol outperforms both hand-crafted contraction strategies in the literature as well as recently proposed general contraction algorithms on a variety of synthetic and physical problems on regular lattices and random regular graphs. We further showcase the power of the approach by demonstrating approximate contraction of tensor networks for frustrated three-dimensional lattice partition functions, dimer counting on random regular graphs, and to access the hardness transition of random tensor network models, in graphs with many thousands of tensors.

arXiv comment33 pages, 26 figures, including SI

References in corpus (47)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Matrix Product States, Projected Entangled Pair States, and variational renormalization group methods for quantum spin systems
• Classical simulation of infinite-size quantum lattice systems in one spatial dimension
• Tensor renormalization group approach to 2D classical lattice models
• Tensor networks for complex quantum systems
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• Competing states in the t-J model: uniform d-wave state versus stripe state
• Simulating quantum computation by contracting tensor networks
• Corner Transfer Matrix Renormalization Group Method
• Coarse-graining renormalization by higher-order singular value decomposition
• Simulation of two dimensional quantum systems on an infinite lattice revisited: corner transfer matrix for tensor contraction
• Studying Two Dimensional Systems With the Density Matrix Renormalization Group
• Tensor Network Renormalization
• The computational complexity of PEPS
• Variational study of hard-core bosons in a 2-D optical lattice using Projected Entangled Pair States (PEPS)
• Second Renormalization of Tensor-Network States
• The XZZX Surface Code
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Corner Transfer Matrix Algorithm for Classical Renormalization Group
• Hyper-optimized tensor network contraction
• Loop optimization for tensor network renormalization
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Tailoring surface codes for highly biased noise
• Renormalization of tensor networks using graph independent local truncations
• Coarse graining methods for spin net and spin foam models
• Statistical mechanical models for quantum codes with correlated noise
• Tensor Networks and Quantum Error Correction
• Gauge fixing, canonical forms and optimal truncations in tensor networks with closed loops
• Renormalization group flows of Hamiltonians using tensor networks
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Residual entropies for three-dimensional frustrated spin systems with tensor networks
• Constraint satisfaction problems with isolated solutions are hard
• Tropical Tensor Network for Ground States of Spin Glasses
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Tensor Network Contractions for #SAT
• Simulation of three-dimensional quantum systems with projected entangled-pair states
• Fast counting with tensor networks
• Tensor network algorithm by coarse-graining tensor renormalization on finite periodic lattices
• Grammar-aware sentence classification on quantum computers
• Entanglement and the Sign Structure of Quantum States
• Boundary Tensor Renormalization Group
• Tensor-network codes
• Modeling Sequences with Quantum States: A Look Under the Hood
• Language Design as Information Renormalization
• Tensor Network Rewriting Strategies for Satisfiability and Counting
• Automatic Contraction of Unstructured Tensor Networks
• Large-scale calculation of ferromagnetic spin systems on the pyrochlore lattice

Cited by in corpus (20)

• The computational power of random quantum circuits in arbitrary geometries
• Real-time operator evolution in two and three dimensions via sparse Pauli dynamics
• Accurate Simulation of the Hubbard Model with Finite Fermionic Projected Entangled Pair States
• Sign problem in tensor network contraction
• Tensor Network Computations That Capture Strict Variationality, Volume Law Behavior, and the Efficient Representation of Neural Network States
• Near-Term Spin-Qubit Architecture Design via Multipartite Maximally-Entangled States
• The resource theory of tensor networks
• Limitations of tensor network approaches for optimization and sampling: A comparison to quantum and classical Ising machines
• Fermionic tensor network contraction for arbitrary geometries
• Improved real-space parallelizable matrix-product state compression and its application to unitary quantum dynamics simulation
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Positive bias makes tensor-network contraction tractable
• Tensor networks for $p$-spin models
• Neuralized Fermionic Tensor Networks for Quantum Many-Body Systems
• Quantum Encoding of Structured Data with Matrix Product States
• Tensor Network Loop Cluster Expansions for Quantum Many-Body Problems
• Implementation of Tensor Network Simulation TN-Sim under NWQ-Sim
• Hierarchical Search of Tree Tensor Networks for High-Dimensional Data
• Classical Neural Networks on Quantum Devices via Tensor Network Disentanglers: A Case Study in Image Classification