第 14 回 量子コンピュータ

本日の内容


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

14-1. 量子コンピュータ

コンピュータとは、計算をさせる装置である以上、何らかの物理法則にした がっています。 我々の世界を支配している物理法則は相対論的量子力学ですから、この力学 に基づいた計算原理を考える必要があります。 現在の電子コンピュータは、シャノンが示したbool演算を実現する電子回路を 原理として動作しています。 しかし、これらと異なる原理による計算が不可能というわけではありません。 ここでは、量子力学を原理とした計算について紹介します。

量子 bit

量子コンピュータで行う計算も情報処理に違いありませんので、情報の単位 は bit になります。 量子状態でbitを保持できるとします。 量子状態は人間による観測によって確定して、情報を取り出すことができま す。 但し、量子状態は通常は確率的な値になります。つまり 1 bit を表す量子 状態を観測すると、確率 a で 0 が取り 出せ、確率 b で 1 が取り出せる ということになります。 この量子bit(q bit)の実現方法も色々議論されてい ますが、ここでは実現法ではな く、数学モデルについて説明します。

量子状態には、重ね合わせという概念があります。 これは複数の状態が同時に重ね合わさっていて、人間が観測することにより、 一つの状態に収束しそれが観測されるという概念です。 これをコペンハーゲン解釈といいます。

量子力学の問題点を指摘するための、「シュレーディンガーの猫」という思考 実験があります。これは、箱の中に猫を綴じ込め、α線の発生源、 観測器、毒ガス発生器を仕組み、α線が観測されたら毒ガスが発生し、猫が 死ぬように作られた装置を考えます。 一時間以内にα線が観測される確率が 50% であるとします。すると、コペンハーゲ ン解釈によると、箱の中の猫は、生きている猫と死んでいる猫が量子状態で 重ね合わさっていると考えることができます。 この生きている猫と死んでいる猫の重ね合わせの状態というのは、人間の思 考として俄に受け入れがたいものですが、コペンハーゲン解釈ではそう考え るもので、しかも、実際に見ようとすると一つの状態に収束してしまうので、 決して重ね合わせ状態を観測することはできません。

ここで、Dirac の記号を導入します。 行ベクトルを φ と書き、ブラベクトルと呼びます。 一方、 列ベクトルを ψ と書き、ケットベクトルと呼びます。 すると、内積は φ ψ と書けます。

さて、量子ビット(q bit) に関しての数学モデルを考えます。0 の状態と 1 の状態をそれぞれ線形代数の位置ベクトルとし、正規直交基底であるとしま す。 0状態の基底を 0 で表し、 1状態の基底を 1 で表すと、これは二次元の正規直交基底なので次が成り立ちます。

0 = 1 0 1 = 0 1

これの重ね合わせは a 0 + b 1 と書けます(a,bは複素数)。 状態ベクトルが常に大きさが1であるとすると、 a2 + b2 = 1 という制約が必要です。 この時、 0, 1 がそれぞれ観測される確率は、 a2 b2 になります。

多 q bit

さて、複数の量子ビットの取扱いをどうするかですが、基本的には同じ考え 方をします。 2 bit の場合、取りうる状態は 00, 01, 10, 11 です。 この 4 状態はそれぞれ別の状態なので、正規直交基底になります。 4次元の正規直交基底なので次のようになります。

00 = 1 0 0 0 01 = 0 1 0 0 10 = 0 0 1 0 11 = 0 0 0 1

これらの状態の重ね合わせを次のように書きます。

φ = α 00 00 + α 01 01 + α 10 10 + α 11 11

つまり、これは4次元単位球の表面の位置ベクトルを意味します。 φ を観測して、 00, 01, 10, 11 が観測される確率は、それぞれ α002 α012 α102 α112 になります。

このように単純にビット数が増えると、次元が増えます。 これを演算として扱う、テンソル積を導入します。 φ ψ = φ φ の意味は前述した通り、次元を拡張するだけです。

n個の q bit はこの様に2n次元の基底の重ね合わせで表現されます。

量子計算

さて、この q bit を物理現象に基づいて計算させることを考えます。 これは量子力学に従います。 先ほども述べたように、大きさ 1 で正規化するので、実際にこの量子計算 は q bit に対するユニタリ行列の積になります。

さらに、研究により、複雑なユニタリ行列は以下のような基本的なユニタリ 行列を多次元に拡張(0を挿入)の積で表せることが分かっています。

Hadamard
1 2 11 1-1
位相
10 0i
制御NOT
10 00 01 00 00 01 00 10
π/8ゲート
10 0eiπ/4

従って、これらのユニタリ行列と対応した物理現象が起きるような装置を作 成すれば、量子コンピュータが実現できるようになります。 一つのq bit を実現するのに、2次元のベクトルが必要で、 上記のユニタリ行列が2または4次元なので、これは従来のコンピュータの概 念では論理ゲートにあたります。 つまり、ある q bit の列、 φ に対して上記のユニタリ行列 U1, U2,...,Un があって、 U1 U2 ... Un φ を計算するのに、実際は個々の特定の q bit に対して、上記の定めら れた演算を行う回路のようなものを考えれば良いことになります。

14-2. 力学

ニュートン力学

ニュートンの力学において、運動方程式など様々な式があります。 例えば、通常の質点の運動に関して 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-3. 量子コンピュータの基礎

二次元複素ベクトル空間

また、複素数 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-4. 量子コンピュータのプログラミング

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-5. 有名なアルゴリズム

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>
東京電機大学工学部情報通信工学科