In this chapter we investigate the complexity of C for various n and A. We consider not only the query complexity of C as defined in Chapter 3, i.e., the least m such that there exists a set X for which C ∈ FQ(m,X), but also the number of queries to A itself that are required to compute C . (Note that, numerically speaking, the former complexity cannot exceed the latter.)
In this chapter we investigate the complexity of C for various n and A. We consider not only the query complexity of C as defined in Chapter 3, i.e., the least m such that there exists a set X for which C ∈ FQ(m,X), but also the number of queries to A itself that are required to compute C . (Note that, numerically speaking, the former complexity cannot exceed the latter.)
We consider problems that can be solved by asking certain queries. The deterministic query complexity D(P,n) of a problem P is the smallest number of queries needed to ask in order to find the solution with an input of size n (in the worst case), while the non-deterministic query complexity D0(P,n) is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently, D(P,n) is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while D0(P) is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values, Dk(P,n) is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most k times. We give bounds on Dk(P,n) for various problems P.
We study the quantum query complexity of maximizing a non-negative submodular function, considering both the unconstrained setting and, for monotone functions, a cardinality constraint k on an n-element ground set. In the exact reversible digital value-oracle model, our unconstrained algorithm achieves an expected (1/2−ε)-approximation using only Oε(logn) queries. In contrast, any classical randomized algorithm that attains a fixed expected ratio above 1/4 requires Ω(n/logn) queries (Li, Feldman, Kazemi, and Karbasi, 2022), establishing an exponential separation in query complexity. For cardinality-constrained maximization, we give a bounded-error quantum algorithm that achieves a (1−1/e−ε)-approximation using Oε(min{n,n/k}) queries. When k=o(n), our algorithm achieves at least a quadratic speedup up to logarithmic factors over classical randomized algorithms (Mirzasoleiman, Badanidiyuru, Karbasi, Vondrák, and Krause, 2015; Peng and Rubinstein, 2025). Moreover, when k=cn for any fixed rational c<1−1/e−ε, the query complexity reduces to Oε,c(logn), yielding an exponential separation from the classical Ω(n/logn) lower bound (Li, Feldman, Kazemi, and Karbasi, 2022). We further prove quantum lower bounds of exp(Ω(ε2n)) queries for achieving a ratio beyond 1/2+ε without constraints, and exp(Ω(ε2k)) queries for exceeding 1−1/e+ε when k/n≤ε. These barriers demonstrate that quantum computation offers no exponential speedup at these approximation thresholds.
In the query model of multi-variate function computation, the values of the variables are queried sequentially, in an order that may depend on previously revealed values, until the function's value can be determined. The function's computation query complexity is the lowest expected number of queries required by any query order. Instead of computation, it is often easier to consider verification, where the value of the function is given and the queries aim to verify it. The lowest expected number of queries necessary is the function's verification query complexity. We show that for all symmetric functions of independent binary random variables, the computation and verification complexities coincide. This provides a simple method for finding the query complexity and the optimal query order for computing many functions. We also show that if the symmetry condition is removed, there are functions whose verification complexity is strictly lower than their computation complexity, and mention that the same holds when the independence or binary conditions are removed.
In this thesis we study various models of query complexity. A query algorithm computes a function under the restriction that the input can be accessed only by making probes to the the bits of the input. The query complexity of a function f is the minimum number of probes made by any query algorithm that computes f. In this thesis, we consider three different models of query complexity, (1) deterministic decision tree complexity (query complexity when the underlying algorithm is deterministic), (2) approximate decision tree complexity aka. property testing (query complexity when the underlying algorithm is probabilistic and only expected to ”approximately ” compute f) and quantum query complexity (query complexity when the underlying algorithm is allowed to make quantum queries). The main results in this thesis are: • We study the relation between deterministic decision tree complexity and other combinatorial measures of complexity measures like sensitivity and block sensitivity. We prove that for minterm-transitive functions the sensitivity is quadratically related to block sensitivity which is polynomially
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 $ \text{EXACT}_{k,l}^n(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.