# How does Deutsch Oracle shows quantum supremacy?

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:

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?

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

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-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: