The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two $n$-bit symmetric functions $\text{MOD}_m^n:\{0,1\}^n \rightarrow \{0,...,m-1\}$ and $\text{EXACT}_{k,l}^n:\{0,1\}^n \rightarrow \{0,1\}$, which are defined as $\text{MOD}_m^n(x) = |x| \bmod m$ and $ \text{EXACT}_{k,l}^n(x) = 1$ iff $|x| \in \{k,l\}$, where $|x|$ is the number of $1$'s in $x$. Our results are as follows: i) We present an optimal quantum algorithm for computing $\text{MOD}_m^n$, achieving a query complexity of $\lceil n(1-\frac{1}{m}) \rceil$ for $1 < m \le n$. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map $\{0,1\}^n$ to a finite set $X$ is less than $n$. ii) When $l-k \ge 2$, we give an optimal exact quantum query algorithm to compute $\text{EXACT}_{k,l}^n$ for the case $k=0$ or $k=1,l=n-1$. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.
On the exact quantum query complexity of MODmn and EXACTk,ln
The query model has generated considerable interest in both classical and quantum computing communities. Typically, quantum advantages are demonstrated by showcasing a quantum algorithm with a better query complexity compared to its classical counterpart. Exact quantum query algorithms play a pivotal role in developing quantum algorithms. For example, the Deutsch-Jozsa algorithm demonstrated exponential quantum advantages over classical deterministic algorithms. As an important complexity measure, exact quantum query complexity describes the minimum number of queries required to solve a specific problem exactly using a quantum algorithm. In this paper, we consider the exact quantum query complexity of the following two n-bit symmetric functions MODmn:{0,1}n→{0,...,m−1} and EXACTk,ln:{0,1}n→{0,1}, which are defined as MODmn(x)=∣x∣modm and EXACTk,ln(x)=1 iff ∣x∣∈{k,l}, where ∣x∣ is the number of 1's in x. Our results are as follows: i) We present an optimal quantum algorithm for computing MODmn, achieving a query complexity of ⌈n(1−m1)⌉ for 1<m≤n. This settles a conjecture proposed by Cornelissen, Mande, Ozols and de Wolf (2021). Based on this algorithm, we show the exact quantum query complexity of a broad class of symmetric functions that map {0,1}n to a finite set X is less than n. ii) When l−k≥2, we give an optimal exact quantum query algorithm to compute EXACTk,ln for the case k=0 or k=1,l=n−1. This resolves the conjecture proposed by Ambainis, Iraids and Nagaj (2017) partially.
The query model (or black-box model) has attracted much attention from the communities of both classical and quantum computing. Usually, quantum advantages are revealed by presenting a quantum algorithm that has a better query complexity than its classical counterpart. For example, the well-known quantum algorithms including Deutsch-Jozsa algorithm, Simon algorithm and Grover algorithm all show a considerable advantage of quantum computing from the viewpoint of query complexity. Recently we have considered in (Phys. Rev. A. {\bf 101}, 02232 (2020)) the problem: what functions can be computed by an exact one-query quantum algorithm? This problem has been addressed for total Boolean functions but still open for partial Boolean functions. Thus, in this paper we continue to characterize the computational power of exact one-query quantum algorithms for partial Boolean functions by giving several necessary and sufficient conditions. By these conditions, we construct some new functions that can be computed exactly by one-query quantum algorithms but have essential difference from the already known ones. Note that before our work, the known functions that can be computed by exact one-query quantum algorithms are all symmetric functions, whereas the ones constructed in this papers are generally asymmetric.
The Deutsch-Jozsa algorithm is one of the first examples of a quantum algorithm that is exponentially faster than any possible deterministic classical algorithm. It was proposed by Deutsch and Jozsa in 1992 with improvements by Cleve, Ekert, Macchiavello, and Mosca in 1998. The Deutsch-Jozsa problem is a promise problem and we can equivalently describe it as a partial function ${\text{DJ}}_{n}^{0}:{{0,1}}^{n}\ensuremath{\rightarrow}{0,1}$ defined as DJn0(x)=1 for ∣x∣=n/2,DJn0(x)=0 for ∣x∣=0,n, and it is undefined for the rest of the cases, where n is even, and ∣x∣ is the Hamming weight of x. The optimal quantum algorithm needs only one query to compute DJn0 but the classical deterministic algorithm requires ${2}^{n\ensuremath{-}1}+1$ queries to compute it in the worse case. In this article, we generalize the Deutsch-Jozsa problem as DJnk(x)=1 for ∣x∣=n/2,DJnk(x)=0 for ∣x∣ in the set ${0,1,...,k,n\ensuremath{-}k,n\ensuremath{-}k+1,...,n}$, and it is undefined for the rest of the cases, where $0\ensuremath{\le}k<n/2$. In particular, we give and prove an optimal exact quantum query algorithm with complexity k+1 for computing the generalized Deutsch-Jozsa problem DJnk. It is clear that the case of k=0 is in accordance with the Deutsch-Jozsa problem. Also, we give a method for finding the approximate and exact degrees of symmetric partial Boolean functions.
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].
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.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.
Deutsch–Jozsa problem (D–J) has exact quantum 1-query complexity (“exact” means no error), but requires super-exponential queries for the optimal classical deterministic decision trees. D–J problem is equivalent to a symmetric partial Boolean function, and in fact, all symmetric partial Boolean functions having exact quantum 1-query complexity have been found out and these functions can be computed by D–J algorithm. A special case is that all symmetric Boolean functions with exact quantum 1-query complexity follow directly and these functions are also all total Boolean functions with exact quantum 1-query complexity obviously. Then there are pending problems concerning partial Boolean functions having exact quantum 1-query complexity and new results have been found, but some problems are still open. In this paper, we review these results regarding exact quantum 1-query complexity and in particular, we also obtain a new result that a partial Boolean function with exact quantum 1-query complexity is constructed and it cannot be computed by D–J algorithm. Further problems are pointed out for future study.