ビリヤードボールを使った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/