Possibilistic simulation of quantum circuits by classical circuits

TitlePossibilistic simulation of quantum circuits by classical circuits
Publication TypeJournal Article
Year of Publication2019
AuthorsWang, D
Date Published04/10/2019

In a recent breakthrough, Bravyi, Gosset and König (BGK) [Science, 2018] proved that a family of shallow quantum circuits cannot be simulated by shallow classical circuits. In our paper, we first formalise their notion of simulation, which we call possibilistic simulation. We then construct classical circuits, using {NOT, AND, OR} gates of fan-in ≤2, that can simulate any given quantum circuit with Clifford+T gates. Our constructions give log-depth classical circuits that solve the Hidden Linear Function problem defined by BGK, matching their classical lower bound. More importantly, our constructions imply that the constant-vs-log circuit depth separation achieved by BGK is the largest achievable for simulating quantum circuits, like theirs, with Clifford+T gates.