Simulating quantum circuits by classical circuits

In a recent breakthrough, Bravyi, Gosset and König (BGK) [Science, 2018] proved that "simulating" constant depth quantum circuits takes classical circuits Ω(logn) depth. In our paper, we first formalise their notion of simulation, which we call "possibilistic simulation". Then, from well-known results, we deduce that their circuits can be simulated in depth O(log2n). Separately, we construct explicit classical circuits that can simulate any depth-d quantum circuit with Clifford and t T-gates in depth O(d+t). Our classical circuits use {NOT, AND, OR} gates of fan-in ≤2.