Goで量子計算シミュレータを実装する。

量子計算

電子などが持つspinと呼ばれる物理量に対して磁場や相互作用をかけ、計算に相当する時間的変化を起こすことを量子計算と呼びます。

量子計算は数学的には線形代数で表せます。spinは複素列ベクトル、磁場や相互作用をかけることはユニタリー行列を複素列ベクトルにかけることに相当します。

量子計算ではこの複素列ベクトルをqubit(量子ビット)、ユニタリー行列を量子ゲートと呼びます。

物理	数学	量子計算
spin	複素列ベクトル	qubit
磁場/相互作用	ユニタリー行列	量子ゲート

量子ゲート(と後ほど出てくる測定)を組み合わせたものを量子回路と呼びます。
量子計算とは量子回路を使ってqubitの状態を変化させること。とも言えます。

古典計算	量子計算
bit	qubit
論理ゲート	量子ゲート
論理回路	量子回路

今回は、Goでqubitや量子ゲートを実装し量子テレポーテーションをシミュレートします。

TL;DR

itsubaki/q: Quantum Computation Simulator

線形代数

まず、基礎となる複素列ベクトルと行列演算を実装します。
行列積、テンソル積を実装すれば十分です。

ベクトル

複素列ベクトルはcomplex128の配列で表すことができます。

type Vector []complex128

ベクトルに対する演算を実装していきます。

v0 := vector.New(1, 1)
v1 := vector.New(1, -1)

// 内積
v0.InnerProduct(v1) // -> complex(0, 0)

// 直交
v0.IsOrthogonal(v1) // -> true

// テンソル積
v0 := vector.New(1, 0)
v1 := v0.TensorProduct(v0) // -> Vector{1, 0, 0, 0}

行列

行列はcomplex128の二次元配列として表せます。

type Matrix [][]complex128

行列演算を実装します。

x := make(Matrix, 2)
x[0] = []complex128{0, 1}
x[1] = []complex128{1, 0}

// 行列積
i := x.Apply(x)
fmt.Println(i)
// ->
[[1, 0] 
 [0, 1]]

// テンソル積
xx := x.TensorProduct(x)
fmt.Println(xx)
// ->
[[0, 0, 0, 1]
 [0, 0, 1, 0]
 [0, 1, 0, 0]
 [1, 0, 0, 0]]

量子計算

次に、ベクトルや行列を使ってqubitや量子ゲートを実装していきます。

qubit

qubitはVectorそのものです。

type Qubit struct {
	v vector.Vector
}

bitを0、1で表すのに対し、qubitは|0>、|1>と表します。

// |0>
q := qubit.Zero()
q.Probability()
// -> [1, 0]
// |0>である確率が1、|1>である確率が0であることを示している。

複数qubitはテンソル積で表せます。
2bitを00、01、10、11と表すように、2qubitでは|00>、|01>、|10>、|11>と表します。

// |00>
zero := qubit.Zero()
q := zero.TensorProduct(zero) 
q.Probability()
// -> [1, 0, 0, 0]
// |00>である確率が1、|01>、|10>、|11>である確率が0。

// これは以下と同じである。
q := qubit.TensorProduct(zero, zero)
// -> [1, 0, 0, 0]

q := qubit.Zero(2)
// -> [1, 0, 0, 0]

量子ゲート

1qubitに対する演算であるパウリゲートとアダマールゲートを実装します。
他にもTゲート、Sゲートなどがよく使われますがここでは割愛します。
ただの行列です。

gate.I()
// ->
[[1, 0]
 [0, 1]]
// このゲートは単位行列であるため、qubitの状態は変化しない。

gate.X()
// ->
[[0, 1]
 [1, 0]]
// NOTゲート。|0>を|1>に、|1>を|0>にする。

gate.Y()
// ->
[[0, -i]
 [i,  0]]

gate.Z()
// ->
[[1,  0]
 [0, -1]]
// |1>の符号を反転させる。

gate.H()
// -> 
1/Sqrt(2) * [[1, 1] [1, -1]]
// |0>と|1>の重ね合わせ状態を生成する。

CNOT(Controlled-NOT)ゲート
2qubitに対する演算です。
1つ目のqubitの値が|1>の場合に、2つ目のqubitの値を反転します。

gate.CNOT()
// ->
[[1, 0, 0, 0]
 [0, 1, 0, 0]
 [0, 0, 0, 1]
 [0, 0, 1, 0]]

複数qubitに対する量子ゲートはqubitと同様にテンソル積で表せます。

// 2qubitに作用する量子ゲート。
// 1つ目のqubitにHゲートを、2つ目のqubitにXゲートを作用させる。
hx := gate.H().TensorProduct(gate.X())

// 以下でも同じである。
hx := matrix.TensorProduct(gate.H(), gate.X())

// 複数qubitに同じゲートを作用させる量子ゲートは以下で生成できる。
// 1つ目と2つ目にアダマールゲートを作用させる量子ゲート。
hh := gate.H(2)

測定

