@article {2391, title = {Simulating quantum circuits by classical circuits}, year = {2019}, month = {04/10/2019}, abstract = {

In a recent breakthrough, Bravyi, Gosset and K{\"o}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.

}, url = {https://arxiv.org/abs/1904.05282}, author = {Daochen Wang} }