量子コンピュータはなぜ速い？【量子コンピュータ入門4】
本記事では量子コンピュータがなぜ速いのかを説明したいと思います。
量子コンピュータはなぜ高速なのか
過去の記事でも述べたように、量子コンピュータは、良いアルゴリズムが見つかっている問題に関しては高速に処理することができます。
ここでの計算の速さというのは、その問題を処理するために必要な計算量が、古典コンピュータ(スーパーコンピュータや普通のコンピュータ)に比べて劇的に少なくなるということでした。
さて、なぜそのようなことが可能になるのでしょうか。これには、
1. 量子ビットの重ね合わせ状態
2. 量子干渉
という二つのキーワードが重要になります。
1. 量子ビットの重ね合わせ状態
量子コンピュータでは、量子ビットと呼ばれる量子情報の最小単位を使って、情報を取り扱います。量子ビットとは、古典コンピュータにおけるビットの量子版です。
詳しい説明は、前回の記事をご覧ください。
結論だけ書きますと、n個の量子ビットの重ね合わせ状態を用いることで、2のn乗個の計算パターンを表現することができます。つまり、非常に多くの計算パターンを同時に表現することができるのです。
量子コンピュータに関してよくある誤解の一つに、「n個の量子ビットの重ね合わせ状態を使うと、2のn乗通りの計算を同時に処理できるので、量子コンピュータは速いのだ」という認識があります。
これは、間違いです。なぜなら量子コンピュータは、2のn乗通りのうちの1つの計算結果しか出力できないからです。
これは、量子力学の要請からきている制約であり、私たちにはどうすることもできません。結局のところ、2のn乗通りのうちどれか1つの計算結果が、ランダムに返されてくるだけであり、計算としては非常に非効率です。
2. 量子干渉
量子アルゴリズム
そこで、欲しい答えが出力される確率を高めることが必要になります。これを実現するのが、量子アルゴリズムとよばれるものです。量子アルゴリズムとは、いわば賢い解き方のことで、量子をどのように制御すれば問題を解くことができるのかを示してくれるレシピのようなものです。
逆のことを言えば、良い量子アルゴリズム(解き方)が見つかっている問題に関してのみ量子コンピュータは、その問題を高速に処理できるのです。この意味で、量子コンピュータはすべての問題を高速に処理できないということになります。
量子の波の意味
それでは、欲しい答えを得る確率を高めるためにはどうすればいいのでしょうか。結論から申し上げると、量子の波の干渉を利用します。
前回の記事では、量子は波としての性質を持つと解説しました。
電子(量子)を例にするとこんな感じです。
量子の波はその量子が観測(発見)される可能性の高さを意味しています。
量子というものはその場所に存在しているor存在していないという0か1かという概念ではなく、その場所に50%の確率で存在しているといったように確率的に存在しています。専門用語的には、確立振幅という概念で説明できます。とりあえず、量子の波の高さが高ければ高いほど、その量子が見つかる可能性が高くなるという理解で十分です。
さて、量子コンピュータの話に戻りましょう。量子コンピュータでは、量子ビットつまり量子を使って様々な計算パターンを表現します。しかしそのままでは、それぞれの計算パターンを表現している量子の波の高さは低いままです。
そこで、欲しい答えの量子ビット(量子)の波の高さを高くすることが必要になります。ここで用いるのが、量子の波の干渉という概念「量子干渉」です。
量子干渉とは、単純に量子の波が干渉することで、その波の高さが高くなったり小さくなったりする現象のことです。
以前の記事で、二重スリットの実験をご紹介しました。この実験がまさしく量子の波の干渉を端的に表しています。
この量子の波の干渉を上手に引き起こすことができるのが、量子アルゴリズムなのです。その結果、特定の結果が出力される確率が高くなるのです。
まとめ
量子コンピュータを一言で、説明すると量子の波の振幅を上手に増幅させて、ほしい答えを探し出すゲームと表現できます。次回は、量子コンピュータを使うことで、どんな問題が解決できるのかを解説したいと思います。
参考文献
[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge Univ. Press, 2000).
[2] 嶋田義皓 (2020) 「量子コンピューティング」 情報処理学会出版委員会
[3] 藤井啓介 (2019) 「驚異の量子コンピュータ」 岩波書店
[4] 武田俊太郎 (2020) 「量子コンピュータが本当にわかる!」 技術評論社