Simulating quantum circuits by classical circuits
Daochen Wang · arXiv (Cornell University) · 2019
In a recent breakthrough, Bravyi, Gosset and Konig (BGK) [Science, 2018] proved that simulating constant depth quantum circuits takes classical circuits $\Omega(\log n)$ 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(\log^{2} n)$. 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 $\{\text{NOT, AND, OR}\}$ gates of fan-in $\leq 2$.