Query Complexity

List of Posts

Last time I posted, which was here, I talked about quantum computation and the need to prove how hard a given problem is to know how good quantum computers can be. As a side note, the question of what problems are hard and what are not is also an important and interesting problem in classical complexity, and we are interested in similar questions in quantum complexity too.

So, last time I said that the query model is the setting in which it is easiest to pose questions about quantum complexity, so let’s define what this model is and how we go about using it.

To better understand the query model, let’s start with the following statement (which we will encounter a lot in subsequent discussions) and deconstruct it.

There is a query algorithm which computes a function with bounded error using $t$ queries.

In the query model, the input is ‘hidden’ from the algorithm, and the algorithm can only access the input through an oracle. The oracle works in the following way. For simplicity, let the input be a string of zeros and ones of length $n$, and the algorithm wants to access a single bit in the input. The algorithm sends the location of this bit to the oracle along with some place where the oracle can write the result. This is called a query. The oracle then returns this bit to the algorithm.

The algorithm may take this input and process it, and the next query may be a result of the processing. In this processing however, the algorithm cannot access bits which have not been previously revealed.

As an aside, note what a ‘query’ to the oracle has to contain. First, if using the binary representation for numbers, we need to ‘ask’ the oracle for the $k^{th}$ position in the input string, so we need at least $log(n)$ bits to specify the position, since $k$ may be as big as $n$. Also, we need some place to write the value of the input string at that position, which may be counted as part of some ‘workspace’ that the algorithm has. Finally we have to have some place to store the output. Since we are considering Boolean functions with output being only a single bit, we only need to have one bit for that.

Note that we have not even mentioned the word ‘quantum’ in this discussion so far! Whatever we have said holds equally well for any kind of computing, classical or quantum.

Classical algorithms can be classified into deterministic, randomized and approximation algorithms.

• A deterministic algorithm outputs the correct answer everytime it runs.

• When randomized algorithm outputs an answer, the probability that this answer is correct is high, but if the answer is incorrect, it may be very far away from the actual answer. We can then run such an algorithm multiple times, thereby increasing the probability that we get the correct answer until it reaches close to 1. The algorithm may use random bits, and the probability being referred to above is calculated on the basis of these random bits. Bounded error means that the probability of the answer being correct is greater than a certain number (usually taken to be $\frac{2}{3}$).

• An approximation algorithm outputs something close to the correct answer everytime it runs.

The query complexity for an algorithm is the number of queries to an oracle needed by the algorithm to compute the function.

Talking about the query complexity for a function means the following : fix a domain (deterministic, randomized, approximation) and find the minimum number of queries required by an algorithm that computes the function among all algorithms of the chosen domain.

There may be situations in which we do not need to look at all the bits to compute the value of the function. For an easy example of this, consider a sorted list of zeros and ones, with the problem being to output the position of the first one. Using binary search, we only need to look at around $log(n)$ bits of the input to find out the required index and it can be proven that this is optimal. The goal in query complexity is the following: given a function, we want to find bounds on the number of queries that any algorithm computing the function makes to an oracle while still being able to compute the value of the function on the given input, in the domain that we choose (deterministic/randomized/approximation).

Note that so far we haven’t talked about quantum or classical computation at all! Whatever we have said holds equally true for classical and quantum computation. Now, let’s move into quantum query complexity. Now, quantum mechanics has an inherent randomness and in some sense this is what gives quantum computing its power. Therefore, it does not make a lot of sense to talk about deterministic quantum computation.

My work in particular is concerned with the query complexity of boolean functions : functions that take $0$s and $1$s as input and output $0$s and $1$s. Since the algorithms cannot output anything other than these two values, approximation algorithms are out of the picture so I will focus on randomized algorithms. In the classical case the randomness in randomized algorithms is due to the use of random bits, but in the quantum case the uncertainly lies in the quantum measurement process, and the probability calculation is based on the same.

The interesting thing about quantum query complexity is that quantum algorithms can query in superposition and thereby (very crudely speaking) get information about multiple bits in the input at once. This is in stark contrast to the query complexity in the classical domain where each query can get information about one bit in the input string. Therefore, questions about the query complexity in the quantum doman are interesting!

Proving such lower bounds on ‘interesting’ functions is even more interesting and happens to be the ultimate goal of my work. There are two interesting ways to do this, called the polynomial and adversary methods, which will be the subject of future posts. Stay tuned!