# Why is the Deutsch algorithm faster on a quantum computer?

I still don't understand what makes the Deutsch algorithm faster in a quantum computer. Why is it not same as in a classical computer? But this algorithm is just mathematics. All gates can be represented in a matrix.

Please, can someone explain this to me? What parts of this algorithm are better in a quantum computer, assuming only this Deutsch algorithm?

• In short, to emulate quantum register of $n$ qubits you need classical register of $2^n$ complex numbers, and to emulate $n\times n$ quantum gate you need $2^n\times 2^n$ complex matrix. Notice that classical sizes grow exponentially. Nov 6 '19 at 8:49
• In addition, brute force matrix multiplication has a much greater time complexity. Nov 6 '19 at 9:49
• @kludg oh so , it's like we have to mention all the possible states of any operation in a matrix to perform in classical computer , but in quantum it gives us only one state only when we measure it, right. So, we don't store the intermidiate states of any running algorithm in quantum computer, just we care about the final data only when we measure it. Am I right? Nov 6 '19 at 10:16
• @bipulkalita I think "we need to store intermediate results in classical computer and don't need in quantum computer" is wrong argument. I guess by "classical computer" you understand modern von Neumann architecture (CPU, Memory, etc), well, von Neumann computer stores intermediate results in memory, but classical computers are not necessarily von Neumann computers. Boolean circuits are also (classical) computers, and they have no memory, just inputs, boolean gates and outputs. Nov 6 '19 at 10:46
• @kludg thank you so much for your clarification . I really thought about Vonn Neumann arch . Nov 6 '19 at 11:19

Deutsch's algorithm is not faster on a quantum computer, Deutsch's algorithm is only possible on a quantum computer.

A classical computer cannot perform Deutsch's algorithm, it can only simulate Deutsch's algorithm. Forget about speed, more fundamental is that we are performing a type of computation that can never be performed, in any amount of time, by any classical system.

Consider the case of two possible evaluations, $$f(0)$$ and $$f(1)$$. In any classical computation these evaluations are mutually exclusive. We can design a classical system that evaluates $$f(0)$$ or $$f(1)$$ probabilistically to simulate Deutsch's algorithm, but any given evaluation is either $$f(0)$$ or $$f(1)$$. Evaluating one means we did not evaluate the other.

In contrast, Deutsch's algorithm is not evaluating $$f(0)$$ with some probability $$p$$ and $$f(1)$$ with probability $$1-p$$, this is only the outcome that we can simulate classically. In Deutsch's algorithm the two evaluations $$f(0)$$ and $$f(1)$$ exist simultaneously (in superposition) and interfere with each other.

I suggest forgetting about performance until you have a very clear understanding of the fundamental difference between a quantum algorithm and a classical simulation of a quantum algorithm. In other words, until you have convinced yourself that Deutsch's algorithm can never be performed by a classical computer.

• Yes, you are right. I still don't have the clear understanding. Hey, I have doubt, if a hadamard gate is performed on a single qubit |0> then why it results |0> if we perform hadamard one more time. Is not superposition mean that it's pure random? But it feels like superposition holds its initial state. Nov 7 '19 at 11:53
• @bipulkalita Superposition does not imply randomness. A wave function evolves deterministically (i.e., no randomness) regardless of superposition. When we perform a measurement, the definite state we observe is determined based on probabilities described by the wave function, and the post-measurement wave function is altered in accordance with the measured outcome. This is a very deep and unintuitive aspect of quantum mechanics known as the measurement problem. Nov 7 '19 at 13:11

On a classical computer, you can recycle memory, so there is no need for storing all intermediate results. The main source of the higher performance of quantum computers is the possibility to do an operation with all different values you can store in n q-bits register at once. However, this is not a case always. For example, the evaluation of Boolean function parity has the same complexity both on a classical and quantum computer.

• " possibility to do operation with all different values you can store in n q-bits register at once" <--but how does it make difference from digital registers/gates? Can you explain a little more please. Nov 6 '19 at 11:55
• In case of classical computers, you have to do a cycle through all possible values and perform some evaluation on them. Since a quantum register can be in all possible values in one time (i.e. the register is in superposition), you can perform the evaluation on all values at once. However, in practice, you have to repeat the calculation many times to get some reasonable distribution of results. But still, the quantum approach is more quick than classical one in many cases. Nov 6 '19 at 12:09
• oh no. I think I have less understanding with "superposition" now. So, if a register (say) is in superposition it has probabilities of collapsing to many values right. So the probability depends on input and operations performed with it! Is it correct? Nov 6 '19 at 12:33
• Yes, you are right. You can set the probability that register collapses to some state after measurement with quantum gates. Nov 6 '19 at 14:19
• However, turn back to Deutsch algorithm. At the beginning, the quantum register has all possible states equally probable because of Hadamard gates application. Then the examined function is applied and after another Hadard gates application we measures the result. See details here: en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm. In fact the described algorithm does the examination whether the function is constant or balanced in one step, you do not need to examine each input to function separately. Nov 6 '19 at 14:28