2022年11月16日水曜日

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

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

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

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

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

ビリヤードボールでスイッチゲートを作る
 まず、Fredkinゲートを構成するためのスイッチゲートを上記のビリヤードボールで作る。図1に示すように、2入力3出力である。ボールはIn1とIn2から投入される。それらのボールは弾性衝突と右上隅と左下隅に設置された鏡での反射を経て、Out1, Out2a, Out2bへ出力される。入力が2つとも与えられない場合は何も出力がない。In1にだけボールが入ると明らかにOut1にだけボールが出てくる。また、In2にのみボールが入るとOut2aにだけ出力がある。入力出力共に、ボール出現有りを1に、無しを0とすると、論理値表は右側のようになる。
 ここで注目すべきは、このゲートは可逆ゲートであることだ。実際、図の下段に示すように、入出力のラベル(論理式)はそのままで矢印だけを逆向き(3入力2出力)にすることで、その事実がわかる。
 さて、少し複雑なのが、In1とIn2に共にボールが投入された場合である。その動きを図2に示した。ここでは、見やすくするため、青と赤のボールを使っているが、本来はその区別は必要がない。入力側、出力側共に、とにかくボールが出現していれば1であり、出現しなければ0だということだけで十分なのである。
 なお、動作の簡単なアニメーション(衝突と反射を反映したスマホアプリ)を自作したので、以下にそのgif画像を示す。

Fredkinゲートをビリヤードボールのスイッチゲートで作る
 上記のスイッチゲート4個を用いて、最初に示したFredkinゲート(図3)を作ることができる。4個のうち2個は、上で述べた可逆性を使って逆向きにしたものが接続されている。結論から言うと、仮にスイッチゲート自体は作成できたとしても、それを組み合わせて、Fredkinゲートを構成するには超絶技巧が必要だ。すなわち、スイッチゲート間を流れるボールを反射させる鏡を適切に設置する必要がある上、衝突すべき時に衝突し、そうでない時には衝突しないように、経路上に適切に遅延を与える必要があるからである。もしも、それが実現できれば、Fredkinゲートは、図3に示すような、3入力3出力の論理ゲートとして使うことができる。
感想
 本書第6章は、量子コンピューティングの基本原理(量子のsuperpositionやentanglement,
Bell's theoremなど)が終わり、次に量子ゲート、量子回路に入る直前の章である。著者は、
「このFredkinゲートはこの後の量子回路に直接必要なものではないが、類稀なる独創性に感銘を受けて本章に含めた」と述べている。小生にもそれが分かった気がするのである。

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

0 件のコメント:

コメントを投稿