Simulating Quantum Computation by Contracting Tensor Networks

2005/11/30 by Igor L. Markov, Yaoyun Shi · 496 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Combinatorics #Complexity and Algorithms in Graphs #Computation #Computer science #Degree (music) #Discrete mathematics #Graph #Line graph #Mathematics #Pathwidth #Physics #Quantum #Quantum Computing Algorithms and Architecture #Quantum circuit #Quantum computer #Quantum mechanics #Quantum network #Qubit #Stochastic Gradient Optimization Techniques #Tree-depth #Treewidth #quant-ph

paper · pdf · doi:10.1137/050644756

published in SIAM Journal on Computing 38(3), 963-981 (Society for Industrial and Applied Mathematics) · 7 figures

openalex publication_date 2008/01/01 · arxiv created 2009/07/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

The treewidth of a graph is a useful combinatorial measure of how close the graph is to a tree. We prove that a quantum circuit with T gates whose underlying graph has a treewidth d can be simulated deterministically in T^O(1)exp[O(d)] time, which, in particular, is polynomial in T if d=O(log T). Among many implications, we show efficient simulations for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also show that one-way quantum computation of Raussendorf and Briegel (Phys. Rev. Lett., 86 (2001), pp. 5188–5191), a universal quantum computation scheme with promising physical implementations, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph with a constant maximum degree. (The requirement on the maximum degree was removed in [I. L. Markov and Y. Shi, preprint:quant-ph/0511069].)

Cited by

