sparse-dense by FoYo: Illustrating Fredkin gate in action with billiard balls

[Abstract] Prof. Chris Bernhardt's book [1] on quantum computing, Chapter 6, describes how to realize a Fredkin gate using virtual billiard balls. Fredkin's original idea is reminiscent of quantum (atomic, molecular) collisions, and is said to have influenced the view of quantum computers of the famous physicist Feynman. This article illustrates such a Fredkin gate. (This is a revised version of the previous report in Japanese.)

● What is Fredkin's gate?

This is a 3-input (x, y, z) 3-output logic gate announced by Edward Fredkin in 1982, and can be simply expressed as a logic function as follows:

F(0, y, z )=(0, y, z), F(1, y, z) = (1, z, y)

The first x is a control bit, so it appears as is at the first output. If x = 0, y and z are output as they are, and if x = 1, y and z are output after being exchanged. A simple calculation shows that it has the following characteristics:

It is a reversible logic gate. That is, the input can be reached from the output.
It is a universal logic gate. In other words, NOT, AND, and fan-out (input duplication function) can be created only with this Fredkin gate.
The number of 1s (True) in input and output is always equal. This corresponds to the fact that the number of billiard balls, which will be described later, is always equal between the input side and the output side.

● The originality of making a Fredkin gate with billiard balls

Fredkin showed how to create this gate using billiard balls. It uses ball-to-ball collision and reflection when it hits a corner mirror. However, assuming perfect elastic collision (no energy loss) and perfect matching of multiple balls in size, mass, speed, and injection timing, it is difficult to manufacture realistically, so this is conceptual, It is a logical logical model. However, this method is said to have been surprisingly original and impressed even the eminent physicist Feynman. Collisions of balls are reminiscent of atomic collisions, and are said to have influenced Feynman's ideas about quantum computers.

● Make a switch gate with billiard balls

First, make a switch gate out of billiard balls to construct the Fredkin gate. As shown in Fig.1, it has two inputs and three outputs. Balls are thrown in from In1 and In2. Those balls are output to Out1, Out2a, Out2b after elastic collision and reflection by the mirrors installed in the upper right and lower left corners. If neither input is given, there is no output. If the ball enters only In1, it will obviously come out only in Out1. Also, if the ball enters only In2, there is output only in Out2a. For both input and output, if the presence of the ball is set to 1 and the absence of the ball is set to 0, the logical value table will be as shown on the right side of the figure.

It should be noted here that this gate is a reversible gate. In fact, as shown in the lower part of the figure, the fact can be seen by reversing the arrows (3 inputs and 2 outputs) while leaving the input and output labels (logical formula) as they are.

Now, it's a little more complicated when the ball is thrown into both In1 and In2. The movement is shown in Fig.2. It doesn't matter which of the two balls appears at which output. It suffices to say that both the input side and the output side are 1 if the ball appears, and 0 if the ball does not appear.

In addition, I made a simple animation (smartphone app that reflects collision and reflection), so the gif image is shown below.

● Make a Fredkin gate out of billiard-ball switch gates

Using four switch gates shown above, the Fredkin gate can be created. These four are all the same switch gates, although they are arranged differently. Fig.3-1 to Fig.3-4 show the behavior for all combinations of inputs of the constructed Fredin gate.

In conclusion, even if we can make the switch gate itself, we need a transcendental skill to combine them to form a Fredkin gate. First, the mirrors must be properly placed to reflect the balls flowing between the switch gates. In addition, it is necessary to properly delay the path so that it collides when it should and does not collide when it should not. If it can be realized, the Fredkin gate works as a 3-input, 3-output logical gate.