Jones多項式のPathモデル表現について


# Jones多項式のPathモデル表現について

「結び目」を表現する重要な不変量として「Jones多項式」というものがあります。Jones多項式は、整数係数の多項式の形をしている不変量ですが、量子計算分野をはじめ、その数学・物理学への幅広い応用性から非常に有用な多項式として注目されています。

今回の記事では、Jones多項式を量子計算によって近似するアルゴリズムを示した論文、"A Polynomial Quantum Algorithm for Approximating the Jones Polynomial"（以下、執筆者（Dorit Aharonov, Vaughan Jones, Zeph Landau）の頭文字をとって「AJL論文」）の内容から、特に「Pathモデル表現」を使ってJones多項式をユニタリ行列で表現する手法について、私自身の理解度をメモしておく意味も込めて、書いてみたいと思います。


## Jones多項式について

まず、Jones多項式の定義と、それに従った求め方について簡単に説明します。

説明が前後しますが、数学でいうところの「結び目」というのは、位相幾何学の一分野です。例えば、連続した紐の両端を繋ぐと環ができますが、このとき紐の絡まり方によって「結び目」ができます。この結び目について、ある「結び目A」を、切ったり繋ぎなおしたりすることなく変形（伸ばしたり、縮めたり、回転したり、裏返したり）していって、最終的に「結び目B」に重ね合わせることが出来るなら結び目Aと結び目Bは「同じ」、そうでない場合「異なる」と言うことが出来ます。

<div>
<img src="https://qiita-image-store.s3.amazonaws.com/0/320885/96e08d4d-e7ad-642d-f959-78f01dd0b21f.jpeg" />
</div>

これらの結び目が「同じであるか否か」を表す指標として様々な「不変量」というものが定義されており、その一つがJones多項式です。

### Jones多項式を定義にしたがって求める

#### 「自明な結び目」

Jones多項式では、「交叉が全くない1個の環」＝「自明な結び目」を1とします。


![knot-trivial1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/6e5c06df-025a-7296-118b-6e6d1974b96a.jpeg) $\hspace{50pt} V_0 = 1 $



#### スケイン関係式

結び目の交差部分に注目して「スケイン関係式」という3つの結び目の関係式を作ります。

![skein1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/045113ec-27ff-cb15-5e86-c516671043fd.jpeg)

