量子計算
電子などが持つ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の探索アルゴリズムも同様にシミュレートできます。