00941nas a2200109 4500008004100000245005400041210005400095260001500149520061200164100001800776856003700794 2019 eng d00aSimulating quantum circuits by classical circuits0 aSimulating quantum circuits by classical circuits c04/10/20193 a
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.
1 aWang, Daochen uhttps://arxiv.org/abs/1904.05282