アーサーは小部屋に通じるドアに体重をかけて、開かないように押さえていた。しかし、ドアはちゃんと合っていない。か細くて毛むくじゃらの小さい手がいくつも、ドアのすきまから突っ込まれてくる。その手の指はインクで汚れていた。小さい声が熱に浮かされたようにぺちゃくちゃ言いつづけている。
アーサーは顔をあげた。
「フォード、ドアの外に無限の数のサルがいて、『ハムレット』の台本を仕上げたからぼくらとその話がしたいと言ってるんだけど」
（ダグラス・アダムズ「銀河ヒッチハイクガイド」安原和見訳）

まあ、これは大好きなＳＦ（原作・映画共お気に入りです！）なのですが、今回の話は、「無限の数の猿がタイプライターを叩き続けば、いつかはフランス国立図書館に収蔵されている書物の全てを書きあげることができる」と言い表される「無限の猿定理」と呼ばれるものについての考察です。

....要するにこれ、非決定性アルゴリズムなんです。以前も「空にカードを放り投げて..」書きましたが、平行プログラミングにちょっと考え方を慣らそう、というイメージトレーニングみたいなことを考えているのですが、そこでのパラドックスみたいなこと、かな？

勿論「無限の猿定理」自体は真実です。しかし、「無限の猿」による無限個の「ハムレット候補」があるために、これをチェックして「本当のハムレット」を見つけ出すための計算量が爆発してしまう....（停止するのは確実でも、異常に時間がかかる可能性も高い）ということになのですね。本当のハムレットを見つけ出すには、猿が抱えるタイプ用紙を1枚づつチェックしていかないとダメなのです。

しかも、「本当のハムレット」を識別するためには、「本当のハムレット」のテキストを「持って」いる必要が出ます。「本当のハムレット」のテキストと猿が打ったテキストとを比較して、正しく打てているかどうかを見るわけです。...しかしこれ、考えてみれば、手元にすでにまぎれもない「本当のハムレット｣があるわけです。無限の猿に仕事をさせる必要が....あるのでしょうか？

同じようなことは、量子コンピュータが使う量子アルゴリズムでもあります。量子ビットは複数の状態を重ね合わせることができ、それらの状態を全体として他の量子ビットと演算させることができるわけです。ですから、結果もやはり量子ビットのかたちで表現される...わけですが、例の「観測問題」のために、いざ結果を得ようとする時に、「量子ビットが重なり合った状態」から「確率的にその量子ビットのどれかを表現する１つの状態」に変化してしまう（重ねあわせが壊れる）ことになります....ですから、「量子アルゴリズム」とされるアルゴリズムは、観測に拠らず値が決まる、という特別な性質を持ったアルゴリズムであるわけです。

量子コンピュータは非決定性チューリング機械の「特別な場合」ということになりそうです。まだまだ全然実験状態で、期待される「素因数分解を超高速で行う！（実際これをするためのアルゴリズムが見つかっているので期待されているわけです）」でも、１５＝５×３に成功してから、どうなっているんだろう....と心配なあたりです（最近あまり記事がないですね）。まあ、そんなところですから、私が実際に量子コンピュータをプログラムする...というのはムリっぽそうなのですが、それでも知的興味は強くあります。

量子コンピュータについてのオススメ本は、やはりブルーバックスの「量子コンピュータ」（竹内繁樹著）です。想像がいろいろと広がりますし、しかもこっちは実用化まであともうちょいの「量子暗号」についてもちゃんとした説明が載っていたりします。エンジニアならば面白く読めると思います。

しかし、どうやら量子力学の多世界解釈によると、観測によって「Ａと観測した世界と、Ｂと観測した世界とに、世界が分岐してしまう」ということにもなるのかもしれません。としてみると、実は「無限の猿」というのは「観測によって分岐した無限の世界」の猿たち...だったのかもしれないです（空想）。