3
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ 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. $\endgroup$
    – kludg
    Commented Nov 6, 2019 at 8:49
  • $\begingroup$ In addition, brute force matrix multiplication has a much greater time complexity. $\endgroup$
    – Sanchayan Dutta
    Commented Nov 6, 2019 at 9:49
  • $\begingroup$ @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? $\endgroup$
    – bipul kalita
    Commented Nov 6, 2019 at 10:16
  • $\begingroup$ @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. $\endgroup$
    – kludg
    Commented Nov 6, 2019 at 10:46
  • $\begingroup$ @kludg thank you so much for your clarification . I really thought about Vonn Neumann arch . $\endgroup$
    – bipul kalita
    Commented Nov 6, 2019 at 11:19

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – bipul kalita
    Commented Nov 7, 2019 at 11:53
  • $\begingroup$ @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. $\endgroup$
    – Jonathan Trousdale
    Commented Nov 7, 2019 at 13:11
2
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ " 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. $\endgroup$
    – bipul kalita
    Commented Nov 6, 2019 at 11:55
  • $\begingroup$ 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. $\endgroup$
    – Martin Vesely
    Commented Nov 6, 2019 at 12:09
  • $\begingroup$ 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? $\endgroup$
    – bipul kalita
    Commented Nov 6, 2019 at 12:33
  • $\begingroup$ Yes, you are right. You can set the probability that register collapses to some state after measurement with quantum gates. $\endgroup$
    – Martin Vesely
    Commented Nov 6, 2019 at 14:19
  • $\begingroup$ 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. $\endgroup$
    – Martin Vesely
    Commented Nov 6, 2019 at 14:28

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.