Plabic tilingのためのRソースメモ

f:id:ryamada:20210506172018j:plain

V <- matrix(0,13,18)
F <- matrix(0,15,18)
E <- matrix(0,18,18)

V[1,c(12,14,7,3,4,5,6,10,8)] <- 1
V[2,c(14,7,16,11,5,6,8,10,12)] <- 1
V[3,c(14,7,16,9,8,11,10,15,12)] <- 1
V[4,c(14,2,16,11,9,13,12,10,15)] <- 1
V[5,c(14,2,16,11,15,13,6,18,12)] <- 1
V[6,c(14,2,16,4,15,6,18,17,13)] <- 1
V[7,c(1,2,16,15,4,6,17,8,18)] <- 1
V[8,c(1,2,3,4,5,6,17,8,18)] <- 1
V[9,c(1,2,3,4,6,5,10,12,8)] <- 1
V[10,c(1,2,16,4,5,6,8,12,18)] <- 1
V[11,c(14,2,16,4,5,6,8,10,12)] <- 1
V[12,c(14,2,16,4,15,6,12,18,8)] <- 1
V[13,c(14,2,16,11,10,15,6,12,8)] <- 1

theta <- (1:18) / 18 * 2 * pi
x <- cbind(cos(theta),sin(theta))

Vx <- V %*% x

plot(Vx,pch=20,col=1,asp=TRUE)

F[1,c(12,2,14,10,3,4,5,6,8)] <- 1
F[2,c(14,7,16,6,4,5,8,12,10)] <- 1
F[3,c(14,16,11,6,10,7,15,8,12)] <- 1
F[4,c(14,2,11,16,9,15,8,10,12)] <- 1
F[5,c(14,2,11,16,15,6,13,12,10)] <- 1
F[6,c(14,13,16,2,4,6,15,18,12)] <- 1
F[7,c(14,2,16,4,8,17,15,6,18)] <- 1
F[8,c(1,2,16,4,5,17,6,8,18)] <- 1
F[9,c(1,2,3,4,5,6,8,18,12)] <- 1
F[10,c(1,2,5,16,4,6,8,10,12)] <- 1
F[11,c(1,2,16,12,15,4,6,8,18)] <- 1
F[12,c(14,2,4,16,12,6,8,5,18)] <- 1
F[13,c(14,12,2,4,16,10,15,6,8)] <- 1
F[14,c(14,2,16,10,11,5,6,8,12)] <- 1
F[15,c(14,6,2,11,18,15,6,8,12,16)] <- 1

Fx <- F %*% x

points(Fx,pch=20,col=2)

E[1,c(2,10,4,3,16,5,6,8,12)] <- 1
E[2,c(14,2,7,6,8,4,5,10,12)] <- 1
E[3,c(14,16,4,11,5,6,8,10,12)] <- 1
E[4,c(10,12,14,6,2,7,11,16,8)] <- 1
E[5,c(14,6,8,16,9,11,15,12,10)] <- 1
E[6,c(14,2,15,16,13,11,8,10,12)] <- 1
E[7,c(14,16,11,2,10,6,15,18,12)] <- 1
E[8,c(14,12,2,8,16,15,13,6,18)] <- 1
E[9,c(14,2,17,16,4,12,15,18,6)] <- 1
E[10,c(1,2,16,6,14,4,15,8,18)] <- 1
E[11,c(17,1,2,16,4,6,8,12,18)] <- 1
E[12,c(1,2,3,4,5,6,8,16,18)] <- 1
E[13,c(1,2,4,12,18,5,6,8,10)] <- 1
E[14,c(1,14,16,2,4,5,6,8,12)] <- 1
E[15,c(2,16,5,15,4,6,18,8,12)] <- 1
E[16,c(14,2,12,4,16,10,6,8,18)] <- 1
E[17,c(14,10,16,2,5,6,15,8,12)] <- 1
E[18,c(14,16,2,4,11,15,12,6,8)] <- 1

Ex <- E %*% x

points(Ex, pch=20,col=3)

VFE <- rbind(V,F,E)
col.v <- c(rep(4,length(V[,1])),rep(5,length(F[,1])),rep(6,length(E[,1])))

X <- VFE %*% x


distmat <- as.matrix(dist(VFE, method="manhattan"))




el <- which(distmat==2,arr.ind=TRUE)


# 3角形は、V,F,Eを1つずつ頂点とするので、適切なトリオを選ぶ


tris <- matrix(0,0,3)

for(i in 1:length(V[,1])){
	for(j in 1:length(F[,1])){
		for(k in 1:length(E[,1])){
			tmp0 <- c(i,j+13,k+13+15)
			tmp <- distmat[tmp0,tmp0]
			diag(tmp) <- 2
			if(sum((tmp-2)^2) == 0){
				tris <- rbind(tris,tmp0)
			}
		}
	}
}

#tris <- rbind(c(1,1,2),c(1,2,2),c(2,2,3),c(2,14,3),c(2,3,4),c(3,3,5),c(3,4,5),c(4,4,6),c(4,5,6),c(5,5,7),c(5,15,7),c(5,6,8),c(6,6,9),c(6,7,9),c(7,7,10),c(7,11,10),c(7,11,11),c(7,8,11),c(8,8,12),c(8,9,12),c(9,9,13),c(9,10,13),c(9,1,1))

#tris[,2] <- tris[,2] + 13
#tris[,3] <- tris[,3] + 13 + 15

tri.col <- rep(0,length(tris[,1]))
for(i in 1:length(tris[,1])){
	tmp <- VFE[tris[i,],]
	if(prod(apply(tmp,2,sum) -1) == 0){
		tri.col[i] <- 2
	}else{
		tri.col[i] <- 3
	}
	
}


