PreprintarXiv licencearXiv
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
Abstract
We give a deterministic classical algorithm that estimates |⟨ x|U|0n⟩|2 to additive error ε in poly(n, 1/ε) time, where U is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and x is an arbitrary n-bit output string. This improves over prior state-of-the-art algorithms that takes nO(log(n)) time for the same task, nO(log(log(n)) when U is geometrically local, and nO(1) for 2D geometrically-local circuits.
Related
- Shallow data-loading circuits for multivariable functions
- Additive solid immersion lenses for enhanced collection efficiency of shallow NV centers by pulsed laser deposition and structurization of high-k amorphous oxides
- Experimentally Testable Quantum Advantage in Shallow Circuits
- Distilling Datasets into Shallow Circuits for Quantum Machine Learning
- Classical Pre-Training of Large Shallow Parametrized Quantum Circuits through Pauli Propagation and deployment on Quantum Hardware
BibTeX
@misc{coudron2026polynomialtime,
title = {{Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits}},
author = {Matthew Coudron and Michael J. Gullans and Jon Nelson and Joel Rajakumar and Shi Jie Samuel Tan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02146},
eprint = {2610.02146},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02146},
}
RIS
TY - UNPB
TI - Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits
AU - Matthew Coudron
AU - Michael J. Gullans
AU - Jon Nelson
AU - Joel Rajakumar
AU - Shi Jie Samuel Tan
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2610.02146
UR - https://arxiv.org/abs/2610.02146
AB - We give a deterministic classical algorithm that estimates |⟨ x|U|0^n⟩|^2 to additive error ε in poly(n, 1/ε) time, where U is a constant-depth quantum circuit comprised of gates with bounded fan-in and arbitrary connectivity, and x is an arbitrary n-bit output string. This improves over prior state-of-the-art algorithms that takes n^O(log(n)) time for the same task, n^O(log(log(n)) when U is geometrically local, and n^O(1) for 2D geometrically-local circuits.
ER -