Tensor networks can often accurately approximate various systems that are of interest to physicists, but the computational cost of contracting the network is often prohibitively demanding. Quantum computer can resolve this bottleneck, but because the size of the computation scales with the size of the network, the existing quantum computers may appear to be far too noisy for this task. We prove a nontrivial error bound on the outcome of the computation that does not scale with the size of the network. This is possible because certain tensor networks are secretly implementing a quantum analogue of a (classical) Markovian dynamics. The long-time stability of the Markovian dynamics gives rise to a nontrivial error bound on the outcome of the computation. This suggests that there may be practical problems of interest that are amenable to relatively noisy quantum computers.
Isaac Kim graduated from Caltech in 2013 with a Ph.D in physics, and then moved to Perimeter institute, IBM T. J. Watson research center, and then to Stanford. Isaac now works at PsiQuantum, a startup company trying to build a quantum computer.