[denimalpaca]

I took a grad-level quantum computing class which I didn't quite have the physics background for, and the lecture that lost me, about 3 weeks in, was on the different kinds of physical gates quantum computers use.

My recollection is that there were 3 necessary gates for a quantum functionally complete set: One gate was classically functionally complete, the other two are where I got lost. Can you explain like I'm 5 (or explain like I'm an undergrad with minimal QM knowledge) what these other gates are doing?

Thanks!

[ScottAaronson]

Actually, if you already have a classically functionally complete gate (say, the Fredkin or Toffoli gates), then you only need one other gate to get a functionally complete set for quantum computing. This one other gate could be the Hadamard, which I discussed in other answers. The Hadamard gate is needed to put your machine into a superposition of states, and then also to create interference between the different branches of the superposition. Of course, if you have no superposition and no interference, then it isn't much of a quantum computer!

If your question was instead to explain the concepts of superposition and interference themselves, then unfortunately that would take more time. However, you could try some essays that I wrote a while ago

https://www.scottaaronson.com/writings/highschool.html

https://www.scottaaronson.com/blog/?p=208

in addition to the resources that have been linked to elsewhere on this thread.