0
$\begingroup$

I learnt from this lecture (at 33:20) that Deutsch Oracle is way faster on quantum computers than on classical computers. However, it seems to me that this is just due to smart structuring of input data, which is also doable on classical computers.

Thus, for me, the only way to accept that Deutsch Oracle is indeed faster on quantum computers is due to the fact that some of the following gates run much faster on quantum computers than being simulated on classical computers:

  1. Hadamard gate
  2. CNOT gate

So here's my questions, is the aformentioned statement true? If so, can you explain why some of the gates run faster on quantum computers? Also, which quantum mechanic principle was abused in this case?

$\endgroup$
  • $\begingroup$ Your link is to a 90 minute video. You do not tell us where they talk about the "Deutsch oracle". If they are talking about the oracle in Deutsch's algorithm, then the reason why it works is not because the Hadamard gate and CNOT gate are faster on qauntum computers than classical computers. It's because they make use of quantum superpositions in such a way that the Deutsch oracle computes the "sum" of $2^n$ inputs at the same time. $\endgroup$ – user1271772 May 11 at 2:48
  • $\begingroup$ Sorry for that, I just added which minute does the video talk about Deutsch Oracle $\endgroup$ – Wong Jia Hau May 11 at 3:48
  • $\begingroup$ okay he's talking about the Deutsch algorithm, I'll answer. $\endgroup$ – user1271772 May 11 at 3:54
  • 2
    $\begingroup$ what does the question body have to do with "supremacy", which is in the question title? $\endgroup$ – DaftWullie May 11 at 8:53
  • 1
    $\begingroup$ Quantum supremacy is a specific concept and you cannot use an oracle based algorithm to demonstrate it. Whether or not it’s obvious to you, your question should be making any connection clear; if there’s a key word in the title, one might reasonably expect it to recur in the question body. $\endgroup$ – DaftWullie May 12 at 5:53
1
$\begingroup$

The video at 33:20 is talking about the Deutsch problem, which is a problem that a quantum computer can solve with 1 query whereas a classical computer only needs 2 queries.

First of all, the quantum query is quite a lot more involved than doing a classical query, so doing 2 classical queries might be faster and easier than doing 1 quantum query, but a generalization of the Deutsch problem called the Deutsch-Josza problem, can be solved on a quantum computer with 1 query instead of $2^n$ on a classical computer, so let's continue.

You are asking whether or not the quantum computer performs better because of certain gates running faster than simulating them on classical computers:

Thus, for me, the only way to accept that Deutsch Oracle is indeed faster on quantum computers is due to the fact that some of the following gates run much faster on quantum computers than being simulated on classical computers:

  • Hadamard gate
  • CNOT gate

The answer, is that this is not the case.

  • First of all, there's no CNOT in the quantum-computer solution to the Deutsch-Josza problem.
  • Second, the way a classical computer solves this problem is not by simulating the Hadamard gates.

The reason why quantum computers can theoretically outperform classical computers for solving Deutsch-Josza problems, is because they can evaluate the mystery function for all possible inputs at the same time. Classical computers cannot do this, they have to evaluate the mystery function for all possible inputs separately. I hope this helps you, and if you still want to know more, I have provided a resource here for you to see every step of how the Deutsch-Josza problems are solved on quantum computers. Unfortunately you'd have to at least know some basics such as Dirac notation and matrix-vector arithmetic, but it is a worthwhile exercise to understand the protocol.

| improve this answer | |
$\endgroup$

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.