Miyamoto
1 はじめに
中山茂氏「量子アルゴリズム」を参考に、入門概説を行います。
近年、世間を賑わせている量子コンピューターについて、簡単な解説を行います。
私の専門は量子論ではなく確率論なので、包括的な説明ではなく、わかる範囲での概略説明となります。ご了承ください。
世間には、ふわふわした説明の資料があふれかえっているので、ここでは簡潔に数式一発で説明していきます。
2 基礎知識
2.1 数学
ユニタリ行列の定義について、簡単に復習しましょう。
定義1 ユニタリ行列
ユニタリ行列とは、随伴行列が逆行列となる複素正方行列である。
すなわち\(n\)次正方行列\(U\)が
(1)
\[U^{-1}=\overline{U^{T}}\]
を満たすことである。
ユニタリ行列は、\(\mathbb{R}^n \to \mathbb{R}^n \)の線形作用素として、自己共役作用素であることに注意しましょう。
ついでに、内積の定義について
定義2 内積
写像\(T\)が線形空間\(\mathcal{X}\)上の内積とは、\(T : \mathcal{X}^2 \to \mathbb{C}\)が以下の条件を満たすことを言う。
(2)
\[T(x, y)=\overline{T(y, x)}\]
(3)
\[\forall \lambda \in \mathbb{C}, T(x, \lambda y)=\lambda T(x, y)\]
(4)
\[T(x, y+z)=T(x, y)+T(x, z)\]
(5)
\[\forall x \in \mathcal{X}, T(x, x) \geq 0\]
(6)
\[T(x,x) = 0 \to x = 0\]
ただし、\(x = 0\)とは、\(x\)が\( \mathcal{X} \)上のゼロ元であることを指します。
また、今後\(T(x,y)\)を\(⟨x,y⟩_ \mathcal{X} \)と表記します
2.2 量子力学
量子とは、ミクロな世界にある「それ以上分解不能な最小単位」で、次のような性質を持ちます。
2.2.1 二重性
角周波数（波の性質）と、粒子として量子化した場合のエネルギー（粒子の性質）両方を持ちます。
2.2.2 離散
エネルギー準位は離散値をとります。つまり、エネルギー量等は、なんらかの最小単位があり、すべてその整数倍で表されます。
2.2.3 不確定性
運動量と位置の両方を観測することはできないという性質です。
ハイゼンベルグの不確定性原理と言い、不確定性は次のような不等式で表されるそうです。
(7)
\[\Delta x \Delta p_{x} \geq h / 2\]
それぞれ位置の不確定性と運動量の不確定性で、\(\hbar > 0\)です。
位置が確定すると\(\Delta x = 0 \)で、\( \Delta p_x = \infty\)になるという話らしいのですが、通常の数の世界では定式化できません。
もしかしたらよく知らないけども超準解析のような枠組みなら定式化可能なのかもしれないと考え、厳密な定義については調査中です。もし資料等ご存知でしたら教えていただけると幸いです。
2.3 量子状態の特徴
量子コンピューターは、このような性質を持つ「量子」という存在を計算に応用します。
古典コンピューターでは、\(0\)と\(1\)という2 つの状態を持つビットを使ったブール論理というものを使います。
一方で量子コンピューターは、\(0\)と\(1\)という状態が確率的に重ね合わさった状態を考えます。
2.3.1 量子重ね合わせ状態
1 つの量子ビットは次のような式で表されます。
(8)
\[|\phi\rangle=\alpha|0\rangle+\beta|1\rangle\]
係数\(\alpha , \beta\)は、量子ビットがそれぞれ\(0,1\)をとる確率を表します。
ただし、ここで注意したいのが、数字そのまま \(\alpha , \beta\) が確率を表すわけではないというのが量子ビットと確率的ビットの違い。
確率的ビットは \(\alpha , \beta \in \mathbb{R}_{0\leq x \leq 1}\)で\(\alpha + \beta = 1\)ですが、
量子ビットは\( \alpha ,\beta \in \mathbb{C_{0\leq \mid z \mid \leq _1}}\)で\(\mid \alpha \mid ^2 + \mid \beta \mid ^2 = 1~\)がなりたちます。
そして、それぞれのビットを取る確率は\(\mid \alpha \mid ^2, \mid \beta \mid ^2 \)です。
確率的ビットは\([0,1]\) 上に存在するビットですが、量子ビットは\(\mid z \mid \leq 1\)上に存在するため、はるかに表現能力が高くなります。
2.3.2 量子干渉効果
波と波が干渉しあうように、量子状態同士にも干渉があります。
下記のもつれと異なり、量子単体で表現が可能です。
(9)
\[\left\langle\phi^{\prime}, \phi\right\rangle \neq 0\]
この値を干渉成分と言います。
2.3.3 量子もつれ状態
2 つ以上の量子間に相関関係が発生しており、切り離せない状態です。
片方の量子を観測すると、もつれ状態が壊れ、別の量子も影響を受けて状態が固定されます。
数式で書くと、最小の量子ビットを用いて、テンソル積分離した表現ができないということです。
(10)
\[\left|\phi_{E P R}\right\rangle \neq\left|\phi_{1}\right\rangle \otimes\left|\phi_{1}\right\rangle\]
この性質により、量子テレポーテーションという現象が起こります。これはテレポーテーションと名がついていながら、光速を超えることはできません。
また、実用的な大質量\(^{\ast 1}\)テレポーテーション技術への応用には程遠く、また倫理的な問題もあるため \(^{\ast 2}\)
2.4 余談：コペンハーゲン解釈とエヴェレット解釈
ここまでに紹介した「確率的に状態が存在しており、観測によって状態が決定される」という解釈はコペンハーゲン解釈と呼ばれます。
それとは別の解釈も存在し、その代表的なものは「エヴェレット解釈」です。
エベレット解釈は簡単に言えば「世界が分岐する」という考え方です。この世界に存在する状態は１つであり、0の世界と1 の世界が並列に存在し、どの世界に分岐していくかが確率的に決まっているという立場をとります。
この考えであれば、「観測により状態が決定される」という諭を持ち出す必要がなく、既存物理学に大きく反しないようです。
この並行宇宙は、SF 作品では「パラレルワールド」と呼ばれます。ダイバージェンスメーターは現在の分岐位置を表すわけです。
量子アルゴリズムはコペンハーゲン解釈に立脚していますが、エヴェレット解釈でしか説明できない現象も存在するようです。
量子アルゴリズムの世界に、強引にエヴェレット解釈を持ち込むと、「パラレルワールドの分岐を利用して計算する」という、たかが計算なのにスケールが大きすぎる話になってしまいます。
しかし、根源的に相いれないというわけではなく、エヴェレット派の学者には「実用的な量子コンピューターが完成することが、パラレルワールドが存在することの証明になる」と主張する人もいるようです。
3 量子もつれ、量子並列
3.1 3 ビットの場合のもつれ
古典ビットでは8 通りの\(000,001,010,011,100,101,110,111\)の状態が考えられるが、これを二進数で表し\(\mid 0 \rangle , \mid 1 \rangle , ……, \mid 7 \rangle \)と書くとします。
では\(\mid 5 \rangle = \mid 101 \rangle \)の場合、エンタングルメント（もつれ）は発生しているでしょうか。答えは発生していない、です。
(11)
\[\mid 101 \rangle = \mid 1 \rangle \otimes \mid 0 \rangle \times \mid 1 \rangle \]
と表せます。ただし\(\mid 1 \rangle = (0,1)^T,\mid 0 \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)\]
が挙げられます。\(^{\ast 3}\)
\(^{\ast 1}\) 基準が量子であるため、1mg でも「超巨大質量」です
\(^{\ast 2}\) 「どこでもドアのパラドックス」「スワンプマン」など、すでに有名な思考実験が存在しています。ここで出てくるどこでもドアは藤子F 不二夫の考案した本来の設定とは異なることに注意。
\(^{\ast 3}\) いろいろ試してみればわかりますが、実際にはビット数が増えると等分割だけでもほとんどのベクトルがエンタングルメントなしで表現できません。むしろ「エンタングルメントがない」ことがとても異常な状況だと言えます。
量子アルゴリズムの強みは、この確率的な不確定性をそのまま扱うことができ、それによって一度の関数評価で多数の計算ができる点にあります。
つまり、重ね合わせ状態を利用することで
(13)
\[f(|\phi\rangle) \rightarrow|f(0)\rangle+\ldots . .+|f(7)\rangle\]
を一度に計算できます。量子ビットの数に対して性能は指数増大すると言われる所以はここにあります。これを量子並列処理と言います。
4 計算量について
ここではまず計算量に関する一般論についてお話し、そのあと計算時間を比較します。
4.1 オーダー
計算量の上限を表す水準です。計算したい任意のデータの規模\(n\)に対して、最悪の場合の計算回数を\(f(n)\)とし、ある定数\(c\)が存在して
(14)
\[f(n) \leq cg(n)\]
と書けるなら、この計算量を\(O(g(n))\)と表記し、「\(g(n)\)のオーダー」と呼びます。
\(n\)は計算対象データの規模です。巡回セールスマン問題なら町の数、迷路ならマス目の数です。
任意の\(n\)に対してある定数\(c\)で上限取れるときは「定数オーダー」と言い、\(O(1)\)と書きます。
ある定数\(k\)が存在し、\(O(n^k)\)のとき、これを「多項式オーダー」と言います。
実用的なアルゴリズムは基本的にこの多項式オーダーです。
\(O(k^n)\)の時、これを「指数オーダー」と言います。あっという間に爆発するので、基本的によほど小さな\(n\)に対してしか使えないアルゴリズムです。\(^{\ast 4}\)
さらに上にあるのが\(O(n!)\)の場合。これは「階乗オーダー」といい、基本的には役に立たないアルゴリズムです。
4.2 多項式オーダーでの計算
通常のコンピューターは決定性チューリングマシンと呼ばれる計算機構です。
それに対して、より計算能力の高い、単体で無制限に並列分岐計算ができる未実現の仮想的な非決定性チューリングマシンと呼ばれる計算機構も考えることができます。\(^{\ast 5}\)
決定性チューリングマシンで多項式オーダーとなる問題を\(P\)問題、非決定性チューリングマシンで多項式オー ダーとなる問題を\(NP\)問題と言います。
\(P\) 問題なら \(NP\) 問題であることは、非決定性チューリングマシンは決定性 チューリングマシンの上位互換であることから自明です。
では「 \(NP\) 問題で \(P\) 問題ではない」という問題は存在する でしょうか。 これについてはまだわかっていません。
具体例もないうえ、理論的にもまだまだ未検証の問題です。これを 「\(P \neq NP\) 予想」と言い、数学の7 大未解決難問である「ミレニアム懸賞問題」の1 つです。
解ければ確実に偉人の 仲間入りです。さあ、みなさんも、「 \(NP\) だが \(P\) でない」タスクを発見しましょう。もしくは \(P = NP\) を証明しま しょう。\(^{\ast 6}\)
\(^{\ast 4}\)n が20 増えるだけで計算量の上限は10,0 00,000,000 倍以上になります。
\(^{\ast 5}\)DNA を使って実現できるのではという仮説もありますが、まだ実験にすら至ってない仮説段階です。
\(^{\ast 6}\)ミレニアム懸賞問題は、2000 年に発表された7 つの問題のことを指します。そのうち「ポアンカレ予想」だけは解かれましたが、残りの6つは未解決です。賞金は100 万ドル。割に合わない。
4.3 計算オーダーの比較
いくつかの問題に対して、通常のコンピューターと量子コンピューターを比較します。
特に重要なのがサイモン問題とドイチ・ジョサ問題です。既存のアルゴリズムでは指数オーダーなので、大きい\(n\)には手も足も出ない状況だったのに対して、量子アルゴリズムでは定数ないし多項式オーダーで計算できます。
無論、ここで列挙したのは量子コンピューターが得意な分野ばかりであり、あらゆる状況で必ず量子が優れているわけではありません。これは量子コンピューターに対する世間の過度な期待の一つです。
5 弊社開発への展望
量子アルゴリズムには、量子ゲート型と量子アニーリング型があり、量子ゲートは汎用性は高いものの実現がより難しいとされています。
もちろん、量子ゲートによる計算時間大幅削減はあらゆるIT 分野に光をもたらすのですが、それ以外の展望として、量子アニーリングによる手法についても、特化領域に対しては非常に強く、近い未来に世界各所で成果を上げるのはこのアニーリングのほうでしょう。
量子アニーリングのビジネス応用と言えば、RCO\(^{\ast 8}\)の有名な量子アニーリングを用いた広告最適化が挙げられますが、弊社もビジネス応用に手を広げる展望があります。
5.1 量子アニーリング入門
量子断熱計算という手法について簡単に基礎を解説します。
次のシュレディンガー方程式 \(^{\ast 9}\) を考えます。
(15)
\[i \hbar \frac{\partial|\psi(t)\rangle}{\partial t}=H(t)|\psi(t)\rangle\]
ただし\(\hbar\)はプランク定数、\(H\)はハミルトニアンで、\(\mid \psi (t)\rangle \)は状態ベクトルです。
ハミルトニアンは時間ごとに変化します。具体的には、問題とは無関係な初期状態の作用素\(H_0\)と、問題に依存する最終状態の\(H_1\)という二つのハミルトニアンを用いて、
(16)
\[H(t):=(1-t)H_0+ tH_1\]
この\(t\)を\(0 \to 1\)とすることで、量子アルゴリズムによる最適化を偏微分方程式で表すことができます。
\(^{\ast 7}\)計算量の下限
\(^{\ast 8}\)リクルートコミュニケーションズ社
\(^{\ast 9} \)量子力学において重要な偏微分方程式
5.2 ダイナミックプライシングへの応用
強化学習への応用はもちろん考えることができます。単純にQ 関数を用いた強化学習に対して、計算が早くなるのは当然のメリットと言えます。
それ以外にも、イジングモデルを用いた新しい手法も考案中です。続報にご期待ください。