反省して軌道修正
量子ゲートの働きを説明するだけでこれだけ回数を必要とするとは思わなかった.しかも万能ゲートが本当に万能なのかを確認しておきたいという個人的な興味から少々横道へ逸れて暴走したのだった.大抵の入門書では軽く流すところだ.
さて,有名なゲートとしてはまだ 3 入力 3 出力を持つ「トフォリゲート」別名「CCNOTゲート」（制御-制御-NOT の略）というものがあるのだが,これは既に話した万能ゲートの組み合わせで実現できるものでもあるし,話の流れで必要になった時に紹介することにしよう.
長々と説明しなくても CCNOT という名前から機能が想像できると思う.制御ビットが |1> の時に限って CNOT ゲートとして働くゲートである.要するに制御ビットが 2 つあってどちらもが |1> の時に限って標的ビットが反転するのである.なお,トフォリというのは人名である.
今回は,もっと基本的なことを話すことにしよう.
量子ビットをどう使うか
量子ビットは工夫次第で色々な使い方ができるわけだが,量子ビットで数値を表したいのなら古典的コンピュータと同じ方法が使える.つまり,多数の量子ビットを並べて,2 進数の各桁に見立てるのである.
例えば 5 量子ビットくらいを用意して,初期状態をどれも
にリセットしておこう.そしてすべてをアダマールゲートに通すのである.
するとどの桁もと
の半々の重ね合わせになる.この 5 つの量子ビットをひとまとめにした状態というのは次のように表せる.
つまり 0 ～ 31 を意味する全ての状態を重ね合わせた状態を意味している.
もしこれとは別にもう一つの 5 量子ビットを用意して加算回路を実現すれば, 0 ～ 31 の数と 0 ～ 31 の数のあらゆる組み合わせでの足し算を並列して実行することになる.つまり,32 × 32 = 1024 回分の計算に相当する.これを一度でやり遂げるところが量子コンピュータの速度の秘密だ.用意する量子ビットの数が一つ増えるごとに,性能は倍々に高まる.
ただしこのような単純な足し算の場合は,結果さえもあらゆる数値の重ね合わせになるだけなので面白くもない.観測してみてもそのうちのどれか一つの答えが得られるだけである.
そこで知恵と工夫が必要である.欲しい答えはどんな条件を満たしていると言えるのか,欲しい答えを意味する状態だけを残すにはどうしたらいいのかを考えて回路を組む必要があるのだ.そこが一番難しい部分である.
「Quantum Algorithm Zoo」（量子アルゴリズム動物園？）というサイトではどのようなアルゴリズムが発表されているかを一覧にしてくれてあり,それに関する論文へのリンクを張ってくれてある.ここにあるのは古典的コンピュータよりも速く計算できるものに限定されており,今のところ 60 種類ほどあるようだ.（代数,数論に関するもの14種,量子ブラックボックス（神託機械／オラクル）に関するもの34種,近似やシミュレーション12種）
このサイトの日本語訳もある.「Quantum Algorithm Zoo全訳」（「Qmedia」というサイトの一部）
足し算の回路
量子ゲートを使って普通の足し算ができるのかと疑う人がいるかも知れないが,意外と簡単である.CNOTゲートの標的ビット側は,入力のどちらもならで出てくるし,どちらか一方だけがならで出てくるし,どちらもならで出てくる.これは繰り上がりを考えない場合の 2 進数の 1 桁どうしの足し算と同じ動作である.要するに,CNOTゲートが一つあれば実現できるのだ.
問題は繰り上がりである.入力のどちらもであったときに限ってになるようにするにはどうしたらいいだろうか？実はそれを手っ取り早く実現できるのが,冒頭で話した「トフォリゲート」(Toffoli gate)である.
後回しにしようと思っていたのにこんなすぐに出てきてしまった.これは2つの制御ビットがともにの時に限って標的ビットを反転させるゲートなので,次のように使えば繰り上がりを表現できる.
ただし,トフォリゲートを実現するのは少々大変である.例えば,トフォリゲートよりも一般的な「制御-制御ユニタリゲート」を実現するためには次のような 5 つの制御ユニタリゲートを組み合わせる必要がある.
この
は
を満たすようなユニタリ行列である.仕組みは難しくないのでじっくり追いかけてみてほしい.
トフォリゲートを作ろうと思ったら
を満たすで制御ユニタリゲートを作らないといけないことになるから,それはそれは大変なことになりそうである.
実際の量子ゲートを作るときにはわざわざ万能ゲートを組み合わせる必要はなくて,物理的な現象をうまく利用して一発でその機能を果たせるような仕組みを作れることもある.とは言うものの簡単なことではない.
さて,2 桁以上の足し算をさせたいときはどうしたらいいだろう？下の桁から来る繰り上がりを考慮した回路を組む必要がある.表を作ってみたりしてちょっと悩んだが,適当に試してみたら意外と簡単に実現できた.
左半分の 2 つのゲートは先ほどの半加算器と同じである.3 番目のゲートでは下からの繰り上がりが来たときの繰り上がり桁の調整を行っているが,なかなか意表を突くような動きをしているので楽しんでみてほしい.4 番目のゲートでは,下からの繰り上がりが来た時に結果を反転させるだけでいいことを利用している.
このようなセットを幾つも並べれば何桁の 2 進数の足し算でも出来てしまうだろう.
このように組んだ回路は,重ね合わせ状態ではないやを入力として使えば,全く古典的な論理ゲートと同じような結果を返してくれるのである.
適材適所
このように,古典的な論理ゲートで出来ることは量子ゲートを使っても実現できてしまう.場合によっては古典ゲートを使うよりもすっきりと表現する方法があったりして面白いが,それだけではどちらを使うのが効率が良いかは決められない.現実には一つのゲートを実現するのに（トフォリゲートのように）複雑な仕組みが要ったりすることもあるからだ.
古典的な論理ゲートの真似ができるからといって何でも量子ゲートを使えばいいというものではない.量子ゲートは状態の重ね合わせが使えるところに利点がある.そうでなければほとんど利点がない.現状では量子ビットはかなり不安定で,状態を長時間維持できないので,全く同じアルゴリズム（計算手順）を実行するだけならば古典的なコンピュータにやらせた方がはるかに低コストだろう.重ね合わせを使うことで古典的なコンピュータより遥かに効率が良い計算方法がある場合にだけ量子コンピュータに任せるというのが賢い運用というものである.
量子ゲートで計算できるアルゴリズムは限られているとは言われているものの,原理的には古典的なコンピュータにできることは全部できてしまうだけの能力はある.コストが合わないだけの話なのだ.
フレドキンゲート
トフォリゲートの話が出てしまったので,もう一つの有名な 3 入力ゲートの話もついでにここでしてしまおう.それは「フレドキンゲート」と呼ばれるもので,別名「制御交換ゲート」である.
制御ビットがの時に限り,残り 2 つの量子ビットの状態を入れ替えるというものである.こんないいものがあればもう色々なことが自由にできそうだ.
どうやって作ったらいいのだろうかと考えてみたが,気付けば意外と簡単である.前々回の話に出て来た交換ゲートで使っていた CNOT ゲートをトフォリゲートに置き換えてやるだけでいい.
これくらいの種類のゲートを知っていればもうほとんどの場面で困ることがないだろう.
