We study the probability of making an error if, by querying an oracle a fixed number of times, we declare constant a randomly chosen n-bit Boolean function. We compare the classical and the quantum case, and we determine for how many oracle-queries k and for how many bits n one querying procedure is more efficient than the other.
Our problem is to evaluate a multi-valued Boolean function F through oracle calls. If F is one-to-one and the size of its domain and range is the same, then our problem can be formulated as follows: Given an oracle f(a,x):{0,1}n×{0,1}n→{0,1} and a fixed (but hidden) value a0, we wish to obtain the value of a0 by querying the oracle f(a0,x). Our goal is to minimize the number of such oracle calls (the query complexity) using a quantum mechanism. Two popular oracles are the EQ-oracle defined as f(a,x)=1 iff x=a and the IP-oracle defined as f(a,x)=a⋅xmod2. It is also well-known that the query complexity is Θ(N) (N=2n) for the EQ-oracle while only O(1) for the IP-oracle. The main purpose of this paper is to fill this gap or to investigate what causes this large difference. To do so, we introduce a parameter K as the maximum number of 1's in a single column of Tf where Tf is the N×N truth-table of the oracle f(a,x). Our main result shows that the (quantum) query complexity is heavily governed by this parameter K: (i) The query complexity is Ω(N/K). (ii) This lower bound is tight in the sense that we can construct an explicit oracle whose query complexity is O(N/K). (iii) The tight complexity, Θ(KN+logK), is also obtained for the classical case. Thus, the quantum algorithm needs a quadratically less number of oracle calls when K is small and this merit becomes larger when K is large, e.g., logK v.s. constant when K=cN.
We study randomized and quantum query (a.k.a. decision tree) complexity for all total Boolean functions, with emphasis to derandomization and dequantization (removing quantumness from algorithms). Firstly, we show that D(f)=O(Q1(f)3) for any total function f, where D(f) is the minimal number of queries made by a deterministic query algorithm and Q1(f) is the number of queries made by any quantum query algorithm (decision tree analog in quantum case) with one-sided constant error; both algorithms compute function f. Secondly, we show that for all total Boolean functions f holds R0(f)=O(R2(f)2logN), where R0(f) and R2(f) are randomized zero-sided (a.k.a Las Vegas) and two-sided (a.k.a. Monte Carlo) error query complexities.
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 study the quantum query complexity of the Boolean hidden shift problem. Given oracle access to f(x+s) for a known Boolean function f, the task is to determine the n-bit string s. The quantum query complexity of this problem depends strongly on f. We demonstrate that the easiest instances of this problem correspond to bent functions, in the sense that an exact one-query algorithm exists if and only if the function is bent. We partially characterize the hardest instances, which include delta functions. Moreover, we show that the problem is easy for random functions, since two queries suffice. Our algorithm for random functions is based on performing the pretty good measurement on several copies of a certain state; its analysis relies on the Fourier transform. We also use this approach to improve the quantum rejection sampling approach to the Boolean hidden shift problem.