Metraipolis › archive › dc_3e0816787bde
Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions — arXiv:2611.09809
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.09809
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:47:42.111Z
- SHA-256 of the archived text
d54439b0bedf3e8317bb01f568aff0baf418f4d0ff27d5841bd2be0f634ffac5- Stable URL of this page
https://metraipolis.com/documento/dc_3e0816787bde
How to cite
Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions — arXiv:2611.09809 — arXiv (en), https://arxiv.org/abs/2611.09809 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3e0816787bde (Metraipolis archive dc_3e0816787bde, sha256 d54439b0bedf3e8317bb01f568aff0baf418f4d0ff27d5841bd2be0f634ffac5)
BibTeX
@misc{dc3e0816787bde,
title = {Beyond the $n/2$ Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions — arXiv:2611.09809},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.09809},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3e0816787bde; sha256 d54439b0bedf3e8317bb01f568aff0baf418f4d0ff27d5841bd2be0f634ffac5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.09809. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every $n$-bit Boolean function with bounded error using $n/2+O(\sqrt n)$ quantum queries. In contrast, parity can be computed exactly using $\lceil n/2\rceil$ queries, but whether an additive overhead beyond $n/2$ is necessary for a single Boolean output has remained open. In this work, we construct an explicit family of symmetric Boolean functions requiring $n/2+\Omega(n^{1/3})$ quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using $n/2+O(n^{1/3})$ quantum queries with bounded error, and therefore computes every symmetric Boolean function within the same query bound. Together, these results determine the optimal additive order for Hamming weight recovery and for the worst case over symmetric Boolean functions at sufficiently small constant error.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Quantum Physics (quant-ph) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2611.09809 — 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-11-09T22:40:59.900Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).