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.
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.
This paper explores a fine-grained version of the Watrous conjecture, including the randomized and quantum algorithms with success probabilities arbitrarily close to 1/2. Our contributions include the following: i) An analysis of the optimal success probability of quantum and randomized query algorithms of two fundamental partial symmetric Boolean functions given a fixed number of queries. We prove that for any quantum algorithm computing these two functions using T queries, there exist randomized algorithms using poly(T) queries that achieve the same success probability as the quantum algorithm, even if the success probability is arbitrarily close to 1/2. ii) We establish that for any total symmetric Boolean function f, if a quantum algorithm uses T queries to compute f with success probability 1/2+β, then there exists a randomized algorithm using O(T2) queries to compute f with success probability 1/2+Ω(δβ2) on a 1−δ fraction of inputs, where β,δ can be arbitrarily small positive values. As a corollary, we prove a randomized version of Aaronson-Ambainis Conjecture for total symmetric Boolean functions in the regime where the success probability of algorithms can be arbitrarily close to 1/2. iii) We present polynomial equivalences for several fundamental complexity measures of partial symmetric Boolean functions. Specifically, we first prove that for certain partial symmetric Boolean functions, quantum query complexity is at most quadratic in approximate degree for any error arbitrarily close to 1/2. Next, we show exact quantum query complexity is at most quadratic in degree. Additionally, we give the tight bounds of several complexity measures, indicating their polynomial equivalence.
Early in 1992, Deutsch-Jozsa algorithm computed a symmetric partial Boolean function with a single quantum query, and thus achieved the best separation between classical deterministic and exact quantum query complexity. Recently, it was clarified that all symmetric partial Boolean functions with a single quantum query can be computed exactly by Deutsch-Jozsa algorithm. For the general partial Boolean functions with a single quantum query, the latest characterizations is complex and not very satisfactory. Based on this, this paper proves and discovers three new results: (1) Under a new equivalence, each partial Boolean function with a single quantum query can be transformed to a simple partial Boolean function whose polynomial degree is just one; (2) For partial Boolean functions up to four bits, there are only 10 non-trivial partial Boolean functions with a single quantum query; (3) For each quantum 1-query algorithm with undefined measurement, there exists a constructive method for finding out all partial Boolean functions that can be computed exactly by the algorithm.
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.
We study how large the certificate complexity C(f) of a total Boolean function can be relative to its randomized and quantum query complexities. We construct a total Boolean function f whose randomized query complexity with one-sided error satisfies R1(f)=Θ(C(f)). This separation is optimal even when two-sided error is allowed.
From this construction, we obtain another total Boolean function F with bounded-error quantum query complexity Q(F)=O(C(F)1/4), attaining the general quartic bound up to polylogarithmic factors. For the same function, both exact and zero-error quantum query complexities are O(C(F)). We also prove matching lower bounds for these two measures on F.
Certificate complexity (C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity (D) and other query models such as bounded-error randomized and quantum complexity (R,Q), but not as well for quantum zero-error (Q0) and exact query complexity (QE), where there is no agreed-upon certificate 'object' (even for Q). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of C,RC (randomized certificate complexity) and QC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on QE and Q0, the quantum analogues of D and R0, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for Q0, but rational degree and Q are asymptotically smaller.