Quantum queries need four steps to exactly solve weight three or four problem
Exact Quantum Query Complexity of the Five-Bit Symmetric Boolean Function $\Exact^5_{3,4}$
Computational Complexity
Summary
This paper looks at a special quantum computing problem where the goal is to find out if a group of bits has exactly three or four ones. Earlier work suggested you might do this perfectly in three tries, but the authors show this is impossible. They prove that you need at least four quantum queries to get an exact answer every time and explain why three queries always have a tiny chance of error. They also confirm a known method that uses four queries can solve this exactly.
What this means in practice
- •For quantum algorithm designers: Avoid claiming exact three-query algorithms for the five-bit weight 3 or 4 Boolean function, due to a proven four-query lower bound.
- •For quantum complexity theorists: Use the dual certificate and Gram matrix framework to rigorously rule out exact low-query quantum algorithms in similar problems.
A theory result. No direct application yet.
Authors
Guoliang Xu, Haoran Zhang, Mengfan Wu, Songyao Xue, Mingke Liu
Abstract
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 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 \(\text{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 \(\frac{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.