What is a gate? (Part 1)

It's been a bit since my last "what is" post, but I'd like to return to talking about science by taking a pause from my build-up to quantum states and quantum computation to instead discuss something more classical: the notion of a logic gate.

One way of modeling classical computation is as a sequence of operations performed on some data. We can then consider each operation independently. Just as we can build up complicated equations from simple arithmetic operations, these computational operations, typically called gates, can be used to build up arbitrarily complicated computations.

Take a specific example, the NOT gate, also written ¬. This gate takes a bit and produced a bit with the opposite value. Since each bit can only have one of two possible values (either 0 or 1), we can completely specify the behavior of the NOT gate by listing what it does to each of these inputs. That is, if I tell you that ¬ 0 = 1 and that ¬ 1 = 0, then in principle, I have told you everything that there is to know about the NOT gate. If this reminds you of a basis, then your intuition serves you well— we will explore that connection more in due time.

For now, though, I would like to discuss a few more examples of gates: the AND and OR gates, often written as ∧ and ∨, respectively (if these symbols seem arcane, it may think of them in terms of set unions and intersections). Each of these gates takes two bits as inputs and produces one output. AND produces 1 if and only if both its inputs are 1 (1 ∧ 1 = 1, 0 ∧ 0 = 0 ∧ 1 = 1 ∧ 0 = 0), while OR produces 1 if and only if at least one input is 1 (0 ∨ 0 = 0, 0 ∨ 1 = 1 ∨ 0 = 1 ∨ 1 = 1). Finally, the XOR gate (short for exclusive or and written ⊕) returns 1 if and only if exactly one input is 1 (0 ⊕ 0 = 1 ⊕ 1 = 0, 0 ⊕ 1 = 1 ⊕ 0 = 1).

With these four gates, we can build up any arbitrarily complicated Boolean function; that is, a function from strings of bits to a single bit. Functions returning multiple bits can in turn be built up by representing each output bit as a Boolean function. We could actually do with less kinds of gates, but that's besides the point. Rather, the point is that together, NOT, AND, OR and XOR are universal for classical computation.

It takes some effort to prove this, but an example helps to make things concrete. The full adder circuit in particular can be used to add two one-bit numbers, and is built up entirely from two XOR gates, two AND and one OR gate, as shown in this circuit diagram from Wikipedia. These full adders in turn can be combined to add arbitrarily long integers. From addition, one can get to subtraction and multiplication, demonstrating the usefulness of the gate model in capturing arithmetic.

Even more compellingly, we can efficiently simulate Turing machines with these few gates, meaning that NOT, AND, OR and XOR are at least as expressive as Turing machines. Thinking about gates, then, is a powerful way of thinking about classical computation. As we shall see, this power carries very nicely to the quantum case as well.