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?

  • $\begingroup$ You say "Considering we've changed the input as well as the function", but we haven't changed the function. It's the same function. What we have changed is using qubits instead of bits; which we have to or else we wouldn't be comparing classical computers with quantum computers. $\endgroup$ Feb 26 '20 at 22:12

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

  • $\begingroup$ Thanks for your response. It looks like I will need to first learn more about oracles, oracle separation as well as fundamentals of quantum complexity theory in order to fully understand Scott Aarsonson's answer. Would be great if you can point to any beginner-friendly resources for understanding these. Having said that, I think I get the intuitive idea that the theoretical exponential speedup is assuming certain conditions (such as an oracle). Thanks! $\endgroup$
    – rahulr92
    Feb 27 '20 at 21:49
  • $\begingroup$ Scott's lecture notes on this subject are good. $\endgroup$ Feb 28 '20 at 0:17

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.

  • $\begingroup$ Hi Nathan, thanks for your response. However, I still don't understand how complexities of algorithms across two fundamental different computational models can be compared. To make the question more explicit, instead of quantum computing, lets consider a new computational model that I call “x-computing”: 1. n x-bits can represent 2^n classical bit information 2. The fundamendal gates of an x-computer offers standard basic operations on these x-bits such as NOT as well as gates which can effect these x-bits in conjunction - x-Hamdard etc. (continued) $\endgroup$
    – rahulr92
    Feb 27 '20 at 19:47
  • $\begingroup$ Each computational step in the x-computer might be taking exponential hardware steps (implementation detail) to achieve the above steps. You can think of an x-computer as being very similar to a quantum-computing simulator. You could potentially implement Deutsch-Jozsa algorithm using this system faster than a classical computer - in terms of number of computational steps. Clearly, no-one would agree that an x-computer is exponentially faster than a classical computer. (continued) $\endgroup$
    – rahulr92
    Feb 27 '20 at 19:48
  • $\begingroup$ There is something different in case of quantum computers which helps us agree that they are faster, even when we have changed the fundamental units of operation (bits and gates). I am trying to understand precisely that difference. $\endgroup$
    – rahulr92
    Feb 27 '20 at 19:49

Your Answer

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

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