• phase2: full-state vector simulation of quantum time evolution at scale
• Stochastic Pauli-path simulator for large-scale quantum optimization
• Matrix product state approach to lossy boson sampling and noisy IQP sampling
• Variance-Reduced Trajectory Unravelings for GPU Noisy Quantum-Circuit Simulation: Characterization and a Qiskit-Aer Integration Gap
• Classical simulation of qubit by a new hardware design and its applications
• A High-Performance Pauli-Algebra Framework for Large-Scale Quantum Simulations
• The Convergence Frontier: Integrating Machine Learning and High Performance Quantum Computing for Next-Generation Drug Discovery
• Real Matrix Representations of Quantum Operators: An Introduction to Quantum Index Algebra
• DeepQuantum: A PyTorch-based Software Platform for Quantum Machine Learning and Photonic Quantum Computing
• How to Square Tensor Networks and Circuits Without Squaring Them
• Scalable Quantum Error Mitigation with Neighbor-Informed Learning
• Tianyan: Cloud services with quantum advantage
• On Sparse Representations of 3-Manifolds
• Superchannel without Tears: A Generalized Occam's Razor for Quantum Processes
• Parameterized Verification of Quantum Circuits (Technical Report)
• ExtraFerm: An Extended Matchgate Simulator
• Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
• Phase transitions in random circuit sampling
• Approximate Equivalence Checking of Noisy Quantum Circuits
• Simulating Clifford Circuits with Gaussian Elimination
• qHiPSTER: The Quantum High Performance Software Testing Environment
• Quantum algorithms for scientific computing
• SANQ: A Simulation Framework for Architecting Noisy Intermediate-Scale Quantum Computing System
• Low Rank Approximation in Simulations of Quantum Algorithms
• Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs
• The limits of quantum circuit simulation with low precision arithmetic
• Convolutional Polar Codes on Channels with Memory using Tensor Networks
• Normalizer Circuits and Quantum Computation
• Renormalization and computation I: motivation and background
• On traces of tensor representations of diagrams
• QuIRK: Quantum-Inspired Re-uploading KAN
• Exponential Speed-ups for Structured Goemans-Williamson relaxations via Quantum Gibbs States and Pauli Sparsity
• Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
• Classical simulation of noisy random circuits from exponential decay of correlation
• Fermionic Insights into Measurement-Based Quantum Computation: Circle Graph States Are Not Universal Resources
• Beyond Belief Propagation: Cluster-Corrected Tensor Network Contraction with Exponential Convergence
• Congestion bounds via Laplacian eigenvalues and their application to tensor networks with arbitrary geometry
• Optimizing Memory Efficiency and Index Ordering to Simulate Quantum Circuits Using Tensor Decision Diagrams
• FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
• Bell's Inequalities: Foundations and Quantum Communication
• Classical Simulation of Quantum Supremacy Circuits
• Variational Quantum Algorithms
• AutoHOOT: Automatic High-Order Optimization for Tensors
• On computing and the complexity of computing higher-order U-statistics, exactly
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Quantum Supremacy Circuit Simulation on Sunway TaihuLight
• Demonstration of Efficient Predictive Surrogates for Large-scale Quantum Processors
• Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
• Importance of Diagonal Gates in Tensor Network Simulations
• Studies on the Role of Entanglement in Mixed-state Quantum Computation
• Scaling Portfolio Diversification with Quantum Circuit Cutting Techniques
• InferQ: A Database-Oriented Benchmark for Quantum Circuits Simulation
• Node Replacement based Approximate Quantum Simulation with Decision Diagrams
• How to Write a Simulator for Quantum Circuits from Scratch: A Tutorial
• Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
• Computational Power of Random Quantum Circuits in Arbitrary Geometries
• On Stability of Tensor Networks and Canonical Forms
• Simulating the Sycamore quantum supremacy circuits
• Implementing Entangled States on a Quantum Computer
• Convolutional Polar Codes
• Zero-free regions of partition functions with applications to algorithms\n and graph limits
• Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
• The quantum FFT can be classically simulated
• Fewer Histories, Faster Paths: Distributed Quantum Circuit Feynman Simulation via History Reduction, Checkpointing, and Pruning
• Fast Trainable Multilinear Bases for Image Compression
• Quon Classical Simulation: Unifying Cliffords, Matchgates and Entanglement
• Tensor-Parallel Emulation of Quantum Circuits with Block-Cyclic Distributed Matrix Product States
• Operator Imprecision and Scaling of Shor's Algorithm
• Matchgates and classical simulation of quantum circuits
• On the simulation of quantum circuits
• Concatenated tensor network states
• Exponential Decay of Correlations Implies Area Law
• Characterizing quantum supremacy in near-term devices
• Sparse LDL, LU, and inverse butterfly factorization via tree decomposition
• Scalable Quantum Molecular Generation via GPU-Accelerated Tensor-Network Simulation
• A Nested Amplitude Amplification Protocol for the Binary Knapsack Problem
• Branch-and-Bound Tensor Networks for Exact Ground-State Characterization
• TTC: A high-performance Compiler for Tensor Transpositions
• Measurement-based quantum computation
• Alibaba Cloud Quantum Development Platform: Surface Code Simulations with Crosstalk
• Efficient classical simulation of the approximate quantum Fourier transform
• Tensor network states in time-bin quantum optics
• What Limits the Simulation of Quantum Computers?
• Statistical assertions for validating patterns and finding bugs in quantum programs
• Feynman-path-type simulation using stabilizer projector decomposition of unitaries
• qTorch: The quantum tensor contraction handler
• Carving-width and contraction trees for tensor networks
• Derivatives of tree tensor networks and its applications in Runge--Kutta methods
• Tree tensor network approach to simulating Shor's algorithm
• Comparative Benchmarking of Utility-Scale Quantum Emulators
• Constructing a virtual two-qubit gate by sampling single-qubit operations
• Trading Classical and Quantum Computational Resources
• Tropical Tensor Network for Ground States of Spin Glasses
• Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem
• Learning to Rank Tensor Network Contraction Plans for GPU-Accelerated Quantum Circuit Simulation
• Scalable projected entangled-pair state representation of random quantum circuit states

Related

• On the simulation of quantum circuits
• Efficiently contractable quantum circuits cannot produce much entanglement
• Simulating Quantum Circuits with Tree Tensor Networks using Density-Matrix Renormalization Group Algorithm
• Breaking the Treewidth Barrier in Quantum Circuit Simulation with Decision Diagrams
• Constructing Optimal Contraction Trees for Tensor Network Quantum Circuit Simulation