OR (the long way)

It’s funny how we hit upon new things in roundabout ways. Some random thought prompted me to do an Internet search for ‘order finding’. Many of the search results related to quantum computing and some of these mentioned a logic element called the ‘Toffoli’ gate. Although I was familiar with the common logic gates AND, OR, NOT, XOR, etc., I had never heard of Toffoli. At first I had trouble remembering the name and how to spell it. Then I thought of ‘toffee’ and memorized that the name has two ‘f’s, two ‘O’s, and one ‘l’.

The Toffoli gate is sometimes also called the C-C-gate, where the letter ‘C’ stands for the word ‘controlled’. However, I will stick with ‘Toffoli’ in this story. It is easy to understand the specific logic function that the Toffoli gate performs. The gate has three inputs, which are typically labelled A, B, and C. It also has three outputs, whereas common ordinary logic gates have one output. Toffoli outputs may similarly be labelled P, Q, and R. The interesting one is R, because P=A and Q=B, by definition. Output R is like an inverter (logical NOT), except that it only inverts the C input if both A and B are true. In shorthand R = not C if both A and B are true; otherwise R = C. This statement can be expressed in a simple mathematical way, but is easier to understand in words, I think.

In the table reproduced above, ‘1’ stands for true and ‘0’ for false, as is the usual convention. (Similarly, in electronic logic circuits, + is usually true, and – is false.) Notice that in the first two rows, both A and B are true and R is not C, while in the remaining rows either A or B or both are false, and R = C.

The reason Toffoli gates are of interest to scientists is due to a property that I will gloss over. They are invertible. If you know the outputs, you can deduce what the inputs are. This feature is not shared by some ordinary gates. For example, if the output of an AND gate is true, you know all the inputs must have been true, but if the output is false, you cannot deduce which inputs were false, since any one of them being false would render the output false. One is inclined to think that of course the Toffoli gate is invertible, because of the cheat that copies A and B inputs to the P and Q outputs. That is true, but in the quantum world things are messy, and since I don’t understand that world I will have to take the scientists’ word for how being invertible causes entropy to increase, and is otherwise a commendable thing.

A second crucial property ensures the Toffoli gate’s interest to researchers: ANY logic function can be expressed as a combination of Toffoli gates! To prove this statement it is only necessary to show that AND, OR, and NOT can be so expressed. It has long been proven that any logic function can be expressed as a function of these three elementary ones. NOT is trivial, of course. Let ‘T’ stand for the Toffoli operator: not C = T(1, 1, C). The other two are also easy, but require more than one Toffoli gate to implement.

The Toffoli gate can be modelled using ordinary gates. The Logic Circuit Designer diagram above depicts two gates AND (top left) and XOR (bottom right), and their interconnections. [XOR means either A or B but not both.] Now, commonly available 2-input AND gates and 2-input XORs are packaged in sets of four. That is to say, each integrated circuit (chip) contains four gates. So on contemplating the simple diagram above I thought of assembling four Toffoli gates using just two ICs, with pin headers for inputs and LEDs to indicate both input and output states. The idea was that with four gates it would be possible to model an AND gate or an OR gate, in other words to demonstrate the universality claim in an actual circuit.

Not long ago I asked a person who had taught electronics in a technical college, what sorts of lab exercises his students were required to do as part of their coursework. His reply surprised me. The labs are all simulations. The students don’t solder anything, or even put together breadboard circuits. They interact with circuits using computer software, first constructing diagrams, and afterward defining parameters that are needed to exercise the circuits, the same as if they were real. —Logic circuits are particularly easy to simulate (or so it seems). Pencil and paper suffice to trace logic levels in simple circuits. They are just algebra, after all.

Logism is a great (free) tool for designing and simulating logic circuits. After diagramming one Toffoli gate with configurable inputs, it was possible to copy/paste the composite diagram a couple of times, and then connect the three identical gates to function as a single 2-input OR gate. In the illustration above, the first OR input is set to false (0), and the second to true (1). The output is of course true (rightmost blue LED). Now, I don’t mean to suggest that a physical demonstration is more persuasive than the corresponding Logism simulation, or more persuasive than working through the logic expression with pencil and paper would be. It is not. However, the photo at the top of this page captures what is perhaps a more vivid demonstration of the exact same circuit as in the Logism simulation. Even the LED colors are the same!

In the photo, the third Toffoli gate from left is not involved. Its A, B, and C inputs were set to false (black plug-in wires) so that the indicator LEDs for that gate would be OFF. Each of the two leftmost gates performs R = T(1, 1, C) = ~C (not C). The final rightmost gate’s A and B inputs receive the R outputs of the first two gates, while the C input of this gate is set to true (1). If C1 represents input variable a and C2 represents variable b, the rightmost gate preforms T(~a, ~b, 1), which is the same as a ⋁ b.

Constructing the physical model was fun but at the same time tedious, in part because I had selected a prototype circuit board that has only 24 × 18 holes. Several of the current limiting resistors had to be soldered on the underside of the board. Similarly, about half the connecting wires are on the bottom. The left IC (type 7408) consists of four AND gates and the right IC (type 7486) contains four XORs. The four Toffoli gates are arranged in vertical columns left to right. In each column the topmost 3-hole pin header corresponds to the inputs A, B, C, and the bottom pin header to the outputs P, Q, and R. Red LEDs indicate states of the A inputs; green LEDs the states of B inputs; and blue LEDs (the larger ones) indicate the ‘R’ output of each gate. Illuminated stands for true, and not illuminated means false.

Just to be clear, ‘real’ Toffoli gates are not made from ordinary TTL gates. Best I can tell they are combinations of quantum dots or some other arcane sub-microscopic thing. The physical model described above is just that, a model. By connecting the leftmost blue and yellow wires, inputs a (C1) and b (C2), alternately to 1 (+) and 0 (–) it is possible to demonstrate that in every case the rightmost blue LED represents the logical OR of a and b, illuminating when either a or b or both are true, and remaining dark when both are false. Of course, the same is more easily demonstrated by toggling pins in Logism. In the simulation below, both inputs are set to false, which causes the OR output to be false, in what surely seems a convoluted way.

Project descriptions on this page are intended for entertainment only. The author makes no claim as to the accuracy or completeness of the information presented. In no event will the author be liable for any damages, lost effort, inability to carry out a similar project, or to reproduce a claimed result, or anything else relating to a decision to use the information on this page.