Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function Exact53,4
Abstract
Let f = EXACT53,4 be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of f is 4. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function EXACT73,4 and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound 25600/43779488192449>0 on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.
Related
- Fanout Complexity of Symmetric Boolean Functions in QAC0
- Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
- Efficient Depth--Ancilla Tradeoffs for Hamming Weight Computation and Symmetric Boolean Functions
- Single and coupled quantum van der Pol oscillators: Wigner-function dynamics, exact qutrit solutions, and synchronization
- Boolean Cumulants and Exact Reduced Descriptions of Renewal-Driven Systems
BibTeX
@misc{xu2026exact,
title = {{Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_3,4$}},
author = {Guoliang Xu and Haoran Zhang and Mengfan Wu and Songyao Xue and Mingke Liu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.24518},
eprint = {2610.24518},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.24518},
}
RIS
TY - UNPB
TI - Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function Exact^5_3,4
AU - Guoliang Xu
AU - Haoran Zhang
AU - Mengfan Wu
AU - Songyao Xue
AU - Mingke Liu
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.24518
UR - https://arxiv.org/abs/2610.24518
AB - Let f = EXACT^5_3,4 be the Boolean function that equals 1 exactly on inputs of Hamming weight 3 or 4. Earlier numerical studies reported success probabilities close to one using three queries, but the existence of an exact three-query algorithm had remained unresolved. This paper settles this problem by proving that the exact quantum query complexity of f is 4. For the lower bound, we express every three-query algorithm through layer-by-layer Gram matrices of low-degree Fourier coefficients. We then construct a fixed rational dual certificate whose slack matrices are all positive definite. This certificate separates the necessary Gram-matrix region from the exact-output condition and therefore rules out every exact algorithm using at most three queries in the stated model. The positivity verification reduces to five small rational matrices and Sylvester's criterion. For the upper bound, we invoke the previously known four-query algorithm for the seven-bit function EXACT^7_3,4 and apply the standard padding reduction. To quantify the near-exact behavior, we use the same certificate to derive a valid, though not claimed tight, lower bound 25600/43779488192449>0 on the worst-case error of every algorithm using at most three queries. This positive error gap is compatible with the near-unit success probabilities reported in earlier numerical studies, which do not establish exact computation.
ER -