Generally, query complexity is thought of as a lower bound on time complexity. It might be true if data is read sequentially. However, in quantum computation, state preparation routines exist that take logarithmic time to prepare a state from classical data. This is one of the key reasons QML algorithms like HHL can claim exponential speed over their classical counter-part. Thus query complexity lower bounding time complexity seems to be false. Is there any formal result which states so under suitable conditions? As in the case of parallel queries, this is clearly false.

  • $\begingroup$ Welcome to cstheory.se . A formal result that states that time complexity can be below query complexity in some cases? Why aren't specific results of this enough to show this? $\endgroup$
    – Neal Young
    Jan 8 at 21:37
  • $\begingroup$ Hi Neal, I wanted to ask if there is any formal result which states that query-complexity lower bounds time-complexity, may be with some suitable assumptions. It seems not to be true in general, as you highlighted there can be specific example where time complexity is below query complexity. If you give me any such theorem or a concrete counter example, it would be helpful. $\endgroup$ Jan 9 at 3:38
  • $\begingroup$ Well, surely, with the standard definitions of worst-case time complexity as a function of input size, for, say, the standard sequential RAM model, if a problem has worst-case deterministic query complexity $q(n)$, and "query" is defined in such a way that a query takes at least constant time (e.g., reading a bit of the input), then any deterministic algorithm will have worst-case time complexity at least $\Omega(q(n))$, just because of the definitions and the fact that each query requires constant time. Are you asking whether something like this is published anywhere as a theorem? $\endgroup$
    – Neal Young
    Jan 9 at 20:12
  • $\begingroup$ Thanks for the answer, it clears my doubt that to formally state query complexity is lower bound to time complexity, I need to use the factors such as. sequential RAM, worst-case time complexity, worst-case query complexity, and deterministic computations. Yes, I was looking for such a theorem in the literature. But thanks anyway for stating it. $\endgroup$ Jan 10 at 10:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.