Demonstrating app for the Billiard-ball Fredkin gate

This app was developed based on the description in Prof. Chris Bernhardt's book "Quantum Computing for Everyone". This Fredkin gate F(x,y,z) is equipped with several mirrors so that the billiard ball can be properly oriented. Also, appropriate delays are added to the paths so that the ball will collide when it should, and not when it does not. Here we can see the behavior of the two most complicated cases F(1,1,0) and F(1,1,1).

For more information, please see this article.

Acknowledgments

This app seems to work, but I'm not sure on some points.

First, for F(1,1,1), unlike F(1,1,0), I gave a delay to the start of ball 3 (input z). That's to make it properly collide with ball 2 within the switch gate.

Second, in the case of F(1,1,1), unlike the other cases, I gave a delay to the path of ball 1 (input x) outside the switch gate. This is to avoid collision with ball 2.

So, my question is:

As mentioned above, the delay is not the same for all input patterns. Is it acceptable to change the delay depending on the combination of inputs?

I would like to thank Prof. Chris Bernhardt for his good advice (2023-07-06).

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:

1. It is a reversible logic gate. That is, the input can be reached from the output.
2. 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.
3. 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.

 Reference

 [1] Chris Bernhardt: Quantum Computing for Everyone, The MIT Press, 2020.

https://www.chrisbernhardt.info/

ビリヤードボールを使ったFredkinの万能論理ゲート

【要旨】量子コンピューティングに関するProf. Chris Bernhardtの著書[1]第６章は、"Classical Logic, Gates, and Circuits"だが、一般の論理回路の教科書には多分載っていない「Fredkinゲート」の説明がある。それは、著名な物理学者ファインマンも感銘を受けたと言われる、「ビリヤードボールによる万能ゲートの作成」である。その独創的なアイディアは量子（原子、分子）の衝突を連想させ、ファインマンの量子コンピュータ観に影響を与えたと言われる。この書籍で学んだことを纏めてみたい。（→改訂英語版はこちらをご覧ください。）

●Fredkinのゲートとは
　これは、Edward Fredkinが1982年に発表した３入力（x, y, z）３出力の論理ゲートで、論理関数で表せば以下のように簡単なものである：
F(0, y, z )=(0, y, z),  F(1, y, z) = (1, z, y)

　最初のxは制御ビットなので、出力の１番目にそのまま出る。x = 0 の場合は、yとzとはそのまま出力され、x = 1 の場合は、yとzが交換されて出力される。簡単な計算で示すことができるのだが、以下の特徴を持つ：

• 可逆論理ゲートになっている。すなわち、出力から入力へ到達できる。
• 万能論理ゲートである。すなわち、NOTとANDとfan-out（入力の複製機能）をこのFredkinゲートのみで作成できる。
• 入力と出力の1（True）の個数は常に等しい。これは後述するが、ビリヤードボールの個数が入力側と出力側で常に等しいことに対応する。

●ビリヤードボールでFredkinゲートを作るという独創性
　Fredkinは、ビリヤードボールを使ってこのゲートを作成する方法を示した。ボール同士の衝突と、ボールと台の淵に置かれた鏡（入射角と反射角が等しい場合を想定した反射板）による反射を使う。ただし、完全な弾性衝突（エネルギーロスなし）や、複数のボールのサイズ、質量、速度、投入タイミングの完全な一致を想定するので、現実的に製造することは明らかに困難であり、概念的、論理的な論理モデルである。しかしながら、この方法は、驚くべき独創性に富んでおり、著名な物理学者ファインマンも感銘を受けた言われる。ボールの衝突が原子の衝突を連想させ、ファインマンの量子コンピュータへの考えにも影響を与えたとされる。

●ビリヤードボールでスイッチゲートを作る
　まず、Fredkinゲートを構成するためのスイッチゲートを上記のビリヤードボールで作る。図１に示すように、２入力３出力である。ボールはIn1とIn2から投入される。それらのボールは弾性衝突と右上隅と左下隅に設置された鏡での反射を経て、Out1, Out2a, Out2bへ出力される。入力が２つとも与えられない場合は何も出力がない。In1にだけボールが入ると明らかにOut1にだけボールが出てくる。また、In2にのみボールが入るとOut2aにだけ出力がある。入力出力共に、ボール出現有りを１に、無しを０とすると、論理値表は右側のようになる。

　ここで注目すべきは、このゲートは可逆ゲートであることだ。実際、図の下段に示すように、入出力のラベル（論理式）はそのままで矢印だけを逆向き（３入力２出力）にすることで、その事実がわかる。

　さて、少し複雑なのが、In1とIn2に共にボールが投入された場合である。その動きを図２に示した。ここでは、見やすくするため、青と赤のボールを使っているが、本来はその区別は必要がない。入力側、出力側共に、とにかくボールが出現していれば１であり、出現しなければ０だということだけで十分なのである。

　なお、動作の簡単なアニメーション（衝突と反射を反映したスマホアプリ）を自作したので、以下にそのgif画像を示す。

●Fredkinゲートをビリヤードボールのスイッチゲートで作る
　上記のスイッチゲート４個を用いて、最初に示したFredkinゲート（図３）を作ることができる。４個のうち２個は、上で述べた可逆性を使って逆向きにしたものが接続されている。結論から言うと、仮にスイッチゲート自体は作成できたとしても、それを組み合わせて、Fredkinゲートを構成するには超絶技巧が必要だ。すなわち、スイッチゲート間を流れるボールを反射させる鏡を適切に設置する必要がある上、衝突すべき時に衝突し、そうでない時には衝突しないように、経路上に適切に遅延を与える必要があるからである。もしも、それが実現できれば、Fredkinゲートは、図３に示すような、３入力３出力の論理ゲートとして使うことができる。

●感想

　本書第６章は、量子コンピューティングの基本原理（量子のsuperpositionやentanglement,

Bell's theoremなど）が終わり、次に量子ゲート、量子回路に入る直前の章である。著者は、

「このFredkinゲートはこの後の量子回路に直接必要なものではないが、類稀なる独創性に感銘を受けて本章に含めた」と述べている。小生にもそれが分かった気がするのである。

References

[1] Chris Bernhardt, “Quantum Computing for Everyone”, MIT Press, 2020 

https://www.chrisbernhardt.info/