Possibilistic simulation of quantum circuits by classical circuits

Abstract

In breakthrough work, Bravyi, Gosset, and König (BGK) [Science, 2018] unconditionally proved that constant depth quantum circuits are more powerful than their classical counterparts. Their result is equivalent to saying that a particular family of constant depth quantum circuits takes classical circuits at least $\Omega (\log n)$ depth to "simulate", in a certain sense. In our paper, we formalise their sense of simulation, which we call "possibilistic simulation" or "p-simulation", and construct explicit classical circuits that can p-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 $\le 2$.

8 pages; v2: major revision of v1 claims due to circuit depth costing error, cf. footnote 29; v3: reverted title back to v1's, refined main theorem statement, and improved presentation; v4: added comparison to weak and strong simulation, further improved presentation

References in corpus (6)

• Simulation of quantum circuits by low-rank stabilizer decompositions
• Quantum advantage with noisy shallow circuits in 3D
• Quantifying quantum speedups: improved classical simulation from tighter magic monotones
• Fast estimation of outcome probabilities for quantum circuits
• Modeling Pauli measurements on graph states with nearest-neighbor classical communication
• How to simulate quantum measurement without computing marginals

Cited by in corpus (1)

• Single-qubit gate teleportation provides a quantum advantage