はじめに中山茂氏「量子アルゴリズム」を参考に、入門概説を行います。近年、世間を賑わせている量子コンピューターについて、簡単な解説を行います。私の専門は量子論ではなく確率論なので、包括的な説明ではなく、わかる範囲での概略説明となります。世間には、ふわふわした説明の資料があふれかえっているので、ここでは簡潔に数式一発で説明していきます。数学ユニタリ行列の定義について、簡単に復習しましょう。ユニタリ行列ユニタリ行列とは、随伴行列が逆行列となる複素正方行列である。\(n\)次正方行列\(U\)が(1)\[U^{-1}=\overline{U^{T}}\]を満たすことである。\)の線形作用素として、自己共役作用素であることに注意しましょう。\mathbb{C}\)が以下の条件を満たすことを言う。\)上のゼロ元であることを指します。量子とは、ミクロな世界にある「それ以上分解不能な最小単位」で、次のような性質を持ちます。角周波数(波の性質)と、粒子として量子化した場合のエネルギー(粒子の性質)両方を持ちます。離散エネルギー準位は離散値をとります。エネルギー量等は、なんらかの最小単位があり、すべてその整数倍で表されます。運動量と位置の両方を観測することはできないという性質です。ハイゼンベルグの不確定性原理と言い、不確定性は次のような不等式で表されるそうです。\infty\)になるという話らしいのですが、通常の数の世界では定式化できません。したらよく知らないけども超準解析のような枠組みなら定式化可能なのかもしれないと考え、厳密な定義については調査中です。資料等ご存知でしたら教えていただけると幸いです。量子コンピューターは、このような性質を持つ「量子」という存在を計算に応用します。つの状態を持つビットを使ったブール論理というものを使います。一方で量子コンピューターは、\(0\)と\(1\)という状態が確率的に重ね合わさった状態を考えます。つの量子ビットは次のような式で表されます。\beta\)は、量子ビットがそれぞれ\(0,1\)をとる確率を表します。確率を表すわけではないというのが量子ビットと確率的ビットの違い。1~\)がなりたちます。1\)上に存在するため、はるかに表現能力が高くなります。波と波が干渉しあうように、量子状態同士にも干渉があります。下記のもつれと異なり、量子単体で表現が可能です。0\]この値を干渉成分と言います。以上の量子間に相関関係が発生しており、切り離せない状態です。片方の量子を観測すると、もつれ状態が壊れ、別の量子も影響を受けて状態が固定されます。数式で書くと、最小の量子ビットを用いて、テンソル積分離した表現ができないということです。\otimes\left|\phi_{1}\right\rangle\]この性質により、量子テレポーテーションという現象が起こります。これはテレポーテーションと名がついていながら、光速を超えることはできません。余談:コペンハーゲン解釈とエヴェレット解釈ここまでに紹介した「確率的に状態が存在しており、観測によって状態が決定される」という解釈はコペンハーゲン解釈と呼ばれます。それとは別の解釈も存在し、その代表的なものは「エヴェレット解釈」です。エベレット解釈は簡単に言えば「世界が分岐する」という考え方です。世界が並列に存在し、どの世界に分岐していくかが確率的に決まっているという立場をとります。この考えであれば、「観測により状態が決定される」という諭を持ち出す必要がなく、既存物理学に大きく反しないようです。作品では「パラレルワールド」と呼ばれます。ダイバージェンスメーターは現在の分岐位置を表すわけです。量子アルゴリズムはコペンハーゲン解釈に立脚していますが、エヴェレット解釈でしか説明できない現象も存在するようです。量子アルゴリズムの世界に、強引にエヴェレット解釈を持ち込むと、「パラレルワールドの分岐を利用して計算する」という、たかが計算なのにスケールが大きすぎる話になってしまいます。根源的に相いれないというわけではなく、エヴェレット派の学者には「実用的な量子コンピューターが完成することが、パラレルワールドが存在することの証明になる」と主張する人もいるようです。\)の場合、エンタングルメント(もつれ)は発生しているでしょうか。答えは発生していない、です。(1,0)^T\)このように、ある一点に集中する測度は、エンタングルメントなしで表現することが可能です。逆に、もつれなしでは表現できない測度の例としては(12)\[|\phi\rangle=\frac{1}{\sqrt{6}}(|0\rangle+|1\rangle+|2\rangle+|3\rangle+|4\rangle+|6\rangle+|7\rangle)\]が挙げられます。「どこでもドアのパラドックス」「スワンプマン」など、すでに有名な思考実験が存在しています。不二夫の考案した本来の設定とは異なることに注意。試してみればわかりますが、実際にはビット数が増えると等分割だけでもほとんどのベクトルがエンタングルメントなしで表現できません。「エンタングルメントがない」ことがとても異常な状況だと言えます。量子アルゴリズムの強みは、この確率的な不確定性をそのまま扱うことができ、それによって一度の関数評価で多数の計算ができる点にあります。.+|f(7)\rangle\]を一度に計算できます。量子ビットの数に対して性能は指数増大すると言われる所以はここにあります。これを量子並列処理と言います。計算量についてここではまず計算量に関する一般論についてお話し、そのあと計算時間を比較します。計算量の上限を表す水準です。cg(n)\]と書けるなら、この計算量を\(O(g(n))\)と表記し、「\(g(n)\)のオーダー」と呼びます。\(n\)は計算対象データの規模です。巡回セールスマン問題なら町の数、迷路ならマス目の数です。任意の\(n\)に対してある定数\(c\)で上限取れるときは「定数オーダー」と言い、\(O(1)\)と書きます。ある定数\(k\)が存在し、\(O(n^k)\)のとき、これを「多項式オーダー」と言います。実用的なアルゴリズムは基本的にこの多項式オーダーです。\(O(k^n)\)の時、これを「指数オーダー」と言います。あっという間に爆発するので、基本的によほど小さな\(n\)に対してしか使えないアルゴリズムです。4}\)さらに上にあるのが\(O(n!)\)の場合。これは「階乗オーダー」といい、基本的には役に立たないアルゴリズムです。通常のコンピューターは決定性チューリングマシンと呼ばれる計算機構です。それに対して、より計算能力の高い、単体で無制限に並列分岐計算ができる未実現の仮想的な非決定性チューリングマシンと呼ばれる計算機構も考えることができます。ダーとなる問題を\(NP\)問題と言います。チューリングマシンの上位互換であることから自明です。これについてはまだわかっていません。具体例もないうえ、理論的にもまだまだ未検証の問題です。