Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
In the authors' words
We give a deterministic classical algorithm that estimates to additive error in time, where is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and is an arbitrary -bit output string. This improves over prior state-of-the-art algorithms that takes time for the same task, when is geometrically local, and for 2D geometrically-local circuits.
Main resultLimitation the authors admit
Appeared: Friday, October 2. arXiv. Preprint, not yet peer-reviewed.