6
$\begingroup$

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.

$\endgroup$
4
  • 2
    $\begingroup$ are you asking specifically about the time cost oracles, or more generally about the cost of gates used in an algorithm? For the former, see also this related post: quantumcomputing.stackexchange.com/q/175/55 $\endgroup$
    – glS
    Mar 27, 2022 at 17:21
  • $\begingroup$ @glS I think I'm asking about the time cost of oracles (once they're implemented). $\endgroup$ Mar 27, 2022 at 17:22
  • 2
    $\begingroup$ Why would you expect it take $N$ seconds to call the oracle? The conversion from a classical oracle to a quantum oracle is very efficient and just replaces NAND gates etc. with CNOT gates etc. It could certainly take longer with a quantum oracle but it would still grow with $n$ in the same manner. $\endgroup$ Mar 28, 2022 at 2:50
  • 1
    $\begingroup$ @MarkS An example of an oracle that translates poorly is one that uses a lot of RAM, because RAM is a monster sized circuit when translated into the gate model. $\endgroup$ Mar 28, 2022 at 21:33

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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å.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.