量子計算機というものが情報科学および物理学の両方で大きな話題となっている。普通の計算機はビット、つまり0または1の値を持つもの、を扱うが、量子計算機はその代わりにキュービット（qubit，quantumbitより）と呼ぱれるものを扱う。このキュービットがビットと違う点は、0または1を持つ、の代わりに、0を持った状態と1を持った状態を「重ね合わせた状態」を持つ、という点である。「重ね合わせた状態」という奇妙な概念は物理の量子力学となじみが深いため、量子計算機の名がついている。
量子計算機の基本的なアイデアは'85年に発表されていたがあまり注目されなかった。また今でも実際に作られたわけではない。それが一転したのは'94年にShor（ベル研の情報科学者）が量子計算機を前提とした高速の（専門用語では多項式時間の）素因数分解のアルゴリズムを発表したことによる。素因数分解は学校で習うとおり、例えぱ15＝3×5と分解することである。小さな数なら普通の計算機でもすぱやくできるが、100桁というような大きな数になると現在知られている普通の計算機用のアルゴリズムでは非常に時間がかかり、現実的に不可能になる。それが可能ということで脚光を浴びることになった。
量子計算機では上記のように「0と1の重ね合わせ」が中心となる。重ね合わせというのはベクトルの足し算だと思えばよい。例えば北を向いているベクトルと東向きのベクトルを足し合わせると北東向きのベクトルになる。この意味では北東向きのベクトルは北向きのベクトルと東向きのベクトルを足し合わせた（重ね合わせた）ものとみなせる。北向きのベクトルが0、東向きが1を表すとみなせば北東向きのものが「0と1の重ね合わせ」となるのである。キュービットひとつがこのようなベクトルひとつに対応し、量子計算機はこのキュービットの集まり（専門用語ではテンソル積）に対してある種の操作を施すことにより計算を行う。その強みは、「重ねあわせ」を使った並列性にある。たとえぱある関数fがあって、f(0)とf(1)を計算したいとする。普通の計算機では引数が0の場合と1の場合のそれぞれで計算する必要がある。ところが量子計算機では「重ね合わせ」のおかげで、f（「0と1の重ね合わせ」）を一度計算するだけで「f(0)とf(1)の重ね合わせ」を得ることができるのである。ただし重ね合わせが得られてもf(0)とf(1)を個別に取り出せるわけではないので、この並列性の利用には工夫がいる。Shorは、うまく工夫すれぱ素因数分解という間題に強力に適用できることを示したのである。
量子計算機の研究は、1）どうやって実際に作るか、2）計算のモデルとしての性質、の2つに分けられる。今のところ作るのは非常に難しいとみられている。問題はキュービットの集まりをいかに実現するかで、提案されているものでは例えぱ電子や原子をひとつだけ取り出してレーザーで制御するなど非常に微妙な操作が要求される。3個のキュービットの実現がニュースになるほどであり、新しいアイデアが模索されている。モデルとしての研究では、素因数分解のほかにどのような問題に有効かや既存の計算モデルとの関係が重要な課題である。また1）にからみ、古典情報理論に習った量子的な符号訂正法も確立されつつある。いずれにせよまだ始まったぱかりの活発な分野である。（教科書に「量子コンピュータ入門」西野哲朗著、束京電機大学出版局があり。）