量子情報：北海道大学大学院情報科学研究科情報エレクトロニクス専攻先端エレクトロニクス講座

　実は量子計算が本当に古典的な計算機より速いかはわかっていません.ただ，ある種の問題についてこれまで知られているどんな古典アルゴリズムよりも計算が速いアルゴリズムがあることは確かで，おそらく古典アルゴリズムが今より速くなることはないだろうと信じられていので量子計算の優位性はかなり確からしいです．とりあえず量子計算を研究するには十分な根拠でしょう．その一例が素因数分解を行うアルゴリズムです．素数の掛け算は簡単にできますが，掛け算の答えから元の数を求めるのは大変な仕事です．これまで知られているアルゴリズムでは問題の数の桁数の準指数で計算に必要な時間が増えていきます．指数といえばねずみ算と一緒であっという間に天文学的な大きさになってしまいます．量子アルゴリズムでは桁数の多項式で増えていくのでまだ計算できることになります（計算機科学の世界では多項式時間で計算できるとき，効率的に計算できるというようです．) 素因数分解の難しさは現代暗号の安全性に深く関連しているため，この量子アルゴリズム（Shorという人が考えたのでShorのアルゴリズムといわれています)が提案されたときはちょっとした騒ぎがおき，多くの人が量子情報の研究に参入しました．
もう一つ実は，ですが，量子計算のスピードアップにどのような量子力学的な性質が重要なのかも確定していません.これは基礎的にも重要な問題であるばかりでなく，計算機の設計にも関係することで現在も多くの研究者が頭を悩ませています． 一応の理解としては以下のようなことです．

　重ね合わせにより全てのビット値の組み合わせを1つの量子状態で表すことができます．例えば，3ビットだと2x2x2=8通りあるあらゆる組み合わせを試すには普通の古典的計算では8回演算が必要になるわけが，ところが量子では8つの状態の重ねあわせを1つの状態ベクトルで表し，1回で全ての組み合わせに対する演算ができることになります．nビット数では2n個の組み合わせがありますから，量子演算は指数的に計算が速く、ビット数が大きくなるほど優位性が際立ってきます．

　ところが，この話には落とし穴があって，演算した結果を求めるためには測定を繰り返さなければなりません.先ほどの話にもあった通り，状態が1個では1回の測定しかできないため，何回も演算した状態を作り直さなければならず，結局指数的な優位性は失われてしまいます．
そこで，演算結果の状態から答えとして必要な状態だけを選び出すアルゴリズムが必要になります．ここで干渉や量子力学的な相関が使われています.そういったうまいアルゴリズムが見つけられた問題というのはまだ限られていて，素因数分解アルゴリズムとその拡張が主なものですが，そこでは(逆)量子フーリエ変換が使われています．

　このアルゴリズムの量子部分の基本は位相推定で，あるユニタリー変換の固有値を求めなさいと言うものです．このために制御ユニタリー変換を使います制御ビット(c)に重ね合わせ状態を使うとユニタリー変換は標的ビット(a)にかかっているのに(あら不思議)制御ビットの位相が変わります(キックバック)．そこで，標的ビットはもう放っておいて制御ビットの位相をフーリエ変換して取り出せばよいというわけです．

　もう一つ有名なものにGroverアルゴリズムがあって，こちらは総当り的なデータ探索を効率よく行うアルゴリズムです．ただし指数的なスピードアップではなく古典でNステップ必要だった計算がNの平方根ステップでできるというものです．このアルゴリズムは汎用性が高く，機械学習への応用も考えられています．