Simulating Quantum Computation by Contracting Tensor Networks
From MaRDI portal
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.
Recommendations
- A near-quadratic lower bound for the size of quantum circuits of constant treewidth
- Quantum computation and the evaluation of tensor networks
- On the satisfiability of quantum circuits of small treewidth
- On the satisfiability of quantum circuits of small treewidth
- Entanglement, flow and classical simulatability in measurement based quantum computation
Cited in
(38)- A new connection between quantum circuits, graphs and the Ising partition function
- Zero-free regions of partition functions with applications to algorithms and graph limits
- Clifford gates in the Holant framework
- Computations in quantum tensor networks
- Efficient tree decomposition of high-rank tensors
- Mixed partition functions and exponentially bounded edge-connection rank
- Quantum median filter for total variation image denoising
- Tensor networks and the enumerative geometry of graphs
- On efficiently solvable cases of quantum \(k\)-SAT
- Algorithms and complexity for Turaev-Viro invariants
- On traces of tensor representations of diagrams
- On the satisfiability of quantum circuits of small treewidth
- Exponential decay of correlations implies area law
- A complete dichotomy rises from the capture of vanishing signatures
- Quantum circuits and low-degree polynomials over \(\mathbb{F}_2\)
- Classical spin systems and the quantum stabilizer formalism: general mappings and applications
- The complexity of counting edge colorings and a dichotomy for some higher domain Holant problems
- On the satisfiability of quantum circuits of small treewidth
- Graph parameters from symplectic group invariants
- Algebraic Methods in Quantum Informatics
- A near-quadratic lower bound for the size of quantum circuits of constant treewidth
- Parameterization of tensor network contraction
- Efficient Construction of Functional Representations for Quantum Algorithms
- Contextuality Scenarios Arising from Networks of Stochastic Processes
- Quantum computation and the evaluation of tensor networks
- Minor-embedding in adiabatic quantum computation. II: Minor-universal graph design
- ON THE COMPUTATIONAL POWER OF PHYSICAL INTERACTIONS: BOUNDS ON THE NUMBER OF TIME STEPS FOR SIMULATING ARBITRARY INTERACTION GRAPHS
- MPS-VQE: a variational quantum computational chemistry simulator with matrix product states
- Computing Solution Space Properties of Combinatorial Optimization Problems Via Generic Tensor Networks
- Simulation of quantum many-body systems on Amazon cloud
- Equivalence between contextuality and negativity of the Wigner function for qudits
- Constant-degree graph expansions that preserve treewidth
- Spectral independence via stability and applications to Holant-type problems
- On the optimal linear contraction order of tree tensor networks, and beyond
- QMin: quantum circuit minimization via gate fusions for efficient state vector simulation
- Near-linear time and fixed-parameter tractable algorithms for tensor decompositions
- Advancements in numerical methods for quantum resources
- Tensor network contractions for \#SAT
This page was built for publication: Simulating Quantum Computation by Contracting Tensor Networks
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3631899)
