David Gosset, Fast Simulation of Planar Clifford Circuits

Abstract

Clifford circuits are a special family of quantum circuits that can be simulated on a classical computer in polynomial time using linear algebra. Recent work has shown that Clifford circuits composed of nearest-neighbor gates in planar geometries can solve certain linear algebra problems provably faster--as measured by circuit depth-- than classical computers. We don't know if these linear algebra tasks also admit polynomial quantum speedups in terms of total runtime (gate complexity). Motivated by this question, here we show that treewidth and planarity can be used to improve classical algorithms for simulating Clifford circuits. Our main result is a classical algorithm with runtime asymptotically upper bounded as n^{W/2} which samples from the output distribution obtained by measuring each qubit of a quantum planar graph state in given Pauli bases, where W is the matrix multiplication exponent. We also provide a classical algorithm with the same asymptotic runtime which samples from the output distribution of any constant-depth Clifford circuit in a planar geometry. This is joint work with Daniel Grier, Alex Kerzner, and Luke Schaeffer (arxiv:2009.03218).


About CFCS Quantum Day
CFCS Quantum Day, organized by Center on Frontiers of Computing Studies (CFCS), Peking University, is a one-day seminar focusing on pioneering works on supremacy, quantum simulation, and applications with near-term quantum computing hardware. Given continued uncertainty surrounding the future of COVID-19 and worldwide travel precautions, CFCS Quantum Day was held online on May 12th, 2021.