pipette
ESEspañol

Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits

Matthew Coudron, Michael J. Gullans, Jon Nelson, Joel Rajakumar, Shi Jie Samuel Tan

Preprint

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.