Simulating Quantum Computation by Contracting Tensor Networks

By Igor L. Markov, Yaoyun Shi. SIAM journal on computing (Print), 2005

533 citations recorded by the source corpus.

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].)

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/3c0e67f3157d9ef4f702f67a77a4b9cb34507486

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Matchgates and classical simulation of quantum circuits (2008, methodology): “Using the formalism of tensor network contractions, it may be shown (Jozsa 2006; Yoran & Short 2006; Markov & Shi 2008) that any poly-sized quantum circuit of one- and two-qubit gates, which has log depth and in which the two-qubit gates are restricted to act at bounded range (i.e. on line pairs at…”
Variational quantum algorithms (2020, background): “Moreover, as quantum circuits can be viewed as tensor networks [51], it is quite natural to combine the existing tensor network techniques with a quantum ansatz [52– 54].”
Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design (2010, methodology): “For the quantum circuit model, it was shown by Markov & Shi [16] that a quantum circuit with n gates whose underlying graph has treewidth tw can be simulated in O ( poly ( n ) exp ( tw )) time.”
Quantum circuits and low-degree polynomials over F2 (2016, background): “Also observe that this simulation does not seem to follow immediately from the results of Markov and Shi [33] on simulating quantum circuits by tensor contraction in time exponential in the tree-width of the circuit.”
Quantum optimization of maximum independent set using Rydberg atom arrays (2022, methodology): “Using recently developed contraction order optimization techniques [67, 68, 69], the contraction can be done e ciently on graphs with a small tree width.”
Potential of quantum computing for drug discovery (2018, background): “In the classical case, despite clever ideas for approximation [81, 82], in worst-case scenarios one still needs to keep track of all of the 2 n amplitudes, which quickly becomes prohibitively expensive.”
Simulation of quantum circuits by low-rank stabilizer decompositions (2018, background): “In certain special cases the memory footprint can be reduced by recasting the simulation problem as a tensor network contraction [1, 8, 40].”
Quantum computational supremacy (2017, methodology): “Methods based on representing the exact state 41 can achieve low enough error rates that we can think of them as low multiplicative error, while methods based on sampling (e.g. 10 ) naturally achieve low additive error.”