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?