量子コンピュータのわかりかた

数理科学、2019年7月号「量子コンピュータの進展」

自慢ではありませんが、管理人も「量子コンピュータ」の仕組みは全く分かりません。量子力学が分からないのですから当然です。しかし、量子コンピュータは量子機械学習でAIを飛躍的に進歩させ、また、暗号通貨の価値(暗号強度)に直結すると知って必死に勉強しています。色んな本を買ってきて読んでいます。勿論わからないのですが、たまにピンと来るような文章に巡り合うこともあります。数理科学2019年7月号にもビビッと来た文章がありました。

それは東洋大学の三原孝志教授の「量子コンピュータと物理」という記事の冒頭にあった次の文章です。


量子コンピュータは量子力学の基本原理を計算に組み込んだ計算モデルである。計算自体は数学的抽象概念であるが、人間は様々な道具や機械を利用し、これらの物理状態の変化を計算と解釈しているにすぎない。


これを読んでガーンと来ましたよ。つまり、量子コンピュータは、量子力学の実験をやって、「量子エネルギーがシュレーディンガー方程式の通りにふるまっている」ということを観測し、それを計算だと言い張っているに過ぎないというのです!

そもそもシュレーディンガー方程式は量子力学のエネルギーの時間変化を記述するために人類が実験を繰り返して発見した方程式なのですから、実験で量子状態を測定すればシュレーディンガー方程式の通りに振る舞うことは当然です。でも、それを見て、量子コンピュータを発明した、ドイチュファインマンさんは、「シュレーディンガー方程式が瞬時に解けた!」と叫んだのです。ちょっと卵が先かニワトリが先かみたいな話なのですが、要するに、量子力学の観測をやるとリアルタイムでシュレーディンガー方程式が解けちゃってるわけです。

で、その、観測データに、シュレーディンガー方程式と数学的に等価な別の計算を当てはめれば、その計算が「超高速で」解けちゃうことになるわけです。観測=計算です。要するにシュレーディンガー方程式を使って、足し算やかけ算も、その他の計算も何でもやってみようというわけなんです。計算の転換には量子フーリエ変換をつかうようです。量子コンピュータは量子フーリエ変換を超高速にネイティブに計算することができるのです。量子コンピュータを理解するにはフーリエ変換を学ぶ必要があります。

アナログコンピュータ

我々は普通のデジタルコンピュータを使うときも観測はしていますが、それは電圧の有る無しをクロック周波数の周期毎に測定して、ゼロか1を区別しているにすぎず、量子コンピュータからみれば、かなり無駄なことをやっているということになってしまいます。ちょっとアナログコンピュータの考え方に似ているかもしれません。量子コンピュータは21世紀に甦った新型のアナログコンピュータなのです。だから、量子コンピュータを理解するには、普通のデジタルコンピュータとチューリングマシンと、機械式計算機、アナログコンピュータを勉強するのも必須のことになります。急がば回れというやつです。

Screenshot of www.tus.ac.jp

東京理科大の近代科学資料館に行って「Bush式アナログ微分解析機」を見てくるのも無駄では無いのです。歯数の違う歯車を組み合わせれば倍算機になるのは直感的にも分かりやすいですが、微分解析機の仕組みは感嘆させられるものです。スライドをずらして足し算をかけ算に変える対数計算尺の仕組みも勉強になります。最新の量子コンピュータを理解するために、一番古い機械式アナログ計算機や計算尺を勉強するなんて面白いですね。

日時計のアナロジー

Screenshot of ja.wikipedia.org

量子コンピューターやアナログコンピューターは、「日時計」に似ています。我々は、太陽高度と方位を観察することにより「時刻」を知る=計算することができますが、同じように量子物理現象(ノイズ=エラーなしに観測するためには絶対零度付近の実験設備が必要ですが)を観測することで、量子フーリエ変換の計算結果を知る=フーリエ変換を計算することができるのです。そう考えると、量子コンピュータの計算は不思議な魔法でも何でもなくて、当たり前の当然の計算であることが理解できます。この認識は、「量子コンピュータの実用化の可能性」に関する正しい認識を与えてくれるものです。

P問題、NP問題、BQP問題、PSPACE問題

多項式(polynomial)時間で解ける問題をP問題と言います。計算時間がパラメータのn次多項式で記述できる計算問題のことです。これに対して、パラメータが増加すると計算量が指数関数的に増加する問題をNP問題と言います。

Screenshot of tcs.c.titech.ac.jp

そして、BQP問題ですが、Bounded-error Quantum Polynomial timeの略で、直訳で有界エラー量子多項式時間問題というわけで、エラー訂正できる量子コンピュータなら多項式時間で解けちゃう問題ということになります。古典コンピュータだとNP問題だ(公開鍵暗号に使える)けど、量子コンピュータだとP問題になっちゃう(公開鍵暗号に使えない)ようなBQP問題が存在することが知られています。ショアのアルゴリズムによって素因数分解問題(RSA暗号)や楕円曲線問題(楕円曲線暗号)が適切な規模の量子コンピュータが実現した場合に多項式時間で解決できることが示されていますので、「適切な規模の量子コンピュータが完成した場合にP問題になる」という意味になります。BQP問題はP問題よりも広い概念ですが、NP問題とBQP問題の関係は数学的に解明されているわけではありません。ただ、素因数分解問題に関して言えば、古典コンピュータでNP問題が量子コンピュータでBQP問題になることが知られています。BQP問題の全貌は、量子アルゴリズムの発展によって明らかになっていくでしょう。

Screenshot of en.wikipedia.org

従来型の古典コンピューターから見れば、量子コンピューターは特定の問題を超高速に計算してしまうサブルーチン(サブプログラム)やコプロセッサのようなものです。量子コンピューターが実用化した場合、それはあたかも、新しい近道を発見したようなことになります。いわば「量子ショートカット」です。普通の(古典)コンピューターなら何万年も掛かる計算を、量子ショートカットを通れば数十秒で計算できてしまうということなのです。

最後に、PSPACE問題(Polynomial SPACE)ですが、これは多項式関数でメモリを増やすことができるコンピュータで無制限の時間を使えば解ける問題ということになります。無制限時間というのが強力な条件です。BQP問題よりも広い概念となり、量子コンピュータでも多項式時間で解けない(安全な公開鍵暗号を設計できる)問題が含まれます。

※参考記事

シンギュラリティ革命と量子コンピュータ


投稿日

カテゴリー:

投稿者:

タグ:

コメント

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です