How can we compare quantum algorithms against classical equivalents?

Question

I am trying to understand Deutsch-Jozsa algorithm. It is mentioned as the first algorithm to demonstrate exponentially faster performance compared to classical algorithms for the same problem.

What I find missing in most explanations is why the quantum algorithm can be analyzed using the same complexity analysis as that of classical algorithms. It doesn't seem like an apple to apple comparison to me.

More concretely:
1. Classical solutions require at-least $2^{n-1}+1$ evaluations of the black-box function where $n$ is the number of classical bits.
2. Deutsch-Jozsa algorithm requires a single evaluation of the black-box function. However, it takes as input $n$ qubits.

1. $n$ qubits is not the same as $n$ classical bits. They require exponentially more information to simulate.
2. The black-box function is not the same in both cases since one deals with classical bits whereas the other deals with qubits.

Considering we've changed the input as well as the function, how can we compare these two solutions and make the claim that one is exponentially faster than the other?

Answer 1

Scott Aarsonson answers your question. There is a difference between the relativized world where the models of computation we are studying have access to oracles and the unrelativized one where there are no oracles. When we claim that "One is exponentially faster than the other" in the Deutsch-Jozsa sense, we are saying that "One is exponentially faster than the other relative to an oracle".

Answer 2

Computational complexity is a concept used to analyze algorithms independently from the physical resources used to implement them. In computational complexity, we generally consider a number of input $n$ and we express the complexity by a function of the number of input $f(n)$, characterizing the resources needed for the computation, typically, time or space.

In quantum computing the inputs are qubits, and so complexity of an algorithm is a function of $n$, If we have $n$ qubits in input. The nature of the input does not influence the complexity of the algorithm. It is true that simulation of quantum computers has an exponential complexity for time and space resources on a classical computer but analysis of quantum algorithms are supposing the existence of an actual quantum computer.

Taking the case of the Deutsch-Jozsa algorithm, for $n$ qubits in input, we need $\mathcal{O(n)}$ gates, $\mathcal{O(n)}$ measurement as well and the application of an oracle, which I think also has $\mathcal{O(n)}$ complexity in time but that would ask for confirmation. Globally, we need $\mathcal{O(n)}$ operations. In the case of a classical computer we need $\mathcal{O}(2^n)$ operations so you can see that there's an exponential speedup for the quantum computer.

Of course complexity is concerned with the asymptotic behavior in the increasing number of inputs and a classical computer can perform better if we take practical consideration into accounts such as constant time needed for operations on small number of inputs, or the actual long time of preparation needed for qubits.

Another consideration for treating complexity in quantum computers is the need for additional qubits for error correcting codes. While it shouldn't influence the complexity in time it does influence the resources needed in space.

This wikipedia article mentions that the Shor's algorithm without correcting codes requires between $L$ and $L^2$ qubits for factoring a number with $L$ bits, but requires to multiply by another factor $L$ the number of qubits needed with quantum error correcting codes.