第 14 回 量子コンピュータ

本日の内容


このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

14-1. 力学

ニュートン力学

ニュートンの力学において、運動方程式など様々な式があります。 例えば、通常の質点の運動に関して F = m a が成り立ちますが、一方剛体の回転 に関しては N = I α と良く似た性質が成り立ちます。 これに対して、数学的に統一的に扱うようにしたのが解析力学です。 ラグランジュ力学では、物体の位置と速度に関して、系のエネルギーを記述するような ラグランジアン と呼ばれる量を定義し、それが時刻 t1 から t2 へ移行する際に、変化が最小になるように、物体は運動するというものでした。 この原理を 最小作用の原理と言います。

その後、ハミルトンはハミルトン力学を提唱しました。 これは ハミルトニアン と呼ばれる、系のエネルギーを運動量と位置で記述したものの和として定義し ました。

ハミルトニアンに関して最小作用の原理を適用します。 最小となる位置の関数を q t , 運動量の関数を p t = m dq dt とします。 これに対して変分法を適用します。 つまりt1 から t2 区間の間、微小な変化 δq t , δp t , を考えます。これらは始点と終点つまり、 t = t1 , t2 で 0 となることを仮定します。 これに関して最小作用の原理は次の δS が 0 に近いということを意味します。

δS = t1 t2 H q + δq p + δ p dt - t1 t2 H q p dt

これは偏微分の定義と、部分積分の公式を用いると次の様になります。

δS = m dH dp δq t1 t2 + t1 t2 - m d dt dH dp + dH dq δq dt

これが常に 0 になるためには次が成り立つことが必要です。

- m d dt dH dp + dH dq = 0

なお、別の議論により 下記の正準方程式が得られます。

dp dt = - dH dq dq dt = dH dp

例14-1

図のような高さ y0 から初速 vx=v で質点を x 軸方向に投げます。 このときハミルトニアンは次の様になります。

量子力学

量子力学とは

小さな物体は通常のニュートン力学の範疇では捉えられないことが分かってき ました。 まず、電磁波はマクスウェルの方程式により波であることが分かりましたが、 コンプトン効果などにより、粒子としての性質を持つことが分かってきました。 このコンプトン効果とは、光がエネルギーとして電子に吸収され、再度それが 光として出力されるような現象において、出力される光のエネルギー分布が離 散的な値になるというものです。 これに対して、アインシュタインは光が粒子であると仮定するとうまく説明で きることを指摘しました。 その後、電子も粒子である性質の他、回析を起こすなど、波の性質があること がわかり、ニュートン力学とは別の物理法則が必要であることがわかりました。

そして生まれたのが量子力学です。 これは、ハミルトン力学の発展形となるようなシュレーディンガー方程式と、 行列力学という二つの定式化がされましたが、後にこれが等価であることがわ かりました。

量子化とは

式変形により、物理量が実数値から微分演算子に変換されることを示します。

波動関数は、空間と場所を引数として得られる運動量の関数を空間をパラメー タにしてフーリエ変換したものです。 シュレーディンガー方程式

i dψ dt = H ψ

なお、シュレーディンガー方程式は、ハミルトニアンが時間に対して一定であ る時、次の様に解を求めることができます。

dψ ψ = H i dt log ψ = - i H t + C ψ = e - i H t + C ψ t = ψ 0 e - i H t

これを 行列力学的に解釈すると 無限次元(ヒルベルト空間)の状態ベクトル |φ> ψ に対して、ユニタリ行列をかけることにより次の時刻の状態が得られ ます。

確率振幅

電子の回析現象とは、次のようなものです。 二つのスリットに対して電子線を当てると、スリットの後ろのどこかに電子が 到達します。 その時の到達確率(統計値)が単なる一つずつのスリットの統計値の和になる のではなく、干渉を起こして一つずつの時より増える部分と減る部分が生じる ということです。 但し、干渉を起こすといっても、それぞれの電子一つ一つが各地点で強弱つけ て観測されるのではなく、電子はあくまでも一個です。 結果として到達する数に関して多い少ないということが干渉として解釈できる ということです。

これの解釈に関してはさまざまな論争があります。 また、実際にどのような仕組みであるかは看破できないかも知れません。 ここではもっとも有力なコペンハーゲン解釈について説明します。

コペンハーゲン解釈とは観測可能な状態が波の様に重なり合った状態になって いて、観測した時に特定の現象に収斂するというものです。 例えば、スリットを通過した電子はスクリーン面に確率分布にしたがって重な り合った形で存在していると考えます。 そして、観測すると、特定の現象がその確率に応じて観測されます。

14-2. 量子コンピュータの基礎

二次元複素ベクトル空間

また、複素数 c = x + y i に対して、共役 c * = x - y i で表します。 また、大きさは c = a2 + b2 とします。

行列 A = a ij に対して、転置行列 A t = a ji で表します。 また、エルミート行列 A * = a* ji で表します。 さらに、単位行列を I としたとき、ユニタリ行列 U は下記を満たす 正方行列です。

U U * = I