量子計算ではqubitの状態を測定すること自体が演算であり、測定を行うとqubitの状態が変化します。
この演算は量子ゲートと異なり不可逆です。
測定を行うとqubitの状態は|0>または|1>になります。

q := qubit.Zero()
q1 := q.Apply(gate.H())

q1.Probability()
// -> [0.5, 0.5]
// 本来はこのときの確率を得ることはできない。
// この出力はシミュレータだからできる。
// 測定したときに、50%の確率で|0>または|1>になることを示している。

q1.Measure()
q1.Probability()
// -> 50%の確率で[0, 1]、50%の確率で[1, 0]
// 我々は測定後の|0>か|1>しか得ることはできない。

部分測定

複数qubitの計算では特定のqubitだけ測定することも(当然)できます。
例えば2qubitの取り得る状態は|00>、|01>、|10>、|11>です。
1つ目のqubitを測定した結果が|0>の場合、取り得る状態は|00>、|01>に収縮します。

q := qubit.Zero(2).Apply(gate.H(2))
q.Probability()
// -> [0.25, 0.25, 0.25, 0.25]
// 25%の確率で|00>、|01>、|10>、|11>

// 1つ目のqubit(0番目)を測定する。
q0 := q.Measure(0)

if q0.IsZero() {
 q.Probability()
 // -> [0.5, 0.5, 0, 0]
 // 1つめのqubitは|0>なので、取り得る値は|00>か|01>となる。
 // 確率はNormalizeされ、各々50%となる。
}

if q0.IsOne() {
 q.Probability()
 // -> [0, 0, 0.5, 0.5]
 // 1つめのqubitは|1>なので、取り得る値は|10>か|11>となる。
 // 確率はNormalizeされ、各々50%となる。
}

量子回路

量子回路は量子ゲートと測定を組み合わせたものです。

ベル状態

ベル状態1/Sqrt(2)*(|00>+|11>)を作る量子回路は以下になります。

// |00>に初期化されたqubit
q := qubit.Zero(2)

// ベル状態を作るための量子回路
hi := gate.H().TensorProduct(gate.I())
cn := gate.CNOT()
qc := hi.Apply(cn)

// 作用させる。
bell := q.Apply(qc)

// 状態を確認する。
bell.Probability()
//-> [0.5, 0, 0, 0.5]
// 測定すると50%の確率で|00>、50%の確率で|11>になる。
// これは1つ目のqubitを測定し結果が|0>の場合、2つ目のqubitは必ず|0>になり、
// 同様に1つ目のqubitが|1>ならば、2つ目のqubitは|1>になることを示している。

ベル状態では1つ目のqubitを測定すると2つ目のqubitの値が確定します。
このような状態をエンタングル状態と呼びます。

量子テレポーテーション

未知のqubitはコピーできないことが知られています。しかし、エンタングルを利用して未知のqubitを他のqubitに移すことは可能です。
これを量子テレポーテーションと呼びます。

量子回路は以下です。

// ベル状態のqubitを用意する。
qc := gate.H().TensorProduct(gate.I()).Apply(gate.CNOT())
bell := qubit.Zero(2).Apply(qc)

// 未知のqubitを用意する。
phi := qubit.New(1, 2)
// 総和が1になるようにNormalizeされる。
// -> [0.2, 0.8]

// ベル状態のqubitと未知のqubitを合わせて3qubitの初期状態を作る。
q := phi.TensorProduct(bell)

// 量子回路を作用させる。
g0 := matrix.TensorProduct(gate.CNOT(), gate.I())
g1 := matrix.TensorProduct(gate.H(), gate.I(2))
q.Apply(g0).Apply(g1)

// 未知のqubit(0番目)とベル状態の1つ目のqubit(1番目）を測定する。
mz := q.Measure(0)
mx := q.Measure(1)

// ベル状態の1つ目の測定結果が|1>の場合
// ベル状態の2つ目のqubitにXゲートを作用させる。
if mx.IsOne() {
 x := gate.I(2).TensorProduct(gate.X())
 q.Apply(x)
}

// 未知のqubitの測定結果が|1>の場合
// ベル状態の2つ目のqubitにZゲートを作用させる。
if mz.IsOne() {
 z := gate.I(2).TensorProduct(gate.Z())
 q.Apply(z)
}

// ベル状態の2つ目のqubitは未知のqubitの状態になっている。
q.Probability()
// 出力は以下の4パターンになる。
mz, mx = |0>|0> -> [0.2, 0.8, 0, 0, 0, 0, 0, 0]
mz, mx = |0>|1> -> [0, 0, 0.2, 0.8, 0, 0, 0, 0]
mz, mx = |1>|0> -> [0, 0, 0, 0, 0.2, 0.8, 0, 0]
mz, mx = |1>|1> -> [0, 0, 0, 0, 0, 0, 0.2, 0.8]

まとめ

Goでqubitや量子ゲートを実装し、量子テレポーテーションをシミュレートしました。
R(θ)ゲートやControlled-Zゲートなどを実装すれば、Shorの素因数分解アルゴリズム(の核である量子フーリエ変換)やGroverの探索アルゴリズムも同様にシミュレートできます。