Hyper-optimized tensor network contraction

Abstract

Tensor networks represent the state-of-the-art in computational methods across many disciplines, including the classical simulation of quantum many-body systems and quantum circuits. Several applications of current interest give rise to tensor networks with irregular geometries. Finding the best possible contraction path for such networks is a central problem, with an exponential effect on computation time and memory footprint. In this work, we implement new randomized protocols that find very high quality contraction paths for arbitrary and large tensor networks. We test our methods on a variety of benchmarks, including the random quantum circuit instances recently implemented on Google quantum chips. We find that the paths obtained can be very close to optimal, and often many orders or magnitude better than the most established approaches. As different underlying geometries suit different methods, we also introduce a hyper-optimization approach, where both the method applied and its algorithmic parameters are tuned during the path finding. The increase in quality of contraction schemes found has significant practical implications for the simulation of quantum many-body systems and particularly for the benchmarking of new quantum chips. Concretely, we estimate a speed-up of over 10,000$\times$ compared to the original expectation for the classical simulation of the Sycamore `supremacy' circuits.

arXiv comment22 pages, 10 figures

References in corpus (42)

• Community structure in social and biological networks
• Community detection in graphs
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• 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
• Universal Linear Optics
• Tensor-Entanglement-Filtering Renormalization Approach and Symmetry Protected Topological Order
• Tensor renormalization group approach to 2D classical lattice models
• Classical simulation of quantum many-body systems with a tree tensor network
• Accurate determination of tensor network state of quantum lattice models in two dimensions
• Simulating quantum computation by contracting tensor networks
• Low-Rank Tensor Networks for Dimensionality Reduction and Large-Scale Optimization Problems: Perspectives and Challenges PART 1
• Quantum Simulation of Electronic Structure with Linear Depth and Connectivity
• Hand-waving and Interpretive Dance: An Introductory Course on Tensor Networks
• Coarse-graining renormalization by higher-order singular value decomposition
• Tensor Network Renormalization
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Tensor Networks for Dimensionality Reduction and Large-Scale Optimizations. Part 2 Applications and Future Perspectives
• Efficient Algorithms for Maximum Likelihood Decoding in the Surface Code
• Entanglement renormalization and topological order
• Loop optimization for tensor network renormalization
• A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
• Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
• Learning Relevant Features of Data with Multi-scale Tensor Networks
• Algorithms for tensor network renormalization
• On the hardness of classically simulating the one clean qubit model
• Exact entanglement renormalization for string-net models
• Probabilistic Planning via Heuristic Forward Search and Weighted Model Counting
• Tensor Networks and Quantum Error Correction
• General-purpose quantum circuit simulator with Projected Entangled-Pair States and the quantum supremacy frontier
• Faster identification of optimal contraction sequences for tensor networks
• Renormalization group flows of Hamiltonians using tensor networks
• qTorch: The Quantum Tensor Contraction Handler
• Fast counting with tensor networks
• Tensor network algorithm by coarse-graining tensor renormalization on finite periodic lattices
• Algebraically contractible topological tensor network states
• Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
• Constant-degree graph expansions that preserve the treewidth
• Evaluating the Jones polynomial with tensor networks
• Parameterization of tensor network contraction

Cited by in corpus (97)

• Strong quantum computational advantage using a superconducting quantum processor
• The ITensor Software Library for Tensor Network Calculations
• Phase-Programmable Gaussian Boson Sampling Using Stimulated Squeezed Light
• Information Scrambling in Computationally Complex Quantum Circuits
• Computational advantage of quantum random sampling
• Solving the sampling problem of the Sycamore quantum circuits
• Tensor Network Algorithms: a Route Map
• TensorCircuit: a Quantum Software Framework for the NISQ Era
• Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
• Quantum Computational Advantage via High-Dimensional Gaussian Boson Sampling
• Phase transition in Random Circuit Sampling
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• The Variational Power of Quantum Circuit Tensor Networks
• Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
• A polynomial-time classical algorithm for noisy random circuit sampling
• Fast quantum circuit cutting with randomized measurements
• NISQ Computers: A Path to Quantum Supremacy
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Boundaries of quantum supremacy via random circuit sampling
• Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
• Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
• Quantum Machine Learning in Drug Discovery: Applications in Academia and Pharmaceutical Industries
• Quantum-Informed Recursive Optimization Algorithms
• Absence of barren plateaus in finite local-depth circuits with long-range entanglement
• Sublinear scaling in non-Markovian open quantum systems simulations
• Computing solution space properties of combinatorial optimization problems via generic tensor networks
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
• Gauging tensor networks with belief propagation
• The computational power of random quantum circuits in arbitrary geometries
• Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
• How to simulate quantum measurement without computing marginals
• The Fermionic Quantum Emulator
• Fast Simulation of High-Depth QAOA Circuits
• Interactive Protocols for Classically-Verifiable Quantum Advantage
• Tensor networks for interpretable and efficient quantum-inspired machine learning
• Simulating quantum circuits using tree tensor networks
• Real-time operator evolution in two and three dimensions via sparse Pauli dynamics
• Tensor networks for quantum computing
• Opening the Black Box Inside Grover's Algorithm
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Simulation Paths for Quantum Circuit Simulation with Decision Diagrams
• Optimization schemes for unitary tensor-network circuit
• Simulation of quantum optics by coherent state decomposition
• Validating quantum-supremacy experiments with exact and fast tensor network contraction
• Fast Evaluation of Finite Element Weak Forms Using Python Tensor Contraction Packages
• Quantum Computing and Tensor Networks for Laminate Design: A Novel Approach to Stacking Sequence Retrieval
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• Lifetime-based Optimization for Simulating Quantum Circuits on a New Sunway Supercomputer
• Quantum simulation using noisy unitary circuits and measurements
• Protocols for classically training quantum generative models on probability distributions
• NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
• Entanglement distillation toward minimal bond cut surface in tensor networks
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Simulation of Quantum Computers: Review and Acceleration Opportunities
• Entanglement entropy scaling of noisy random quantum circuits in two dimensions
• Near-Term Spin-Qubit Architecture Design via Multipartite Maximally-Entangled States
• Dynamics of disordered quantum systems with two- and three-dimensional tensor networks
• Simulating Quantum Computations with Tutte Polynomials
• Fermionic tensor network contraction for arbitrary geometries
• The resource theory of tensor networks
• Picturing Counting Reductions with the ZH-Calculus
• Probabilistic Inference in the Era of Tensor Networks and Differential Programming
• RosneT: A Block Tensor Algebra Library for Out-of-Core Quantum Computing Simulation
• Improved real-space parallelizable matrix-product state compression and its application to unitary quantum dynamics simulation
• Quantum Circuit Simulation with Fast Tensor Decision Diagram
• Survey on Computational Applications of Tensor Network Simulations
• TensorKrowch: Smooth integration of tensor networks in machine learning
• Hyperoptimized approximate contraction of tensor networks for rugged-energy-landscape spin glasses on periodic square and cubic lattices
• Efficient and systematic calculation of arbitrary observables for the matrix product state excitation ansatz
• Efficient Optimization of Variational Autoregressive Networks with Natural Gradient
• Simulating quantum circuits using the multi-scale entanglement renormalization ansatz
• HybridQ: A Hybrid Simulator for Quantum Circuits
• Equivalence checking of quantum circuits via intermediary matrix product operator
• Scaling of contraction costs for entanglement renormalization algorithms including tensor Trotterization and variational Monte Carlo
• Tensor Decompositions and Adiabatic Quantum Computing for Discovering Practical Matrix Multiplication Algorithms
• SuperGrad: a differentiable simulator for superconducting processors
• Approximate Contraction of Arbitrary Tensor Networks with a Flexible and Efficient Density Matrix Algorithm
• Scalable projected entangled-pair state representation of random quantum circuit states
• Tensor networks for $p$-spin models
• Exploring the Nexus between Thermodynamic Phase Transitions and Geometric Fractals through Systematic Lattice Point Classification
• Analog simulation of noisy quantum circuits
• On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
• Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
• Analysis of Quantum Image Representations for Supervised Classification
• The Software Landscape for the Density Matrix Renormalization Group
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• State of practice: evaluating GPU performance of state vector and tensor network methods
• NordIQuEst: the Nordic-Estonian Quantum Computing e-Infrastructure Quest
• Implementation of Tensor Network Simulation TN-Sim under NWQ-Sim
• Integrating Neural Networks and Tensor Networks for Computing Free Energy
• End-to-End Quantum Algorithms for the Jones Polynomial
• Dynamical cluster-based strategy for improving tensor network algorithms in quantum circuit simulations
• Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits
• Counting with the quantum alternating operator ansatz
• Tensor Network Loop Cluster Expansions for Quantum Many-Body Problems
• Pilot-Wave Simulator: Exact Classical Sampling from Ideal and Noisy Quantum Circuits up to Hundreds of Qubits