一様な磁場の中での陽子などの スピンを考えると、 特定の量子が重ね合わさっている状態で、観測すると 0 の情報か 1 の情報が 得られます。 このように、行列力学的な解釈として現象が二現象の重ね合わせになるような ものをデータの保存を行う単位として選びます。 この時、状態として、二つの現象を区別する単位ベクトルを 0 = 1 0 1 = 0 1 とし、これの重ね合わせを計算の単位(1bit)とすることとします。 これを Qbit と呼びます。 φ=φ0 (1,0) + φ1 (0,1) ψ = ψ0 1 0 + ψ1 0 1 = ψ0 0 + ψ1 1 となっているような状態の時、 1 0 に対応した現象が実際に観測される確率は、 ψ0 2 ψ0 2 + ψ1 2 |φ1^2/(φ1^2+φ2^2) となります。

さらにこの現象が複数存在し、直積的な関係のあるような状況を考える。 つまり、 ψ 1 = ψ 10 1 0 + ψ 11 0 1 ψ 2 = ψ 20 1 0 + ψ 21 0 1 の直積 ψ 1 ψ 2 = ψ 1 ψ 2 を考える。

最初の2現象と次の2現象に関して、起きうる現象は 最初が  で、次が 最初が で、次が など4通りの組み合わせがある。 これに対して、それぞれ単位ベクトルを用意し、 と単位ベクトル同士の直積を定義する。 0 1 = 0 1 などと定義します。

これは、 |φ1> = φ10(1,0)+φ11(0,1) |φ2> = φ20(1,0)+φ21(0,1) 単位ベクトル (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1) 1 0 0 0 , 0 1 0 0 , 0 0 1 0 , 0 0 0 1 に対し て、

これを |φ1,φ2> と書くと

φ10φ20(1,0,0,0)+ φ11φ20(0,1,0,0)+ φ10φ21(0,0,1,0)+ φ11φ21(0,0,0,1)

を意味します。 同様の意味で 以下を |φ1,...,φn> のような表記をします。

ψ1 ... ψn = i1 ... in = 0 1 ψ 1 , i 1 ... ψ n , i n i1 ... in

n 個の 2x2 の正方行列 A1 , ... , An について、下記の様に積を定義する。特に A1 ... An をテンソル積と言う。 (n Qbit に対して、 2n 個の計算があることに注意)

A1 ... An ψ1 ... ψn = i1 ... in = 0 1 ψ 1 , i 1 ... ψ n , i n A1 i1 ... An in

量子チューリング機械

量子チューリング機械はテープとして、 Qbit が連続してあるようなものを考 えます。 また、状態遷移関数は δ p a b q d = c δ(p,a,b,q,d)=c という 状態が p, ヘッドが a を読んでいるとき(観測ではなく)、新たに b を書き込 み、状態を q に移し、ヘッドの方向を d に移動する事象の確率振幅を |c|2 と定義する。 このとき、行列 Mδ のc1 行 c2 列は、 c2 から c1 への 1 ステッ プの遷移と対応したδの値になる。 ただし、ここでも Mδ はユニタリ行列になる。

14-3. 量子コンピュータのプログラミング

NOT

01 10 ψ = ψ 1 , 0 01 10 1 0 + ψ 1 , 1 01 10 0 1 |x> → |1-x>

AND

f(x,y,0)=x,y, x and y

|0> <0| x |0> <0| x I + |0> <0| x |1> <1| x I + |1> <1| x |0> <0| x I + |1> <1| x |1> <1| x (0 1 ; 1 0)

14-4. 有名なアルゴリズム

Shor のアルゴリズム

実は、 n Qbit のベクトルに対して、離散フーリエ変換を行ったときの nQbit の関数表は量子多項式時間で求めることができます。

Shor は量子コンピュータを使って、多項式時間で高い確率で、因数分解と、 離散対数問題が解けることを示しました。

yr = 1 mod n となるようなもっとも小さい r を y の mod n のオーダーと言います。 もし、非自明な r が求まると、 n の素因数分解ができます。

  1. 入力を n とします
  2. n2≤q≤2n2 となる「なめらかな整数」q を 選びます
  3. n と互いに素な整数 x をランダムに選びます
  4. 同じ x を用いてオーダー log q 回繰り返す
    1. 二つの量子変数 reg1, reg2 を用意する
    2. reg1 は 0 から q-1 までの全ての値の重ね合わせとする
    3. reg1 の各値 a に対して、xa mod n の値の重ね合わせを reg2 に入れる
    4. reg2 を観測する。 k' が観測されると、reg1 には xa' = k mod n となるような a' が観測できる
    5. この、 a' を離散フーリエ変換する
    6. フーリエ変換の結果を観測すると、ある値 c' が得られる。 これは、 q/r の λ 倍になっている
    7. c'/q の連分数展開を行うと λ/r が求められる
  5. これによりサンプルがいくつか分かり、最終的に r が求まる。
  6. gcd(xr/2-1,n) と gcd(xr/2+1,n) より n を素因 数分解する

Groover の選択問題

関数 f(x) が特定の x=x0 で f(x0)=1 になり、他の x では f(x)=0 となるよ うなことを考えます。


坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科