Simulating quantum circuits using efficient tensor network contraction algorithms with subexponential upper bound

Abstract

We derive a rigorous upper bound on the classical computation time of finite-ranged tensor network contractions in $d\ge 2$ dimensions. Consequently, we show that quantum circuits of single-qubit and finite-ranged two-qubit gates can be classically simulated in subexponential time in the number of gates. Moreover, we present and implement an algorithm guaranteed to meet our bound and which finds contraction orders with vastly lower computational times in practice. In many practically relevant cases this beats standard simulation schemes and, for certain quantum circuits, also a state-of-the-art method. Specifically, our algorithm leads to speedups of several orders of magnitude over naive contraction schemes for two-dimensional quantum circuits on as little as an $8\times 8$ lattice. We obtain similarly efficient contraction schemes for Google's Sycamore-type quantum circuits, instantaneous quantum polynomial-time circuits, and non-homogeneous (2+1)-dimensional random quantum circuits.

7 pages, 5 figures

References in corpus (7)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Solving the sampling problem of the Sycamore quantum circuits
• Tensor Networks for Lattice Gauge Theories with continuous groups
• Lattice Gauge Tensor Networks
• A density-matrix renormalization group algorithm for simulating quantum circuits with a finite fidelity
• Projected Entangled Pair States with non-Abelian gauge symmetries: an SU(2) study
• Verifying Random Quantum Circuits with Arbitrary Geometry Using Tensor Network States Algorithm

Cited by in corpus (7)

• Dynamical Magic Transitions in Monitored Clifford+T Circuits
• Quantum algorithms for scientific computing
• Unveiling quantum phase transitions from traps in variational quantum algorithms
• Qu-Trefoil: Large-Scale Quantum Circuit Simulator Working on FPGA With SATA Storages
• Tomography-assisted noisy quantum circuit simulator using matrix product density operators
• Classically Simulating Quantum Supremacy IQP Circuits through a Random Graph Approach
• Challenges and opportunities in the supervised learning of quantum circuit outputs