体調を崩したりしたので間が空いてしまったが，「数理科学」を読んで，やっと，何となく量子コンピュータのイメージがつかめたような気がする。要するに，量子アルゴリズムの実装である。といっても，これだけでは何のことやらわからないと思うので，もう少し説明する。
まず，ある系の状態を，内積をもつ線形空間の単位ベクトルで表す。状態変化は，そのユニタリ変換で表される。すると，すべての計算は，基本演算を表すユニタリ変換の積として表される。言い換えると，任意の計算結果は計算基底の状態の重ね合わせなので，終了状態で計算基底を測定すれば，測定値が確率的に得られる。これが量子アルゴリズムである。量子アルゴリズムとして現在定式化されているものは，量子回路と量子テューリング機械である。
量子テューリング機械は，古典的テューリング機械と同様，左右に無限に伸びた長いテープ，テープ上の記号を読み書きするヘッド，ヘッドの制御部からなっている。テープ上の各マス目は２準位系で，１マスが１量子ビット，つまり記号の有限集合Σと一対一対応する計算基底をもつとする。テープのマスには整数の番号がつけてあって，ヘッドの位置はマス目番号となるので，整数の集合と一対一対応する計算基底をもつことになる。有限制御部は記号の有限集合と一対一対応する計算基底をもつ量子系とする。この量子テューリング機械の計算基底は，有限制御部の状態q，テープの内容T，ヘッド位置hによって，｜q,T,h＞と表すことができる。量子テューリング機械の量子状態は，計算基底で張られる無限次元線形空間の単位ベクトルで表される。状態変化は上述のようにユニタリ変換で表されるので，時間が経つと，もとの状態にステップ数だけこのユニタリ変換を掛け合わせた状態になる。ステップとはテープの１マスと有限制御部がヘッドを通して相互作用するだけであり，そのときのヘッド移動は確率的に１マス以内で振幅する。終了状態が計算基底に含まれるため，終了状態になったら自動的に停止ということはできず，外部の観測者が有限制御部が終了状態になったかを監視していてその時点でテープの内容を観測しなければならない。しかし終了前に観測してしまうと測定装置と量子テューリング機械が相互作用して計算が妨害されるおそれがあるので，停止フラグという1 qubitを導入して停止フラグだけを毎ステップ観測するなどの工夫が必要である。
ああ難しい。完全に理解したわけではないので，もし間違いがあったらご指摘いただければ幸いである。ともあれ，世間的価値として大事なのは，確率的計算が瞬時にできることである。シミュレーション時間の大幅短縮が見込まれる。さらに，探索が効率化されるため，暗号解読などに有効だといわれている。量子コンピュータのログインとかパスワードとかどうするのだろう？ と心配したくなるが，それについては絶対安全な量子暗号というものもあるそうだ（下記「FAQ about Quantum Computer etc.」による）。
量子アルゴリズムは，1994年に発表された素因数分解を高速に行うShorのアルゴリズムで実用性が期待されて以来，世界の注目を集めるようになったそうで，研究が進んでいる分野である。しかし，測定系の実現が大変に難しいため，実用規模の実装は当分実現されないようである。NMR量子コンピュータというモノは小規模ながら（2 qubit）既に存在すると書かれていたが（Chuangのグループなどがやっているもので，日経サイエンスの9月号に出ていたという「クロロホルムが量子コンピュータの心臓部となる」という話はこれのことである），実用性が見込まれる100 qubitなんてのは他の実装手段を含めても来世紀中には実現しないだろう（まあ，世の常として思っても見なかったブレークスルーが起きてあっさり実現するかもしれないが）。
WEB上での情報を探してみたら，こことかここにも書かれていたが，量子コンピュータ素子の話がメインであった。「FAQ about Quantum Computer etc.」の話もわかりやすいが，量子アルゴリズムと計算量について詳しくは書かれていないので，「数理科学」10月号の記事が現存する最良のテキストと思う。いろいろな研究者が手を変え品を変え同じ内容を説明しているきらいもあるが，小澤さんと西野さんの両方を読んでやっと量子テューリング機械がイメージできかけたような気がする。
さて，こういうことを念頭に置いて，「量子コンピュータ」を気にするきっかけとなった作品群を読み直してみた。ベアの「凍月」その他におけるQL Thinkerは厳密には「量子コンピュータ」ではないのかもしれないが，まあ似たようなものだろう。しかし，結果の解釈に翻訳機を必要とするという属性は量子コンピュータの特性ではない筈である。量子アルゴリズムを逐次的に理解することが恐ろしく非能率だから，ヒトは量子コンピュータを作って結果を得たいわけであり，QL Thinkerが何をするものなのかが若干腑に落ちない。
瀬名秀明「BRAIN VALLEY」や鈴木光司「ループ」で出てきたのは超並列コンピュータであって，量子コンピュータではなかった。どちらでも人工生命のシミュレーションに使っているのだから，量子コンピュータの利用に適している筈だが，舞台装置としてリアリティがあって欲しいところでは，まだ「量子コンピュータ」という呼称は使いにくいという判断なのだろう（もちろん量子コンピュータに超並列計算をさせてもいいわけだから，実は量子コンピュータなのかもしれない）。まあ妥当な読みと思う。さっきも書いたように測定系も含めて実用化されるのは22世紀に入ってからだろうから，ベアの世界では使えてもBVやループの近未来での現実側の描写としてのリアリティを失う。まあ，ループで出てきたNSCSというのもとんでもないシロモノではあるが，あれはSF的アイディアとして評価すればよい「あっち側のモノ」なので許せるのである。現実世界から如何にうまく「あっち側」へ離陸させるかがキモだから，22世紀以降の話にしか量子コンピュータは出てこないだろうなぁ，当分。