Metraipolis › archive › dc_dc72224fafbb
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits — arXiv:2610.02146
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.02146
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-07T11:38:36.497Z
- SHA-256 of the archived text
3a5999c5557b5764759233d20cf97360af821877eedcc5c92bde30bdedb51505- Stable URL of this page
https://metraipolis.com/documento/dc_dc72224fafbb
How to cite
Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits — arXiv:2610.02146 — arXiv (en), https://arxiv.org/abs/2610.02146 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dc72224fafbb (Metraipolis archive dc_dc72224fafbb, sha256 3a5999c5557b5764759233d20cf97360af821877eedcc5c92bde30bdedb51505)
BibTeX
@misc{dcdc72224fafbb,
title = {Polynomial-time additive-error estimation of output probabilities for shallow quantum circuits — arXiv:2610.02146},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.02146},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dc72224fafbb; sha256 3a5999c5557b5764759233d20cf97360af821877eedcc5c92bde30bdedb51505},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.02146. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We give a deterministic classical algorithm that estimates $|\langle x|U|0^n\rangle|^2$ to additive error $\varepsilon$ in $\mathrm{poly}(n, 1/\varepsilon)$ 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.
Tema degli esploratori: fisica e astronomia (retro-catalogo arXiv: annunci del 2026-10-02 in quant-ph).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2610.02146 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T11:19:01.761Z dalla pagina https://arxiv.org/catchup/quant-ph/2026-10-02?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).