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.
AI Summary
The paper determines the exact quantum query complexity of $\mathrm{EXACT}^{5}_{3,4}$, which accepts five-bit inputs of Hamming weight three or four. Earlier numerical searches reported three-query success probabilities above $0.999$, leaving open whether exact computation required three or four queries. The main result is $Q_{\mathrm E}(\mathrm{EXACT}^{5}_{3,4})=4$.
The lower bound represents arbitrary three-query algorithms through layer-by-layer Gram matrices of low-degree Fourier coefficients, with coefficient-space dimensions $1,6,16$. An explicit rational dual certificate separates these necessary query-process constraints from the final-state orthogonality required for exact output. Permutation symmetry compresses certificate verification without restricting the algorithms themselves: the argument allows arbitrary finite-dimensional workspaces, complex amplitudes, and purified intermediate measurements. Positive definiteness of the certificate slacks reduces to five small rational matrices, checked through exact principal minors; embedded code provides an additional exact-arithmetic audit. The four-query upper bound follows from a previously known algorithm for $\mathrm{EXACT}^{7}_{3,4}$ by padding with two fixed zeros.
The same certificate gives a worst-case error lower bound of $25600/43779488192449>5.84\times10^{-10}$ for every algorithm using at most three queries. This bound is not claimed tight, and the optimal three-query error remains undetermined. The paper also records a fully symmetric degree-three sum-of-squares representation, yielding $\mathrm{sosdeg}(f)=3<Q_{\mathrm E}(f)=4$. This pointwise representation does not impose the inter-layer constraints needed for a query algorithm. The analysis concerns this five-bit instance; analogous certificates for other adjacent-weight functions are left for future work.
Likely largely AI-generatedAI use disclosedIncremental
During manuscript preparation, the authors used OpenAI ChatGPT to assist with language editing, checking, reformulation of some derivations, and the search and computation of some numerical values.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper determines the exact quantum query complexity of EXACT3,45, which accepts five-bit inputs of Hamming weight three or four. Earlier numerical searches reported three-query success probabilities above 0.999, leaving open whether exact computation required three or four queries. The main result is QE(EXACT3,45)=4.
The lower bound represents arbitrary three-query algorithms through layer-by-layer Gram matrices of low-degree Fourier coefficients, with coefficient-space dimensions 1,6,16. An explicit rational dual certificate separates these necessary query-process constraints from the final-state orthogonality required for exact output. Permutation symmetry compresses certificate verification without restricting the algorithms themselves: the argument allows arbitrary finite-dimensional workspaces, complex amplitudes, and purified intermediate measurements. Positive definiteness of the certificate slacks reduces to five small rational matrices, checked through exact principal minors; embedded code provides an additional exact-arithmetic audit. The four-query upper bound follows from a previously known algorithm for EXACT3,47 by padding with two fixed zeros.
The same certificate gives a worst-case error lower bound of 25600/43779488192449>5.84×10−10 for every algorithm using at most three queries. This bound is not claimed tight, and the optimal three-query error remains undetermined. The paper also records a fully symmetric degree-three sum-of-squares representation, yielding sosdeg(f)=3<QE(f)=4. This pointwise representation does not impose the inter-layer constraints needed for a query algorithm. The analysis concerns this five-bit instance; analogous certificates for other adjacent-weight functions are left for future work.
We study the problem of computing the Hamming weight of an n-bit string modulo m, for any positive integer m≤n whose only prime factors are 2 and 3. We show that the exact quantum query complexity of this problem is ⌈n(1−1/m)⌉. The upper bound is via an iterative query algorithm whose core components are the well-known 1-query quantum algorithm (essentially due to Deutsch) to compute the Hamming weight a 2-bit string mod 2 (i.e., the parity of the input bits), and a new 2-query quantum algorithm to compute the Hamming weight of a 3-bit string mod 3. We show a matching lower bound (in fact for arbitrary moduli m) via a variant of the polynomial method [de Wolf, SIAM J. Comput., 32(3), 2003]. This bound is for the weaker task of deciding whether or not a given n-bit input has Hamming weight 0 modulo m, and it holds even in the stronger non-deterministic quantum query model where an algorithm must have positive acceptance probability iff its input evaluates to 1. For m>2 our lower bound exceeds n/2, beating the best lower bound provable using the general polynomial method [Theorem 4.3, Beals et al., J. ACM 48(4), 2001].
Beyond the n/2 Threshold: Quantum Query Complexity for Computing Hamming Weight and Symmetric Functions
The oracle-interrogation algorithm [van Dam, FOCS '98] computes every n-bit Boolean function with bounded error using n/2+O(n) quantum queries. In contrast, parity can be computed exactly using ⌈n/2⌉ 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+Ω(n1/3) quantum queries at a fixed positive constant error. We also give an algorithm that recovers the exact Hamming weight using n/2+O(n1/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.
We give and prove an optimal exact quantum query algorithm with complexity k+1 for computing the promise problem (i.e., symmetric and partial Boolean function) DJnk defined as: DJnk(x)=1 for ∣x∣=n/2, DJnk(x)=0 for ∣x∣ in the set {0,1,…,k,n−k,n−k+1,…,n}, and it is undefined for the rest cases, where n is even, ∣x∣ is the Hamming weight of x. The case of k=0 is the well-known Deutsch-Jozsa problem. We outline all symmetric (and partial) Boolean functions with degrees 1 and 2, and prove their exact quantum query complexity. Then we prove that any symmetrical (and partial) Boolean function f has exact quantum 1-query complexity if and only if f can be computed by the Deutsch-Jozsa algorithm. We also discover the optimal exact quantum 2-query complexity for distinguishing between inputs of Hamming weight {⌊n/2⌋,⌈n/2⌉} and Hamming weight in the set {0,n} for all odd n. In addition, a method is provided to determine the degree of any symmetrical (and partial) Boolean function.
We provide two sufficient and necessary conditions to characterize any n-bit partial Boolean function with exact quantum query complexity 1. Using the first characterization, we present all n-bit partial Boolean functions that depend on n bits and can be computed exactly by a 1-query quantum algorithm. Due to the second characterization, we construct a function F that maps any n-bit partial Boolean function to some integer, and if an n-bit partial Boolean function f depends on k bits and can be computed exactly by a 1-query quantum algorithm, then F(f) is non-positive. In addition, we show that the number of all n-bit partial Boolean functions that depend on k bits and can be computed exactly by a 1-query quantum algorithm is not bigger than an upper bound depending on n and k. Most importantly, the upper bound is far less than the number of all n-bit partial Boolean functions for all efficiently big n.
We prove the first non-trivial upper bound for the quantum query complexity of Boolean Matrix Product Verification (BMPV), answering a longstanding open question in quantum query complexity. For n×n matrices, our upper bound is O(n17/12), improving on the standard O(n3/2) bound obtained using Grover search by Buhrman and Špalek [SODA 2006]. We complement this result by showing an Ω(n5/4) lower bound, which improves over the previous best known lower bound of Ω(n19/18) by Childs, Kimmel, and Kothari [ESA 2012]. Our approach centers on a connection with Orthogonal Vectors (OV), which asks whether an indexed list of n Boolean vectors of dimension n contains two vectors with disjoint supports. In particular, we prove equivalences between OV and BMPV and establish the above bounds for OV. We also prove a tight Θ(n3/2) bound for a variant of BMPV that asks whether the product contains a given row vector. Together, these results imply a polynomial separation between the quantum query complexities of deciding whether a graph has radius at most two and whether it has diameter at most two.
One of the main reasons for query model's prominence in quantum complexity is the presence of concrete lower bounding techniques: polynomial method and adversary method. There have been considerable efforts to not just give lower bounds using these methods but even to compare and relate them. We explore the value of these bounds on quantum query complexity for the class of symmetric functions, arguably one of the most natural and basic set of Boolean functions. We show (using the recently introduced spectral sensitivity) that both these bounds (positive adversary and approximate degree) give the same value for every total symmetric Boolean function. We also look at the quantum query complexity of Gap Majority, a partial symmetric function. It has gained importance recently in regard to understanding the composition of randomized query complexity. We characterize the quantum query complexity of Gap Majority and show a lower bound on noisy randomized query complexity (Ben-David and Blais, FOCS 2020) in terms of quantum query complexity. In addition, we study how large certificate complexity and block sensitivity can be as compared to sensitivity (even up to constant factors) for symmetric functions. We show tight separations, i.e., give upper bound on possible separations and construct functions achieving the same.