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