########
# Plabic graph G*
par(mfcol=c(2,2))

plot(X, pch=20,cex=2,col=col.v,asp=TRUE)
segments(X[el[,1],1], X[el[,1],2],X[el[,2],1],X[el[,2],2])

for(i in 1:length(tris[,1])){
	polygon(X[tris[i,c(1,2,3,1)],1],X[tris[i,c(1,2,3,1)],2],col=tri.col[i])
}

points(X,pch=20,col=col.v,cex=2)


#########
# Vの3角形はうまく描ける
plot(X, pch=20,cex=2,col=col.v,asp=TRUE)
segments(X[el[,1],1], X[el[,1],2],X[el[,2],1],X[el[,2],2])

for(i in 1:length(tris[,1])){
	polygon(X[tris[i,c(1,2,3,1)],1],X[tris[i,c(1,2,3,1)],2],col=tri.col[i])
}


distmat.v <- as.matrix(dist(V,method="manhattan"))
el.v <- which(distmat.v==4,arr.ind=TRUE)

points(Vx,pch=20)
segments(Vx[el.v[,1],1],Vx[el.v[,1],2],Vx[el.v[,2],1],Vx[el.v[,2],2],lw=2)

##########
# Fの3-valentグラフはこの方法ではうまく描けない
# 組み合わせ的距離では、Vを介して多数のFペアの距離が同じになるから
plot(X, pch=20,cex=2,col=col.v,asp=TRUE)
segments(X[el[,1],1], X[el[,1],2],X[el[,2],1],X[el[,2],2])

for(i in 1:length(tris[,1])){
	polygon(X[tris[i,c(1,2,3,1)],1],X[tris[i,c(1,2,3,1)],2],col=tri.col[i])
}


distmat.f <- as.matrix(dist(F,method="manhattan"))
el.f <- which(distmat.f==4,arr.ind=TRUE)

points(Fx,pch=20)
segments(Fx[el.f[,1],1],Fx[el.f[,1],2],Fx[el.f[,2],1],Fx[el.f[,2],2])

##########
# Eをつないだ箙はこの方法ではうまく描けない
# 組み合わせ的距離では、Vを介して多数のEペアの距離が同じになるから

plot(X, pch=20,cex=2,col=col.v,asp=TRUE)
segments(X[el[,1],1], X[el[,1],2],X[el[,2],1],X[el[,2],2])

for(i in 1:length(tris[,1])){
	polygon(X[tris[i,c(1,2,3,1)],1],X[tris[i,c(1,2,3,1)],2],col=tri.col[i])
}


distmat.e <- as.matrix(dist(E,method="manhattan"))
el.e <- which(distmat.e==4,arr.ind=TRUE)

points(Ex,pch=20)
segments(Ex[el.e[,1],1],Ex[el.e[,1],2],Ex[el.e[,2],1],Ex[el.e[,2],2])

平面ネットワークのPlucker 座標

