Simulating quantum computation by contracting tensor networks
arXiv:quant-ph/0511069 · 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 gates whose underlying graph has treewidth can be simulated deterministically in time, which, in particular, is polynomial in if . 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 (Physical Review Letters, 86:5188--5191, 2001), 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.
7 figures
References in corpus (21)
- Efficient classical simulation of slightly entangled quantum computations
- Persistent entanglement in arrays of interacting particles
- Efficient simulation of one-dimensional quantum many-body systems
- Improved Simulation of Stabilizer Circuits
- Experimental One-Way Quantum Computing
- Matrix Product Density Operators: Simulation of finite-T and dissipative systems
- Mixed-state dynamics in one-dimensional quantum lattice systems: a time-dependent superoperator renormalization algorithm
- Renormalization algorithms for Quantum-Many Body Systems in two and higher dimensions
- Instantaneous non-local computation of low T-depth quantum circuits
- The Heisenberg Representation of Quantum Computers
- Simulating quantum computation by contracting tensor networks
- Classical simulation of noninteracting-fermion quantum circuits
- Universal resources for measurement-based quantum computation
- Efficient quantum computation with probabilistic quantum gates
- Classical simulation versus universality in measurement based quantum computation
- On measurement-based quantum computation with the toric code states
- Quantum Circuits with Mixed States
- Renormalization algorithm for the calculation of spectra of interacting quantum systems
- Efficient classical simulation of the approximate quantum Fourier transform
- On the simulation of quantum circuits
- The quantum FFT can be classically simulated
Cited by in corpus (230)
- Variational Quantum Algorithms
- Characterizing Quantum Supremacy in Near-Term Devices
- Strong quantum computational advantage using a superconducting quantum processor
- Measurement-based quantum computation
- Quantum Computational Supremacy
- Validating quantum computers using randomized model circuits
- Simulating quantum computation by contracting tensor networks
- Quantum Optimization of Maximum Independent Set using Rydberg Atom Arrays
- Positive Wigner functions render classical simulation of quantum computation efficient
- Improved classical simulation of quantum circuits dominated by Clifford gates
- Qulacs: a fast and versatile quantum circuit simulator for research purpose
- Information Scrambling in Computationally Complex Quantum Circuits
- Trading classical and quantum computational resources
- Simulation of quantum circuits by low-rank stabilizer decompositions
- Most quantum states are too entangled to be useful as computational resources
- Simulating Large Quantum Circuits on a Small Quantum Computer
- Differentiable Programming Tensor Networks
- Matchgates and classical simulation of quantum circuits
- What limits the simulation of quantum computers?
- Achieving quantum supremacy with sparse and noisy commuting quantum computations
- Hyper-optimized tensor network contraction
- Lecture Notes of Tensor Network Contractions
- Instantaneous Quantum Computation
- Doubling the size of quantum simulators by entanglement forging
- Exponential Decay of Correlations Implies Area Law
- Quantum Machine Learning for Chemistry and Physics
- A flexible high-performance simulator for verifying and benchmarking quantum circuits implemented on real hardware
- Efficient classical simulation of random shallow 2D quantum circuits
- Computational advantage of quantum random sampling
- The Tensor Networks Anthology: Simulation techniques for many-body quantum lattice systems
- Full-State Quantum Circuit Simulation by Using Data Compression
- Qibo: a framework for quantum simulation with hardware acceleration
- An area law for entanglement from exponential decay of correlations
- TensorCircuit: a Quantum Software Framework for the NISQ Era
- Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
- Leveraging Secondary Storage to Simulate Deep 54-qubit Sycamore Circuits
- Statistical Assertions for Validating Patterns and Finding Bugs in Quantum Programs
- Establishing the Quantum Supremacy Frontier with a 281 Pflop/s Simulation
- Universal quantum computation with little entanglement
- Beyond-classical computation in quantum simulation
- Closing the "Quantum Supremacy" Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer
- PyZX: Large Scale Automated Diagrammatic Reasoning
- qHiPSTER: The Quantum High Performance Software Testing Environment
- Phase transition in Random Circuit Sampling
- Automated distribution of quantum circuits via hypergraph partitioning
- Intel Quantum Simulator: A cloud-ready high-performance simulator of quantum circuits
- Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
- Constructing a virtual two-qubit gate by sampling single-qubit operations
- Fast and converged classical simulations of evidence for the utility of quantum computing before fault tolerance
- Tensor Networks and Quantum Error Correction
- Quantum-centric Supercomputing for Materials Science: A Perspective on Challenges and Future Directions
- Tensor operators: constructions and applications for long-range interaction systems
- Classical Simulation of Quantum Supremacy Circuits
- Extracting Success from IBM's 20-Qubit Machines Using Error-Aware Compilation
- Does provable absence of barren plateaus imply classical simulability?
- Fast quantum circuit cutting with randomized measurements
- Equivalence between contextuality and negativity of the Wigner function for qudits
- A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
- Contracting Arbitrary Tensor Networks: General Approximate Algorithm and Applications in Graphical Models and Quantum Circuit Simulations
- Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage
- Encoding Hypergraphs into Quantum States
- Dynamical Magic Transitions in Monitored Clifford+T Circuits
- Classical algorithms for quantum mean values
- Quantum interference as a resource for quantum speedup
- Contracting projected entangled pair states is average-case hard
- The MQT Handbook: A Summary of Design Automation Tools and Software for Quantum Computing
- Probabilistic Simulation of Quantum Circuits with the Transformer
- Tropical Tensor Network for Ground States of Spin Glasses
- qTorch: The Quantum Tensor Contraction Handler
- Quantum Supremacy Is Both Closer and Farther than It Appears
- On the simulation of quantum circuits
- Boundaries of quantum supremacy via random circuit sampling
- Jet: Fast quantum circuit simulations with parallel task-based tensor-network contraction
- Simulating quantum circuits with ZX-calculus reduced stabiliser decompositions
- Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments
- Simulating the Sycamore quantum supremacy circuits
- Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm
- Tensor Network Contractions for #SAT
- Classical simulation of boson sampling based on graph structure
- Tensor network states in time-bin quantum optics
- Fast counting with tensor networks
- A Comprehensive Review of Quantum Circuit Optimization: Current Trends and Future Directions
- The quantum FFT can be classically simulated
- Accurate simulation for finite projected entangled pair states in two dimensions
- Absence of barren plateaus in finite local-depth circuits with long-range entanglement
- Density Matrix Renormalization Group with Tensor Processing Units
- Fast estimation of outcome probabilities for quantum circuits
- Pareto-Efficient Quantum Circuit Simulation Using Tensor Contraction Deferral
- Computing solution space properties of combinatorial optimization problems via generic tensor networks
- Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
- Tensor Networks contraction and the Belief Propagation algorithm
- The computational power of random quantum circuits in arbitrary geometries
- Quantum Divide and Compute: Exploring The Effect of Different Noise Sources
- Concatenated tensor network states
- An adaptive algorithm for quantum circuit simulation
- Quantum Teleportation-Inspired Algorithm for Sampling Large Random Quantum Circuits
- Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm
- Hyper-optimized approximate contraction of tensor networks with arbitrary geometry
- Quantum circuits and low-degree polynomials over F_2
- Fourier expansion in variational quantum algorithms
- How to simulate quantum measurement without computing marginals
- Renormalization and computation I: motivation and background
- The Fermionic Quantum Emulator
- Classically estimating observables of noiseless quantum circuits
- Tensor networks for interpretable and efficient quantum-inspired machine learning
- Performance Evaluation and Acceleration of the QTensor Quantum Circuit Simulator on GPUs
- Quantum Supremacy Circuit Simulation on Sunway TaihuLight
- Certainty and Uncertainty in Quantum Information Processing
- An Efficient Algorithm for approximating 1D Ground States
- A tree tensor network approach to simulating Shor's algorithm
- Tensor networks for quantum computing
- Simple heuristics for efficient parallel tensor contraction and quantum circuit simulation
- Solving search problems by strongly simulating quantum circuits
- TenCirChem: An Efficient Quantum Computational Chemistry Package for the NISQ Era
- Capturing exponential variance using polynomial resources: applying tensor networks to non-equilibrium stochastic processes
- Quantum algorithms for scientific computing
- Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
- Convolutional Polar Codes
- Unbiasing Fermionic Auxiliary-Field Quantum Monte Carlo with Matrix Product State Trial Wavefunctions
- Simulation Paths for Quantum Circuit Simulation with Decision Diagrams
- Alibaba Cloud Quantum Development Platform: Applications to Quantum Algorithm Design
- Symbolic Execution for Quantum Error Correction Programs
- Quantum circuit compilation and hybrid computation using Pauli-based computation
- Simulation of quantum optics by coherent state decomposition
- Validating quantum-supremacy experiments with exact and fast tensor network contraction
- Detecting Violations of Differential Privacy for Quantum Algorithms
- Benchmarking treewidth as a practical component of tensor-network--based quantum simulation
- Discrete-time quantum walks as fermions of lattice gauge theory
- Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound
- Local tensor-network codes
- Sharp complexity phase transitions generated by entanglement
- Simulation of Quantum Computing on Classical Supercomputers
- Making Classical Ground State Spin Computing Fault-Tolerant
- Functional Tensor Network Solving Many-body Schrödinger Equation
- Protocols for classically training quantum generative models on probability distributions
- Algorithms and complexity for Turaev-Viro invariants
- From Ansätze to Z-gates: a NASA View of Quantum Computing
- SANQ: A Simulation Framework for Architecting Noisy Intermediate-Scale Quantum Computing System
- Tensor network methods with graph enhancement
- Simulating local measurements on a quantum many body system with stochastic matrix product states
- Automatic Contraction of Unstructured Tensor Networks
- NISQ-compatible approximate quantum algorithm for unconstrained and constrained discrete optimization
- Minimum Cost Loop Nests for Contraction of a Sparse Tensor with a Tensor Network
- Simulation of Quantum Computers: Review and Acceleration Opportunities
- Non-Pauli errors can be efficiently sampled in qudit surface codes
- Qsun: an open-source platform towards practical quantum machine learning applications
- Constant-degree graph expansions that preserve the treewidth
- Memory-Efficient Quantum Circuit Simulation by Using Lossy Data Compression
- Alibaba Cloud Quantum Development Platform: Surface Code Simulations with Crosstalk
- FeynmanDD: Quantum Circuit Analysis with Classical Decision Diagrams
- Tensor Network Computations That Capture Strict Variationality, Volume Law Behavior, and the Efficient Representation of Neural Network States
- Deep Quantum Circuit Simulations of Low-Energy Nuclear States
- Efficient classical simulation and benchmarking of quantum processes in the Weyl basis
- Efficient Contraction of Large Tensor Networks for Weighted Model Counting through Graph Decompositions
- Enhancing the efficiency of quantum annealing via reinforcement: A path-integral Monte Carlo simulation of the quantum reinforcement algorithm
- Approximation Algorithms for Complex-Valued Ising Models on Bounded Degree Graphs
- Efficient Decomposition of High-Rank Tensors
- Branching MERA codes: a natural extension of polar codes
- Entanglement Scaling in Quantum Advantage Benchmarks
- Classical spin systems and the quantum stabilizer formalism: general mappings and applications
- A BQP-complete problem related to the Ising model partition function via a new connection between quantum circuits and graphs
- Fault-tolerant compiling of classically hard IQP circuits on hypercubes
- Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits
- Tensor Networks for Simulating Quantum Circuits on FPGAs
- Efficient classical computation of expectation values in a class of quantum circuits with an epistemically restricted phase space representation
- Noisy induced entanglement transition in one-dimensional random quantum circuits
- Bell's Inequalities: Foundations and Quantum Communication
- Simulating Quantum Computations with Tutte Polynomials
- Feynman-path type simulation using stabilizer projector decomposition of unitaries
- Understanding the Quantum Computational Speed-up via De-quantisation
- Fast simulation of planar Clifford circuits
- Amplitude-Aware Lossy Compression for Quantum Circuit Simulation
- TTC: A high-performance Compiler for Tensor Transpositions
- Probabilistic Inference in the Era of Tensor Networks and Differential Programming
- On Stability of Tensor Networks and Canonical Forms
- RosneT: A Block Tensor Algebra Library for Out-of-Core Quantum Computing Simulation
- The resource theory of tensor networks
- Normalizer Circuits and Quantum Computation
- Quantum mean value approximator for hard integer value problems
- Variational Quantum Simulation of Valence-Bond Solids
- Quantum Circuit Simulation with Fast Tensor Decision Diagram
- On efficiently solvable cases of Quantum k-SAT
- Matchgate circuits deeply thermalize
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Importance of Diagonal Gates in Tensor Network Simulations
- Tensor networks and the enumeration of regular subgraphs
- Simulation of Quantum Many-Body Systems on Amazon Cloud
- Limitations of Noisy Quantum Devices in Computational and Entangling Power
- Approximate Equivalence Checking of Noisy Quantum Circuits
- Survey on Computational Applications of Tensor Network Simulations
- HybridQ: A Hybrid Simulator for Quantum Circuits
- Generalized operads and their inner cohomomorphisms
- Quantum median filter for Total Variation image denoising
- Implementing Entangled States on a Quantum Computer
- Tomography-assisted noisy quantum circuit simulator using matrix product density operators
- Efficient Mean-Field Simulation of Quantum Circuits Inspired by Density Functional Theory
- Studies on the Role of Entanglement in Mixed-state Quantum Computation
- Scalable projected entangled-pair state representation of random quantum circuit states
- Adiabatic ground state preparation in an expanding lattice
- A multiprecision C++ library for matrix-product-state simulation of quantum computing: Evaluation of numerical errors
- An Extensible Quantum Network Simulator Built on ns-3: Q2NS Design and Evaluation
- Positive bias makes tensor-network contraction tractable
- Vanishing performance of the parity-encoded quantum approximate optimization algorithm applied to spin-glass models
- AutoHOOT: Automatic High-Order Optimization for Tensors
- Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
- Carving-width and contraction trees for tensor networks
- Commuting Quantum Circuits with Few Outputs are Unlikely to be Classically Simulatable
- On the Optimal Linear Contraction Order of Tree Tensor Networks, and Beyond
- Contextuality scenarios arising from networks of stochastic processes
- Classical simulation of measurement-based quantum computation on higher-genus surface-code states
- Recursive Path-Summing Simulation of Quantum Computation
- Belief propagation in monoidal categories
- Spectral Independence via Stability and Applications to Holant-Type Problems
- Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
- State of practice: evaluating GPU performance of state vector and tensor network methods
- Efficient Construction of Functional Representations for Quantum Algorithms
- Optimal Scheduling of Graph States via Path Decompositions
- On traces of tensor representations of diagrams
- Operator Imprecision and Scaling of Shor's Algorithm
- One-Way Quantum Computer Simulation
- Joint Cutting for Hybrid Schrödinger-Feynman Simulation of Quantum Circuits
- Convolutional Polar Codes on Channels with Memory using Tensor Networks
- Reducing depth and measurement weights in Pauli-based computation
- Efficient classical simulation of cluster state quantum circuits with alternative inputs
- Logical Abstractions for Noisy Variational Quantum Algorithm Simulation
- Low Rank Approximation in Simulations of Quantum Algorithms
- The limits of quantum circuit simulation with low precision arithmetic
- Formal Verification of Quantum Ancilla Safety
- Classical simulation of qubit by a new hardware design and its applications
- Efficient Quantum Circuit Simulation by Tensor Network Methods on Modern GPUs