(57)【特許請求の範囲】
【請求項１】
プログラムがコンピュータに読み込まれることでそれぞれ構成される記憶部と処理設定部と行列分解部と行列リスト更新部と制御部とを有するユニタリ行列分解装置で実行され、量子コンピュータ上の演算を表すサイズがdn×dn(d≧3，n≧2)の特殊ユニタリ行列SU(dn)を、量子コンピュータのための量子回路に対応する疎行列の積に分解するユニタリ行列分解方法であって、
入力された特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として上記記憶部に格納する行列格納過程と、
上記処理設定部が、上記記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列を読み出し、それを行列Gとする処理設定過程と、
上記行列分解部が、m/2以下の最大の整数又はm/2以上の最小の整数をｔとし、dt/2以上の最小の整数をc1とし、dt/2以下の最大の整数をc2とし、pをp=c1・dm-tとし、qをq=c2・dm-tとし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とした場合における、上記処理設定過程で読み出された上記行列Gから、G=K1・A1・K2を満たす行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1とを計算する行列分解過程と、
上記行列リスト更新部が、上記行列分解過程で計算された上記行列K1の部分行列K11∈SU(p),K12∈SU(q)と、上記行列分解過程で計算された上記行列K2の部分行列K21∈SU(p),K22∈SU(q)と、上記行列分解過程で計算された上記ブロック対角行列A1のdr×drの対角ブロックのユニタリ行列である部分行列とを、上記行列リストの要素として上記記憶部に格納し、これらの部分行列に対応する上記処理設定過程で読み出された上記行列Gを上記記憶部に格納された上記行列リストの要素から排除する行列リスト更新過程と、
上記制御部が、上記処理設定過程と上記行列分離過程と上記行列リスト更新過程とを、上記記憶部に格納された行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り繰り返し実行させる制御過程と、
を有し、
上記行列分解過程は、
上記行列分解部の第１行列積演算部が、上記処理設定過程で読み出された上記行列Gとその複素共役転置行列G*とを用い、σを1と-1とが対角成分に交互に並ぶdt×dtの対角行列σ=diag(1,-1,1,-1,...)とし、S=dm-tとし、IをS×Sの単位行列として、単位行列Iと対角行列σとのテンソル積を計算することにより行列ρを計算し、行列X=ρ・G*・ρ・Gを生成する第１行列積演算過程と、
上記行列分解部の対角化行列生成部が、上記第１行列積演算過程で生成された上記行列Xを用い、上記行列Xをブロック対角化する行列Pを生成する対角化行列生成過程と、
上記行列分解部の第２行列積演算部が、上記第１行列積演算過程で生成された上記行列Xと上記対角化行列生成過程で生成された上記行列Pとその複素共役転置行列P*とを用い、B=P*・X・Pの演算によってブロック対角行列Bを生成する第２行列積演算過程と、
上記行列分解部のブロック対角行列変換部が、上記第２行列積演算過程で生成された上記ブロック対角行列Bの対角要素が１でない場合に、当該要素を[1,1]成分とする上記ブロック対角行列Bの４×４部分行列
【数２１】
0004758965.tif 000022
に置き換えることによりブロック対角行列Yを計算するブロック対角行列変換過程と、
上記行列分解部の第３行列積演算部が、上記ブロック対角行列変換過程で計算されたブロック対角行列Yと上記対角化行列生成過程で生成された上記行列Pと上記複素共役転置行列P*とを用い、M＝P・Y・P*の演算を行って行列Mを生成する第３行列積演算過程と、
上記行列分解部の第４行列積演算部が、上記処理設定過程で読み出された上記行列Gとその複素共役転置行列M*とを用い、K=G・M*の演算を行って行列Kを生成する第４行列積演算過程と、
上記行列分解部の第５行列積演算部が、上記第４行列積演算過程で生成された上記行列Kと上記対角化行列生成過程で生成された上記行列Pとを用い、K1=K・Pの演算を行って上記行列K1を生成する第５行列積演算過程と、
上記行列分解部の行列分割部が、上記対角化行列生成過程で生成された上記行列Ｐの複素共役転置行列Ｐ＊を行列K2とし、上記行列ＹをＡ１として、上記行列Ｋ１と上記行列Ｋ２と上記行列A1とを出力する行列分割過程と、を有し、
上記対角化行列生成過程は、
上記対角化行列生成部の固有値・固有ベクトル算出部が、上記第１行列積演算過程で生成された上記行列Ｘの固有値と固有ベクトルとを算出する固有値・固有ベクトル算出過程と、
上記対角化行列生成部の第１リスト要素生成部が、上記固有値・固有ベクトル算出過程で算出された上記固有値と固有ベクトルのうち、対応する固有値が虚数である固有ベクトルuk（kは自然数）に対し、ベクトルuk+ρ・uk及びuk-ρ・ukを生成し、当該ベクトルuk+ρ・ukを奇数要素に、uk−ρ・ukを偶数要素に格納したリストV1を生成する第１リスト要素生成過程と、
上記対角化行列生成部の第２リスト要素生成部が、上記固有値・固有ベクトル算出過程で算出された上記固有値と固有ベクトルのうち、対応する固有値が実数である固有ベクトルukのうち、uk+ρ・uk=ukを満たす固有ベクトルukをリストW1の要素として格納し、uk-ρ・uk=-ukを満たす固有ベクトルukに対するベクトル-ukをリストW2の要素として格納し、対応する固有値が実数である固有ベクトルukについて (uk+ρ・uk)/‖uk+ρ・uk‖（‖α‖はαのノルムを示す）をリストW1及びW2の要素として格納したリストを生成する第２リスト要素生成過程と、
dが奇数である場合には、上記対角化行列生成部の行列配列部が、上記第１リスト要素生成過程で生成された上記リストV1又は上記第２リスト要素生成過程で生成された上記リストW2に属するdt-1個の要素と上記第２リスト要素生成過程で生成された上記リストW1の1個の要素とからなるdt列のベクトル列を、上記リストV1、リストW1及びリストW2の各要素をそれぞれ重複させることなく用いて上記リストV1及びリストW2のすべての要素を使い切るまで生成し、生成された各dt列のベクトル列とリストW2の残りの要素とを列方向に並べた行列を上記行列Pとして生成し、生成された上記行列Pを出力し、dが偶数である場合には、上記対角化行列生成部の行列配列部が、上記第１リスト要素生成過程で生成された上記リストV1、上記第２リスト要素生成過程で生成された上記リストW1及びリストW2の各要素をそれぞれ重複させることなく列方向に並べた行列を上記対角化行列生成過程で生成される上記行列Pとして生成する行列配列過程と、を有し、
上記行列リスト更新過程は、
上記行列リスト更新部の第１ベクトル生成部が、上記第１行列積演算過程で計算された行列上記ρの対角成分からなるベクトルの-1の要素を0に置換したベクトルτ1を生成する第１ベクトル生成過程と、
上記行列リスト更新部の第２ベクトル生成部が、上記第１行列積演算過程で計算された上記行列ρの対角成分からなるベクトルの1の要素を0に置換したベクトルτ2を生成する第２ベクトル生成過程と、
上記行列リスト更新部の第１抽出行列生成部が、上記第１ベクトル生成過程で生成された上記ベクトルτ１を用いて、行列T1=τ1・τ1T（αTは転置ベクトル）を生成する第１抽出行列生成過程と、
上記行列リスト更新部の第２抽出行列生成部が、上記第２ベクトル生成過程で生成されたベクトルτ２を用いて、行列T2=τ2・τ2Tを生成する第２抽出行列生成過程と、
上記行列リスト更新部の第１部分行列抽出部が、上記行列分割過程で出力された上記行列K1から、上記第１抽出行列生成過程で生成された上記行列T1の行列成分が１である行−列の要素のみを取り出した上記部分行列K11を生成する第１部分行列抽出過程と、
上記行列リスト更新部の第２部分行列抽出部が、上記行列分割過程で出力された上記行列K1から、上記第２抽出行列生成過程で生成された上記行列T2の行列成分が１である行−列の要素のみを取り出した上記部分行列K12を生成する第２部分行列抽出過程と、
上記行列リスト更新部の第３部分行列抽出部が、上記行列分割過程で出力された上記行列K2から、上記第１抽出行列生成過程で生成された上記行列T1の行列成分が１である行−列の要素のみを取り出した上記部分行列K21を生成する第３部分行列抽出過程と、
上記行列リスト更新部の第４部分行列抽出部が、上記行列分割過程で出力された上記行列K2から、上記第２抽出行列生成過程で生成された上記行列T2の行列成分が１である行−列の要素のみを取り出した上記部分行列K22を生成する第４部分行列抽出過程と、を有する、
ことを特徴とするユニタリ行列分解方法。
【請求項２】
プログラムがコンピュータに読み込まれることでそれぞれ構成される記憶部と処理設定部と行列分解部と行列リスト更新部と制御部とを有するユニタリ行列分解装置で実行され、量子コンピュータ上の演算を表すサイズがdn×dn(d≧3，n≧2)の特殊ユニタリ行列SU(dn)を、量子コンピュータのための量子回路に対応する疎行列の積に分解するユニタリ行列分解方法であって、
入力された特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として上記記憶部に格納する行列格納過程と、
上記処理設定部が、上記記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列を読み出し、それを行列Gとする処理設定過程と、
上記行列分解部が、m/2以下の最大の整数又はm/2以上の最小の整数をｔとし、dt/2以上の最小の整数をc1とし、dt/2以下の最大の整数をc2とし、pをp=c1・dm-tとし、qをq=c2・dm-tとし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とした場合における、上記処理設定過程で読み出された上記行列Gから、G=K1・A1・K2を満たす行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1とを計算する行列分解過程と、
上記行列リスト更新部が、上記行列分解過程で計算された上記行列K1の部分行列K11∈SU(p),K12∈SU(q)と、上記行列分解過程で計算された上記行列K2の部分行列K21∈SU(p),K22∈SU(q)と、上記行列分解過程で計算された上記ブロック対角行列A1のdr×drの対角ブロックのユニタリ行列である部分行列とを、上記行列リストの要素として上記記憶部に格納し、これらの部分行列に対応する上記処理設定過程で読み出された上記行列Gを上記記憶部に格納された上記行列リストの要素から排除する行列リスト更新過程と、
上記制御部が、上記処理設定過程と上記行列分離過程と上記行列リスト更新過程とを、上記行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り繰り返し実行させる制御過程と、
を有し、
上記行列分解過程は、
上記行列分解部のコサインサイン分解部が、上記処理設定過程で読み出されたdm×dmの上記行列Gを、q×qのブロックG11と、q×pのブロックG12と、p×qのブロックG21と、p×pのブロックG22とに分割して各ブロックについて行列分解を行い、上記行列Gから４つの対角行列D11,D12,D21,D22と正方行列K11, K12, K21, K22とを抽出するコサインサイン分解過程と、
上記行列分解部のブロック抽出部が、上記コサインサイン分解過程で抽出された上記４つの対角行列D11,D12,D21,D22の各j行j列目の対角成分D11[j,j],D12[j,j],D21[j,j],D22[j,j]を要素とする2×2の行列Rjを生成し、当該行列Rjを出力するブロック抽出過程と、
dが偶数である場合には、上記行列分解部のブロック対角化部が、重複しないようにd/2個選択された上記ブロック抽出過程で生成された上記行列Rjをブロックとしたd×dのブロック対角行列と、2×2の単位行列と、をブロックとするブロック対角行列A1を生成し、dが奇数である場合には、上記ブロック対角化部が、ηをdt/2以下の最大の整数とした場合における上記ブロック抽出過程で生成されたη個の上記行列Riと１つの１とを対角成分に配置したdt×dtのユニタリ行列をブロックとするブロック対角行列A1を生成するブロック対角化過程と、
を有し、
上記コサインサイン分解過程は、
上記コサインサイン分解部のブロック分割部が、上記処理設定過程で読み出された上記行列Gから
【数２２】
0004758965.tif 000023
を満たす４つのブロックG11, G12, G21, G22を生成するブロック分割過程と、
上記コサインサイン分解部の特異値分割部が、上記ブロック分割過程で生成された上記ブロックG11の特異値分解を行うことでG11=K11・D11・K21を満たす上記正方行列K11, K21とd1, d2, …, dq（1＞d1≧d2≧d3≧…≧dq＞0）を対角成分とする上記対角行列D11=diag (d1, d2, …, dq )とを生成し、さらに上記対角行列D11を用いて上記対角行列D22 =D11を生成する特異値分割過程と、
上記コサインサイン分解部のアークコサイン部が、上記特異値分割過程で生成された上記対角行列D11の各対角成分d1, d2, …, dqに対する角度φk = arccos dk (0≦φk＜π,  k =1,2,…,q) を計算するアークコサイン過程と、
上記コサインサイン分解部の第１ブロック算出部が、上記アークコサイン過程で計算された上記角度φk (k = 1, 2,…, q)より、上記対角行列D12= diag(sinφ1, sinφ2, …, sinφq)を算出し、さらに上記対角行列D12を用いて上記対角行列D21=-D12を計算する第１ブロック算出過程と、
上記コサインサイン分解部の第２ブロック算出部が、上記第１ブロック算出過程で計算された上記対角行列D12, D21の複素共役転置行列D12*, D21*と、上記ブロック分割過程で生成された上記ブロックG12, G21と、上記特異値分割過程で生成された上記正方行列K11の複素共役転置行列K11*とから、K22=D12*・K11*・G12及びK12=G21・D21*によって上記正方行列K22, K12を算出する第２ブロック算出過程と、を有する、
ことを特徴とするユニタリ行列分解方法。
【請求項３】
プログラムがコンピュータに読み込まれることでそれぞれ構成される記憶部と処理設定部と行列分解部と行列リスト更新部と制御部とを有し、量子コンピュータ上の演算を表すサイズがdn×dn(d≧3，n≧2)の特殊ユニタリ行列SU(dn)を、量子コンピュータのための量子回路に対応する疎行列の積に分解するユニタリ行列分解装置であって、
上記記憶部は、入力された特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として格納するように構成され、
上記処理設定部は、上記記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列を読み出し、それを行列Gとするように構成され、
上記行列分解部は、m/2以下の最大の整数又はm/2以上の最小の整数をｔとし、dt/2以上の最小の整数をc1とし、dt/2以下の最大の整数をc2とし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とした場合における、上記処理設定部で読み出された上記行列Gから、G=K1・A1・K2を満たす行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1とを計算するように構成され、
上記行列リスト更新部は、上記行列分解部で計算された上記行列K1の部分行列K11∈SU(p),K12∈SU(q)と、上記行列分解部で計算された上記行列K2の部分行列K21∈SU(p),K22∈SU(q)と、上記行列分解部で計算された上記ブロック対角行列A1の対角ブロックのdr×drのユニタリ行列である部分行列とを、上記行列リストの要素として上記記憶部に格納し、これらの部分行列に対応する上記処理設定過程で読み出された上記行列Gを上記記憶部に格納された上記行列リストの要素から排除するように構成され、
上記制御部は、上記処理設定部の処理と上記行列分離部の処理と上記行列リスト更新部の処理とを、上記記憶部に格納された行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り繰り返し実行させる制御を行うように構成され、
上記行列分解部は、
上記処理設定部で読み出された上記行列Gとその複素共役転置行列G*とを用い、σを1と-1とが対角成分に交互に並ぶdt×dtの対角行列σ=diag(1,-1,1,-1,...)とし、S=dm-tとし、IをS×Sの単位行列として、単位行列Iと対角行列σとのテンソル積を計算することにより行列ρを計算し、行列X=ρ・G*・ρ・Gを生成する第１行列積演算部と、
上記第１行列積演算部で生成された上記行列Xを用い、上記行列Xをブロック対角化する行列Pを生成する対角化行列生成部と、
上記第１行列積演算部で生成された上記行列Xと上記対角化行列生成部で生成された上記行列Pとその複素共役転置行列P*とを用い、B=P*・X・Pの演算によってブロック対角行列Bを生成する第２行列積演算部と、
上記第２行列積演算部で生成された上記ブロック対角行列Bの対角要素が１でない場合に、当該要素を[1,1]成分とする上記ブロック対角行列Bの４×４部分行列
【数２３】
0004758965.tif 000024
に置き換えることによりブロック対角行列Yを計算するブロック対角行列変換部と、
上記ブロック対角行列変換部で計算されたブロック対角行列Yと上記対角化行列生成部で生成された上記行列Pと上記複素共役転置行列P*とを用い、M＝P・Y・P*の演算を行って行列Mを生成する第３行列積演算部と、
上記処理設定部で読み出された上記行列Gとその複素共役転置行列M*とを用い、K=G・M*の演算を行って行列Kを生成する第４行列積演算部と、
上記第４行列積演算部で生成された上記行列Kと上記対角化行列生成部で生成された上記行列Pとを用い、K1=K・Pの演算を行って上記行列K1を生成する第５行列積演算部と、
上記対角化行列生成部で生成された上記行列Ｐの複素共役転置行列Ｐ＊を行列K2とし、上記行列ＹをＡ１として、上記行列Ｋ１と上記行列Ｋ２と上記行列A1とを出力する行列分割部と、を有し、
上記対角化行列生成部は、
上記第１行列積演算部で生成された上記行列Ｘの固有値と固有ベクトルとを算出する固有値・固有ベクトル算出部と、
上記固有値・固有ベクトル算出部で算出された上記固有値と固有ベクトルのうち、対応する固有値が虚数である固有ベクトルuk（kは自然数）に対し、ベクトルuk+ρ・uk及びuk-ρ・ukを生成し、当該ベクトルuk+ρ・ukを奇数要素に、uk−ρ・ukを偶数要素に格納したリストV1を生成する第１リスト要素生成部と、
上記固有値・固有ベクトル算出部で算出された上記固有値と固有ベクトルのうち、対応する固有値が実数である固有ベクトルukのうち、uk+ρ・uk=ukを満たす固有ベクトルukをリストW1の要素として格納し、uk-ρ・uk=-ukを満たす固有ベクトルukに対するベクトル-ukをリストW2の要素として格納し、対応する固有値が実数である固有ベクトルukについて (uk+ρ・uk)/‖uk+ρ・uk‖（‖α‖はαのノルムを示す）をリストW1及びW2の要素として格納したリストを生成する第２リスト要素生成部と、
dが奇数である場合には、上記第１リスト要素生成部で生成された上記リストV1又は上記第２リスト要素生成部で生成された上記リストW2に属するdt-1個の要素と上記第２リスト要素生成部で生成された上記リストW1の1個の要素とからなるdt列のベクトル列を、上記リストV1、リストW1及びリストW2の各要素をそれぞれ重複させることなく用いて上記リストV1及びリストW2のすべての要素を使い切るまで生成し、生成された各dt列のベクトル列とリストW2の残りの要素とを列方向に並べた行列を上記行列Pとして生成し、生成された上記行列Pを出力し、dが偶数である場合には、上記第１リスト要素生成部で生成された上記リストV1、上記第２リスト要素生成部で生成された上記リストW1及びリストW2の各要素をそれぞれ重複させることなく列方向に並べた行列を上記対角化行列生成部で生成される上記行列Pとして生成する行列配列部と、を有し、
上記行列リスト更新部は、
上記第１行列積演算部で計算された行列上記ρの対角成分からなるベクトルの-1の要素を0に置換したベクトルτ1を生成する第１ベクトル生成部と、
上記第１行列積演算部で計算された上記行列ρの対角成分からなるベクトルの1の要素を0に置換したベクトルτ2を生成する第２ベクトル生成部と、
上記第１ベクトル生成部で生成された上記ベクトルτ１を用いて、行列T1=τ1・τ1T（αTは転置ベクトル）を生成する第１抽出行列生成部と、
上記第２ベクトル生成部で生成されたベクトルτ２を用いて、行列T2=τ2・τ2Tを生成する第２抽出行列生成部と、
上記行列分割部で出力された上記行列K1から、上記第１抽出行列生成部で生成された上記行列T1の行列成分が１である行−列の要素のみを取り出した上記部分行列K11を生成する第１部分行列抽出部と、
上記行列分割部で出力された上記行列K1から、上記第２抽出行列生成部で生成された上記行列T2の行列成分が１である行−列の要素のみを取り出した上記部分行列K12を生成する第２部分行列抽出部と、
上記行列分割部で出力された上記行列K2から、上記第１抽出行列生成部で生成された上記行列T1の行列成分が１である行−列の要素のみを取り出した上記部分行列K21を生成する第３部分行列抽出部と、
上記行列分割部で出力された上記行列K2から、上記第２抽出行列生成部で生成された上記行列T2の行列成分が１である行−列の要素のみを取り出した上記部分行列K22を生成する第４部分行列抽出部と、を有する、
ことを特徴とするユニタリ行列分解装置。
【請求項４】
プログラムがコンピュータに読み込まれることでそれぞれ構成される記憶部と処理設定部と行列分解部と行列リスト更新部と制御部とを有し、量子コンピュータ上の演算を表すサイズがdn×dn(d≧3，n≧2)の特殊ユニタリ行列SU(dn)を、量子コンピュータのための量子回路に対応する疎行列の積に分解するユニタリ行列分解装置であって、
上記記憶部は、入力された特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として格納するように構成され、
上記処理設定部は、上記記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列を読み出し、それを行列Gとするように構成され、
上記行列分解部は、m/2以下の最大の整数又はm/2以上の最小の整数をｔとし、dt/2以上の最小の整数をc1とし、dt/2以下の最大の整数をc2とし、pをp=c1・dm-tとし、qをq=c2・dm-tとし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とした場合における、上記処理設定部で読み出された上記行列Gから、G=K1・A1・K2を満たす行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1とを計算するように構成され、
上記行列リスト更新部は、上記行列分解部で計算された上記行列K1の部分行列K11∈SU(p),K12∈SU(q)と、上記行列分解部で計算された上記行列K2の部分行列K21∈SU(p),K22∈SU(q)と、上記行列分解部で計算された上記ブロック対角行列A1のdr×drの対角ブロックのユニタリ行列である部分行列とを、上記行列リストの要素として上記記憶部に格納し、これらの部分行列に対応する上記処理設定部で読み出された上記行列Gを上記記憶部に格納された上記行列リストの要素から排除するように構成され、
上記制御部が、上記処理設定部の処理と上記行列分離部の処理と上記行列リスト更新部の処理とを、上記行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り繰り返し実行させる制御を行うように構成され、
上記行列分解部は、
上記処理設定部で読み出されたdm×dmの上記行列Gを、q×qのブロックG11と、q×pのブロックG12と、p×qのブロックG21と、p×pのブロックG22とに分割して各ブロックについて行列分解を行い、上記行列Gから４つの対角行列D11,D12,D21,D22と正方行列K11, K12, K21, K22とを抽出するコサインサイン分解部と、
上記コサインサイン分解部で抽出された上記４つの対角行列D11,D12,D21,D22の各j行j列目の対角成分D11[j,j],D12[j,j],D21[j,j],D22[j,j]を要素とする2×2の行列Rjを生成し、当該行列Rjを出力するブロック抽出部と、
dが偶数である場合には、重複しないようにd/2個選択された上記ブロック抽出部で生成された上記行列Rjをブロックとしたd×dのブロック対角行列と、2×2の単位行列と、をブロックとするブロック対角行列A1を生成し、dが奇数である場合には、ηをdt/2以下の最大の整数とした場合における上記ブロック抽出部で生成されたη個の上記行列Riと１つの１とを対角成分に配置したdt×dtのユニタリ行列をブロックとするブロック対角行列A1を生成するブロック対角化部と、
を有し、
上記コサインサイン分解部は、
上記処理設定部で読み出された上記行列Gから
【数２４】
0004758965.tif 000025
を満たす４つのブロックG11, G12, G21, G22を生成するブロック分割部と、
上記ブロック分割部で生成された上記ブロックG11の特異値分解を行うことでG11=K11・D11・K21を満たす上記正方行列K11, K21とd1, d2, …, dq（1＞d1≧d2≧d3≧…≧dq＞0）を対角成分とする上記対角行列D11=diag (d1, d2, …, dq )とを生成し、さらに上記対角行列D11を用いて上記対角行列D22 =D11を生成する特異値分割部と、
上記特異値分割部で生成された上記対角行列D11の各対角成分d1, d2, …, dqに対する角度φk = arccos dk (0≦φk＜π,  k =1,2,…,q) を計算するアークコサイン部と、
上記アークコサイン部で計算された上記角度φk (k = 1, 2,…, q)より、上記対角行列D12= diag(sinφ1, sinφ2, …, sinφq)を算出し、さらに上記対角行列D12を用いて上記対角行列D21=-D12を計算する第１ブロック算出部と、
上記第１ブロック算出部で計算された上記対角行列D12, D21の複素共役転置行列D12*, D21*と、上記ブロック分割部で生成された上記ブロックG12, G21と、上記特異値分割部で生成された上記正方行列K11の複素共役転置行列K11*とから、K22=D12*・K11*・G12及びK12=G21・D21*によって上記正方行列K22, K12を算出する第２ブロック算出部と、を有する、
ことを特徴とするユニタリ行列分解装置。
【請求項５】
請求項１又は２に記載のユニタリ行列分解方法の各過程をコンピュータに実行させるためのユニタリ行列分解プログラム。
【請求項６】
請求項５に記載のユニタリ行列分解プログラムを格納したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意のユニタリ行列を疎行列（行列の大部分が０となるような行列）の積に分解するユニタリ行列分解装置、ユニタリ行列分解方法、その機能をコンピュータで実現するためのプログラム及びそれを格納した記録媒体に関する。
【背景技術】
【０００２】
量子コンピュータにおける各操作はユニタリ行列によって表現されるが、ユニタリ行列によって表現される量子操作を実際の量子コンピュータで実現するためには、ユニタリ行列を量子コンピュータで実装可能な行列に分解しなければならない。このユニタリ行列を分解する手法は、大きく２つに分けられる。一つは、2n×2nのユニタリ行列を分解する手法であり、0,1の２値の重ね合わせ状態を採る系（量子２準位系）で動作する量子コンピュータのための量子回路設計（量子コンパイラ）に応用される。もう一つは、dn×dn(d≧2)のユニタリ行列を分解する手法であり、0,1,...,d-1のｄ値の重ね合わせ状態を採る系（量子ｄ準位系）で動作する量子コンピュータのための量子回路設計（量子コンパイラ）に応用される。なお、nは量子ビット数に対応する。
【０００３】
以下、従来のユニタリ行列の分解手法について説明する。
【０００４】
〔従来手法１〕
2n×2nのユニタリ行列を分解する手法として、KAK分解と呼ばれる行列分解の枠組みを用いる手法がある（例えば、特許文献１、非特許文献１等参照）。この手法では、2n×2nの特殊ユニタリ行列G∈SU(2n)を、行列K1,K2∈K(2n)と、2×2のユニタリ行列をブロックとするブロック対角行列Aとの積G=K1・A・K2に分解する（図２３（ａ）参照）。なお、K(2n)は、2n-1×2n-1の特殊ユニタリ行列の集合SU(2n-1)と2n-1×2n-1の特殊ユニタリ行列の集合SU(2n-1)との直和からなる行列の集合である。
【０００５】
このように分解された2×2の要素をブロックとするブロック対角行列Aは、容易に量子２準位系で動作する量子コンピュータのための量子回路へ変換可能である（図２３（ｂ）参照）。一方、nが大きい場合、行列K1,K2を容易に量子回路に変換することはできない。そこで、行列K1をその部分行列K11∈SU(2n-1),K12∈SU(2n-1)に分解し、行列K2をその部分行列K21∈SU(2n-1),K22∈SU(2n-1)に分解する。ここで、行列K1は部分行列K11,K12の直和であり、行列K2は部分行列K21,K22の直和であるため、これらの部分行列への分解は容易である。そして、分解によってサイズが小さくなった部分行列K11,K12,K21,K22をそれぞれ新たな行列Gとして同様な処理を再帰的に行う。以上により、2n×2nのユニタリ行列が、量子回路に変換可能な行列に分解される。
【０００６】
〔従来手法２〕
また、dn×dn(d≧2)のユニタリ行列を分解する手法として、コサインサイン（Cosine-Sine）分解を用いる手法がある（例えば、非特許文献３等参照）。
【０００７】
この手法では、dn×dnの特殊ユニタリ行列G∈SU(dn)を、dn-1×dn-1のブロックG11、dn-1×(d-1)dn-1のブロックG12、(d-1)dn-1×dn-1のブロックG21、及び、(d-1)dn-1×(d-1)dn-1のブロックG22の４つのブロックに分割し、特異値分解によって各ブロックをG11= K11・D11・K21, G12= K11・D12・K22, G21= K12・D21・K21, G22= K12・D22・K22のように分解する（図２４（ａ）参照）。ここで、ブロックD11，D12，D21，D22は、2×2の要素をブロックとするブロック対角行列Aに変換される。このブロック対角行列Aは、容易に量子ｄ準位系で動作する量子コンピュータのための量子回路へ変換できる（図２４（ｂ）参照）。また、K11,K21∈SU(dn-1),K12,K22∈SU((d-1)dn-1)は、それぞれ新たな行列Gとされ、同様な処理が再帰的に行われる。以上により、dn×dn(d≧2)のユニタリ行列が、量子回路に変換可能な行列に分解される。図２５は、d=2,n=5の場合のユニタリ行列の分解例である。分解のたびに分解対象の行列に対応する量子ビットの数が１つずつ減っているのが分かる。
【特許文献１】特開２００６−１９５５８７
【非特許文献１】Nakajima, Y., Kawano Y. and Sekigawa,H, “A new algorithm for producing quantum circuits using KAK decompositions,” Quantum Information & Computation, Vol. 6, No. 1, pp. 067-080 (2006).
【非特許文献２】Khan, F. A. and Perkowski, M. M.“Synthesis of multi-qudit hybrid and d-valued quantum logic circuits by decomposition,” Theoretical Computer Science, Vol. 367, No. 3, pp. 336-356 (2006).
【非特許文献３】Paige, C. and Wei,M. “History and generality of the CS decomposition,” Linear Algebra and its Applications, pp.303-326, 1994.
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかし、従来は、dn×dn(d≧3)のユニタリ行列を、量子ｄ準位系で動作する量子コンピュータのための量子回路に変換可能な行列の積に効率的に分解する手法は存在しなかった。
【０００９】
すなわち、従来手法１は、2n×2nのユニタリ行列の分解のみに適用可能な手法であり、従来手法１をdn×dn(d≧3)のユニタリ行列の分解に適用することはできない。また、仮に従来手法１をdn×dn(d≧3)のユニタリ行列の分解に適用できたとしても、量子ｄ準位系で動作する量子コンピュータに適した量子回路への変換に不適切な分解がなされてしまう場合がある。以下、この事例を説明する。
【００１０】
n個の量子ビット数を用いた量子ｄ準位系にはdn個の基底が存在し、それらの基底はdn個のdn次元の基底ベクトル[1,0,....,0]T,[0,1,....,0]T,...,[0,0,....,1]T（[・]Tは[・]の転置）で表現できる。また、n個の量子ビットの量子状態は、これらの基底ベクトルに係数（確率）を掛けたものを線形結合したベクトルで表現できる。そして、量子操作前の量子状態を表すベクトルに、量子操作を示すユニタリ行列を掛けた場合、量子操作後の量子状態を表すベクトルが得られる。ここで、従来手法よって生成されたブロック対角行列Aが2×2の対角ブロックを有するブロック対角行列であった場合、それぞれ2×2の対角成分は、量子状態を表すベクトルのうち２つの基底に対応する要素（係数）のみに作用する。そのため、この2×2の対角ブロック成分のみでは、３つ以上の基底に関する量子操作を完全に表現できない。このようなブロック対角行列Aを、各量子ビットが３つ以上の準位を持つ量子ｄ（d≧3）準位系の量子回路に対応する行列にそのまま変換することはできない。
【００１１】
また、従来手法２をdn×dn(d≧3)のユニタリ行列の分解に適用した場合、１回の分解によってもなお(d-1)dn-1×(d-1)dn-1という大きなサイズの行列が生成されてしまう。その結果、行列を分解するための再帰的処理の回数も多くなり、最終的に分解される行列の数も多くなってしまう。
【００１２】
本発明はこのような点に鑑みてなされたものであり、dn×dn(d≧3)のユニタリ行列を、量子ｄ準位系で動作する量子コンピュータのための量子回路に対応する行列の積に効率的に分解する技術的思想を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明では上記課題を解決するために、入力された特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として記憶部に格納する（行列格納過程）。次に、処理設定部が、記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列Gを読み出し、それを行列Gとする（処理設定過程）。次に、行列分解部が、行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1との積G=K1・A1・K2に分解する（行列分解過程）。なお、c1, c2, tを実数とし、c1+c2=dtとし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とする。次に、行列リスト更新部が、行列K1の部分行列K11∈SU(p),K12∈SU(q)と、行列K2の部分行列K21∈SU(p),K22∈SU(q)と、ブロック対角行列A1の対角ブロックのdr×drのユニタリ行列である部分行列とを、行列リストの要素として記憶部に格納し、これらの部分行列に対応する行列Gを行列リストの要素から排除する（行列リスト更新過程）。そして、行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り、処理設定過程と行列分離過程と行列リスト更新過程とを繰り返し実行する。
【００１４】
ここで、行列分解過程では、行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1との積G=K1・A1・K2に分解する。また、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる集合K(dm)に属する行列K1,K2∈K(dm)は、それぞれp×pの部分行列K11, K21とq×qの部分行列K12, K22とに容易に分解できる。そして、q<p<(d-1)・dm-1であるため、部分行列K11, K12,K21, K22のサイズは、必ず(d-1)・dm-1×(d-1)・dm-1未満となる。そして、m≦nであるため、本発明の場合、１回の分解で従来手法２よりも小さなサイズの行列に分解できる。その結果、行列を分解するための再帰的処理の回数も削減でき、最終的に分解される行列の数も減らすことができる。
【００１５】
また、行列分解過程では、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1も得られるが、このようなブロック対角行列A1を、ブロック対角行列A1の対角部分に並ぶ部分ブロックであるdr×drのユニタリ行列に分解することは容易である。また、dr×drのユニタリ行列であれば、ｄ個の準位をとる或る数の量子ビットに対する量子操作を完全に表現できる。よって、再帰的な処理を行うことによって、このようなdr×drの行列を量子回路に変換可能な行列に分解することは可能である。
【発明の効果】
【００１６】
以上のように、本発明では、dn×dn(d≧3)のユニタリ行列を、量子ｄ準位系で動作する量子コンピュータのための量子回路に変換可能な行列の積に効率的に分解することができる。
【発明を実施するための最良の形態】
【００１７】
以下、本発明を実施するための最良の形態を図面を参照して説明する。
【００１８】
〔使用する記号の定義〕
まず、本形態で使用する記号を以下のように定義する。
【００１９】
i：虚数単位（i2=-1）
A*：行列Ａの複素共役転置行列
I：単位行列
0：成分が０の行列
diag(a,b,c,d)：対角成分がa,b,c,dの順に並んだ対角行列
∈：左辺が右辺の集合の元
‖・‖：・のノルム
【００２０】
【数１】
0004758965.tif 000002
SU(dm)：サイズがdn×dnの特殊ユニタリ行列
K(dm)：特殊ユニタリ行列の集合SU(p)と特殊ユニタリ行列の集合SU(q)との直和（ただし、p+q=dm）からなる行列の集合
floor(α)：α以下の最大の整数
ceil(α)：α以上の最小の整数
B[α,β]：行列Bのα行−β列の要素
【００２１】
〔原理〕
次に、本形態の原理について説明する。
【００２２】
前述のように、本形態では、まず、分解対象の特殊ユニタリ行列G’∈SU(dn)を行列リストの要素として記憶部に格納する（行列格納過程）。次に、処理設定部が、記憶部に格納された行列リストの要素からサイズがdm×dm(n≧m≧2)の行列Gを読み出し、それを行列Gとする（処理設定過程）。次に、行列分解部が、行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1との積G=K1・A1・K2に分解する（行列分解過程）。なお、c1, c2, tを実数とし、c1+c2=dtとし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とする。次に、行列リスト更新部が、行列K1の部分行列K11∈SU(p),K12∈SU(q)と、行列K2の部分行列K21∈SU(p),K22∈SU(q)と、ブロック対角行列A1の対角ブロックのdr×drのユニタリ行列である部分行列とを、行列リストの要素として記憶部に格納し、これらの部分行列に対応する行列Gを行列リストの要素から排除する（行列リスト更新過程）。そして、行列リストの要素としてサイズがd×dよりも大きな行列が存在する限り、処理設定過程と行列分離過程と行列リスト更新過程とを繰り返し実行する。
【００２３】
これにより、１回の分解で従来手法２よりも小さなサイズの行列に分解できるため、行列を分解するための再帰的処理の回数を削減でき、最終的に分解される行列の数も減らすことができる。また、前述のように本形態では、量子ｄ準位系の量子コンピュータの量子回路に容易に変換可能な行列に分解できる。
【００２４】
また、tをm/2以上の最小の整数とし、c1をdt/2以上の最小の整数とし、c2をdt/2以下の最大の整数とした場合、１回の分解でほぼ同程度のサイズの行列へ分解できる。この場合、再帰的処理を行うたびに行列のサイズをすべて約半分にできるため、再帰的処理の回数を最大限削減できる。その結果、分解処理効率を最大化することができる。
【００２５】
〔第１実施形態〕
本形態は、KAK分解の性質を利用して行列分解過程を実行する形態である。
【００２６】
すなわち、本形態の行列分解過程では、まず、入力された行列Gの複素共役転置行列G*を生成し（第１複素共役転置行列生成過程）、行列X=ρ・G*・ρ・Gを生成する（第１行列積演算過程）。なお、ρは、S×S（S=dm-t）の単位行列Iと対角行列σとのテンソル積であり、σは1と-1とが対角成分に交互に並ぶdt×dtの対角行列σ=diag(1,-1,1,-1,...)である。次に、行列Xをブロック対角化する行列Pを生成し（対角化行列生成過程）、行列Pの複素共役転置行列P*を生成し（第２複素共役転置行列生成過程）、B=P*・X・Pの演算によってブロック対角行列Bを生成し（第２行列積演算過程）、このブロック対角行列BをG=K・M、K∈K(dm)、X=M2及びY=P*・M・Pを満たすブロック対角行列Yに変換する（ブロック対角行列変換過程）。そして、M＝P・Y・P*の演算を行って行列Mを生成し（第３行列積演算過程）、行列Mの複素共役転置行列M*を生成し（第３複素共役転置行列生成過程）、K=G・M*の演算を行って行列Kを生成し（第４行列積演算過程）、K1=K・Pの演算を行って行列K1を生成する（第５行列積演算過程）。そして、G=K1・A1・K2を満たす、行列K1と、複素共役転置行列P*（=行列K2）と、ブロック対角行列Y（=ブロック対角行列A1）とを出力する。
【００２７】
ここで、上述のように生成されたρは、以下の関係を満たす。
【００２８】
【数２】
0004758965.tif 000003
よって、第１行列積演算過程で生成された行列X=ρ・G*・ρ・Gは、G=K・Mを満たす特殊ユニタリ行列K,Mに対し、以下の関係を満たす。
【００２９】
X=ρ・G*・ρ・G
=ψ(G*) ・G（（１）の関係より）
=ψ(M*・K*) ・K・M
=ψ(M*)・ψ(K*) ・K・M
=M・K*・K・M（（１）の関係より）
=M2（Kがユニタリ行列でありK*・Kが単位行列となるため）
すなわち、d≧3であっても、行列GからG=K・M,X=M2を満たす行列Xを求めることは容易である。この点、従来手法１と相違する。また、この行列Xをブロック対角化する行列Pを生成し（対角化行列生成過程）、当該行列Pの複素共役転置行列P*を生成し（第２複素共役転置行列生成過程）、ブロック対角行列B=P*・X・Pを求める（第２行列積演算過程）ことも容易である。また、行列Pはユニタリ行列となりP・P*=Iを満たし、Ｂ=P*・X・P=P*・M2・P=(P*・M・P)(P*・M・P)=Y2となるから、ブロック対角行列Bからブロック対角行列Yへは規則的に変換できる（ブロック対角行列変換過程）。さらに、求められたブロック対角行列Yと行列Pと複素共役転置行列P*とからM=P・Y・P*の演算によって行列Mを生成し（第３行列積演算過程）、当該行列Ｍの複素共役転置行列M*を生成し（第３複素共役転置行列生成過程）、行列Gと複素共役転置行列M*とからK=G・M*の演算によって行列Kを生成することも容易である（第４行列積演算過程）。さらに、K1=K・Pの演算を行って行列K1を生成することも容易である（第５行列積演算過程）。
【００３０】
なお、第１実施形態の行列分解過程は、サイズがdm×dm(m≧2,d≧3)の行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1との積G=K1・A1・K2に分解するものであり、c1, c2, tを実数とし、c1+c2=dtとし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とした場合に広く適用可能なものである。しかし、以下では、説明の簡略化のため、tをm/2以下の最大の整数とし、c1をdt/2以上の最小の整数とし、c2をdt/2以下の最大の整数とした場合を例にとって説明する。
【００３１】
＜ハードウェア構成＞
図５は、第１実施形態におけるユニタリ行列分解装置１００の構成を例示したブロック図である。
【００３２】
図５に例示するように、この例のユニタリ行列分解装置１００は、ＣＰＵ（Central Processing Unit）１１０、入力部１２０、出力部１３０、補助記憶装置１４０、ＲＡＭ（Random Access Memory）１５０、ＲＯＭ（Read Only Memory）１６０及びバス１７０を有している。
【００３３】
この例のＣＰＵ１１０は、制御部１１１、演算部１１２及びレジスタ１１３を有し、レジスタ１１３に読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２０は、データが入力される入力ポート、キーボード、マウス等であり、出力部１３０は、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１４０は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、本形態のユニタリ行列の分解処理を実行するためのユニタリ行列分解プログラムを格納したユニタリ行列分解プログラム領域１４１及び分解対象となるユニタリ行列Ｇ等の各種データが格納されるデータ領域１４２を有している。また、ＲＡＭ１５０は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、ユニタリ行列分解プログラムが書き込まれるユニタリ行列分解プログラム領域１５１及び分解対象となるユニタリ行列Ｇ等の各種データが格納されるデータ領域１５２を有している。また、バス１７０は、ＣＰＵ１１０、入力部１２０、出力部１３０、補助記憶装置１４０、ＲＡＭ１５０及びＲＯＭ１６０を通信可能に接続している。
【００３４】
＜ハードウェアとソフトウェアとの協働＞
ＣＰＵ１１０は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４０のユニタリ行列分解プログラム領域１４１に格納されているユニタリ行列分解プログラムを、ＲＡＭ１５０のユニタリ行列分解プログラム領域１５１に書き込む。同様にＣＰＵ１１０は、補助記憶装置１４０のデータ領域１４２に格納されている分解対象のユニタリ行列等のデータを、ＲＡＭ１５０のデータ領域１５２に書き込む。そして、このユニタリ行列分解プログラムやデータが書き込まれたＲＡＭ１５０上のアドレスがＣＰＵ１１０のレジスタ１１３に格納される。ＣＰＵ１１０の制御部１１１は、レジスタ１１３に格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１５０上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１２に順次実行させ、その演算結果をレジスタ１１３に格納していく。
【００３５】
図１から図４は、このようにＣＰＵ１１０にユニタリ行列分解プログラムが読み込まれることにより実現されるユニタリ行列分解装置１００の機能構成を例示したブロック図である。ここで、図１は、第１実施形態のユニタリ行列分解装置１００の全体構成を示したブロック図であり、図２は、図１の行列分解部１５０の詳細構成を示したブロック図であり、図３（ａ）は、図２の対角化行列生成部１５４の詳細構成を示したブロック図である。また、図３（ｂ）は、図１の処理設定部１４０の詳細構成を示したブロック図であり、図４は、行列リスト更新部１７０の詳細構成を示したブロック図である。
【００３６】
図１に示すように、本形態のユニタリ行列分解装置１００は、入力部１１０と、出力部１２０と、記憶部１３０と、処理設定部１４０と、行列分解部１５０と、行列リスト更新部１７０と、制御部１８０と、一時記憶部１９０とを有する。また、図２に示すように、本形態の行列分解部１５０は、対角行列生成部１５１と、第１複素共役転置行列生成部１５２と、第１行列積演算部１５３と、対角化行列生成部１５４と、第２行列積演算部１５５と、第２複素共役転置行列生成部１５６と、ブロック対角行列変換部１５７と、第３行列積演算部１５８と、第３複素共役転置行列生成部１５９と、第４行列積演算部１６０と、第５行列積演算部とを有する。また、図３（ａ）に示すように、対角化行列生成部１５４は、固有値・固有ベクトル算出部１５４ａと、第１リスト要素生成部１５４ｂと、第２リスト要素生成部１５４ｃと、行列配列部１５４ｄとを有する。また、図３（ｂ）に示すように、処理設定部１４０は、パラメータ更新部１４１と、行列読み出し部１４２と、対角行列生成部１４３とを有する。さらに、行列リスト更新部１７０は、第１ベクトル生成部１７１と、第２ベクトル生成部１７２と、第１抽出行列生成部１７３と、第２抽出行列生成部１７４と、第１部分行列抽出部１７５と、第２部分行列抽出部１７６と、第３部分行列抽出部１７７と、第４部分行列抽出部１７８と、ブロック分割部１７９とを有する。
【００３７】
なお、記憶部１３０及び一時記憶部１９０は、レジスタ１１３、ＲＡＭ１５０のデータ領域１５２、補助記憶装置１４０のデータ領域１４２等に相当する。また、処理設定部１４０、行列分解部１５０、行列リスト更新部１７０及び制御部１８０は、ユニタリ行列分解プログラムがＣＰＵ１１０に読み込まれることにより構成されるものである。
【００３８】
＜処理＞
次に本形態におけるユニタリ行列分解装置１００の処理について説明する。
【００３９】
図６は本形態におけるユニタリ行列分解装置１００の処理の全体を説明するためのフローチャートである。なお、以下の処理は制御部１８０（図１）の制御のもと実行される。また、以下では説明を省略するが、各処理過程におけるデータは、逐一一時メモリ１９０に格納され、格納されたデータは他の処理に利用される。
【００４０】
まず、入力部１１０（図１）に、分割対象のdn×dn(d≧3，n≧2)の特殊ユニタリ行列G’∈SU(dn)が入力され、リストLの要素として記憶部１３０に格納される（ステップＳ１／行列格納過程）。また、この際、入力部１１０にd,nの値も入力されて、記憶部１３０に格納される。
【００４１】
次に、処理設定部１４０のパラメータ更新部１４１（図３（ｂ））が、記憶部１３０からnを読み込み、 t=floor(n/2)によってtを求めて出力する（ステップＳ２）。次に、対角行列生成部１４３に、このtと記憶部１３０から読み込まれたdとが入力され、対角行列生成部１４３は、1と-1とが対角成分に交互に並ぶdt×dtの対角行列σ=diag(1,-1,1,-1,...)を求めて出力する（ステップＳ３）。また、パラメータ更新部１４１から出力されたtは行列読み出し部１４２に送られ、行列読み出し部１４２は、記憶部１３０に格納されたリストLの要素からサイズがdt×dtよりも大きなdm×dm(n≧m≧2)の行列を読み出し、それを行列Gとする（処理設定過程／ステップＳ４）。なお、最初のループではm=nとなる。
【００４２】
次に、行列Gと対角行列σとdとtとmとは行列分解部１５０に入力され、行列分解部１５０は、これらを用い、行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1と、の積G=K1・A1・K2に分解し、その分解された行列のリストであるリストL’を出力する（行列分解過程／ステップＳ５）。以下、行列分解過程／ステップＳ５（処理１）の詳細を説明する。
【００４３】
［行列分解過程／ステップＳ５（処理１）の詳細］
図７は、行列分解過程／ステップＳ５（処理１）の詳細を説明するためのフローチャートである。
【００４４】
まず、行列分解部１５０の対角行列生成部１５１（図２）にdとtとmとが入力され、対角行列生成部１５１は、S = N/dtを算出する（ステップにＳ１１）。ただし、Nは行列Gのサイズ（N×N）である。次に、対角行列生成部１５１に対角行列σが入力され、対角行列σとS×Sの単位行列Iとのテンソル積を求め、その結果を行列ρとして出力する（ステップＳ１２）。
【００４５】
次に、第１複素共役転置行列生成部１５２に行列Gが入力され、第１複素共役転置行列生成部１５２が、その複素共役転置行列G＊を生成して出力する（第１複素共役転置行列生成過程）。次に、第１行列積演算部１５３に、行列ρと行列Gとその複素共役転置行列G＊とが入力され、第１行列積演算部１５３は、行列X=ρ・G*・ρ・Gを生成して出力する（第１行列積演算過程／ステップＳ１３）。
【００４６】
次に、対角化行列生成部１５４に行列Xが入力され、対角化行列生成部１５４は、入力された行列Xを用い、行列Xをブロック対角化する行列Pを生成して出力する（対角化行列生成過程／ステップＳ１４）。
【００４７】
［対角化行列生成過程／ステップＳ１４の詳細］
図８は、対角化行列生成過程／ステップＳ１４の詳細を例示するためのフローチャートである。また、図９は図８におけるステップＳ３２の詳細を、図１０は図８におけるステップＳ３３の詳細をそれぞれ説明するためのフローチャートである。
【００４８】
まず、対角化行列生成部１５４の固有値・固有ベクトル算出部１５４ａ（図３（ａ））に行列Ｘが入力され、固有値・固有ベクトル算出部１５４ａは、その固有値と固有ベクトルとを算出し、
リストＥ１＝［［虚の固有値，対応する固有ベクトル］，・・・］
リストＥ２＝［［実の固有値，対応する固有ベクトル］，・・・］
となるリストＥ１，Ｅ２を一時記憶部１９０に格納する（ステップＳ３１）。
【００４９】
次に、第１リスト要素生成部１５３ｂにリストＥ１と行列ρとが入力される。第１リスト要素生成部１５３ｂは、対応する固有値が虚数である固有ベクトルuk（kは自然数）に対し、ベクトルuk+ρ・uk及びuk-ρ・ukを生成し、当該ベクトルuk+ρ・uk及びuk-ρ・ukをリストV1の要素として出力する（第１リスト要素生成過程／ステップＳ３２（処理５））。
【００５０】
この例の場合（図９）、まず、第１リスト要素生成部１５３ｂは、ck=0と初期化し、ckにck+1の演算結果を代入し（ステップＳ４１）、リストＥ１からまだ調べていない正の固有値（符号が正の固有値）を１つ選び、対応する固有ベクトルukを抽出する（ステップＳ４２）。そして、第１リスト要素生成部１５３ｂは、この固有ベクトルukに対し、
V1[2ck‐1]=uk+ρ・uk
V1[2ck]=uk‐ρ・uk
を計算し、これらをリストV1の要素として一時記憶部１９０に格納する（ステップＳ４３）。その後、この例の第１の要素生成部４１２は、リストＥ１に、まだ調べていない正の固有値が存在するか否かを判断し（ステップＳ４４）、存在すればステップＳ４１以降の処理に戻り、存在しなければステップＳ３２（図９）の処理を終了する。なお、この例の処理の場合、V1は複素共役な固有値のペアに対応するベクトルのペアを[u1+ρ・u1,u1‐ρ・u1, u2+ρ・u2,u2‐ρ・u2,・・・]と配列したリストとなる。なお、図９の例では、ステップＳ４２において、リストＥ１からまだ調べていない正の固有値（符号が正の固有値）を１つ選び、対応する固有ベクトルｕｋを抽出することとし、ステップＳ４４において、ストＥ１に、まだ調べていない正の固有値が存在するか否かを判断することとしたが、ステップＳ４２において、リストＥ１からまだ調べていない負の固有値（符号が負の固有値）を１つ選び、対応する固有ベクトルｕｋを抽出することとし、ステップＳ４４において、リストＥ１に、まだ調べていない負の固有値が存在するか否かを判断することとしてもよい。要は、複素共役な固有値のペアに対応する固有ベクトルｕｋを用いればよい。
【００５１】
ステップＳ３２の処理が終了すると、次に第２リスト要素生成部１５３ｃ（図３）にリストＥ１と行列ρとが入力される。第２リスト要素生成部１５３ｃは、対応する固有値が実数である固有ベクトルukのうち、uk+ρ・uk=ukを満たす固有ベクトルukをリストW1の要素として出力し、uk-ρ・uk=-ukを満たす固有ベクトルukに対するベクトル-ukをリストW2の要素として出力し、対応する固有値が実数である固有ベクトルukについて (uk+ρ・uk)/‖uk+ρ・uk‖（‖α‖はαのノルムを示す）をリストW1及びW2の要素として出力する（第２リスト要素生成過程／ステップＳ３３（図８））。
【００５２】
この例の場合（図１０）、まず、第２リスト要素生成部１５３ｃは、c1=1,c2=1と初期化し、リストＥ２からまだ調べていない固有ベクトルを１つ選びukとする（ステップＳ５１）。次に、第２リスト要素生成部１５３ｃは、このukがuk+ρ・uk=ukを満たすか否かを判断し（ステップＳ５２）、満たす場合にのみW1[c1]=ukをリストW1の要素として一時記憶部１９０に格納し、c1=c1+1の演算を行う（ステップＳ５３）。次に、第２リスト要素生成部１５３ｃは、ukがuk+ρ・uk=-ukを満たすか否かを判断する（ステップＳ５４）。そして第２リスト要素生成部１５３ｃは、uk+ρ・uk=-ukを満たす場合にのみ、W2[c2]=-ukをリストW2の要素として一時記憶部１９０に格納し、c2=c2+1の演算を行う（ステップＳ５５）。次に、第２リスト要素生成部１５３ｃは、(uk+ρ・uk)/‖uk+ρ・uk‖を計算し、これをリストW1の要素W1[c1]として一時記憶部１９０に格納し、c1=c1+1の演算を行う（ステップＳ５６）。また、第２リスト要素生成部１５３ｃは、(uk+ρ・uk)/‖uk+ρ・uk‖を計算し、これをリストW2の要素W2[c2]として一時記憶部１９０に格納し、c2=c2+1の演算を行う（ステップＳ５７）。
【００５３】
その後、第２リスト要素生成部１５３ｃは、リストＥ２に、まだ調べていない固有ベクトルが存在するか否かを判断し（ステップＳ５８）、存在すればステップＳ５１以降の処理に戻り、存在しなければ、リストW1,W2について、それぞれ線形従属な要素を削除した後、各ベクトルを正規直行化し（ステップＳ５９）、ステップＳ３３（図８）の処理を終了する。
【００５４】
ステップＳ３３の処理が終了すると、行列構成部４１４は、dが奇数であるか否かを判断する（ステップＳ３４）。ここで、dが奇数でなければ、行列構成部４１４は、V1, W1, W2 に含まれるベクトルを重複させることなく列方向に順番に並べて行列Pを作り、出力する（ステップＳ３８）。なお、ベクトルの並べ方に制限はない。一方、dが奇数であれば、行列構成部４１４は、V’= [V1,W2]に含まれるベクトルを列方向にdt-1個並べた後、W1に含まれるベクトルを1個並べる処理（ステップＳ３５）を、V’に含まれるベクトルをすべて使用するまで繰り返す（ステップＳ３６）。そして、その後に、W1に含まれる残りのベクトルを列方向に並べ、行列Pとする（行列配列過程／ステップＳ３７）。なお、dが奇数の場合については、リストV1又はリストW2に属するdt-1個の要素とリストW1の1個の要素とからなるdt列のベクトル列を、リストV1、リストW1及びリストW2の各要素をそれぞれ重複させることなく用いてリストV1及びリストW2のすべての要素を使い切るまで生成し、生成された各dt列のベクトル列とリストW2の残りの要素とを列方向に並べた行列を行列Pとして生成するのであれば、ステップＳ３５〜Ｓ３７の処理以外の順序で処理してもよい。例えば、V’= [V1,W2]に含まれるベクトルを列方向にdt-1個並べた後、W1に含まれるベクトルを1個並べる処理（ステップＳ３５）の代わりに、W 1に含まれるベクトルを1個並べた後にV’= [V1,W2]に含まれるベクトルを列方向にdt-1個並べる処理をおこなってもよい（［対角化行列生成過程／ステップＳ１４の詳細］の説明終わり）。
【００５５】
ステップＳ１４の処理が終了すると（図７に戻る）、次に第２複素共役転置行列生成部１５６に行列Pが入力され、第２複素共役転置行列生成部１５６は、その行列Ｐの複素共役転置行列P*を生成して出力する（第２複素共役転置行列生成過程）。次に、第２行列積演算部１５５に、行列Xと複素共役転置行列P*とが入力され、第２行列積演算部１５５は、これらを用い、B=P*・X・Pの演算によってブロック対角行列Bを生成し、出力する（第２行列積演算過程／ステップＳ１５）。
【００５６】
次に、ブロック対角行列変換部１５７にブロック対角行列Bが入力され、ブロック対角行列変換部１５７は、入力されたブロック対角行列Bを、G=K・M、K∈K(dm)、X=M2及びY=P*・M・Pを満たすブロック対角行列Yに変換し、出力する（ブロック対角行列変換過程／ステップＳ１６（処理３））。ここで、ブロック対角行列Bは、2×2の行列或いは1が対角成分に並び他の要素が０のブロック対角行列である。また、前述の通りブロック対角行列Ｂとブロック対角行列YとはB=P*・X・P=P*・M2・P=(P*・M・P)(P*・M・P)=Y2の関係を満たす。よって、ブロック対角行列Bからブロック対角行列Yへの変換は、ブロック対角行列Bの対角部分に並んだ正方行列Cを正方行列E（C=E2を満たす）に置き換えることのみによって可能である。これにより、低い演算コストでブロック対角行列Bからブロック対角行列Yへの変換を行うことができる。以下、このブロック対角行列変換過程／ステップＳ１６（処理３）の詳細を例示する。
【００５７】
［ブロック対角行列変換過程／ステップＳ１６（処理３）の詳細］
図１１は、ブロック対角行列変換過程／ステップＳ１６（処理３）の詳細を説明するためのフローチャートである。
【００５８】
まず、ブロック対角行列変換部１５７は、k=1に初期化し（ステップＳ７１）、B[k,k]=1であるか否かを判断する（ステップＳ７２）。
【００５９】
ここで、B[k,k]=1であると判断された場合、ブロック対角行列変換部１５７は、k+1を新たなkとし（ステップＳ７３）、kは行列Bのサイズ(dm)より小さいか否かを判断する（ステップＳ７９）、ここで、kが行列Bのサイズ(dm)以上であればステップＳ１６の処理を終了する。一方、kが行列Bのサイズ(dm)より小さければ、ステップＳ７２の処理に戻る。
【００６０】
一方、ステップＳ７２でB[k,k]=1でないと判断された場合、ブロック対角行列変換部１５７は、
【００６１】
【数３】
0004758965.tif 000004
とする（ステップＳ７４）。
【００６２】
ここで、Cは
【００６３】
【数４】
0004758965.tif 000005
で書けるため、ブロック対角行列変換部１５７は、Cを
【００６４】
【数５】
0004758965.tif 000006
で置き換える（ステップＳ７７）。なお、式(3)の代わりに、以下の
【００６５】
【数６】
0004758965.tif 000007
によってCを置き換えてもよい。
【００６６】
その後、ブロック対角行列変換部１５７は、k+2を新たなkとし（ステップＳ７８）、前述のステップＳ７９の処理に進む（［ブロック対角行列変換過程／ステップＳ１６（処理３）の詳細］の説明終わり）。
【００６７】
ステップＳ１６の処理が終了すると、次に第３行列積演算部１５８に、行列Pと複素共役転置行列P*とブロック対角行列変換部１５７から出力された行列Yとが入力され、第３行列積演算部１５８は、M＝P・Y・P*の演算を行って行列Mを生成し、出力する（第３行列積演算過程）。また、第３複素共役転置行列生成部１５９に行列Mが入力され、第３複素共役転置行列生成部１５９は、その複素共役転置行列M*を生成して出力する（第３複素共役転置行列生成過程）。また、第４行列積演算部１６０に行列Gと複素共役転置行列M*とが入力され、第４行列積演算部１６０は、K=G・M*の演算を行って行列Kを生成し、出力する（第４行列積演算過程）。さらに、第５行列積演算部１６１に行列Pと行列Kとが入力され、第５行列積演算部１６１は、K1=K・Pの演算を行って行列K1を生成し、出力する（第５行列積演算過程）。そして、行列分割部１５０は、行列K1と行列K2(=P*)と行列A1(=Y)とを出力する（ステップＳ１７）。
【００６８】
次に、行列リスト更新部１７０（図１）が、行列K1の部分行列K11∈SU(p),K12∈SU(q)と、行列K2の部分行列K21∈SU(p),K22∈SU(q)とを抽出する（ステップＳ１８（処理４））。以下、この処理の詳細を説明する。
【００６９】
［ステップＳ１８（処理４）の詳細］
図１２は、ステップＳ１８（処理４）の詳細を説明するためのフローチャートである。
【００７０】
まず、行列リスト更新部１７０の第１ベクトル生成部１７１（図４）に行列ρが入力され、第１ベクトル生成部１７１は、ρの対角成分からなるベクトルの-1の要素を0に置換したベクトルτ1を生成し、出力する（第１ベクトル生成過程／ステップＳ８１）。また、第２ベクトル生成部１７２に行列ρが入力され、第２ベクトル生成部１７２は、ρの対角成分からなるベクトルの1の要素を0に置換したベクトルτ2を生成し、出力する（第２ベクトル生成過程／ステップＳ８２）。
【００７１】
次に、第１抽出行列生成部１７３にベクトルτ1が入力され、第１抽出行列生成部１７３は、行列T1=τ1・τ1T（αTは転置ベクトル）生成し、出力する（第１抽出行列生成過程）。また、第２抽出行列生成部１７４にベクトルτ2が入力され、第２抽出行列生成部１７４が、行列T2=τ2・τ2Tを生成し、出力する（第２抽出行列生成過程／ステップＳ８３）。
【００７２】
その後、第１部分行列抽出部１７５に、行列T1と行列K1とが入力され、第１部分行列抽出部１７５は、行列K1から、行列T1の行列成分が１である行−列の要素のみを取り出した部分行列K11を生成し、出力する（第１部分行列抽出過程／ステップＳ８４）。例えば、このように行列K1から取り出した要素の行と列とをつめたものを部分行列K11とする。同様に、第２部分行列抽出部１７６に、行列T2と行列K1とが入力され、第２部分行列抽出部１７６は、行列K1から、行列T2の行列成分が１である行−列の要素のみを取り出した部分行列K12を生成し、出力する（第２部分行列抽出過程／ステップＳ８５）。同様に、第３部分行列抽出部１７７に、行列T1と行列K2とが入力され、第３部分行列抽出部１７７は、行列K2から、行列T1の行列成分が１である行−列の要素のみを取り出した部分行列K12を生成し、出力する（第３部分行列抽出過程／ステップＳ８６）。同様に、第４部分行列抽出部１７８に、行列T2と行列K2とが入力され、第４部分行列抽出部１７８は、行列K2から、行列T2の行列成分が１である行−列の要素のみを取り出した部分行列K22を生成し、出力する（第４部分行列抽出過程／ステップＳ８７）（［ステップＳ１８（処理４）の詳細］の説明終わり）。
【００７３】
次に、ブロック分割部１７９（図４）に、ブロック対角行列A1が入力され、ブロック分割部１７９は、ブロック対角行列A1の対角ブロックのdt×dtのユニタリ行列を部分行列BA1,BA2,...,BAhとして取り出し、出力する（ステップＳ１９）。そして、行列リスト更新部１７０は、リストL’の要素として [[K11,K12], BA1,BA2,...,BAh, [K21,K22]]を出力する（ステップＳ２０）（［行列分解過程／ステップＳ５（処理１）の詳細］の説明終わり）。
【００７４】
ステップＳ５の処理が終了すると（図６に戻る）、次に、制御部１８０は、リストL’にサイズがdt×dtよりも大きな行列が含まれるか否かを判断する（ステップＳ６）。ここで、リストL’にサイズがdt×dtよりも大きな行列が含まれると判断された場合には、処理がステップＳ４に戻される。一方、リストL’にサイズがdt×dtよりも大きな行列が含まれないと判断された場合には、リストLにリストL’に含まれる部分行列を追加し、これらの部分行列に対応する行列GをリストLの要素から排除する（ステップＳ７）。
【００７５】
次に、制御部１８０は、リストLにd×dよりも大きな行列が含まれるか否かを判断する（ステップＳ８）。リストLにd×dよりも大きな行列が含まれると判断された場合には、処理設定部１４０のパラメータ設定部１４１がfloor(t/2)を新たなtとし、処理がステップＳ３に戻される（ステップＳ９）。一方、リストLにd×dよりも大きな行列が含まれないと判断された場合には、処理を終了する。
【００７６】
＜実施例＞
次に、d=3,n=2の場合の本形態の実施例を説明する。
【００７７】
本実施例では、入力行列を
【００７８】
【数７】
0004758965.tif 000008
とする。
【００７９】
ステップＳ２（図６）では、t=1とされ、ステップＳ３では、3×3の対角行列σが生成される。ステップＳ４では、上記の行列がGとされ、ステップＳ５に属するステップＳ１１（図７）では、S=32-1=3となり、ステップＳ１２ではρ=(1,-1,1,1,-1,1,1,-1,1)となる。また、ステップＳ１３で行列X=ρ・G*・ρ・Gを計算すると、
【００８０】
【数８】
0004758965.tif 000009
となる。
【００８１】
次に、ステップＳ１４に属するステップＳ３１でXの固有値を求めると
(1,-1,1,-1,1,-1,1,-1,1)
となる。
【００８２】
ここで、固有値１に対する固有ベクトルは、
【００８３】
【数９】
0004758965.tif 000010
となり、固有値−１に対する固有ベクトルは、
【００８４】
【数１０】
0004758965.tif 000011
となる。
【００８５】
図８の処理に従って行列Pを計算すると、行列Ｐは、
【００８６】
【数１１】
0004758965.tif 000012
となる。
【００８７】
次に、ステップＳ１５で、B=P*・X・Pを計算すると、
B=diag(-1,-1,-1,-1,1,1,1,1)
となる。これをステップＳ１６で行列Yに書き換えると、
【００８８】
【数１２】
0004758965.tif 000013
となる。次に、ステップＳ１７でM＝P・Y・P*を計算すると、
【００８９】
【数１３】
0004758965.tif 000014
となる。さらに、K=G・M*を計算すると、
【００９０】
【数１４】
0004758965.tif 000015
となる。また、K1=K・Pを計算すると、
【００９１】
【数１５】
0004758965.tif 000016
となる。そして、ステップＳ１８で部分行列K11,K12，K21,K22を取り出すと、
【００９２】
【数１６】
0004758965.tif 000017
【００９３】
【数１７】
0004758965.tif 000018
ここで、3×3よりも大きな行列K11,K12については（ステップＳ８）、ステップＳ４に戻り、ρ=(1,-1,1,1,-1,1)（ステップＳ３）についてステップ４以降の処理を繰り返す。行列K12,K22については3×3行列なので繰り返しは行わない。
【００９４】
図１３は、本形態によって分割された行列を量子回路に変換した図である。ここで図１３（ａ）は、dが奇数の場合の例であり、図１３（ｂ）はdが偶数の場合の例である。このように、dが奇数が偶数かによってゲートの形が変化する。
【００９５】
図１４は、d=2,n=5の場合に本形態を適用して分解された行列に対応する量子回路を示した図である。また、図１５は、d=3,n=5の場合に本形態を適用して分解された行列に対応する量子回路を示した図である。いずれも、分解のたびに分解対象となる行列に対応する量子ビットの数が約半分にできていることが分かる。
【００９６】
〔第２実施形態〕
次に、本発明の第２実施形態について説明する。
【００９７】
本形態は、コサインサイン（cosine-sin）分解を利用して行列分解過程を実行する形態である。
【００９８】
すなわち、本形態の行列分解過程では、まず、dm×dmの行列Gを、q×qのブロックG11と、q×pのブロックG12と、p×qのブロックG21と、p×pのブロックG22とに分割してコサインサイン分解を行い、行列Gを、４つの対角行列D11,D12,D21,D22と単位行列とを要素に含む行列Dと、行列K1,K2∈K(dm)と、の積G=K1・D・K2に分解する（コサインサイン分解過程）。なお、c1, c2, tを実数とし、c1+c2=dtとし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とし、p×pの特殊ユニタリ行列の集合SU(p)とq×qの特殊ユニタリ行列の集合SU(q)との直和からなる行列の集合をK(dm)とする。次に、４つの対角行列D11,D12,D21,D22の各対角成分D11[j,j],D12[j,j],D21[j,j],D22[j,j]を要素とする2×2の行列Rjを生成し、当該行列Rjを出力する（ブロック抽出過程）。ここで、dが偶数である場合には、重複しないようにd/2個選択された行列Rjをブロックとしたd×dのブロック対角行列と、2×2の単位行列と、をブロックとするブロック対角行列A1を生成し、dが奇数である場合には、ηをdt/2以下の最大の整数とした場合におけるη個の上記行列Riと１つの１とを対角成分に配置したdt×dtのブロック対角行列をブロックとするブロック対角行列A1を生成する（ブロック対角化過程）。
【００９９】
ここで本形態ではp=c1・dm-t<(d-1)・dm-1としているため、１回の分解で分割される行列のサイズは、p=(d-1)・dm-1としていた従来手法２よりも小さい。これにより、行列を分解するための再帰的処理の回数を削減でき、最終的に分解される行列の数も減らすことができる。また、ブロック対角化過程では、dが奇数である場合に、ηをdt/2以下の最大の整数とした場合におけるη個の上記行列Riと１つの１とを対角成分に配置したdt×dtのブロック対角行列をブロックとするブロック対角行列A1を生成することとしたため、量子ｄ準位系の量子コンピュータの量子回路に容易に変換可能な行列に分解できる。
【０１００】
なお、第２実施形態の行列分解過程は、サイズがdm×dm(m≧2,d≧3)の行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1との積G=K1・A1・K2に分解するものであり、c1, c2, tを実数とし、c1+c2=dtとし、pをp=c1・dm-t<(d-1)・dm-1を満たす整数とし、qをq=c2・dm-t≦p, 2・q≦dmを満たす整数とした場合に広く適用可能なものである。しかし、以下では、説明の簡略化のため、tをm/2以下の最大の整数とし、c1をdt/2以上の最小の整数とし、c2をdt/2以下の最大の整数とした場合を例にとって説明する。また、第１実施形態と共通する事項については説明を省略する。
【０１０１】
＜ハードウェア構成＞
第１実施形態と同じであるため説明を省略する。
【０１０２】
＜ハードウェアとソフトウェアとの協働＞
本形態のユニタリ行列分解装置もＣＰＵにユニタリ行列分解プログラムが読み込まれることによって構成されるものである。
【０１０３】
図１６，１７は、このようにＣＰＵ１１０にユニタリ行列分解プログラムが読み込まれることにより本形態のユニタリ行列分解装置２００の機能構成を例示したブロック図である。ここで、図１６は、第２実施形態のユニタリ行列分解装置２００の全体構成を示したブロック図であり、図１７（ａ）は、図１６の処理設定部２４０の詳細構成を示したブロック図であり、図１７（ｂ）は、図１６の行列分解部２５０の詳細構成を示したブロック図である。なお、これらの図において、第１実施形態と共通する部分については、第１実施形態と同じ符号を付した。
【０１０４】
図１６に示すように、本形態のユニタリ行列分解装置２００は、入力部１１０と、出力部１２０と、記憶部１３０と、処理設定部２４０と、行列分解部２５０と、行列リスト更新部２７０と、制御部１８０と、一時記憶部１９０とを有する。また、図１７（ａ）に示すように、本形態の処理設定部２４０は、パラメータ設定部２４１と行列読み出し部２４２とを有する。また、図１７（ｂ）に示すように、本形態の行列分解部２５０は、コサインサイン分解部２５１と、ブロック抽出部２５２と、ブロック対角化部２５３とを有する。また、コサインサイン分解部２５１は、パラメータ設定部２５１ａと、ブロック分割部２５１ｂと、特異値分割部２５１ｃと、アークコサイン部２５１ｄと、ブロック算出部２５１ｄ，２５１ｅとを有する。
【０１０５】
なお、処理設定部２４０、行列分解部２５０、行列リスト更新部２７０は、ユニタリ行列分解プログラムがＣＰＵに読み込まれることにより構成されるものである。
【０１０６】
＜処理＞
次に本形態におけるユニタリ行列分解装置２００の処理について説明する。
【０１０７】
図１８は本形態におけるユニタリ行列分解装置２００の処理の全体を説明するためのフローチャートである。
【０１０８】
まず、入力部１１０（図１６）に、分割対象のdn×dn(d≧3，n≧2)の特殊ユニタリ行列G’∈SU(dn)が入力され、リストLの要素として記憶部１３０に格納される（ステップＳ１０１／行列格納過程）。また、この際、入力部１１０にd,nの値も入力されて記憶部１３０に格納される。
【０１０９】
次に、処理設定部２４０のパラメータ更新部２４１（図１７（ａ））が、記憶部１３０からnを読み込み、t=ceil(n/2)によってtを求めて出力する（ステップＳ１０２）。パラメータ更新部２４１から出力されたtは行列読み出し部２４２に送られ、行列読み出し部２４２は、記憶部１３０に格納されたリストLの要素からサイズがdm-t×dm-t（なお、最初のループではm=nである）よりも大きな行列を読み出し、それを行列Gとする（処理設定過程／ステップＳ１０４）。また、行列Gのサイズをdm×dmとしてmの値を更新する。
【０１１０】
次に、行列Gとdとtとmとが行列分解部２５０に入力され、行列分解部２５０は、これらを用い、行列Gを、行列K1,K2∈K(dm)と、dr×dr(r≧1)のユニタリ行列をブロックとするブロック対角行列A1と、の積G=K1・A1・K2に分解し、その分解された行列のリストであるリストL’を出力する（行列分解過程／ステップＳ１０４）。以下、行列分解過程／ステップＳ１０５（処理１１）の詳細を説明する。
【０１１１】
［行列分解過程／ステップＳ１０４の詳細（処理１１）］
図１９は、本形態の行列分解過程／ステップＳ１０４の詳細（処理１１）の詳細を説明するためのフローチャートである。
【０１１２】
まず、コサインサイン分解部２５１（図１７）が、dm×dmの行列Gを、q×qのブロックG11と、q×pのブロックG12と、p×qのブロックG21と、p×pのブロックG22とに分割してコサインサイン分解を行い、行列Gを、４つの対角行列D11,D12,D21,D22と単位行列とを要素に含む行列Dと、行列K1,K2∈K(dm)と、の積G=K1・D・K2に分解する（コサインサイン分解過程／ステップＳ１１１（処理１２））。ここで、コサインサイン分解過程／ステップＳ１１１（処理１２）を説明する。
【０１１３】
［コサインサイン分解過程／ステップＳ１１１（処理１２）の詳細］
図２０は、図１９のステップＳ１１１の詳細を説明するためのフローチャートである。
【０１１４】
まず、サインサイン分解部２５１のパラメータ設定部２５１ａ（図１７）にt,d,mが入力され、パラメータ設定部２５１ａは、q=dn-t・floor(dt/2) によってqを算出して出力する（ステップＳ１２１）。次に、ブロック分割部２５１ｂにq,G,mが入力され、ブロック分割部２５１ｂは、これらの情報を用い、行列Gを
【０１１５】
【数１８】
0004758965.tif 000019
ブロックG11: q×q
ブロックG12: q×(dn-q)
ブロックG21:(dn-q)×q
ブロックG22:(dn-q)×(dn-q)
のサイズで４分割し、ブロックG11, G12, G21, G22を出力する（ステップＳ１２２）。
【０１１６】
次に、特異値分割部２５１ｃにブロックG11が入力され、特異値分割部２５１ｃは、G11=K11・D11・K21の特異値分解を行い、分割されたK11, D11, K21を出力する。なお、D11 =diag (d1, d2, …, dq )は、1＞d1≧d2≧d3≧…≧dq＞0 を満たすものとする。なお、特異値分割については「伊理正夫：岩波講座  応用数学『線形代数ＩＩ』，pp.251-253,岩波書店,1994.」「島内剛一，有澤誠，野下造平，浜田穂積，伏見正則：『アルゴリズム辞典』，p.564，共立出版，1994.」等参照。
【０１１７】
さらに、分割されたD11を用いてD22 = D11を求め、出力する（ステップＳ１２３）。次に、アークコサイン部２５１ｄにD11が入力され、アークコサイン部２５１ｄは、D11= diag(d1, d2, …, dJ )について、角度φk = arccos dk； (0≦φk＜π,  k =1,2,…,q) を求め、出力する（ステップＳ１２４）。これらの角度φkは、ブロック算出部２５１ｄに入力され、ブロック算出部２５１ｄは、φk (k = 1, 2,…, q)より、D12= diag(sinφ1, sinφ2, …, sinφq)を算出し、さらに、D21=-D12を求め、これらを出力する（ステップＳ１２５）。次に、ブロック算出部２５１ｅにG11, G12, K11, D11, D12が入力され、ブロック算出部２５１ｅは、K22 =D12*・ K11*・ G12 及びK12 =G21・D21* によってK22, K12を算出し、出力する（ステップＳ１２６）。そして、コサインサイン分解部２５１は、リストL’の要素としてK12, K12, D11, D12, D21, D22, K21, K22を出力する（ステップＳ１２７）（［コサインサイン分解過程／ステップＳ１１１（処理１２）の詳細］の説明終わり）。
【０１１８】
次に、ブロック抽出部２５２にD11, D12, D21, D22が入力され、ブロック抽出部２５２は、４つの対角行列D11,D12,D21,D22の各j行j列目の対角成分D11[j,j],D12[j,j],D21[j,j],D22[j,j]を要素とする2×2の行列Rjを
【０１１９】
【数１９】
0004758965.tif 000020
と生成し、当該行列Rjを出力する（ブロック抽出過程／ステップＳ１１２）。
【０１２０】
行列Rjはブロック対角化部２５３に入力される。また、ブロック対角化部２５３には、dも入力され、ブロック対角化部２５３は、dが偶数であるか否かを判断する（ステップＳ１１３）。ここで、ｄが偶数であれば、ブロック対角化部２５３は、重複しないようにd/2個選択された行列Rjをブロックとしたd×dのブロック対角行列と、2×2の単位行列と、をブロックとするブロック対角行列A1を生成する。すなわち、
【０１２１】
【数２０】
0004758965.tif 000021
（なお、ζ>dm-tのときは、行列Rζを2×2の単位行列として式（８）の演算を行う）
をブロックとするブロック対角行列A1を生成する(ブロック対角化過程／ステップＳ１１４)。
【０１２２】
一方、dが奇数である場合には、ブロック対角化部２５３は、ηをdt/2以下の最大の整数とした場合におけるη個の上記行列Riと１つの１とを対角成分に配置したdt×dtのブロック対角行列をブロックとするブロック対角行列A1を生成する。例えば、bi = diag (R(i-1)・η+1, R(i-1)・η+2,…, R(i-1)・η+η, 1）とする (ブロック対角化過程／ステップＳ１１５)。そして、ブロック対角化部２５３は、リストL’におけるDに対応する要素を、生成した対角行列A1の対角ブロック[b1, b2,...,bs]で置き換える。なお、リストL’にDに対応する要素がなければ、生成した対角行列A1の対角ブロック[b1, b2,...,bs]をリストL’に追加する。なお、dが偶数ならs=d・(m-1)であり、奇数ならs=dm-tである（ステップＳ１１６）。図２１に、このような方法によって行列が分解された様子を示す。また、図２２は、このように分割された行列を量子回路に変換した図である。ここで図２２（ａ）は、dが奇数の場合の例であり、図２２（ｂ）はdが偶数の場合の例である。このように、dが奇数が偶数かによってゲートの形が変化する（［コサインサイン分解過程／ステップＳ１１１（処理１２）の詳細］の説明終わり）。
【０１２３】
ステップＳ１１６の処理が終了すると（図１８に戻る）、次に、制御部１８０は、リストL’にサイズがdt×dtよりも大きな行列が含まれるか否かを判断する（ステップＳ１０６）。ここで、リストL’にサイズがdt×dtよりも大きな行列が含まれると判断された場合には、処理がステップＳ１０４に戻される。一方、リストL’にサイズがdt×dtよりも大きな行列が含まれないと判断された場合には、リストLに含まれる行列Gに対応する要素を、リストL’に含まれる要素で置き換える（ステップＳ１０７）。
【０１２４】
次に、制御部１８０は、リストLにd×dよりも大きな行列が含まれるか否かを判断する（ステップＳ１０８）。リストLにd×dよりも大きな行列が含まれると判断された場合には、処理設定部２４０のパラメータ設定部２４１がceil(t/2)を新たなtとし、処理がステップＳ１０４に戻される（ステップＳ１０９）。一方、リストLにd×dよりも大きな行列が含まれないと判断された場合には、処理を終了する。
【０１２５】
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１２６】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１２７】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【０１２８】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１２９】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１３０】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１３１】
本発明の産業上の利用分野としては、量子コンピュータの量子コンパイラ分野を例示できる。本発明を適用することにより、容易に任意のユニタリ変換量子回路を量子コンピュータの実行命令に適したゲートに分解することができる。
【図面の簡単な説明】
【０１３２】
【図１】図１は、第１実施形態のユニタリ行列分解装置の全体構成を示したブロック図である。
【図２】図２は、図１の行列分解部の詳細構成を示したブロック図である。
【図３】図３（ａ）は、図２の対角化行列生成部の詳細構成を示したブロック図であり、図３（ｂ）は、図１の処理設定部の詳細構成を示したブロック図である。
【図４】図４は、図１の行列リスト更新部の詳細構成を示したブロック図である。
【図５】図５は、第１実施形態におけるユニタリ行列分解装置の構成を例示したブロック図である。
【図６】図６は、第２実施形態におけるユニタリ行列分解装置の処理の全体を説明するためのフローチャートである。
【図７】図７は、行列分解過程／ステップＳ５（処理１）の詳細を説明するためのフローチャートである。
【図８】図８は、対角化行列生成過程／ステップＳ１４の詳細を例示するためのフローチャートである。
【図９】また、図９は図８におけるステップＳ３２の詳細を説明するためのフローチャートである。
【図１０】図１０は図８におけるステップＳ３３の詳細を説明するためのフローチャートである。
【図１１】図１１は、ブロック対角行列変換過程／ステップＳ１６（処理３）の詳細を説明するためのフローチャートである。
【図１２】図１２は、ステップＳ１８（処理４）の詳細を説明するためのフローチャートである。
【図１３】図１３は、第１実施形態によって分割された行列を量子回路に変換した図である。ここで図１３（ａ）は、dが奇数の場合の例であり、図１３（ｂ）はdが偶数の場合の例である。
【図１４】図１４は、d=2,n=5の場合に第１実施形態を適用して分解された行列に対応する量子回路を示した図である。
【図１５】図１５は、d=3,n=5の場合に第１実施形態を適用して分解された行列に対応する量子回路を示した図である。
【図１６】図１６は、第２実施形態のユニタリ行列分解装置の全体構成を示したブロック図である。
【図１７】図１７（ａ）は、図１６の処理設定部の詳細構成を示したブロック図であり、図１７（ｂ）は、図１６の行列分解部の詳細構成を示したブロック図である。
【図１８】図１８は第２実施形態におけるユニタリ行列分解装置の処理の全体を説明するためのフローチャートである。
【図１９】図１９は、第２実施形態の行列分解過程／ステップＳ１０４の詳細（処理１１）の詳細を説明するためのフローチャートである。
【図２０】図２０は、図１９のステップＳ１１１の詳細を説明するためのフローチャートである。
【図２１】図２１は、第２実施形態の方法によって行列が分解された様子を例示した図である。
【図２２】図２２は、第２実施形態の方法によって分割された行列を量子回路に変換した図である。ここで図２２（ａ）は、dが奇数の場合の例であり、図２２（ｂ）はdが偶数の場合の例である。
【図２３】図２３（ａ）は、従来手法１による行列分解の様子を示した図である。図２３（ｂ）は、それに対応する量子回路を示した図である。
【図２４】図２４（ａ）は、従来手法２による行列分解の様子を示した図である。図２４（ｂ）は、それに対応する量子回路を示した図である。
【図２５】図２５は、従来手法２によって分解された行列に対応する量子回路を示した図である。
【符号の説明】
【０１３３】
１００，２００  ユニタリ行列分解装置
【図１】
0004758965.tif 000026
【図２】
0004758965.tif 000027
【図３】
0004758965.tif 000028
【図４】
0004758965.tif 000029
【図５】
0004758965.tif 000030
【図６】
0004758965.tif 000031
【図７】
0004758965.tif 000032
【図８】
0004758965.tif 000033
【図９】
0004758965.tif 000034
【図１０】
0004758965.tif 000035
【図１１】
0004758965.tif 000036
【図１２】
0004758965.tif 000037
【図１３】
0004758965.tif 000038
【図１４】
0004758965.tif 000039
【図１５】
0004758965.tif 000040
【図１６】
0004758965.tif 000041
【図１７】
0004758965.tif 000042
【図１８】
0004758965.tif 000043
【図１９】
0004758965.tif 000044
【図２０】
0004758965.tif 000045
【図２１】
0004758965.tif 000046
【図２２】
0004758965.tif 000047
【図２３】
0004758965.tif 000048
【図２４】
0004758965.tif 000049
【図２５】
0004758965.tif 000050