1
$\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$
6
  • $\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$ Commented May 11, 2020 at 2:48
  • $\begingroup$ Sorry for that, I just added which minute does the video talk about Deutsch Oracle $\endgroup$ Commented May 11, 2020 at 3:48
  • $\begingroup$ okay he's talking about the Deutsch algorithm, I'll answer. $\endgroup$ Commented May 11, 2020 at 3:54
  • 2
    $\begingroup$ what does the question body have to do with "supremacy", which is in the question title? $\endgroup$
    – DaftWullie
    Commented May 11, 2020 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
    Commented May 12, 2020 at 5:53

1 Answer 1

2
$\begingroup$

The video at 33:20 is talking about the Deutsch problem, which is a problem that a quantum computer can solve with only 1 query whereas a classical computer 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-Jozsa 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-Jozsa 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-Jozsa 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-Jozsa 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.

$\endgroup$

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.