Benchmarking treewidth as a practical component of tensor-network--based quantum simulation

Abstract

Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms. The computational complexity of a tensor network simulation depends on the tensor ranks and the order in which they are contracted. Unfortunately, computing optimal contraction sequences (orderings) in general is known to be a computationally difficult (NP-complete) task. In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph, relating the contraction sequence problem to a rich literature in structural graph theory. While treewidth-based methods have largely been ignored in favor of dataset-specific algorithms in the prior tensor networks literature, we demonstrate their practical relevance for problems arising from two distinct methods used in quantum simulation: multi-scale entanglement renormalization ansatz (MERA) datasets and quantum circuits generated by the quantum approximate optimization algorithm (QAOA). We exhibit multiple regimes where treewidth-based algorithms outperform domain-specific algorithms, while demonstrating that the optimal choice of algorithm has a complex dependence on the network density, expected contraction complexity, and user run time requirements. We further provide an open source software framework designed with an emphasis on accessibility and extendability, enabling replicable experimental evaluations and future exploration of competing methods by practitioners.

Open source code available

References in corpus (24)

• Area laws for the entanglement entropy - a review
• Efficient classical simulation of slightly entangled quantum computations
• A Quantum Approximate Optimization Algorithm
• Characterizing Quantum Supremacy in Near-Term Devices
• Matrix Product Density Operators: Simulation of finite-T and dissipative systems
• A class of quantum many-body states that can be efficiently simulated
• Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
• Classifying quantum phases using Matrix Product States and PEPS
• Simulating quantum computation by contracting tensor networks
• Algorithms for entanglement renormalization
• A positive tensor network approach for simulating open quantum many-body systems
• Tensor networks for Lattice Gauge Theories and Atomic Quantum Simulation
• LIQUi|>: A Software Design Architecture and Domain-Specific Language for Quantum Computing
• Tensor Networks in a Nutshell
• Tensor-Network Simulations of the Surface Code under Realistic Noise
• Tensor Networks and Quantum Error Correction
• Faster identification of optimal contraction sequences for tensor networks
• qTorch: The Quantum Tensor Contraction Handler
• Tensor Network Contractions for #SAT
• Optimising Matrix Product State Simulations of Shor's Algorithm
• Improving the efficiency of variational tensor network algorithms
• NCON: A tensor network contractor for MATLAB
• A tree tensor network approach to simulating Shor's algorithm
• Computing Treewidth on the GPU

Cited by in corpus (11)

• Hyper-optimized tensor network contraction
• Application of Quantum Annealing to Nurse Scheduling Problem
• Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
• Tropical Tensor Network for Ground States of Spin Glasses
• An entanglement perspective on the quantum approximate optimization algorithm
• Calibrating the Classical Hardness of the Quantum Approximate Optimization Algorithm
• Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
• Algorithms for Tensor Network Contraction Ordering
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• Survey on Computational Applications of Tensor Network Simulations
• Carving-width and contraction trees for tensor networks