量子コンピューティングについて
シニアエンジニアは将来の技術に目を向けておかねばならん、というわけで量子コンピューティングについて少々真面目に勉強してみた。「量子コンピューターが実用化されると素因数分解が高速でできてしまい、RSA暗号が無力化される」といった噂は本当なのか？
ネタは 量子コンピュータ Advent Calendar 2017 - Qiita と、王道の IBM Q Experience で。*1
私が改めて解説しても巷にある解説の劣化版にしかならないので、今後学ぶ人の参考になりそうな所感を中心に。実際に勉強を進めようと思ったら、上の Advent Calendar を取っ掛かりにあちこち読み漁り、異なる文書に繰り返し登場する && 自分のアンテナに引っかかるところを重要ポイントとして深めていけばいいと思う。人によって(前提知識やゴールによって)適切な勉強パスは異なるだろうから、必読リンク集みたいのを作るのもなかなか難しい。気が向いたらそのうちやるかもしれない。
アナログコンピューター(アナログ電気回路による計算機)のイメージで取り組むとよい
論理の世界で完全に理解できる古典的なデジタルコンピューターとは異なり、素子の物理的性質を表す数式がわからないとそもそも解説がまったく理解できず、文字通り途方に暮れるしかない。まずはアナログコンピューターだと思って取り組むとよい。
アナログコンピューターの一例はCR積分回路だが、これはコンデンサーという素子が「電流を積分して電圧として出力する積分器」として働くという物理的性質およびその数式を理解し、回路全体とどう作用するのかを考えないと動作が理解できない。その素子が実際にどんな物質で作られていてどう働くかの物性的な原理はさておき、数式として理解するところまでは必要である。量子コンピューターを理解するにも似たような思考が必要である。
将来はそんなこと理解しなくても量子コンピューターを使えるようになるのかもしれないが、残念ながら今学ぶ人はそんな楽はできないと覚悟するべし。
量子ビットは確率的に0 or 1の値を取り、「観測」によって値が決まる
ひとつの量子ビットは {0: 25%, 1: 75%} のように複数の状態を確率的に取る。そして、この状態(確率)を直接取り出すことはできず、代わりに「観測」を繰り返すことで例えば「0が24回、1が76回観測された」のような結果を得ることができる。
量子ビットの解説を読むと、その状態を表すのにいきなり |ψ> みたいな記号が出てきて面食らうが、何のことはない、単に(√<0を取る確率> √<1を取る確率>)を縦に積んだ2x1の行列のことである。ちなみに |0> は0が100%の状態＝(1 0)、|1> は1が100%の状態＝(0 1)を表わしたもので基底と呼ばれる。わかってしまえば恐れるには及ばない。
実際にはこの確率は実数ではなく複素数で表される、つまり位相を持つ。位相も含めて量子ビットの状態はブロッホ球という球面上の一点に視覚化でき、状態を変えるということはこの点をブロッホ球面上でくるくると移動させることに相当する。この位相が計算処理の中でどんな意味を持つのかは、グローバーのアルゴリズム等をじっくり追ってみる過程できっとわかってくるだろう。
量子ビットの状態(0と1の確率)を変えるには、数学的には上記の2x1の行列にパウリ行列やアダマール行列といった2x2の行列(ユニタリ行列と呼ばれる類の行列)を掛け算することで行なう。先の位相の話も含めて「なんでそんなまどろっこしいことを、直接数字をいじればいいのに」と思うがそういう素子の性質なので仕方がない。物理的には「ある波長のレーザーを一定時間当てる」みたいな操作でそれらの数式相当の変化を起こすらしい。
このあたりが概ね理解できれば、前述の「素子の性質を数式として理解できた」レベルに相当し、計算機としての動作を理解するための下地はできたと言えるだろう。
複数量子ビットは相関を持ち(entangleされ)組み合わせに依存した確率を持てる
例えば2つの量子ビットがあったときに、それらの間に相関を持たせて {00: 50%, 11: 50%} のような組み合わせに依存した確率を作ることができる(それぞれが勝手に確率的に値を取ったら01や10も否応なしに発生するのでこうはならない)。物理的には量子entanglementという現象を利用するらしいが、実際どうやるのかは筆者には見当もつかない。
このような相関のある2つの量子ビットの状態は、組み合わせごとの確率、つまり(√<00を取る確率> √<01を取る確率> √<10を取る確率> √<11を取る確率>)を縦に積んだ4x1の行列で表わせる。1ビットのときと同様に基底 |00>, |01>, |10>, |11> も定義でき、それぞれ00, 01, 10, 11が100%の状態、つまり(1 0 0 0), (0 1 0 0), (0 0 1 0), (0 0 0 1)を表す。
このような相関のある2量子ビットに対する操作は、お察しの通り、4x4の行列を掛け算することで行なう。だんだんとめんどくさくはなってくるが、頑張ればまぁ自然な拡張として理解できる。
量子ビットの状態に手を加える手順が「量子コンピューターの回路あるいはプログラム」である
ある初期状態(例えば {00: 100%})から出発し、その状態に手を加える操作を何回か繰り返し、最終的な状態(例えば{00: 50%, 11: 50%})を観測によって知る、というのが量子コンピューターによる計算のやり方である。この操作手順の設計こそが、従来のコンピューターの回路設計あるいはプログラミングに相当する。
例えば「数値21311をショアのアルゴリズムで素因数分解する」といった解きたい課題をこの操作手順に落とし込み、量子コンピューターの実機あるいはシミュレータ上に再現し、ﾜｸﾜｸしながら何度も状態観測することで、「98%の確率で101が観測されました。おめでとうございます！」といったかたちで答を得ることができるはず…なのである。
量子コンピューターの回路設計あるいはプログラミングは現時点で超ハードル高い
現代のコンピューターであれば、上記のような問題はCなりJavaなりPythonなりの言語で誰でも記述でき、それを言語処理系がコンピューターが実行可能なかたちに解釈して答を与えてくれるわけである。が、量子コンピューターの世界はまだそこまで行っていない。
IBM Qの設計画面(例えばグローバーアルゴリズムの実装例)を見ればわかる通り、かなりプリミティブな操作の組み合わせで課題を表現する必要がある。これはAND/OR/NOTといった基本的な論理回路だけで、あるいはベアなチューリングマシンだけで課題を解くようなものである。もちろんこれは非常に興味深く楽しいパズルではあるし、原理を学ぶために通って損はないものであるが、誰でもできるか？実用的か？と言われたらまだまだ距離がある。
今後誰でも量子コンピュータープログラミングできるコンパイラ技術が登場するのかもしれないが、量子コンピューターが(古典的コンピューターよりも劇的に速く)解ける問題の種類は少ないらしいので、プログラムは職人に実装させてそれを万人が使えるようにする、というモデルでも構わないのかもしれない*2。それにしてももう少しはましになるべきだとは思う。
RSA暗号は無力化されるのか？DBは一瞬で検索できるのか？
現在の技術で作れる量子コンピューターが扱えるビット数は49ビットや72ビット程度で、暗号解読やDB検索にはまだ足りない。またプログラミングも難しすぎる。古典的コンピューターで言うとENIAC登場のような黎明期と言える。
ただ古典的コンピューターがそうであったように、これらが進歩してくるのは時間の問題で、ある閾値を越えたら一気に(一部研究者ではなく世間にとって)現実のものになるタイミングが来るのだろう。
