Divide-and-conquer method for approximating output probabilities of constant-depth, geometrically-local quantum circuits

Many schemes for obtaining a computational advantage with near-term quantum hardware are motivated by mathematical results proving the computational hardness of sampling from near-term quantum circuits. Near-term quantum circuits are often modeled as geometrically-local, shallow-depth (GLSD) quantum circuits. That is, circuits consisting of two qubit gates that can act only on neighboring qubits, and that have polylogarithmic depth in the number of qubits. In this talk, we consider the task of estimating output probabilities of GLSD circuits to inverse polynomial error. In particular, we will demonstrate how the output state of a GLSD circuit can be approximated via a linear combination of product states, each of which are produced via new GLSD circuits on approximately half the original number of qubits. We will show how this idea can be used to develop a classical divide-and-conquer algorithm for calculating the output probabilities of a 3D geometrically-local circuit. This talk is based on joint work with Matthew Coudron.

Reference: N. Coble, M. Coudron.  “Quasi-polynomial time approximation of output probabilities of geometrically-local, shallow quantum circuits.”  arXiv:2012.05460