arxiv.org

  • n個の点が円周上に配置されているとする
  • その内部円板に有向グラフがあるとき、適当な変形を加えることで、3-valent有向グラフに変えることができる
  • このグラフをplanar circular directed graphと呼ぶ
  • さらに、3-valent有向グラフを3-valent bipartite plabic グラフに変えることもできる
  • このplanar circular directed graphの円周上の点はただ1本の辺に接続するというルールがあるので、すべての円周上の点は、湧き出し口か吸い込み口かのどちらかになる
  • 今、湧き出し口の数がk個、吸い込み口の数がn-k個であり、円周上の点の数がnであるとする
  • このグラフにk \times n行列を定義することができる。Boundary measurement matrixと呼ぶ
  • この行列はk \times n; k \le nであるので、この行列には、Plucker座標が定められる
  • ちなみに、Plucker座標とは、(1,2,...,n)からk個の要素を取り出したときに(_n C_k通りの組合せが作れる)、それぞれの組について、Boundary measurement matrixの該当列を取り出すことで、k \times k行列が取れるが、そのk \times k行列の行列式の値を取り出すことで、結局、_n C_k個の値が取れることとなり、その値を並べたものがPlucker 座標であり、グラスマニアンという空間上の点を指し示している(ただし、斉次座標になっている)
  • さて、planar circular directed graphの場合に、Boundary measurement matrix ( A=(a_{i,j})の要素a_{i,j}として、湧き出し口頂点から1頂点 i を取り除き、その代わりに吸い込み口の頂点から1頂点 jを追加してできるk個の頂点の組合せを考えた時に、頂点iから湧き出して、頂点jに吸い込まれるようなパスの本数に相当する値m_{i,j}を考え、j番目が、湧き出し口のすべてより若いか、すべてより大きいか、湧き出し口の間に挟まれているか、さらには気にしている湧き出し口頂点 i番と比べて若いか大きいかによって、m_{i,j}の符号を変えたものをa_{i,j}とすることにする
  • このとき、Plucker 座標の要素のすべてが非負になることが知られている
  • その結果、planar circular networkはpositive grassmanian上の点に対応付けられる、という話がある
  • このリンク先のペイパーでは、このPlucker座標が、k個の列の選び方に応じて、networkに取れる、ある種の正エッジ重みづけパス本数セットに関する値になっていることを示している
  • 基本的には、正重みづけでの「取りうるパスの場合」に関する足し合わせであることから、すべてのPlucker座標が非負になる
  • また、そのパス本数セットに相当する値の計算式は、内部にサイクルがなければ単純な式になり、サイクルがあると、有理式になるのだが、その様子が団代数・団変数と同じ挙動をすることも示せる
  • そもそも、planar circular networkで小行列式が非交叉パスの取り方の場合分けと関係した非負の値がとれる(ただし、符号の考慮が必要)な話は、左列にあるn頂点から、右列にあるn頂点へのplanar directed graphがあったときに、非交叉パスの場合の数が符号を考えなくて良い小行列式で表されることが知られており、それをcircularに拡張した時に、湧き出し口・吸い込み口の相互位置関係に関して複雑になっている部分を符号操作で一般化したものになっている
  • 内部のサイクルによる補正のことは忘れて、あるplanar circular networkがあって、そのBoundary measurement matrixを取り、そのPlucker 座標がすべて正になることを例で確かめてみよう
  • こんなグラフ

f:id:ryamada:20210429113353j:plain

tmp <- c(7,1,2,8,11,3,12,4,5,15,6,18,7,8,8,9,9,10,10,11,11,12,13,12,14,13,15,14,15,16,16,17,17,18,18,19,19,20,20,7,9,20,13,10,19,21,21,22,22,14,22,16,17,21)
el <- matrix(tmp,byrow=TRUE,ncol=2)

library(igraph)
g <- graph.edgelist(el)

theta <- pi/2 - (1:14)/14 * 2 * pi

theta. <- theta[c(1,2,5,6,9,12,1:14,13,9)]
r <- c(rep(1,6),rep(0.8,14),rep(0.4,2))
coords <- cbind(cos(theta.),sin(theta.)) * r
plot(g,layout = coords)
  • 湧き出し口頂点は2,5,6で、吸い込み口頂点は1,3,4
  • このBoundary measurement matrixは以下のようになる
# 頂点 iからjへのパスの数の列挙
paths <- list()

for(i in 1:22){
	paths[[i]] <- list()
	for(j in 1:22){
		paths[[i]][[j]] <- all_simple_paths(g,i,j)
	}
}

A <- matrix(0,3,6) # 湧き出し口数 x 全周囲頂点数 の行列
sources <- c(2,5,6) # 湧き出し頂点ID
for(i in 1:3){ # 湧き出し頂点ループ
	for(j in 1:6){ # 全周囲頂点ループ
		A[i,j] <- length(paths[[sources[i]]][[j]]) # i ---> j パス数列挙
		btwn <- which((j-sources) * (sources[i] - sources) < 0) # i---j間の湧き出し頂点の判別
		tmp.sign <- (-1)^length(btwn) # length(btwn)は i---j間湧き出し頂点数
		A[i,j] <- A[i,j] * tmp.sign
		if(sources[i] == j){
			A[i,j] <- 1 
		}
	}
}
> A
     [,1] [,2] [,3] [,4] [,5] [,6]
[1,]    1    1    1    1    0    0
[2,]   -1    0    4    7    1    0
[3,]    1    0   -2   -3    0    1
    • 1,2,3行目はそれぞれ、2,5,6湧き出し頂点に対応する
    • 1行目は、2番頂点から、1,2,3,4,5,6頂点へのパスの場合の数。2と1,2,3,4,5,6の間には、湧き出し口が挟まれていないので、すべての値が正。湧き出し口5,6へのパスはなく、自身へのパスの数は1
    • 2行目は、5番頂点から、1,2,3,4,5,6頂点のパスの場合の数。5と1の間には湧き出し口2(1個、奇数個)あるので、負。2,3,45,6と5の間には湧き出し口はないので正
    • 3行目は、6番頂点から、1,2,3,4,5,6頂点のパスの場合の数。6と1の間には湧き出し口2,5(2個、偶数個)あるので、正。2,3,4と6の間には、湧き出し口5(1個、奇数個)あるので負(ただし、0は0)
  • すべての組合せについて小行列式を計算して表示してみると正になっている
library(gtools)
cmb <- combinations(6,3)
for(i in 1:length(cmb[,1])){
	print("cmb")
	print(cmb[i,])
	print(det(A[,cmb[i,]]))
}
> for(i in 1:length(cmb[,1])){
+ print("cmb")
+ print(cmb[i,])
+ print(det(A[,cmb[i,]]))
+ }
[1] "cmb"
[1] 1 2 3
[1] 2
[1] "cmb"
[1] 1 2 4
[1] 4
[1] "cmb"
[1] 1 2 5
[1] 1
[1] "cmb"
[1] 1 2 6
[1] 1
[1] "cmb"
[1] 1 3 4
[1] 4
[1] "cmb"
[1] 1 3 5
[1] 3
[1] "cmb"
[1] 1 3 6
[1] 5
[1] "cmb"
[1] 1 4 5
[1] 4
[1] "cmb"
[1] 1 4 6
[1] 8
[1] "cmb"
[1] 1 5 6
[1] 1
[1] "cmb"
[1] 2 3 4
[1] 2
[1] "cmb"
[1] 2 3 5
[1] 2
[1] "cmb"
[1] 2 3 6
[1] 4
[1] "cmb"
[1] 2 4 5
[1] 3
[1] "cmb"
[1] 2 4 6
[1] 7
[1] "cmb"
[1] 2 5 6
[1] 1
[1] "cmb"
[1] 3 4 5
[1] 1
[1] "cmb"
[1] 3 4 6
[1] 3
[1] "cmb"
[1] 3 5 6
[1] 1
[1] "cmb"
[1] 4 5 6
[1] 1
  • サイクルがある場合は解りにくいので「絵」を描く

f:id:ryamada:20210430060911j:plainf:id:ryamada:20210430060917j:plain

  • この行列Mに、頂点ペア間のソース頂点数で符号をつけ、Plucker座標を計算すると、すべて非負
  • このPlucker座標(小行列式)は、符号を変える前のMの要素を使って、ソースから行先頂点への矢印の交叉の有無・交叉の数を考慮した式でも計算できることが示せる
D <- matrix(c(1/2,1,1/2,1/2,0,0,1/2,0,3/2,3/2,1,0,1/2,0,1/2,1/2,0,1),byrow=TRUE,ncol=6)

D2 <- D * sign(A) # 頂点ペア間のソース数で符号を変える

library(gtools)
cmb <- combinations(6,3)
for(i in 1:length(cmb[,1])){
	print("cmb")
	print(cmb[i,])
	print(det(D[,cmb[i,]]))
}
> D <- matrix(c(1/2,1,1/2,1/2,0,0,1/2,0,3/2,3/2,1,0,1/2,0,1/2,1/2,0,1),byrow=TRUE,ncol=6)
> D[1,2] <- D[2,5] <- D[3,6] <- 1
> D2 <- D * sign(A) # 頂点ペア間のソース数で符号を変える
> 
> library(gtools)
> cmb <- combinations(6,3)
> for(i in 1:length(cmb[,1])){
+ print("cmb")
+ print(cmb[i,])
+ print(det(D2[,cmb[i,]]))
+ }
[1] "cmb"
[1] 1 2 3
[1] 0.5
[1] "cmb"
[1] 1 2 4
[1] 0.5
[1] "cmb"
[1] 1 2 5
[1] 0.5
[1] "cmb"
[1] 1 2 6
[1] 0.5
[1] "cmb"
[1] 1 3 4
[1] 0
[1] "cmb"
[1] 1 3 5
[1] 0.5
[1] "cmb"
[1] 1 3 6
[1] 1
[1] "cmb"
[1] 1 4 5
[1] 0.5
[1] "cmb"
[1] 1 4 6
[1] 1
[1] "cmb"
[1] 1 5 6
[1] 0.5
[1] "cmb"
[1] 2 3 4
[1] 0
[1] "cmb"
[1] 2 3 5
[1] 0.5
[1] "cmb"
[1] 2 3 6
[1] 1.5
[1] "cmb"
[1] 2 4 5
[1] 0.5
[1] "cmb"
[1] 2 4 6
[1] 1.5
[1] "cmb"
[1] 2 5 6
[1] 1
[1] "cmb"
[1] 3 4 5
[1] 0
[1] "cmb"
[1] 3 4 6
[1] 0
[1] "cmb"
[1] 3 5 6
[1] 0.5
[1] "cmb"
[1] 4 5 6
[1] 0.5

Plabic Graph, Polypositroid and Coxeter Triangulation

https://egunawan.github.io/combinatorics/notes/notes_plabic_graphs2.pdf
arxiv.org

  • このペイパーのp18の図は、Plabic graphから組み合わせ三角化・多角形化をしつつ、それをCoxeter membrane座標にしているもの。確かに、正n-gonの頂点ベクトルの組み合わせ和によって頂点座標が指定できること、そのため、三角化・多角形化にて現れる辺の方向が有理的に限定していることを視覚的に確認するRコードは以下
  • PolyhedraのCoxeter投影はこちら

f:id:ryamada:20210426104558j:plain

n <- 8

theta <- -(1:n)/n * 2 * pi +  7/8 * pi
V <- cbind(cos(theta),sin(theta))

V123 <- apply(V[c(1,2,3),],2,sum)
V234 <- apply(V[c(2,3,4),],2,sum)
V345 <- apply(V[c(3,4,5),],2,sum)
V456 <- apply(V[c(4,5,6),],2,sum)
V567 <- apply(V[c(5,6,7),],2,sum)
V678 <- apply(V[c(6,7,8),],2,sum)
V781 <- apply(V[c(7,8,1),],2,sum)
V812 <- apply(V[c(8,1,2),],2,sum)

V127 <- apply(V[c(1,2,7),],2,sum)
V137 <- apply(V[c(1,3,7),],2,sum)
V134 <- apply(V[c(1,3,4),],2,sum)
V136 <- apply(V[c(1,3,6),],2,sum)
V135 <- apply(V[c(1,3,5),],2,sum)
V167 <- apply(V[c(1,6,7),],2,sum)
V145 <- apply(V[c(1,4,5),],2,sum)
V156 <- apply(V[c(1,5,6),],2,sum)


Vs <- rbind(V123,V234,V345,V456,V567,V678,V781,V812,V127,V137,V134,V136,V135,V167,V156,V145)

plot(Vs,asp=TRUE)

s1 <- c(1,2,3,4,5,6,7,8,1,1,1,9,2,3,3,7,6,5,5,4,4,12,13,13,11,12,15,8,10,12,7)
s2 <- c(2,3,4,5,6,7,8,1,9,10,11,10,11,11,16,14,14,14,15,15,16,15,15,16,13,13,16,9,14,14,9)
segments(Vs[s1,1],Vs[s1,2],Vs[s2,1],Vs[s2,2])

V.lab <- c("123","234","345","456","567","678","178","128","127","137","134","136","135","167","156","145")

library(igraph)

g <- graph.edgelist(cbind(s1,s2),directed=FALSE)

plot(g,layout=Vs,vertex.label=V.lab)

link.springer.com
arxiv.org
arxiv.org

ぱらぱらめくる『量子コンピュータによる機械学習』

目次

監訳者まえがき
  • 機械学習の基礎は高次元データ・線形代数・確率分布の計算であり、それを適切な精度で高速に計算するための近似を発展させてきた
  • 量子力学では確率分布関数が対象であり、1つの自由度に無限(次元)の可能性が付随する。この関数を量子ビットに限定しても、ビットを増やすとその組み合わせは指数関数的に増大する。そのことが量子計算の可能性を支えるが、地道に計算すると、逆行列計算、固有値固有ベクトル計算をすることに対応し、それは、線形代数演算で最も計算量が多いものであることから、「地道な計算」には向いていない
  • 計算すると時間がかかるはずだが、現実世界では、ミクロには量子計算が行われつつ、マクロな現象は瞬時に観測されている。この現実世界が行っていることが「量子コンピュータ計算」である
  • 量子力学の原理に基づく計算手法を、機械学習の手続きに組み込もうとする試み
  • 章立て
    • 第1章で本の概要、第2章で機械学習の概観、第3章で量子力学の最低限の知識、第4章で計算複雑性、第5章で情報の符号化、第6章で量子機械学習に入り、第7章で量子計算のデバイスを意識した話題、第8章で量子機械学習の基礎となる量子モデルを、第9章で将来展望
まえがき
  • 量子機械学習の進展には、量子技術と機械学習との2方面からの学問的興味があるとともに、IT企業活動からの注目と言う2面がある
  • 量子機械学習の可能性が学際的学問として解明される必要がある。それを理解するための基礎となる概念・アイデアアルゴリズムを取り扱う
  • 物理学・計算機科学に詳しく、線形代数と計算機アルゴリズムを理解しているならば、読み進められるようなレベルで書いた
第1章 はじめに
  • 広義の量子機械学習は「機械学習と量子情報の相乗効果を用いたアプローチ全般」
  • 本書では狭義の定義「量子コンピュータを用いた機械学習」または「量子の知見に基づいた機械学習」を採用する
  • この本が扱う問い
    • パターンをいかに認識するかについて、量子情報は新たな知見を提供するか?
    • 量子コンピュータは高速に問題を解くか?少サンプルでの学習を可能にするか?大ノイズデータを扱えるか?
    • 量子コンピューティングを定式化する言語は機械学習技術を改善するか?
    • 量子機械学習アルゴリズムの構成要素は何か?そのボトルネックは?
  • 1.1 背景
    • 量子論の法則を用いなければ述できない計算を実行するコンピュータを量子コンピュータと呼ぶ
    • 理論的に量子デバイス量子コンピュータがデザインされ、実際の作成も進んでいる
    • その理論的な量子デバイス上で実装されるアルゴリズムが量子アルゴリズム
    • 量子ビットと量子ゲートは、そのような量子デバイスに含まれる。逆に言うと、量子ビット・量子ゲート以外の量子デバイスもある
    • 量子コンピュータが行う「演算」は繊細であり、その繊細な状態が首尾一貫していて、正しいことを量子コヒーレンスと呼ぶ
    • 量子コヒーレンスを乱さないことは大事だが、乱れることを前提にした対処も求められる。その対処の一つが誤り訂正である
    • 誤り訂正は、首尾一貫性の確保であるから、大規模であるほど必要性が大きくなり、量子ビット間の相互作用が多いほど必要性が大きくなる
    • 量子デバイス・コンピュータの開発は、大規模・中規模・小規模でそれぞれ進んでいる
    • 小規模かつ、ビット間相互作用が少ない量子コンピュータは誤り訂正問題の影響が小さいので、先行している
    • したがって、現時点での、実用を意識した量子アルゴリズム開発は、小規模・低相互作用系で解くことができ、かつ、古典アルゴリズムよりも十分に高速化することができるものを標的としている
    • 機械学習は「統計学・数学・計算機科学」の交点
    • データ量の増大に伴い、機械学習は日常生活・経済活動の中ですでに役割を有している
    • 昨今の機械学習の「ブレイクスルー」のほとんどは、「計算能力の向上」「データセット規模の拡大への対応」などの量的改善にとどまる
    • ニューラルネットワーク、サポート・ベクターマシン、AdaBoost、深層学習はいずれも理論的には1990年代から知られており、難しい最適化問題を解きつつ、その処理をブラックボックス化している
    • 量子計算を機械学習に持ち込むことは質的改変となる可能性がある
    • 量子機械学習の4類型
      • (データ生成が量子系か古典系か) x (情報処理デバイスが量子系か古典系か) が作る4パターン
        • CC:データ生成が古典系で、かつ、情報処理デバイスが古典系であっても、量子情報手法を理論的に用いていれば、「量子機械学習」と言える
        • QC:量子計算を古典的機械学習で調べてみるようなスタンス
        • CQ:本書が扱う対象。古典的機械学習が取り組んできた問題に量子デバイスで取り組む話。特に教師あり学習を本書では扱う
        • QQ:量子現象、量子計算機によるシミュレーション出力を、そのまま量子計算に連結する・・・2段階学習はこれに相当する???生体の情報処理は実はこれになっている(例えば、視覚処理では、入力データ生成が光という量子現象であり、それを神経系による分子・電気現象を扱う量子デバイスであるから?
    • CQアプローチによる教師あり学習
      • 翻訳的アプローチ
        • 学習方法は古典的学習と同じ
        • タスクの下請け:非線形関数や逆行列の計算、非凸な目的関数の最適解探索のような数学的に定義づけられた問題への量子応用
      • 探索的アプローチ
  • 1.2 量子コンピュータによる識別
    • 例:アダマールゲートにより誘発される量子干渉を用いて、ある種の最近傍法を実装する
    • 1.2.1 二乗距離識別機
      • 近傍法
      • 最近傍法
        • 新標本と、既標本との近接度を算出し、最近傍の既標本のラベルを新標本も持つものとする
      • k-近傍法
        • 既標本のうち、1,2,...,k番に近い標本のラベルの多数決で新標本のラベルを決める
      • 重み付き近傍法
        • 既標本と新標本の近接度により、各既標本に重みを与え、その重み付き多数決で新標本のラベルを決める。最近傍法、k-近傍法も、重み付き近傍法の重み関数のバリエーションとなる
    • 近接度を二乗距離としたとき、「二乗距離法」となる
    • 重みを(1- \frac{1}{k} ||x_{new} - x_{sample}||^2)とすると…
my.sq.dist.classifier <- function(new.x,X,Y,k=1){
	Q <- unique(Y)
	
	w <-apply( (t(X) - new.x)^2, 2, sum)
	
	Pr <- rep(0,length(Q))
	
	for(i in 1:length(Pr)){
		tmp <- which(Y==Q[i])
		
		Pr[i] <- sum((1 - 1/k * w[tmp]))
	}
	Pr <- Pr/sum(Pr)
	
	return(list(Pr=Pr,Class=Q))
}
n <- 5 # No. samples
p <- 2 # No. features
X <- matrix(rnorm(p*n),ncol=p)

# No. classes
q <- 3

Y <- sample(1:q,n,replace=TRUE)

new.x <- rnorm(p)

my.sq.dist.classifier(new.x,X,Y)
> my.sq.dist.classifier(new.x,X,Y)
$Pr
[1] 0.80814006 0.02022597 0.17163397

$Class
[1] 1 3 2

1.2.2 アダマール変換による干渉

    • アダマール変換は、確定した状態を均等確率にする変換
    • 古典系でのコイン投げになぞらえて話を進めている
    • コインを2回投げたときの状態(確率質量分布)と、アダマール変換を2回続けて行ったときの状態とが違うことを述べている
    • 状態変換を行列で表すと、古典系の場合には、非負の値のみが現れるのに対して、量子系では負の値も現れ、その結果、2回のアダマール変換で元に戻ったり、1つのビットへの作用で全通りの確率振幅に影響が出るなどの、「干渉」が現れる
from sympy.physics.quantum import *
         # ↑基本機能のインポート
from sympy.physics.quantum.qubit import Qubit,QubitBra, measure_all, measure_partial
         # ↑ブラケットを使えるようにします
from sympy.physics.quantum.gate import X,Y,Z,H,T,S,CNOT,SWAP,HadamardGate
         # ↑基本的な量子ゲートを使えるようにします
from sympy.physics.quantum.gate import IdentityGate as I
         # ↑恒等変換は省略されないため I と省略できるようにします
from sympy.physics.quantum.dagger import Dagger
from sympy import sqrt
from sympy.physics.quantum.qapply import qapply
# 表・表状態
q1 = Qubit('00')
q1
# 最も右のビットにだけアダマール変換
q2 = H(0) * q1
q2
# この状態q2を測定してみる
q2a = qapply(q2)
measure_all(q2a)
# 状態をq2に変え、そこで観測をせずに、もう一度、片方にだけアダマール変換
q2 = H(0) * q1
q3 = H(0) * q2
# q3を測定してみる
q3a = qapply(q3)
measure_all(q3a)
# ビットの数を増やす
n = 5
q1 = Qubit('0'* n)
q1
# ごちゃごちゃさせておく
q2 = H(0) * H(1) * H(2) * q1
q2
# この状態q2を測定してみる
q2a = qapply(q2)
measure_all(q2a)
  • 1.2.3 量子二乗距離識別器
    • ステップA:データを単位球面上の点に座標変換する
    • ステップB:データ符号化。教師情報と新規標本情報から量子ビット状態(ベクトル)を作る
    • ステップC:教師情報と新規標本情報とを区分けしている量子ビットについてアダマール変換する。これにより、教師情報に対応する組み合わせに新規標本情報が「加え」られる
    • ステップD:教師情報と新規標本情報とを区分けしている量子ビットを観察し、特定の場合にのみ、下流処理を行うことにする。これにより、新規標本に対応する組み合わせの振幅はゼロのベクトルに変わる
    • ステップE:教師情報・新規標本情報の両方に関して、「分類ラベル」に相当する量子ビットを観察する。この観察で0/1のいずれかがどのくらいの割合で観察されるかの推定となる
    • データ符号化の後のステップは、C,D,Eの3ステップのみ。これを入力後の処理と見做せば、入力がどんなに多くても、3段階処理で済み、入力データのサイズによらない~定数時間アルゴリズムである、と言う
    • これを、二乗距離識別器で、古典的に実行すると以下のようになる
> X <- matrix(c(0.921,0.390,0.141,0.990),byrow=TRUE,ncol=2)
> new.x <- c(0.866,0.500)
> 
> Y <- c(1,0)
> 
> my.sq.dist.classifier(new.x,X,Y,k=4)
$Pr
[1] 0.5519867 0.4480133

$Class
[1] 1 0
    • 対応するSympyの処理は、データ符号化のやり方がわからないが・・・
      • ステップB
# これではだめ!
q1 = (Qubit('0001') * 0.921 + Qubit('0011') * 0.390 + Qubit('0100') * 0.141 + Qubit('0110') * 0.990 + Qubit('1001') * 0.866 + Qubit('1011') * 0.500 + Qubit('1100') * 0.866 + Qubit('1110') * 0.500) * 1/sqrt(4)
q1
      • ステップC
q2 = H(3) * q1
q2
  • 1.3 本書の構成
第2章 機械学習
  • 2.1 推定
    • データをモデルに入力として与え、モデルが導き出す結果を出力・推定結果と呼ぶことにする
    • 教師アリ学習(識別・回帰、予測)
    • 教師ナシ学習(仮説推測)
    • 強化学習(ゲーム)
  • 2.2 モデル
    • 決定論的モデルと確率論的モデル
    • 確率モデル、生成モデル分布(生起確率)と識別モデル分布(尤度)
    • 最大事後確率推定(~最尤推定)と、期待値推定
    • 教師アリ推定プロセス
      • データ、モデル族、モデル選択(パラメタ推定)、予測
    • コスト関数・誤差・精度・偽陽性/偽陰性
    • 過剰適合・汎化(データ依存性)、正則化、枝刈り・変数選択、Shrinkage
    • 訓練データ・テストデータ
    • ベイズ学習
    • カーネルと特徴写像
      • 類似性の尺度としてのカーネル関数
      • カーネル関数を選ぶことで、コスト関数の最適化のやり方が規定される
      • 言い換えると、カーネル関数のとっかえひっかえで機械学習モデルを取り換えることができる
      • カーネル関数は、入力データを変換(特徴空間への写像)した上で、内積を取ることに相当する
      • その特徴空間は次元を増やすことができるし、ガウシアンカーネルは無限次元特徴空間への写像になっている(指数関数が無限級数分解できるから)
  • 2.3 訓練
  • 2.4 機械学習の手法
    • 表2.3をよく見よう
    • fはモデル関数、pは分布(関数)
    • (w,x)は変数とその係数。それらの関係性
    • 線形なことは、線形計算(w^Tx)で表されている。非線形は、その計算が「非線形関数」になっている
    • w(ベクトル)ではなくW(行列)ならば、次元が増減できる
    • 層をなしているネットワークは行列の適用の繰り返し
    • グラフィカルモデルになると、Wの繰り返しのような構造がなくなり、グラフの構成要素がパラメタを持ち、その総体としての計算になる
    • 隠れマルコフモデルはv(t),v(t-1)の関係を持ち込んでいることが式からわかる
    • カーネル法は、標本ペアに関して計算する関数を使う方法。変数や隠れ変数を使った関数表現ではなく、標本由来の演算。スカラー値を返すカーネル関数、その束、さらにグラム行列を用いて記述されている
    • 線形回帰:行列演算
    • 非線形回帰
    • グラフィカルモデル:ベイジアンネットワーク、隠れマルコフモデル
    • カーネル法カーネル密度推定、k-近傍法、サポートベクターマシン、ガウシアン過程(モデル関数を確率的に選び出す)・・・標本駆動的・・・ノンパラ的・・・
第3章 量子情報入門

quantumalgorithmzoo.org

    • 量子ビットを使う計算モデルとそうでないモデルとがある(が、量子ビットを使うモデルを基本として、以降の話は進む)
    • 量子コンピュータは、状態の時間変化を正確に制御するn量子ビットの物理的な実装」である
    • 量子コンピュータを使うということは、レーザーの強度や地場などの特定の実験構成で、物理的な観測量の分布を読み取るということ」
    • 「量子系の時間発展が、1つまたは2つの量子ビットだけに作用する、量子ゲートと呼ばれるほんの一握りの基本的な「操作」の組み合わせで近似できる」
    • 量子ビットは2つの基底状態。その重ね合わせで長さ2のベクトル(ケットベクトル)で表せる
    • 2つの基底状態を長さ2の複素ベクトルでも表す
    • エンタングルメントないとき(純粋状態)は、複数の量子ビットの集合状態はテンソル積で書ける。エンタングルメントしているとき(混合状態)は、テンソル積で書けない値を取るので、2^n通りの状態に確率振幅を与えて「足し合わせ」た状態となる
      • 純粋状態は[tex:\rho_{純粋} = |\psi> < \psi | = \sum_{i,j=1}^N \alpha_i^* \alpha_j | i>
      • 混合状態は\rho_{混合} = \sum_{i,j=1}^N \alpha_{i,j} | i> < j|, \alpha_{i,j} \in \mathcal{C}
      • ちなみに純粋状態を指定する係数の数は2N、混合状態のそれはN^2。この複雑さ~自由度の高さが混合状態の複雑さ
    • 観測は2^nの場合に分散している確率振幅を、一つに(もしくは部分観測の場合はそれに応じた、少な目の場合に分散して残りの場合の確率振幅がゼロの状態に)変換すること
    • 量子ゲートはユニタリ変換をすること
    • 円タングル回路の例がある。これをSympyで書けるか?
    • 関数f(x)の作用の実装
      • 「x -> f(x)(とする回路構成は)、一般的にユニタリではないため」別の回路実装「x \to f(x) , y \to y \oplus f(x)とされる…(?)
      • その実装により、重ね合わせ状態が作られる。重ね合わせ状態を作るということは、2つの状態(f(0)とf(1))とを同時に保持できることを意味し、それが量子コンピューティングのメリットの源泉
  • 3.3 Deutsch-Joszaのアルゴリズム
    • 量子計算が、古典計算より、少ステップで、あることの確認が取れるという例を示している
    • ディラック表記が追えるか??
    • 量子ビット・量子ゲートモデル以外のモデル
      • 量子アニーリング
      • 物理実験的。状態変化を量子力学的に起こすにあたり、「乗り越える壁」の「高さ」と「厚さ」があるが、量子的には高さは問題にならず薄ければ状態推移ができるようなことがある。それを応用。「急激に変化して複雑な構造を持つ目的関数」を持つ問題に適しているという。量子ビットを使う
      • 一方向量子計算。測定型の量子計算。非常にもつれた状態(クラスター状態)を作り、測定結果依存性に次の動作を定め、量子ビットの測定を繰り返していくモデル。量子ビットを使う
      • 連続変数量子計算。連続基底を持つ量子状態で情報を符号化する。量子機械学習で有用と目されている
  • 3.4 情報の符号化の方法
    • データマイニング機械学習では情報の符号化の問題が中心になるのに対して、量子計算の領域では話題にならない
    • 情報の符号化符号化されるものによっていくつかに分けられる
    • 「計算基底符号化 basis encoding」
      • 実数を二進法表現し、その01列を量子ビットにに対応させる
      • 複数の実数があれば、それをタンデムにつなぐ
    • 「振幅符号化 amplitude encoding」
      • 量子状態は確率振幅を持つので、振幅情報を量子状態として保持するというアイディアがある。その方法はベクトルでその情報を持つ場合と行列で持つ場合とがある。ただし、いったん量子状態として振幅情報を持つと、振幅情報の変化には、量子状態の変化として実現するしか手がなくなる。言い換えるとユニタリ変換を強制される~線形変換を強制される
      • 自由度を確保するために、振幅情報の持ち方に冗長化が必要だったりもする
    • 「量子サンプル状態符号化 qsample encoding」
      • 量子状態から観測をし、それを繰り返すことで、古典的な確率分布情報が得られる。その変換のこと
    • ハミルトニアン符号化 dynamic encoding」
      • 行列状の情報は、そのような値を持つハミルトニアンとして持つことができる
      • ユニタリ行列として持つか、エルミート行列として持つかすれば、量子計算の登場人物とすることができる
  • 3.5 需要な量子ルーチン
    • グローバー探索
      • やみくもに登録しただけのデータベースに問い合わせをして、登録されている名前が入っている番地を見つけるタスク
      • 量子アルゴリズムでは、該当番地に対応する確率振幅が実行するにしたがって高くなることを利用して、地道な古典探索アルゴリズムより少ステップを可能にする
    • 量子位相推定
    • 行列の乗算と逆行列
第4章 量子優位性
  • 4.1 学習の計算複雑性
  • 4.2 サンプル複雑性
  • 4.3 モデルの複雑性
第5章 情報の符号化
  • 5.1 計算基底符号化
  • 5.2 振幅符号化
  • 5.3 量子サンプル状態符号化
  • 5.4 ハミルトニアン符号化
第6章 推論のための量子計算
第7章 量子計算による学習
  • 7.1 量子BLAS
  • 7.2 探索と振幅増幅
  • 7.3 さまざまなハイブリッドアルゴリズム
  • 7.4 量子断熱学習
第8章 量子モデルを利用した学習
第9章 これからの量子機械学習

平面グラフを全域木と完全マッチングに対応させる

  • 平面グラフでは|V| - |E| + |F| =2が成り立つ
  • この式を変形して(|V|-1) + |F|-1) = |E|が得られる
  • 頂点を1つ取り除き、面も1つ取り除くと、辺の数は、残った頂点の数と残った面の数の和に等しい、と読める
  • 「等しい」ということを、「辺に対して、頂点もしくは面を一つ対応させると、完全マッチングさせることができる」と読み替える
  • この読み替えが、具体的には、平面グラフから、その頂点・辺・面のすべてを頂点とした平面グラフを構成し、そこから元の頂点と元の面とに対応する頂点を取り除いた後の平面グラフでは、完全マッチングが取れる、ということに対応付けられる
  • ただし、取り除く元の頂点は、取り除く元の面を構成する頂点であることが必要
  • この構成法において、「取り除く予定の頂点」を根とした有向全域木と、元の平面グラフの双対グラフにおいて「取り除く予定の面」に対応する頂点を根とする有向全域木とが、フォークの相互かみ合わせのようになっていると見立てられることから、全域木とも関係する
  • それについて記した文書がこちら:"Trees and matchings"

http://emis.impa.br/EMIS/journals/EJC/Volume_7/PDF/v7i1r25.pdf

www.math.lsa.umich.edu

2枚の正三角形

  • 辺の長さが1の正三角形2枚を貼り合わせる
  • 1枚目の正三角形の頂点を(\frac{\sqrt{3}}{2},0,0),(0,0.5,0),(0,-0.5,0)に取り
  • 2枚目の正三角形の頂点を(\frac{\sqrt{2}}{2}\cos{\psi},0,\frac{\sqrt{3}}{2}\sin{\psi}),(0,0.5,0),(0,-0.5,0)に取る
  • このとき、1枚目の三角形の2点(\frac{\sqrt{3}}{2},0,0),(0,-0.5,0)の中点(\frac{\sqrt{3}}{4},-0.25,0)(0,0.5,0),(0,-0.5,0)の中点(0,0,0)を結ぶ線分と
  • 2枚目の三角形の2点(\frac{\sqrt{2}}{2}\cos{\psi},0,\frac{\sqrt{3}}{2}\sin{\psi}),(0,0.5,0)の中点\frac{\sqrt{3}}{4}\cos{\psi},0.25,\frac{\sqrt{3}}{4}\sin{\psi}(0,0,0)を結ぶ線分とが
  • なす角\thetaとの関係が知りたいとする
  • 今、特に、\theta=\frac{k-1}{k}\piであるような場合(これは、正2k角形の内角)を計算してみる
theta <- (1:10)/(2:11) * pi
ct <- cos(theta)
plot(ct)
cp <- 4/3 * (ct + 1/4)
p <- acos(cp)
plot(theta,p)
p/theta