Trade off between time and query complexity Working directly with time complexity or circuit lower bounds is scary. Hence, we develop tools like query complexity (or decision-tree complexity) to get a handle on lower bounds. Since each query takes at least one unit step, and computations between queries are counted as free, time complexity is as at least as high as query complexity. However, can we say anything about the separations? 

I am curious about work in the classical, or quantum literature, but provide examples from QC since I am more familiar.

Some famous algorithms such as Grover’s search and Shor’s period finding, the time complexity is within poly-logarithmic factors of the query complexity. For others, such as the Hidden Subgroup Problem, we have polynomial query complexity, yet polynomial time algorithms are not known.

Since a gap potentially exists between time and query complexity, it is not clear that an optimal time complexity algorithm has to have the same query complexity as the optimal query complexity algorithm.


  Are there examples of trade-offs between time and query complexity?


Are there problems where the best known time complexity algorithm has a different query complexity than the best known query complexity algorithm? In other words, can we perform more queries to make the between-query operations easier? 

Or is there an argument that shows that there is always a version of an asymptotically optimal query algorithm having an implementation with asymptotically best time-complexity?
Here's an attempt at creating an artificial function with the following property:


The problem can be solved with $O(\log n)$ queries, but requires $\exp(n)$ time.
The problem can be solved with $O(n)$ time but that requires $O(n)$ queries


Let the input size be $n + \log n$. Let the first $\log n$ bits (let's call this string x) encode the input to a problem complete for EEXP. The next $n$ bits (let's call this string y) have the property that they are all zero if and only if x is a NO instance of the EEXP-complete problem.

In words, the first $\log n$ bits encode a hard problem, and the next $n$ bits give you a clue about the solution of the problem. However, to figure out the solution by looking at the $n$ bit string you make $\Omega(n)$ queries.

So this problem can be solved by either reading only the first $\log n$ bits and spending exp(n) time or by reading $n$ bits and using only linear time.

The same function goes through for quantum query complexity.. insert square root signs where necessary.