## Friday, 6 September 2013

### Query Complexity

The previous section on time complexity concerned itself specifically with the total amount of steps or gates in a circuit that are needed to explicitly compute some algorithm. Generally, algorithms consists of collections of multiple steps, and these steps may themselves be thought of as sub-algorithms with sub-steps that comprise the total algorithm. Instead of directly inquiring about the total number of steps required to compute the whole algorithm, it may be of interest to simply ask how many times a certain sub-routine needs to be performed. This is the objective of query complexity, which counts the number of \emph{queries}, or evaluations, of some function of the form $f:\{0,1\}^n\rightarrow\{0,1\}$ that are needed to solve some problem. By indexing each bitstring $\omega\in\{0,1\}^n$ as $x_i$, with $i\in\{1,2,3,...N\}$ where $N=2^n$, the information needed to specify this function can be encoded in a bitstring $X=X_1X_2...X_N\in\{0,1\}^N$ that satisfies $X_i=f(x_i)$ for all $i\in\{1,2,3,...N\}$. A query is an evaluation of $f(\omega)\in\{0,1\}$ for some bitstring $\omega\in\{0,1\}^n$, or equivalently can be thought of as accessing the value of some bit $X_i$ of the bitstring $X$.

Queries can also be made to a more general function of the form $f':\{0,1\}^n\rightarrow\{0,1\}^m$. In which case $f'(\omega)\in\{0,1\}^m$ is some bitstring $X'_\omega$ of length $m$. Then the function $f'$ can be though of as encoding some larger bitstring $X'=X'_1X'_2...X'_N\in\{0,1\}^{Nm}$, where each $X'_i\in\{0,1\}^m$. However, note that making queries to $f'$ can be though of as making queries to $N$ other functions of the form $f_i:\{0,1\}^n\rightarrow\{0,1\}$ each encoding the bitstring $X'_i$. Therefore, making general queries of the function $f'$ can be done by making a query to each of the functions $f_i$ for $1\leq i\leq N$. Hence, we can limit the discussion of query complexity to the context of function of the form $f:\{0,1\}^n\rightarrow\{0,1\}$.

Making queries to some function $f:\{0,1\}^n\rightarrow\{0,1\}$, or bitstring $X=X_1X_2...X_N\in\{0,1\}^N$ representing the function, can be incorporated into the circuit model by defining a gate called a black-box. This black-box is defined as the gate that implements $f$ by taking some bitstring $x_i\in\{0,1\}^n$ as input and outputting $f(x_i)=X_i$. In this black-box model, we are not necessarily concerned with the details actually needed to implement the black-box in terms of other logical operations. Instead, we are able to assume that such a gate is given and able to omnisciently provide answers to any query made in just a single evaluation of the black-box. As the input for a problem in the time complexity context, we are given some bitstring of length $n$ and determine the size of a circuit needed in terms of $n$. In the context of the black-box model, instead of a bitstring a black-box computing some function $f$ is provided and the objective is to determine the number of queries made to the black-box. Sometimes, the black-box is called an Oracle and queries are phrased as making Oracle calls.

The query complexity of an algorithm in the black-box model is the number of queries needed to successfully complete the algorithm by learning some property of the function encoded by the black-box. The query complexity is a useful measure for an algorithm because it helps establish lower bounds on the actual complete computational complexity of an algorithm. Suppose the amount of queries needed in some algorithm is given by some function $Q(n)$. Now suppose that the hidden details describing the workings of the black-box are made transparent and turned into a white-box, which is an explicit circuit for the construction of the black-box. Moreover, suppose that the size of the white box is given by some function $R(n)$, and that our algorithm under consideration requires $S(n)$ more steps in addition to the queries needed in the algorithm. Then the total time complexity of the algorithm can be described as some function of the form $T(n)=Q(n)R(n)+S(n)$. If for instance all of the functions $Q(n),R(n)$, and $S(n)$ are  bounded above by some polynomials, then it follows that $T(n)$ itself will be bounded by some polynomial. If instead only $R(n)$ and $S(n)$ happened to be bounded above by some polynomials, and the amount of queries $Q(n)$ grew exponentially in terms of $n$, then the total time complexity will not be polynomially bounded. In this case, an exponential lower bound in the black-box model implies a lower bound in the time complexity model.

Merely obtaining a polynomial upper bound on the query complexity of some algorithm does not necessarily imply a polynomial upper bound on the actual algorithm when the black-boxes are replaced with white-boxes. It may be the case that the size of the circuit represented by a white-box is exponential in size. Then regardless of the form of the query complexity given by $Q(n)$, the contribution given by $Q(n)R(s)$ in the time complexity will still be lower bounded by some exponential function. However, if a reasonable upper bound can be established in the black-box model, there may be hopes of achieving a reasonable bound in the computational complexity of some problem. Therefore, by simply focusing on the query complexity of an algorithm before getting into the details of how to rigorously represent the algorithm in terms of a complete circuit, insights can be obtained that expose how difficult a problem must be. Many of the quantum algorithms that will be presented were motivated with the block-box model. For many of the problems of interest, it can be shown that exponentially fewer queries are needed of some function in the quantum model when compared to the classical model.