The Most Important Gates in Quantum Computing Explained

Key Takeaways

The question I probably spend the most time answering in my job is, how does a quantum computer actually work? It's a deep question and a very fair one. One thing that surprises people is that both classical and quantum computers use gates to process information. Now, every program, both classical and quantum, uses gates as building blocks. And a gate is simply something that is an instruction that changes the state of information. Classical gates change bits. Quantum gates, on the other hand, change qubits. For example, the not gate in classical computing changes the zero to a one and the one to the zero. Simple. But quantum gates are a little bit different. And today we're going to focus on a few key ones. Together, they create what makes quantum computing so special. First, we're going to talk about something called the Hadamard gate. Now, the Hadamard gate is related to a quantum phenomena called superposition. Now, superposition means that a qubit can exist in multiple states at once until it is measured. In quantum mechanics, we use something called Dirac notation. So, when we write classical states in this language, they look like this: zero and one. An equal superposition of these two states looks like this: 1 over root 2 zero plus one. And this coefficient matters a lot. When you square it, you get 1/2. And if you distribute that, you get 1/2 zero, 1/2 one, which means that the probabilities of measuring both zero and one are both 50% which add up to a total of one. Now, let's connect this to linear algebra. In the language of linear algebra, zero looks like this. And one looks like this. These are vectors. If the states are vectors, that means that gates have to be matrices. And the most important single qubit gate is the Hadamard gate, as I said. The Hadamard gate looks something like this. 1 over root 2 1 1 1 -1 So, now let's work through some of this math and make sure that we actually get a superposition when we apply the Hadamard gate to one of our two vectors. So, let's pick zero. Let's apply Hadamard to the state zero. And what that looks like is 1 over root 2 1 1 1 -1 multiplied by 1 and 0. So, if you've never multiplied a vector in a matrix before, it's very easy. You simply look at the column here and you multiply it by the row here to get the component which goes in the top. So, here that would be one, it's just a dot product, and the same down here. One again. And we can't forget the coefficient 1 over root 2. So, this is what we get when we multiply the H acting on the zero gate or the zero state. And if we want to rewrite that in terms of Dirac notation, we would get 1 over root 2 zero plus one. So, that's the exact equal weighted superposition that I showed you at the beginning. So, with just one Hadamard gate, we are able to create superposition. And that's the first quantum phenomenon. Now, let's talk about the second quantum phenomena. It's called entanglement. Now, entanglement means that two qubits share one unified state. Measure one and you instantly know the state of the other, no matter the distance. The gate that creates entanglement is called the CNOT gate. And remember, it's a matrix, and it looks something like this. So, the first thing you'll notice is that the CNOT gate, unlike the Hadamard gate, is a 4 by 4 matrix, which means it acts on two qubits simultaneously, where the Hadamard gate only acted on one. And we say that the CNOT gate flips the target qubit only when the control qubit, or the first qubit, is in state one. So, now let's work through the math and actually see how the CNOT gate creates entanglement. The first thing we'll actually have to do is create a superposition state again, which means we'll need to act with the Hadamard gate on two qubits this time to make sure that they're both in superposition and in the ground state. So, we'll start with them both being in the ground state and we'll expand our Hadamard gate so that it's a 4 by 4 matrix. And the way that we can do that is like this. So, you'll notice the Hadamard gate, which we had before, still lives in the upper and lower quadrants, and we just put zeros everywhere else. And this assures that we're creating a superposition on the first qubit, but leaving the other one alone. And if we work through the math, you'll also see to get the state written in 4 by 4 language, the 0 0 state looks like this, and we can multiply this across. Again, if you have never worked through matrix multiplication before, you just take this column and you multiply it by each of these four vectors, and that gives you the corresponding digit. So, now this works out to 1 over root 2 1 1 0 0. But, we're not done. We still have to apply the CNOT gate. So, we'll multiply the CNOT gate by the state that we just created here. So, we write our CNOT matrix. Can't forget the root 2. Do all that math again, and what you'll actually see, multiplying each of these four rows by this vector, is that we end up with this equation. Which is actually a really famous equation, one of the most famous in all of physics. This is called a Bell state. It's named after John Bell, and he showed something extraordinary. He showed that if quantum mechanics is correct, the universe cannot obey local realism, which means that either things have definite properties regardless of if you are looking at them or not, and things can't go faster than the speed of light. So, in quantum mechanics, one of those two things cannot possibly be true. So, we usually say the speed of light is the one that we hold constant, but in quantum mechanics, states do not have definite properties until you measure them. So, that's pretty extraordinary. And what's also pretty extraordinary is that we have created this Bell state. We've created superposition and entanglement with just two gates. But now, here's the final twist. Both the Hadamard gate and the CNOT gate belong to something called the Clifford group. They feel deeply quantum, right? They are creating superposition, entanglement. However, the Clifford group of gates are not enough to make something that a classical computer can't also simulate. This is known as the Gottesman-Knill theorem. It says, "Clifford only circuits are actually classically tractable." So, what's missing here? The answer is phase, specifically the T gate. Now, the T gate is really small. And it looks pretty insignificant if I'm being honest. This is what it looks like. All it does is it rotates one by a phase of e to the i pi over 4, and doesn't change anything else. It doesn't change probabilities, it doesn't change measurements directly, it only changes the phase. But that tiny phase somehow still changes everything. And with T gates, states become harder to compress because it adds an additional dimension to the zero and the one states, even if they're in a superposition. The simulation costs can then explode exponentially. And so, things are no longer classically tractable. The Clifford plus the T gates creates universality, which means that we can approximate any quantum evolution that could be created in nature with these gates. This small phase rotation is really the crack in the classical world. So, with phase, we unlock universality. We unlock everything that nature allows. And it turns out at the end of the day, the universe is more than just zeros and ones.