Simulating Quantum Computation by Contracting Tensor Networks

2008/01/01 by Igor L. Markov, Yaoyun Shi · 48 citations
Computer Science · #Quantum Computing Algorithms and Architecture #Stochastic Gradient Optimization Techniques #Complexity and Algorithms in Graphs

paper · doi:10.1137/050644756

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 treewidth d can be simulated classically in poly(T)*exp(O(d)) time, which, in particular, is polynomial in T if d = O(logT). Among many implications, we show efficient simulations for quantum formulas, defined and studied by Yao (Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 352-361, 1993), and for log-depth circuits whose gates apply to nearby qubits only, a natural constraint satisfied by most physical implementations. We also extend the result to show that one-way quantum computation of Raussendorf and Briegel (Physical Review Letters, 86:5188-5191, 2001), a universal quantum computation scheme very promising for its physical implementation, can be efficiently simulated by a randomized algorithm if its quantum resource is derived from a small-treewidth graph.

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

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