上図の例では、赤い丸で囲まれた部分の交叉を入れ替えることで3種類の結び目、$L_{+}, L_{-}, L_o$を作っていますが、それぞれの結び目のJones多項式$V_{L_{+}}, V_{L_{-}}, V_{L_{o}}$の間には、変数$t$を用いた関係式
$$
t^{-1} V_{L_{+}} - t V_{L_{-}} = (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{L_{o}}
$$
が成り立ちます。

このスケイン関係式を交叉点ごとに次々に生成していき、全てが「自明な結び目」となるまで繰り返し、対象となる結び目のJones多項式を計算します。

#### 8の字結び

比較的単純な結び目として「8の字結び」というものがあります。
![knot8-1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/f25267d2-8c10-dbf3-d95d-18b13d669cfd.jpeg)


この「8の字結び」のJones多項式を実際に計算してみましょう。

- 第1段階

![knot8-skein1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/9be4cf92-f5bf-80e1-b417-9fe8f2ba2a99.jpeg)

左から、それぞれのJones多項式を、$V_8, V_0, V_{HL}$とすると、
$$
t^{-1} V_{8} - t V_{0} = (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{HL}
$$

- 第2段階

第1段階の中央は「自明な結び目」なので、右端の$V_{HL}$(「ホップリンク」という結び目)をさらに分解します。

 ![knot8-skein2.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/e155a7b3-0566-652e-00ac-d9fae9f05d0b.jpeg)

同様に、左から$V_{HL}, V_{oo}, V_0$とすると

$$
t^{-1} V_{oo} - t V_{HL} = (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{0}
$$


- 第3段階

第2段階の右端は「自明な結び目」です。中央の$V_{oo}$は「自明な結び目」が2つあるので、ここからさらに関係式を作ります。

![knot8-skein3.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/c0f275fd-f571-f594-aa26-877eb946c1c7.jpeg)

$$
t^{-1} V_{0} - t V_{0} = (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{oo}
$$

これで、図中に登場する全ての結び目と「自明な結び目」の関係式を作ることが出来ました。

```math
\begin{align}
t^{-1} V_{8} - t =& \; (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{HL} \\
t^{-1} V_{oo} - t V_{HL} =& \; t^{\frac{1}{2}} - t^{-\frac{1}{2}} \\
t^{-1} - t =& \; (t^{\frac{1}{2}} - t^{-\frac{1}{2}}) V_{oo}
\end{align}
```
以上の式を解くことによって、目的の「8の字結び」のJones多項式は

```math
V_8 = t^2 - t + 1 - t^{-1} + t^{-2}
```
となります。

## Jones多項式の行列表現

上記のやり方を複雑な結び目に対して行うのは簡単なことではなく、また、このままでは量子計算に応用することが出来ません。AJL論文では、結び目を行列の積で表すことにより、任意の結び目に対応する表現を簡単に計算する手法が述べられています。

行列を得るまでのステップを簡単に並べると、

1. 結び目を組み紐（Braid）群で表現する
2. Braid群をTemperley-Lieb代数によって表現する
3. Temperley-Lieb代数を満たすビット列「Pathモデル」を定義する
4. Pathモデルを量子ビットで表現する
5. Temperley-Lieb代数の生成元を表現する行列を求める
6. Braid群の生成元の行列を求める

といった流れになります。

### 1. 結び目を組み紐（Braid）群で表現する

まず、結び目理論と密接な関係にあるBraid群（組み紐群）について考えます。
Braidというのは、複数の紐がどのように絡み合っているかを数学的に表現したもので、結び目はBraidに対応させることが出来ます。
![braid-closure.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/dc3e9ca7-7728-cd30-dca0-5116c7dff800.jpeg)


Braidの形にすることで、積を使った合成、およびBraidの群が定義できます。任意のBraidはBraid群の生成元の積で表現することが出来るので、Braid群の生成元を行列で表すことができれば、結び目を表現できると言えます。

![braid-product.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/ecc23242-633b-b831-1977-ff0cbd79d80d.jpeg)


Braid群の生成元は具体的には以下のようなもので、下記の式で表される性質を持っています（図は紐が4本の場合）。

$ \sigma_1 = \hspace{10mm} $![braid-s1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/11d8469f-5f91-819c-7209-76d65740ab6a.jpeg)


$ \sigma_2 =  \hspace{10mm} $![braid-s2.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/58bf974b-ced0-0bcf-3302-2ae13bdf1a59.jpeg)



```math
\begin{align}
\sigma_{i}\sigma_{j} =& \; \sigma_{j}\sigma_{i} \hspace{10mm} (| i-j | \geq 2)  \\
\sigma_{i+1}\sigma_{i}\sigma_{i+1} =& \; \sigma_{i}\sigma_{i+1}\sigma_{i}
\end{align}
```

(この関係式は、Braidの生成元の積を実際に作ってみると簡単に確認することが出来ます）

### 2. Braid群をTemperley-Leib代数によって表現する

ここで、AJL論文には「Temperley-Lieb代数(以下、TL代数)」というものが登場します。TL代数は図のような生成元に基づいた計算を提供するものです。

- TL代数の生成元の例

$ E_1 = \hspace{10mm} $ ![tld-e1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/55da354b-266f-40dd-d9f8-f308244b4838.jpeg)
$ E_2 = \hspace{10mm} $ ![tld-e2.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/2745510b-0809-59a9-8077-7089f8db5833.jpeg)

- TL代数の積

![tld-prod.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/6453191e-a01b-ad0c-a7e9-dc4236f218b9.jpeg)

TL代数の生成元には、下記の性質があります。

```math
\begin{align}
E_i E_j =& \; E_j E_i \hspace{10mm} (|i-j| \geq 2) \\
E_i E_{i \pm 1} E_i =& \; E_i \\
E_i ^2 =& \; d E_i
\end{align}
```

Braid群、TL代数、それぞれの生成元の性質を見比べると、適切な複素数Aを定義することによって下記のような関係式を成立させることが出来ることがわかります。

Braid群の生成元$\sigma_i$のTL代数における表現を$\rho(\sigma_i)$で表した場合

```math
\begin{align}
d =& \; -A^2 - A^{-2} \\
\rho(\sigma_i) =& \; A E_i + A^{-1} I
\end{align}
```

![braid-tld.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/77b1ac75-f1d5-15d6-3c35-e954b0db1656.jpeg)

ここで、行列表現への変換$\tau$を定義して、

```math
\begin{align}
\tau(E_i) = & \Phi_i \\
\end{align}
```
と表すことにします。

### 3. TL代数を満たすビット列「Pathモデル」を定義する

TL代数の生成元を行列で表現するために、TL代数の線で区切られた領域に番号をつけることを考えます。

![tld-region1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/0cfcbacc-0921-58a5-d6e6-bab41ff7c0b9.jpeg)

TL代数の要素は上半分の数列を下半分の数列に変換（または、その逆）するものと考え、各数列をベクトルに割り当てることでTL代数を行列で表現することを考えます。

AJL論文ではこの数列、およびベクトルの作り方として、ノード数が$(k-1)$の一次元グラフ上を移動する「Pathモデル」を使って表現します。「Pathモデル」では左端を1として、紐をまたぐごとに$\pm 1$して自然数の数列を作ります。

Braidの紐が3本(n=3)の場合について考えると、下記のような番号の付け方が考えられます。
![path1.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/23c0e38e-c429-80b1-5064-826e581a8de4.jpeg)

このPathそれぞれについて、左から右へ+1した場合を"1"、-1した場合を"0"で符号化した数列をベクトルと考えます。上記の3種類のベクトルはそれぞれ、"101", "110", "111"となります。

これらのベクトルとTL代数の生成元との間には、



```math
\begin{align}
\Phi_i \big{\vert} p \big{\vert} _{i} 00 \big{>} =& 0 \\
\Phi_i \big{\vert} p \big{\vert} _{i} 01 \big{>} =& \frac{\lambda_{z_{i}-1}}{\lambda_{z_{i}}} \big{\vert} p \big{\vert} _{i} 01 \big{>}+ \frac{\sqrt{\lambda_{z_{i}+1} \lambda_{z_{i}-1}}}{\lambda_{z_{i}}} \big{\vert} p \big{\vert} _{i} 10 \big{>} \\
\Phi_i \big{\vert} p \big{\vert} _{i} 10 \big{>} =& \frac{\lambda_{z_{i}+1}}{\lambda_{z_{i}}} \big{\vert} p \big{\vert} _{i} 10 \big{>} + \frac{\sqrt{\lambda_{z_{i}+1} \lambda_{z_{i}-1}}}{\lambda_{z_{i}}} \big{\vert} p \big{\vert} _{i} 01 \big{>} \\
\Phi_i \big{\vert} p \big{\vert} _{i} 11 \big{>} =& 0 \\
\end{align}
```

の関係式が成り立ちます。（$\lambda_l = sin \frac{\pi l}{k} (l \in \{ 1, 2, ... k-1\})$ で、$z_i$は$i$番目の領域に割り当てられた番号です）

なお、この式中で例えば、$\, \big{\vert} p \big{\vert} _{i} 10 \big{>} \,$という表記は、以下のようなベクトルを意味しています。

![path2.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/33765a17-d19a-5272-a8f6-4681814bb963.jpeg)


### 4. Pathモデルを量子ビットで表現する

ここでは、最も簡単なk=4の場合のPathモデルについて考えることにします。k=4の場合、割り当て可能な数字は{1, 2, 3}のいずれかのみとなるため、ベクトルとして下記の2通りのPathが存在します。
![path3.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/f5dfbedb-9e44-dd0f-db68-b5e06916e79b.jpeg)


それぞれのPathを量子ビットの0と1に対応させ、関係式を作ります。

```math
\begin{align}
\big{\vert} 0 \big{>} =& \; \big{\vert} "101" \big{>} \\
\big{\vert} 1 \big{>} =& \; \big{\vert} "110" \big{>} \\
A =& \; i \cdot e^{-\frac{\pi i}{8}} \\
d =& \;  2cos\frac{\pi}{4} (= \sqrt{2}) \\
\lambda_l =&  \;  sin \frac{\pi l}{4} \hspace{10mm} (l \in \{ 1, 2, 3\}) \\
\lambda_l =&  \;  0  \hspace{10mm} (l \notin \{ 1, 2, 3\}) \\
\end{align}
```
として、計算を行います。


### 5. TL代数の生成元を表現する行列を求める

これで、ようやく$E_1$の行列表現$\Phi_1$を求めることが出来るようになりました。3.にある関係式に値を代入して

```math
\begin{align}
\Phi_1 \big{\vert} 0 \big{>} =& \; \frac{\lambda_2}{\lambda_1} \big{\vert} 0 \big{>} + \frac{\sqrt{\lambda_0 \lambda_2}}{\lambda_1} \big{\vert} 1 \big{>}\\
\Phi_1 \big{\vert} 1 \big{>} =& \; 0 \\
\end{align}
```


となることから

```math
\Phi_1 = 
\Big{(}
\begin{matrix}
\sqrt{2} & 0 \\
0 & 0 
\end{matrix}
\Big{)} 
```
と計算できます。

### 6. Braid群の生成元の行列を求める

2.にあるTL代数とBraid群の生成元の関係式

$$
\tau(\rho(\sigma_1)) = \; A \Phi_1 + A^{-1} I
$$
より、

```math
\tau(\rho(\sigma_1)) = 
e^{\frac{\pi i}{8}}
\Big{(}
\begin{matrix}
1 & 0 \\
0 & -i 
\end{matrix}
\Big{)}
```
となります。

他の生成元についても同様に$\Phi_2, \rho(\sigma_2)$を求めると、以下のようになります。

```math
\begin{align}
\Phi_2 \big{\vert} 0 \big{>} =& \; \frac{\lambda_1}{\lambda_2} \big{\vert} 0 \big{>}+ \frac{\sqrt{\lambda_1 \lambda_3}}{\lambda_2} \big{\vert} 1 \big{>}\\
\Phi_2 \big{\vert} 1 \big{>} =& \; \frac{\sqrt{\lambda_1 \lambda_3}}{\lambda_2} \big{\vert} 0 \big{>}+ \frac{\lambda_3}{\lambda_2}\big{\vert} 1 \big{>}\\
\end{align}
```

```math
\Phi_2 = \frac{1}{\sqrt{2}}
\Big{(}
\begin{matrix}
1 & 1 \\
1 & 1 
\end{matrix}
\Big{)} 
```


```math
\tau(\rho(\sigma_2)) = \frac{1}{\sqrt{2}}
\Big{(}
\begin{matrix}
e^{-\frac{\pi i}{8}} & e^{\frac{3 \pi i}{8}} \\
e^{\frac{3 \pi i}{8}} & e^{-\frac{\pi i}{8}} 
\end{matrix}
\Big{)}
```


## 行列表現を使ってみる

以上でBraid群の生成元を行列で表現することができたので、任意の結び目を行列の積として表現することが可能になります。

具体的に、8の次結びを行列の積で表現してみます。8の字結びはBraidで表現すると図のようになります。
![braid-knot8.jpg](https://qiita-image-store.s3.amazonaws.com/0/320885/94d31173-bc0a-75d9-fb35-252dd038e5ac.jpeg)

したがって、求めたい行列表現$\Phi$は

```math
\begin{align}
\Phi =& \; \tau(\rho(\sigma_2^{-1})) \cdot \tau(\rho(\sigma_1))  \cdot
\tau(\rho(\sigma_2^{-1}))  \cdot
\tau(\rho(\sigma_1)) \end{align}
```
と行列の積によって求めることが出来ます。生成元の行列さえ求めてしまえば、とても簡単に計算できることが解ると思います。


## 量子計算

結び目を表現する行列を求めることが出来るようになったので、「アダマールテスト」という量子計算を行うことで「Jones多項式の１の累乗根における近似値」を求めることができます。この具体的な計算を含めた実行例については、別途、改めて記事を書いてみたいと思います。

## 最後に

以上、長々と書いてまいりましたが、私の理解が浅い部分もあり、また間違っている部分もあるかもしれません。その場合は、ご指摘いただけましたらありがたい限りです。
今回は拙い記事をお読みいただき、どうもありがとうございました。

## 参考文献、および参考記事
- Dorit Aharonov, Vaughan Jones, Zeph Landau, A Polynomial Quantum Algorithm for Approximating the Jones Polynomial
- [QISKitでJones多項式の量子アルゴリズム](https://qiita.com/SelMut/items/8aa2a9a21b39da2bd28d)