Divide-and-conquer method for approximating output probabilities of constant-depth, geometrically-local quantum circuits
Nolan Coble, University of Maryland, College Park
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
Join the seminar on Zoom
Meeting link: https://umd.zoom.us/j/97341197318
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Hakop Pashayan (hpashaya@uwaterloo.ca).