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.
- $n$ qubits is not the same as $n$ classical bits. They require exponentially more information to simulate.
- 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?