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

# 量子計算

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

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

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

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


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

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

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

## TL;DR

[itsubaki/q: Quantum Computation Simulator](https://github.com/itsubaki/q)

## 線形代数

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

### ベクトル

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

```go
type Vector []complex128
```

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

```go
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`の二次元配列として表せます。

```go
type Matrix [][]complex128
```

行列演算を実装します。

```go
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そのものです。

```go
type Qubit struct {
	v vector.Vector
}
```

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

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

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

```go
// |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ゲートなどがよく使われますがここでは割愛します。
ただの行列です。

```go
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の値を反転します。

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

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

```go
// 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>`になります。

```go
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>`に収縮します。

```go
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>)`を作る量子回路は以下になります。

```go
// |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に移すことは可能です。
これを量子テレポーテーションと呼びます。

量子回路は以下です。

```go
// ベル状態の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の探索アルゴリズムも同様にシミュレートできます。