般若心経はさすがに、、、という声もありましたので普通のシンボルで記事を再開します。。。
今回は量子計算の計算量を推定する方法を紹介します。
import opt_einsum as oe
import numpy as np
hanya = [oe.get_symbol(i) for i in range(118)]
kanji = []
for item in hanya:
if not item in kanji:
kanji += item
l2 = [[0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 6], [6, 7], [7, 8], [8, 9], [9, 10], [10, 11], [11, 12], [12, 13], [13, 14], [14, 15], [15, 0], [5, 8], [7, 12], [0, 3], [2, 14], [7, 9], [7, 11], [0, 14], [6, 13], [13, 15], [8, 12], [7, 10], [10, 13], [6, 8], [2, 7], [7, 14], [1, 14], [11, 15], [1, 9], [9, 13]]
#量子ビット数
N = 16
#初期量子状態
psi = [1,0]
arr_tensor = []
arr_arm = []
#kanji
n_kanji = 0
for i in range(N):
arr_arm.append(hanya[i])
arr_tensor.append(psi)
arr_state = []
for i in range(N):
arr_state.append(arr_arm[i])
n_kanji += 1
H = np.array([[1,1],[1,-1]])/np.sqrt(2)
for i in range(N):
arr_tensor.append(H)
arr_arm.append(arr_state[i] + kanji[n_kanji])
arr_state[i] = kanji[n_kanji]
n_kanji += 1
theta = np.random.rand()*np.pi*2
ZZ = np.array([[np.exp(-1*1j*theta/2),0,0,0],[0,np.exp(-1*1j*theta/2),0,0],[0,0,np.exp(1j*theta/2),0],[0,0,0,np.exp(-1*1j*theta/2)]]).reshape(2,2,2,2)
for item in l2:
in1 = item[0]
in2 = item[1]
arr_tensor.append(ZZ)
arr_arm.append(arr_state[in1] + arr_state[in2] + kanji[n_kanji] + kanji[n_kanji+1])
arr_state[in1] = kanji[n_kanji]
arr_state[in2] = kanji[n_kanji+1]
n_kanji += 2
theta2 = np.random.rand()*np.pi*2
RX = np.array([[np.cos(theta2/2),-1j*np.sin(theta2/2)],[-1j*np.sin(theta2/2),np.cos(theta2/2)]])
for i in range(N):
arr_tensor.append(RX)
arr_arm.append(arr_state[i] + kanji[n_kanji])
arr_state[i] = kanji[n_kanji]
n_kanji += 1
path_info = oe.contract_path(','.join(arr_arm), *arr_tensor)
print(path_info[1])
Complete contraction: a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,aq,br,cs,dt,eu,fv,gw,hx,iy,jz,kA,lB,mC,nD,oE,pF,qrGH,HsIJ,JtKL,LuMN,NvOP,PwQR,RxST,TyUV,VzWX,XAYZ,ZBÀÁ,ÁCÂÃ,ÃDÄÅ,ÅEÆÇ,ÇFÈÉ,ÉGÊË,QWÌÍ,UÄÎÏ,ËMÐÑ,KÈÒÓ,ÎYÔÕ,ÔÂÖ×,ÐÓØÙ,SÆÚÛ,ÛÊÜÝ,ÍÏÞß,ÖÀàá,áÜâã,ÚÞäå,Òàæç,çÙèé,Iéêë,×Ýìí,êÕîï,ïãðñ,Øò,îó,æô,Ñõ,Oö,Ì÷,äø,èù,åú,ðû,âü,ìý,ßþ,ñÿ,ëĀ,íā->òóôõö÷øùúûüýþÿĀā
Naive scaling: 118
Optimized scaling: 21
Naive FLOP count: 2.758e+37
Optimized FLOP count: 9.311e+6
Theoretical speedup: 2.962e+30
Largest intermediate: 6.554e+4 elements
--------------------------------------------------------------------------------
scaling BLAS current remaining
--------------------------------------------------------------------------------
2 GEMM aq,a->q ...
4 GEMM q,qrGH->rGH ...
2 GEMM br,b->r ...
3 GEMM r,rGH->GH ...
2 GEMM cs,c->s ...
4 GEMV/EINSUM s,HsIJ->HIJ ...
2 GEMM dt,d->t ...
4 GEMV/EINSUM t,JtKL->JKL ...
2 GEMM eu,e->u ...
4 GEMV/EINSUM u,LuMN->LMN ...
2 GEMM fv,f->v ...
4 GEMV/EINSUM v,NvOP->NOP ...
2 GEMM gw,g->w ...
4 GEMV/EINSUM w,PwQR->PQR ...
2 GEMM hx,h->x ...
4 GEMV/EINSUM x,RxST->RST ...
2 GEMM iy,i->y ...
4 GEMV/EINSUM y,TyUV->TUV ...
2 GEMM jz,j->z ...
4 GEMV/EINSUM z,VzWX->VWX ...
2 GEMM kA,k->A ...
4 GEMV/EINSUM A,XAYZ->XYZ ...
2 GEMM lB,l->B ...
4 GEMV/EINSUM B,ZBÀÁ->ZÀÁ ...
2 GEMM mC,m->C ...
4 GEMV/EINSUM C,ÁCÂÃ->ÁÂÃ ...
2 GEMM nD,n->D ...
4 GEMV/EINSUM D,ÃDÄÅ->ÃÄÅ ...
2 GEMM oE,o->E ...
4 GEMV/EINSUM E,ÅEÆÇ->ÅÆÇ ...
2 GEMM pF,p->F ...
4 GEMV/EINSUM F,ÇFÈÉ->ÇÈÉ ...
5 TDOT Øò,ÐÓØÙ->òÐÓÙ ...
5 TDOT îó,êÕîï->óêÕï ...
5 TDOT æô,Òàæç->ôÒàç ...
5 GEMM Ñõ,ËMÐÑ->õËMÐ ...
5 TDOT Ì÷,QWÌÍ->÷QWÍ ...
5 TDOT äø,ÚÞäå->øÚÞå ...
5 TDOT èù,çÙèé->ùçÙé ...
5 TDOT ðû,ïãðñ->ûïãñ ...
5 TDOT âü,áÜâã->üáÜã ...
5 TDOT ìý,×Ýìí->ý×Ýí ...
5 GEMM ßþ,ÍÏÞß->þÍÏÞ ...
5 GEMM ëĀ,Iéêë->ĀIéê ...
4 GEMM HIJ,GH->IJG ...
4 TDOT NOP,Oö->NPö ...
5 GEMM øÚÞå,åú->øÚÞú ...
5 GEMM ûïãñ,ñÿ->ûïãÿ ...
5 GEMM ý×Ýí,íā->ý×Ýā ...
5 GEMM LMN,JKL->MNJK ...
5 GEMM RST,PQR->STPQ ...
5 GEMM VWX,TUV->WXTU ...
5 GEMM ZÀÁ,XYZ->ÀÁXY ...
5 GEMM ÃÄÅ,ÁÂÃ->ÄÅÁÂ ...
5 GEMM ÇÈÉ,ÅÆÇ->ÈÉÅÆ ...
6 TDOT MNJK,IJG->MNKIG ...
7 TDOT MNKIG,NPö->MKIGPö ...
7 TDOT ÎYÔÕ,UÄÎÏ->YÔÕUÄÏ ...
7 TDOT ÛÊÜÝ,ÉGÊË->ÛÜÝÉGË ...
7 TDOT ÖÀàá,ÔÂÖ×->ÀàáÔÂ× ...
7 TDOT ôÒàç,KÈÒÓ->ôàçKÈÓ ...
7 TDOT øÚÞú,SÆÚÛ->øÞúSÆÛ ...
7 TDOT ûïãÿ,óêÕï->ûãÿóêÕ òÐÓÙ,õËMÐ,÷QWÍ,ùçÙé,üáÜã,þÍÏÞ,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ôàçKÈÓ,øÞúSÆÛ,ûãÿóêÕ->òóôõö÷øùúûüýþÿĀā
9 TDOT ôàçKÈÓ,òÐÓÙ->ôàçKÈòÐÙ õËMÐ,÷QWÍ,ùçÙé,üáÜã,þÍÏÞ,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,øÞúSÆÛ,ûãÿóêÕ,ôàçKÈòÐÙ->òóôõö÷øùúûüýþÿĀā
10 TDOT ôàçKÈòÐÙ,ùçÙé->ôàKÈòÐùé õËMÐ,÷QWÍ,üáÜã,þÍÏÞ,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,øÞúSÆÛ,ûãÿóêÕ,ôàKÈòÐùé->òóôõö÷øùúûüýþÿĀā
9 TDOT øÞúSÆÛ,þÍÏÞ->øúSÆÛþÍÏ õËMÐ,÷QWÍ,üáÜã,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ûãÿóêÕ,ôàKÈòÐùé,øúSÆÛþÍÏ->òóôõö÷øùúûüýþÿĀā
9 TDOT ûãÿóêÕ,üáÜã->ûÿóêÕüáÜ õËMÐ,÷QWÍ,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ôàKÈòÐùé,øúSÆÛþÍÏ,ûÿóêÕüáÜ->òóôõö÷øùúûüýþÿĀā
11 TDOT ôàKÈòÐùé,õËMÐ->ôàKÈòùéõËM ÷QWÍ,ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,øúSÆÛþÍÏ,ûÿóêÕüáÜ,ôàKÈòùéõËM->òóôõö÷øùúûüýþÿĀā
11 TDOT øúSÆÛþÍÏ,÷QWÍ->øúSÆÛþÏ÷QW ĀIéê,ý×Ýā,STPQ,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóêÕüáÜ,ôàKÈòùéõËM,øúSÆÛþÏ÷QW->òóôõö÷øùúûüýþÿĀā
12 TDOT øúSÆÛþÏ÷QW,STPQ->øúÆÛþÏ÷WTP ĀIéê,ý×Ýā,WXTU,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóêÕüáÜ,ôàKÈòùéõËM,øúÆÛþÏ÷WTP->òóôõö÷øùúûüýþÿĀā
12 TDOT øúÆÛþÏ÷WTP,WXTU->øúÆÛþÏ÷PXU ĀIéê,ý×Ýā,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóêÕüáÜ,ôàKÈòùéõËM,øúÆÛþÏ÷PXU->òóôõö÷øùúûüýþÿĀā
11 TDOT ûÿóêÕüáÜ,ĀIéê->ûÿóÕüáÜĀIé ý×Ýā,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,MKIGPö,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,ôàKÈòùéõËM,øúÆÛþÏ÷PXU,ûÿóÕüáÜĀIé->òóôõö÷øùúûüýþÿĀā
14 TDOT ôàKÈòùéõËM,MKIGPö->ôàÈòùéõËIGPö ý×Ýā,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,YÔÕUÄÏ,ÛÜÝÉGË,ÀàáÔÂ×,øúÆÛþÏ÷PXU,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö->òóôõö÷øùúûüýþÿĀā
14 TDOT øúÆÛþÏ÷PXU,YÔÕUÄÏ->øúÆÛþ÷PXYÔÕÄ ý×Ýā,ÀÁXY,ÄÅÁÂ,ÈÉÅÆ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö,øúÆÛþ÷PXYÔÕÄ->òóôõö÷øùúûüýþÿĀā
14 TDOT øúÆÛþ÷PXYÔÕÄ,ÀÁXY->øúÆÛþ÷PÔÕÄÀÁ ý×Ýā,ÄÅÁÂ,ÈÉÅÆ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö,øúÆÛþ÷PÔÕÄÀÁ->òóôõö÷øùúûüýþÿĀā
14 TDOT øúÆÛþ÷PÔÕÄÀÁ,ÄÅÁÂ->øúÆÛþ÷PÔÕÀÅ ý×Ýā,ÈÉÅÆ,ÛÜÝÉGË,ÀàáÔÂ×,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö,øúÆÛþ÷PÔÕÀÅÂ->òóôõö÷øùúûüýþÿĀā
15 TDOT øúÆÛþ÷PÔÕÀÅÂ,ÀàáÔÂ×->øúÆÛþ÷PÕÅàá× ý×Ýā,ÈÉÅÆ,ÛÜÝÉGË,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö,øúÆÛþ÷PÕÅàá×->òóôõö÷øùúûüýþÿĀā
14 TDOT øúÆÛþ÷PÕÅàá×,ÈÉÅÆ->øúÛþ÷PÕàá×ÈÉ ý×Ýā,ÛÜÝÉGË,ûÿóÕüáÜĀIé,ôàÈòùéõËIGPö,øúÛþ÷PÕàá×ÈÉ->òóôõö÷øùúûüýþÿĀā
16 TDOT ôàÈòùéõËIGPö,ÛÜÝÉGË->ôàÈòùéõIPöÛÜÝÉ ý×Ýā,ûÿóÕüáÜĀIé,øúÛþ÷PÕàá×ÈÉ,ôàÈòùéõIPöÛÜÝÉ->òóôõö÷øùúûüýþÿĀā
21 TDOT ôàÈòùéõIPöÛÜÝÉ,øúÛþ÷PÕàá×ÈÉ->ôòùéõIöÜÝøúþ÷Õá× ý×Ýā,ûÿóÕüáÜĀIé,ôòùéõIöÜÝøúþ÷Õá×->òóôõö÷øùúûüýþÿĀā
21 TDOT ôòùéõIöÜÝøúþ÷Õá×,ûÿóÕüáÜĀIé->ôòùõöÝøúþ÷×ûÿóüĀ ý×Ýā,ôòùõöÝøúþ÷×ûÿóüĀ->òóôõö÷øùúûüýþÿĀā
18 TDOT ôòùõöÝøúþ÷×ûÿóüĀ,ý×Ýā->òóôõö÷øùúûüýþÿĀā òóôõö÷øùúûüýþÿĀā->òóôõö÷øùúûüýþÿĀā
118文字ありますが、再度まで最大scalingは21で済みました。