{"id":"arxiv/2610.24518","url":"https://arxiv.org/abs/2610.24518","tags":["quant-ph","cs.CC"],"score":0,"title":"Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\\Exact^5_{3,4}$","domain":"quant-ph","source":"arxiv","authors":["Guoliang Xu","Haoran Zhang","Mengfan Wu","Songyao Xue","Mingke Liu"],"reviews":0,"subject":"quant-ph","summary":"Let \\(f = \\text{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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-17","reactions":{}}