How do we know a "quantum function call" is worth the same amount of time as a "classical function call?"

Question

In quantum and classical algorithms, we often need to do "function calls." Quantum algorithms such as Grover's algorithm or the Deutsch–Jozsa algorithm can take a fewer number of function calls than their classical counterparts, and this is often argued as a reason why these algorithms are more efficient. However, I see these arguments as having a gap.

My main question is, how do we know a "quantum function call" is worth the same amount of time as a "classical function call?"

For example, in an unstructured search problem, we have a function $f$ such that $f(x) = 0$ if $x$ is not a solution to our search problem and $f(x) = 1$ if $x$ is a solution to our search problem. In Grover's algorithm, we utilize an oracle $\hat{O}_{f}:|x\rangle\mapsto (-1)^{f(x)}|x\rangle$. Now we could imagine a scenario where an implementation of $\hat{O}_{f}$ that would require $N$ seconds. Meanwhile a classical call to $f$ for a single item might take $1$ second. In this scenario, Grover's algorithm would take $O(\sqrt{N})$ oracle calls, but the entire search would take $O(N\sqrt{N})$ seconds to complete, which is not faster than $O(N)$ seconds classically.

Answer 1

You are probably mixing two aspects. One is the actual complexity of an algorithm and second one is "auxiliary work", i.e. preparing the circuit, transpiling, setting qubits to initial state etc. On classical computer you also do not care about time to load data into RAM, set up registers in processor, compiling source code or interpreting scripts etc. You just care about actual number of operation needed to perform the algorithm. In assessing complexity of for example Grover algorithm you assume that your circuit is already prepared. Of course, there will be some auxiliary work which can a little bit hinder speed up provided by a quantum computer but this is a classical issue of difference between theory and practical application. See this paper Is Quantum Database Search Practical? for additional information on this issue.

Answer 2

We don't know whether one individual call to an oracle will take the same amount of time on a quantum computer as the same call would on a quantum computer. Indeed, I would bet that a quantum computer could take much longer, per oracle call, than a classical computer.

However, there is no reason to believe that the resources required per oracle call on a quantum computer scale as proposed.

That is, the statement:

Now we could imagine a scenario where an implementation of $\hat{O}_{f}$ that would require $N$ seconds,

is not clearly justified and is indeed hard to imagine. The conversion from a classical circuit realizing the oracle (using NAND gates and NOR gates etc.) to a quantum circuit realizing the oracle (using CNOT gates etc.) is very efficient, and does not grow with $N$.

This is why we speak of asymptotic complexity. For small $n$, certainly a classical computer should handily defeat a quantum computer. But eventually, the quantum computer wins out.

---

^{For Shor's algorithm, we are getting a better handle on that cross-over point; see this paper by Gidney and Ekerå.}