(57)【要約】【課題】対称群Sn上のフーリエ変換FTnを実行するための技術を提供する。【解決手段】FTm-1,Tm,Hm,Imに基づいてFTm=TmHm(FTm-1(×)Im)を計算する処理をm=1,2,…,nの各整数について順次行うことにより、フーリエ変換FTnを計算する。そこで、Hmについて、Hm=AmPmH’’m-1Kmと分解する。Am,Pm,H’’m-1,Kmのそれぞれは比較的簡単に実行することができる演算である。このように分解を行うことにより、フーリエ変換をより効率的に行うことができる。【選択図】図１４
2014203182.tif 000002
【特許請求の範囲】
【請求項１】
nを3以上の予め定められた整数とし、対称群Sn上の高速フーリエ変換FTnを実行する方法であって、
(×)をテンソル積とし、kを所定の正の整数とし、Ikをk×kの単位行列として、FTm-1,Tm,Hm,Imに基づいてFTm=TmHm(FTm-1(×)Im)を計算する処理をm=1,2,…,nの各整数について順次行うことにより、FTnを計算する計算ステップを含み、
FT2は以下の行列であり、
【数７３】
2014203182.tif 000075
Hm=AmPmH’’m-1Kmであり、
(+)を直和とし、ρをブラテリダイアグラムにおける任意の既約表現とし、dρをρの表現空間の次元数とし、λ↓μはブラテリダイアグラムにおいて既約表現λが既約表現μの親ノードであることを表すとし、ν↓λはブラテリダイアグラムにおいて既約表現νが既約表現λの親ノードであることを表すとし、Λm-1をm-1の既約表現の集合とし、rを正の整数とし、[μ(c(m-1,m))]qμ,ν,qμ,νを巡回置換c(m-1,m)に対応するμによる既約表現μ(c(m-1,m))に至るルートノードからのパスに基づいて定まる値とし、x,yを任意の既約表現とし、|x,y>をx,yに基づいて定まるベクトルとし、<x,y|を|x,y>の転置として、Amは以下の式により定義される行列であり、
【数７４】
2014203182.tif 000076
aを任意の既約表現とし、b,cのそれぞれをaに至るパスとし、dを0以上の整数とし、|a,b,c,d>をa,b,c,dに基づいて定まるベクトルとし、hλ,q,r,i,jを以下の式により定まる値とし、
【数７５】
2014203182.tif 000077
H’’m-1は以下の式により定義される行列であり、
【数７６】
2014203182.tif 000078
Xを任意の行列としてX†をXの転置行列として、p’=(p1,p2,…,pm-1)とし、p’|m-2=(p1,p2,…,pm-2)とし、q=q’,p=p’|m-2,p∈P(λ)としたとき、|λ’,p’,q’>→|λ,p,q>へ基底を変換する行列をT†mとし、Tm=(T†m)†とし、
fm-1をHm-1をH’’m-1に変換する関数とし、Sm-1におけるadapted Gel’fand-Tsetlin basesでの行列表現をρm-1(g)とし、Smにおけるadapted Gel’fand-Tsetlin basesでの行列表現をρm(g)として、Pmfm-1(T†m-1ρm-1(g)Tm-1)P†mとT†mρm(g)Tmの類似度が最大となるようにT†mρm(g)Tmの基底を変換する行列をPmとし、
λ(c(j,j+1,…,m-1))を巡回置換c(j,j+1,…,m-1)に対応するλによる既約表現とし、|j>をj番目の成分が1であり他の成分が0であるベクトルとし、<j|を|j>の転置とし、Kmは以下の式により定義される行列である、
【数７７】
2014203182.tif 000079
フーリエ変換計算方法。
【請求項２】
入力状態|i>=|i1,i2,・・・,in-1>に対して対称群上の量子フーリエ変換FTnを適用する量子回路であって、
入力状態|i1>を入力レジスタとして、第１出力レジスタと第２出力レジスタと第３出力レジスタとからなる出力状態を出力するゲートであるH2ゲートと、
直前のゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとし、入力状態|im>を第４レジスタとし、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するHmゲートと、Hmゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとして、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するTmゲートと、がm=3,4,・・・,nの順番で配置されたゲートと、を含み、
H2ゲートは、第１レジスタ|x>を入力レジスタとして、
(a-1) 第１入力レジスタ|x>に対するHadamardゲートと、
(a-2) 第１補助レジスタ|0>を導入して、上記第１入力レジスタを制御ビットとし、第１補助レジスタ|0>を標的ビットとする制御ＮＯＴゲートと、
(a-3) 第２補助レジスタ|a1>（|a1>の初期値を|0>とする。）を導入して、前記第１入力レジスタを制御ビットとし、制御ビットが|1>のときに第２補助レジスタ|a1>の状態を|a1+1 mоd t>（ただしtは|a1>の取りうる量子状態の基底の総数）に変換するゲートと、
(a-4) 第３補助レジスタ|a2>を導入し、前記第１入力レジスタを制御ビットとし、制御ビットが|0>のときに第３補助レジスタ|a2>（|a2>の初期値を|1>とする。）の状態を|a2+1 mоd t>（ただしtは|a2>の取りうる量子状態の基底の総数）に変換するゲートと、
を含み、上記(a-1)〜(a-4)を適用した後の前記第３補助レジスタと前記第２補助レジスタからなるレジスタを第１出力レジスタ、前記第１補助レジスタを第２出力レジスタ、上記第１入力レジスタを第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Hmゲートは、第１レジスタ|λ>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-2>と、第４レジスタ|x>とを入力レジスタとして、
(b-1) 第４レジスタ|x>を制御ビットとし、第１、第２、第３レジスタを標的ビットとして、制御ビットの状態がα(α=0,1,・・・,m-1)のとき標的ビットにλ(c(α,α+1,・・・,m-1))を適用するゲートと、
(b-2) 第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートと、
(b-3) |i>を|i-1 mоd m>に変換する操作を第４レジスタ|x>に適用するゲートと、
(b-4) 第１レジスタ|λ>、第２レジスタの|p1,・・・,pm-3>、第３レジスタの|q1,・・・,qm-3>、第４レジスタ|x>に対して適用されるHm-1ゲートと、
(b-5) |i>を|i+1 mоd m>に変換する操作を第４レジスタ|x>に適用するゲートと、
(b-6) 第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートと、
(b-7) 第１レジスタから第４レジスタに、Pmfm-1(T†m-1ρm-1(g)Tm-1)P†mの行と列の入れ替えに対応する量子ビットの交換操作Pmに対応する操作を適用するゲートと、
(b-8) 第１レジスタ|λ>を制御ビットとし、第３レジスタ|qm-2>を標的ビットとし、(+)を直和とし、ρをブラテリダイアグラムにおける任意の既約表現とし、dρをρの表現空間の次元数とし、λ↓μはブラテリダイアグラムにおいて既約表現λが既約表現μの親ノードであることを表すとし、ν↓λはブラテリダイアグラムにおいて既約表現νが既約表現λの親ノードであることを表すとし、Λm-1をm-1の既約表現の集合とし、rを正の整数とし、[μ(c(m-1,m))]qμ,ν,qμ,νを巡回置換c(m-1,m)に対応するμによる既約表現μ(c(m-1,m))に至るルートノードからのパスに基づいて定まる値とし、x,yを任意の既約表現とし、|x,y>をx,yに基づいて定まるベクトルとし、<x,y|を|x,y>の転置として、以下の式により定義されるA’m,λに対応する操作を適用するゲートと、
【数７８】
2014203182.tif 000080
を含み、上記(b-1)から(b-8)を適用した後の、第１レジスタを第１出力レジスタ、第２レジスタを第２出力レジスタ、第３レジスタと第４レジスタを合わせたレジスタを第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Tmゲートは、第１レジスタ|λ>=|λ1,・・・,λm-2>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-1>とを入力レジスタとして、
(c-1) 第２レジスタ|p>と第３レジスタ|q>を制御ビットとして、新たに導入した第１補助レジスタ|0>を
【数７９】
2014203182.tif 000081
に変換する演算を適用するTm,1ゲートと、
(c-2) 第３レジスタの|qm-1>を制御ビットとし、Tmゲートの第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>（|λm-1>の初期値を|0>とする。）を標的ビットとするTm,2ゲートと、
を含み、Tm,1ゲート及びTm,2ゲートを適用した後の、第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>を第１出力レジスタ、第２レジスタ|p>=|p1,・・・,pm-1>及び制御ビットを第２出力レジスタ、第３レジスタ|q>=|q1,・・・,qm-1>を第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Tm,2ゲートは、制御ビットを|c1>とし、標的ビットを|λ>=|λ1,・・・,λm-2>としたとき、制御ビットの状態がｊのときに標的ビット|λj>（ただし|λm-1>は第２補助レジスタ|c2>を導入し第２補助レジスタで代用する）を|λj+1 mоd t>（ただしｔは|λj>の取りうる量子状態の基底の総数）に変換するゲートである、
ことを特徴とする量子回路。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、古典コンピュータ及び量子コンピュータのそれぞれで対称群上のフーリエ変換を多項式時間で実行する技術に関する。
【背景技術】
【０００２】
グラフ同型性判定問題とは、２つのグラフが与えられたときに、それらのグラフの頂点間の写像で、辺を保存するものが存在するかどうかを判定する問題である。例えば、図２３の例では、G1とG2は同型だが、それらとG3は同型ではない。グラフ同型性判定問題は、パターンマッチングの一種であり、高速なアルゴリズムが見つかればその応用範囲はきわめて広い。しかしながら、グラフ同型性判定問題を現在のコンピュータ上で解くための高速なアルゴリズムは見つかっていない。
【０００３】
現在のコンピュータ上で解くことが困難とされている因数分解を、量子コンピュータ上で高速に行うことができるアルゴリズムとして、ショーアのアルゴリズムが知られている。ショーアのアルゴリズムにおけるZn上の量子フーリエ変換を対称群Sn上の量子フーリエ変換で置き換えると、グラフ同型性判定問題に拡張することができる。そのため、対称群Sn上の量子フーリエ変換を高速に実行できるアルゴリズムは、グラフ同型性判定問題を量子コンピュータ上で高速に解くためのアルゴリズムを構成する上で重要な役割を果たすことが期待されている。ここで対称群Snとは、与えられた自然数nに対して、n個の(異なる)文字の集合からそれ自身への一対一対応全体を表す。n個の文字に1,2,…,nという数字を割り当てれば、{1,2,…,n−1,n}の置換によって作られる群である。Snはn!個の元をもち、置換の積を群の演算とみなす。
【０００４】
対称群Sn上の高速フーリエ変換は、
【０００５】
【数１】
2014203182.tif 000003
【０００６】
と表せることが知られている（例えば、非特許文献１参照。）。
【０００７】
また、非特許文献２では、上記対称群Sn上の高速フーリエ変換のTnHn=Fnと表したときの、Fnの行列に対応する量子回路の具体的な構成法が提案されている。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】P.DIACONIS, D.ROCKMORE, “EFFICIENT COMPUTATION OF THE FOURIER TRANSFORM ON FINITE GROUPS”, JOUNAL OF THE AMERICAN MATHEMATICAL SOCIETY, Volume 3, Number 2, April 1990, P.297-332
【非特許文献２】Yasuhito Kawano, Hiroshi Sekigawa, “Algorithm for QFT Circuits on Symmetric Groups”, 11th Asian Quatnum Infromation Science conference(AQIS2011), 2011
【発明の概要】
【発明が解決しようとする課題】
【０００９】
しかしながら、非特許文献１の高速フーリエ変換における行列Hnはブロック対角行列であるが、各ブロックのサイズがｎに対して指数関数的に増大するものであり、非常に大きな行列である。そのため、古典コンピュータ上でこの行列の乗算を実行するのは非常にコストがかかる。
【００１０】
非特許文献２では、行列Fi(i=2,3,…,n)がブロック対角行列で表せるので、量子回路に変換可能であることが示されている。しかし、非特許文献１と同様にFiの大きさはiの値に応じて指数関数的に大きくなるので、単純にFiのブロック対角行列を量子回路に置き換える非特許文献２の手法では、効率の悪い量子回路になってしまう。なお、非特許文献２では、行列FiをGiと表記している点に注意すること。
【００１１】
この発明の目的は、非特許文献１よりも演算コストの小さなフーリエ変換計算方法、及び、これを用いた非特許文献２よりも効率的な量子回路を提案することである。
【課題を解決するための手段】
【００１２】
この発明の一態様によるフーリエ変換計算方法は、nを3以上の予め定められた整数とし、対称群Sn上の高速フーリエ変換FTnを実行する方法であって、
(×)をテンソル積とし、kを所定の正の整数とし、Ikをk×kの単位行列として、FTm-1,Tm,Hm,Imに基づいてFTm=TmHm(FTm-1(×)Im)を計算する処理をm=1,2,…,nの各整数について順次行うことにより、FTnを計算する計算ステップを含み、
FT2は以下の行列であり、
【００１３】
【数２】
2014203182.tif 000004
【００１４】
Hm=AmPmH’’m-1Kmであり、
(+)を直和とし、ρをブラテリダイアグラムにおける任意の既約表現とし、dρをρの表現空間の次元数とし、λ↓μはブラテリダイアグラムにおいて既約表現λが既約表現μの親ノードであることを表すとし、ν↓λはブラテリダイアグラムにおいて既約表現νが既約表現λの親ノードであることを表すとし、Λm-1をm-1の既約表現の集合とし、rを正の整数とし、[μ(c(m-1,m))]qμ,ν,qμ,νを巡回置換c(m-1,m)に対応するμによる既約表現μ(c(m-1,m))に至るルートノードからのパスに基づいて定まる値とし、x,yを任意の既約表現とし、|x,y>をx,yに基づいて定まるベクトルとし、<x,y|を|x,y>の転置として、Amは以下の式により定義される行列であり、
【００１５】
【数３】
2014203182.tif 000005
【００１６】
aを任意の既約表現とし、b,cのそれぞれをaに至るパスとし、dを0以上の整数とし、|a,b,c,d>をa,b,c,dに基づいて定まるベクトルとし、hλ,q,r,i,jを以下の式により定まる値とし、
【００１７】
【数４】
2014203182.tif 000006
【００１８】
H’’m-1は以下の式により定義される行列であり、
【００１９】
【数５】
2014203182.tif 000007
【００２０】
Xを任意の行列としてX†をXの転置行列として、p’=(p1,p2,…,pm-1)とし、p’|m-2=(p1,p2,…,pm-2)とし、q=q’,p=p’|m-2,p∈P(λ)としたとき、|λ’,p’,q’>→|λ,p,q>へ基底を変換する行列をT†mとし、Tm=(T†m)†とし、
fm-1をHm-1をH’’m-1に変換する関数とし、Sm-1におけるadapted Gel’fand-Tsetlin basesでの行列表現をρm-1(g)とし、Smにおけるadapted Gel’fand-Tsetlin basesでの行列表現をρm(g)として、Pmfm-1(T†m-1ρm-1(g)Tm-1)P†mとT†mρm(g)Tmの類似度が最大となるようにT†mρm(g)Tmの基底を変換する行列をPmとし、
λ(c(j,j+1,…,m-1))を巡回置換c(j,j+1,…,m-1)に対応するλによる既約表現とし、|j>をj番目の成分が1であり他の成分が0であるベクトルとし、<j|を|j>の転置とし、Kmは以下の式により定義される行列である。
【００２１】
【数６】
2014203182.tif 000008
【００２２】
この発明の一態様による量子回路は、入力状態|i>=|i1,i2,・・・,in-1>に対して対称群上の量子フーリエ変換FTnを適用する量子回路であって、
入力状態|i1>を入力レジスタとして、第１出力レジスタと第２出力レジスタと第３出力レジスタとからなる出力状態を出力するゲートであるH2ゲートと、
直前のゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとし、入力状態|im>を第４レジスタとし、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するHmゲートと、Hmゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとして、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するTmゲートと、がm=3,4,・・・,nの順番で配置されたゲートと、を含み、
H2ゲートは、第１レジスタ|x>を入力レジスタとして、
(a-1) 第１入力レジスタ|x>に対するHadamardゲートと、
(a-2) 第１補助レジスタ|0>を導入して、上記第１入力レジスタを制御ビットとし、第１補助レジスタ|0>を標的ビットとする制御ＮＯＴゲートと、
(a-3) 第２補助レジスタ|a1>（|a1>の初期値を|0>とする。）を導入して、前記第１入力レジスタを制御ビットとし、制御ビットが|1>のときに第２補助レジスタ|a1>の状態を|a1+1 mоd t>（ただしtは|a1>の取りうる量子状態の基底の総数）に変換するゲートと、
(a-4) 第３補助レジスタ|a2>を導入し、前記第１入力レジスタを制御ビットとし、制御ビットが|0>のときに第３補助レジスタ|a2>（|a2>の初期値を|1>とする。）の状態を|a2+1 mоd t>（ただしtは|a2>の取りうる量子状態の基底の総数）に変換するゲートと、
を含み、上記(a-1)〜(a-4)を適用した後の前記第３補助レジスタと前記第２補助レジスタからなるレジスタを第１出力レジスタ、前記第１補助レジスタを第２出力レジスタ、上記第１入力レジスタを第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Hmゲートは、第１レジスタ|λ>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-2>と、第４レジスタ|x>とを入力レジスタとして、
(b-1) 第４レジスタ|x>を制御ビットとし、第１、第２、第３レジスタを標的ビットとして、制御ビットの状態がα(α=0,1,・・・,m-1)のとき標的ビットにλ(c(α,α+1,・・・,m-1))を適用するゲートと、
(b-2) 第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートと、
(b-3) |i>を|i-1 mоd m>に変換する操作を第４レジスタ|x>に適用するゲートと、
(b-4) 第１レジスタ|λ>、第２レジスタの|p1,・・・,pm-3>、第３レジスタの|q1,・・・,qm-3>、第４レジスタ|x>に対して適用されるHm-1ゲートと、
(b-5) |i>を|i+1 mоd m>に変換する操作を第４レジスタ|x>に適用するゲートと、
(b-6) 第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートと、
(b-7) 第１レジスタから第４レジスタに、Pmfm-1(T†m-1ρm-1(g)Tm-1)P†mの行と列の入れ替えに対応する量子ビットの交換操作Pmに対応する操作を適用するゲートと、
(b-8) 第１レジスタ|λ>を制御ビットとし、第３レジスタ|qm-2>を標的ビットとし、(+)を直和とし、ρをブラテリダイアグラムにおける任意の既約表現とし、dρをρの表現空間の次元数とし、λ↓μはブラテリダイアグラムにおいて既約表現λが既約表現μの親ノードであることを表すとし、ν↓λはブラテリダイアグラムにおいて既約表現νが既約表現λの親ノードであることを表すとし、Λm-1をm-1の既約表現の集合とし、rを正の整数とし、[μ(c(m-1,m))]qμ,ν,qμ,νを巡回置換c(m-1,m)に対応するμによる既約表現μ(c(m-1,m))に至るルートノードからのパスに基づいて定まる値とし、x,yを任意の既約表現とし、|x,y>をx,yに基づいて定まるベクトルとし、<x,y|を|x,y>の転置として、以下の式により定義されるA’m,λに対応する操作を適用するゲートと、
【００２３】
【数７】
2014203182.tif 000009
【００２４】
を含み、上記(b-1)から(b-8)を適用した後の、第１レジスタを第１出力レジスタ、第２レジスタを第２出力レジスタ、第３レジスタと第４レジスタを合わせたレジスタを第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Tmゲートは、第１レジスタ|λ>=|λ1,・・・,λm-2>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-1>とを入力レジスタとして、
(c-1) 第２レジスタ|p>と第３レジスタ|q>を制御ビットとして、新たに導入した第１補助レジスタ|0>を
【００２５】
【数８】
2014203182.tif 000010
【００２６】
に変換する演算を適用するTm,1ゲートと、
(c-2) 第３レジスタの|qm-1>を制御ビットとし、Tmゲートの第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>（|λm-1>の初期値を|0>とする。）を標的ビットとするTm,2ゲートと、
を含み、Tm,1ゲート及びTm,2ゲートを適用した後の、第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>を第１出力レジスタ、第２レジスタ|p>=|p1,・・・,pm-1>及び制御ビットを第２出力レジスタ、第３レジスタ|q>=|q1,・・・,qm-1>を第３出力レジスタとするゲートであり、
m=3,4,・・・,nの各整数として、Tm,2ゲートは、制御ビットを|c1>とし、標的ビットを|λ>=|λ1,・・・,λm-2>としたとき、制御ビットの状態がｊのときに標的ビット|λj>（ただし|λm-1>は第２補助レジスタ|c2>を導入し第２補助レジスタで代用する）を|λj+1 mоd t>（ただしｔは|λj>の取りうる量子状態の基底の総数）に変換するゲートである。
【発明の効果】
【００２７】
非特許文献１よりも小さな演算コストによりフーリエ変換を行うすることができる。また、非特許文献２よりも量子回路は効率的である。
【図面の簡単な説明】
【００２８】
【図１】ヤング図形を説明するための図。
【図２】ヤング盤を説明するための図。
【図３】標準ヤング図形を説明するための図。
【図４】ブラテリダイアグラムを説明するための図。
【図５】Tnを説明するための図。
【図６】Tnを説明するための図。
【図７】Hn-1のU(Cn!)への埋め込みを説明するための図。
【図８】Hn-1のU(Cn!)への埋め込みを説明するための図。
【図９】Pnを説明するための図。
【図１０】Vandermonde行列式を説明するための図。
【図１１】FTnを説明するための図。
【図１２】FTnを行うための量子回路を説明するための図。
【図１３】H2ゲートの例を説明するための図。
【図１４】Hｍゲートの例を説明するための図。
【図１５】量子回路の変形例を説明するための図。
【図１６】Tｍゲートの例を説明するための図。
【図１７】Pnの計算の例を説明するための図。
【図１８】パスを説明するための図。
【図１９】λ(c(m-1,m))の計算の例を説明するための図。
【図２０】マンハッタン距離を説明するための図。
【図２１】実施形態の量子回路生成装置の構成を説明するためのブロック図。
【図２２】実施形態の量子回路生成装置を説明するためのフローチャート。
【図２３】グラフ同型性判定問題を説明するための図。
【発明を実施するための形態】
【００２９】
まず、この発明を理解するための背景知識について説明する。
【００３０】
［対称群の基礎］
ｎを1以上の整数とし、集合{1,2,…,n}上の置換
【００３１】
【数９】
2014203182.tif 000011
【００３２】
の全体を考える。ちなみに、上記の置換は、1→i1,2→i2,…,n→inの意味である。連続的な置換を置換同士の積と定義する、すなわち、
【００３３】
【数１０】
2014203182.tif 000012
【００３４】
により積を定義することにより、集合{1,2,…,n}上の置換は非可換群となる。この非可換群をSnと表記し、対称群と呼ぶ。|Sn|（Snの要素数）はn!である。
【００３５】
Snの元で、
【００３６】
【数１１】
2014203182.tif 000013
【００３７】
（i1,i2,…,ik以外は不変）となるものを巡回置換と呼び、c(i1,i2,…,ik)又はi1→i2→…→ik→i1と略記する。k=2の場合、上記の巡回置換を互換と呼ぶ。Snの任意の元は互換の積に分解できる。この分解は一意ではないが、分解したときの互換の数の偶奇は一意的に定まる事が知られている。
【００３８】
Snの任意の元gに対して、
【００３９】
【数１２】
2014203182.tif 000014
【００４０】
となる（i1,i2,…,in-1）∈Z2×Z3×…Znが一意的に定まる。a,bを任意の正の整数として、c ib (i1,i2,…,ia)は、c(i1,i2,…,ia)をib回行う置換を意味する。このg→（i1,i2,…,in-1）の対応を標準コーディングと呼ぶことにする。標準コーディングは、後にSnの元を量子状態でコーディングするときに用いる。つまり、qubit,qutrit, …,qunitを用いて、Snの元gを|i1,i2,…,in-1>でコーディングする。
【００４１】
g→（i1,i2,…,in-1）を標準コーディングとする。i=Σj=1n-1ij・(n!/(j+1)!)とおき、gi=gと定義すると、gi(i=0,1,…,n!-1)はSnの列挙となる。すなわち、S={g0,g1,…,gn!-1}である。特にg0=identity,gn!/2=c(1,2)である。この順序は、後にフーリエ変換を行列で表記した時の列の順序として用いられる。ここで、identityとはg0が恒等変換であることを意味する。
【００４２】
［既約表現］
Vをベクトル空間とする。U(V)をVからVへのユニタリ変換の集合とし、U(V)の元の積をそれらの元による連続的な変換で定義することにより、U(V)は群となる。Vの正規直交基底ベクトルを定めると、U(V)の元はユニタリ行列で書ける。
【００４３】
適当なベクトル空間Vに対して、写像ρ:Sn→U(V)が群の演算と可換になるとき（つまり写像が準同型のとき）、ρを表現と呼び、Vを表現空間と呼ぶ。W⊆Vがρ(Sn)で不変になるとき、Wを不変部分空間と呼ぶ。V（空間全体）と{0}は明らかに不変なため、自明な不変部分空間と呼ばれる。不変部分空間として自明なものしか存在しないとき、ρを既約表現と呼ぶ。Snの既約表現の集合をΛnと表記する。
【００４４】
例えば、S3の元をg0=(1), g1=(1,2,3), g2=(1,3,2), g3=(1,2), g4=(2,3), g5=(1,3)と表記する。対称群は、全ての並べ替えの操作を元とする集合である。g0=(1)は単位元、つまり、順番を何も変えない操作を表す。(a,b,c)は、aをbに、bをcに、cをaに順番を１つずつ後ろにずらす操作を意味する。(a,b)は、aとbを入れ替える操作である。
【００４５】
このとき、
【００４６】
【数１３】
2014203182.tif 000015
【００４７】
で定義されるρは、準同型写像であるため表現であるが、既約ではない。なぜなら、
【００４８】
【数１４】
2014203182.tif 000016
【００４９】
は非自明な不変部分空間だからである。後に述べるとおりS3の既約表現は3つしかなく、上記の表現はその中には入らない。
【００５０】
［ヤング図形］
Snのヤング図形とは、n個の四角い箱を左上づめに並べた図形である。それぞれのヤング図形は、1行目、2行目、・・・、k行目の箱の数を書き並べることにより、(a1,a2,…,ak)（ここでn=Σi=1kaiかつa1≧a2≧…≧ak>0）と表記することができる。Snのヤング図形は、和がnになる降順の数字の列であるため、「nの分割」とも呼ばれる。ヤング図形を用いたSnの表現論の詳細は専門書に譲り、ここでは発明を理解するために必要な最小限の説明にとどめる。
【００５１】
図１に、箱の数が2,3,4の場合のヤング図形をすべて列挙する。
【００５２】
Snの既約表現は、nの分割（=箱数nのヤング図形）と一対一に対応することが知られている。S3の既約表現が3つなのは、n=3の場合のヤング図形が(3),(2,1),(1,1,1)の3種類であるためである。nの分割の集合（すなわち、Snの既約表現の集合）をΛnと表記する。以下、Snの既約表現とnの分割と箱数nのヤング図形をすべて同一視し、しばしば同じ記号λ∈Λnで表記する。
【００５３】
n=3の例を見ると、λ=(3)は１列に３つの箱が並んだヤング図形に対応し、λ=(2,1)は一列目に2個、二列目に1個の箱が並んだヤング図形に対応し、λ=(1,1,1)は一列目に1個、二列目に1個、3列目に1個の箱を並べたヤング図形に対応する。
【００５４】
λ=(2,1)は3の分割、箱数3のヤング図形であると同時に、Snの既約表現（すなわち、適当な表現空間Vに対してλ:Sn→U(V)は準同型写像）である。
【００５５】
［標準ヤング盤］
既約表現の表現空間の次元数を計算するために、標準ヤング盤の概念を導入する。
【００５６】
Snのヤング図形の各箱に、1からnまでの数字を書き込んだ図形をヤング盤と呼ぶ。Snの各ヤング図形には、n!個のヤング盤がある。図２は、n=2,3に対するヤング盤を列挙したものである。
【００５７】
ヤング盤の中で、全ての行と列に関して、書き込まれる数字が下に行くほど大きく、かつ右に行くほど大きくなっているものを標準ヤング盤と呼ぶ。標準ヤング盤の例を図３に示す。
【００５８】
各ヤング図形に対する標準ヤング盤の数は、そのヤング図形に対応する既約表現の表現空間の次元数に一致することが知られている。すなわち、既約表現λに対する表現空間の次元数をdλで表すと、λ:Sn→U(Cdλ)は非自明な準同型写像である。dλに関して、次の式が成立する。
【００５９】
【数１５】
2014203182.tif 000017
【００６０】
そこで、ρ=(+)λ∈Λn(Idλ(×)λ)をρ(g)・(+)λ∈Λn(Idλ(×)λ(g)で定義すると、ρはSn→U(Cn!)の準同型写像となっている。つまり、Snの元はn!×n!のユニタリ行列で表現ができ、それぞれのユニタリ行列はdλ個のdλ×dλ行列をλ∈Λnに関して並べて作ったブロック対角行列で書ける。(+)は直和であり、(×)はテンソル積を意味する。数式では、丸の中に+がある記号で直和を表し、丸の中に×がある記号でテンソル積を表すこともある。
【００６１】
［Bratteli図］
フーリエ変換の列番号は{g0,g1,…,gn!-1}によって決められたが、行番号を決めるためにBratteli図を用いる。Bratteli図とは、箱数nのYoung図形（nの分割）をn段目のノードとして持ち、各Young図形はそれに一つだけ箱を付け加えたヤング図形を子とするような無閉路有向グラフである。Bratteli図のことをブラテリダイアグラムと呼ぶこともある。頂点のノードをルートノードと呼ぶ。各ノードには、以下のようにして決まる数が割り当てられる。
【００６２】
１．ルートノードは1
２．各ノードに割り当てられる数は、その親ノードの数の和
この数は、ルートノードから各ノードに到達する道数に等しい。
【００６３】
各ノードを辞書式順序（すなわち、nの分割を比較するとき、最初に現れたai≠ai’に対してai>ai’ならば(a1,a2,…,ak)>(a1’,a2’,…,ak’)で降順に並べることにより、Bratteli図を平面上に書くことができる。図４は、7段目までのBratteli図である。
【００６４】
すでに説明したとおり、Snの表現はnの分割（箱数nのヤング図形）と一対一に対応している。従って、Bratteli図のn段目のノードと、Snの既約表現が一対一に対応する。また、各ノードの数字は、そのノードに対応するnの分割λの表現空間の次元数dλに一致する。以下、Bratteli図のn段目のノード、Snの既約表現、箱数nのヤング図形、nの分割をすべて同一視し、しばしば同じ記号λ∈Λnで表記する。
【００６５】
Bratteli図に関して、以下の１．から３．の関係が成り立つ。
【００６６】
【数１６】
2014203182.tif 000018
【００６７】
ここで、λ∈Λn-1に対して、λ↓μはμがλの子ノードを意味するものとする。ここで、「↓」は、数式では右下方向の矢印に対応する。例えば、n=5とし、4の分割λ=(3,1)∈Λ5-1に対してd(3,1)=3、λ↓μとなるμは(4,1),(3,2),(3,1,1)であり、図４からd(3,1)=3,d(4,1)=4,d(3,2)=5,d(4,1)=6,なので、5・3=4+5+6となって関係式が正しいことがわかる。
【００６８】
３．各ノードの子ノードの数は親ノードの数よりも一つ多い
P(λ)を、Bratteli図でルートノードからノードλに至る経路の全体とする。|P(λ)=dλである。λ∈λnとすると、P(λ)の元はn-1個の数の組（i1,i2,…,in-1）によってコーディングされる。ここで、（i1,i2,…,in-1）は、ルートノードから出発してj段目のノードにおいて左からij番目の子ノードを選ぶ経路という意味である。例えば、P(3,1)={(0,0,1),(0,1,0),(1,0,0)}である。j段目のヤング図形は箱数jなので、その子ノード数はj+1以下であり、Zj+1でコーディングできる。したがって、（i1,i2,…,in-1）∈Z2×Z3×…×Znである。このコーディングが、Snの元のコーディングと類似していることに注意されたい。後に量子フーリエ変換を可逆回路として設計する際に、同じキュービットリソースを使う必要性に配慮したものである。
【００６９】
{|λ,p,q>|λ∈Λn,p,q∈P(λ)}とすると、n!=Σλ∈Λndλ2により、|{|λ,p,q>|λ∈Λn,p,q∈P(λ)}|=n!である。この集合内での順序を|λ,p,q><|λ’,p’,q’> iff λ>λ’ or λ=λ’∧p<p’ or λ=λ’∧p=p’∧q<q’のように定める。ここで、λ>λ’だけ順序が反転していることに注意。この順序に対して、{|λ,p,q>|λ∈Λn,p,q∈P(λ)}の要素を0からn!-1の数字で番号付けする。この順序が、今回提案するフーリエ変換行列の行の順序となる。
【００７０】
［正規直交基底の選択］
Snの既約表現、表現空間の次元や、表現空間における不変部分空間の次元は上記の議論より明らかになったが、Snの任意の元を具体的な行列で表現するためには、表現空間の正規直交基底ベクトルを定めなければならない。表現空間の正規直交基底ベクトルの取り方は一意ではない。したがって、Snの各元に対する行列も一意的には決まらない。しかし、正規直交基底としてadapted Gel’fand-Tsetlin Basesを選べば、後に構成する量子回路を効率的にすることができる。ここで、adapted Gel’fand-Tsetlin Basesとは、以下の条件を満たすorthonormal Bases νλ,p(λ∈Λn,p∈P(λ))のことである。
【００７１】
λはヤング図形と一対一で対応している。Bratteli図においてμがλの親であることをμ↓λと表記する。Bratteli図の性質からdλ=Σμ↓λdμが成立する。λはSnの表現で、Sn-1⊆Snなので、任意のσ∈Sn-1は適当な正規直交基底を決めるとdλ×dλ行列で表現される。dλ次元表現空間の正規直交基底がBλの場合、この行列をλ(σ)Bλと表記する。一方、{μ|μ↓λ}はSn-1の表現の集合なので、任意のσ∈Sn-1は適当な正規直交基底の族{Bλ|μ↓λ}を決めるとdμ×dμ行列の{μ|μ↓λ}に関するブロック対角行列（dλ×dλ行列(+)μ↓λμ(σ)Bμ）で表現される。これらの行列は、正規直交基底の取り方に依存するため、一致するとは限らない。しかし、正規直交基底をうまく選択すれば、任意のσ∈Sn-1に対して両者が一致し、
【００７２】
【数１７】
2014203182.tif 000019
【００７３】
となる。この正規直交基底をadapted Gel’fand-Tsetlin Bases（アダプテッドゲルファンドツェッテリン基底）と呼ぶ。adapted Gel’fand-Tsetlin Basesの存在は保証されているが、一意ではない。
【００７４】
なお、次の項目でadapted Gel’fand-Tsetlin Basesとして特定の正規直交基底を選び、以降、この特許ではその正規直交基底しか用いない。そこで、混乱の起こらない限り、λ(σ)Bλやμ(σ)Bμの記号Bλ,Bμを省略し、単純にλ(σ)やμ(σ)と表記する。
【００７５】
［adapted Gel’fand-Tsetlin Basesの計算］
以下、Specht多項式を用いたadapted Gel’fand-Tsetlin Basesの計算方法を述べる。Vandermonde行列式Δ(x1,…,xn)を
【００７６】
【数１８】
2014203182.tif 000020
【００７７】
と定義する。行の数がm、列の数が1であるヤング盤Tに対し、Specht多項式Δ(T)を、
【００７８】
【数１９】
2014203182.tif 000021
【００７９】
と定義し、一般のヤング盤T（列の数はi）に対しは、Specht多項式Δ(T)を以下のように定義する。
【００８０】
【数２０】
2014203182.tif 000022
【００８１】
ただし、TjはTの第j列を取り出したヤング盤、Δ(Tj)はヤング盤に書かれている数字を添え字としたVandermonde行列式である。たとえば、Tが3列からなり、Tに書かれている数字が第1列の上から1、4、5、第2列の上から2、3、第3列の上から6、7なら、
【００８２】
【数２１】
2014203182.tif 000023
【００８３】
となる。
【００８４】
σをSnの元とする。サイズがnのヤング盤Tに対応するSpecht多項式Δ(T)に対し、σ(Δ(T))を、Δ(T)においてxiの添え字iをσ(i)に書き換えたものとする。サイズがnのヤング図形を一つ固定し、それに1からnの数字を記入したヤング盤に対応するSpecht多項式全体の、係数を複素とする一次結合で書ける多項式全体は複素数上の有限次元のベクトル空間Vとなる。
【００８５】
Vの基底として、標準ヤング盤に対応するSpecht多項式の全体を取ることができることが知られている。また、上記σ∈Snの作用はVの線形変換に自然に拡張されるので、SnからU(V)への写像が得られる。この写像は準同型となるので、Vを表現空間とするSnの表現となる。この表現が既約であること、Snの既約表現は、サイズがnのすべてのヤング図形に対してこのように作った表現で尽くされることが知られている。ただし、標準ヤング盤に対応するSpecht多項式全体からなる基底は、adapted Gel’fand-Tsetlin Basesにはなっていない。
【００８６】
箱の数がnである同じヤング図形に数字を入れた異なる二つのヤング盤T1,T2に対し、T1<T2であるとは「あるi(1≦i≦n)が存在して、すべてのj(i<j≦n)について、jが属する列はT1とT2で同じであり、T2においてiが属する列はT2においてiが属する列よりも左にあること」と定義する。こうすると、「<」は箱の数がnであるヤング図形に数字を記入したヤング盤の集合の全順序となる。
【００８７】
箱の数がnである標準ヤング盤に対応するSpecht多項式が生成する複素ベクトル空間Vのエルミート積を以下で定義する。Vは、x1,…,xnの単項式の一次結合が生成する複素ベクトル空間Wの部分空間であるので、f,g∈W、ただし、
【００８８】
【数２２】
2014203182.tif 000024
【００８９】
ここで、λを多重指数に対するWのエルミート積とし、
【００９０】
【数２３】
2014203182.tif 000025
【００９１】
をVに制限したものをVのエルミート積とする。
【００９２】
今回提案するSnのGel’fand-Tsetlin Basesを計算する方法は以下の「１．」「２．」で述べる通りである。
１．箱の数がnであるヤング図形を列挙し、一列にならべる。
２．一列にならべたヤング図形を順に一つずつ取り、以下の（１）（２）の操作を行う。
（１）ヤング図形に対する標準ヤング盤を列挙し、上で定義した全順序により一列にならべる。すなわち、順序が大きいものを後ろにする。
（２）標準ヤング盤を後ろから順に取り、対応するSpecht多項式にGram-Schmidtの正規直交化法を適用する。
この結果得られる多項式の集合はadapted Gel’fand-Tsetlin Basesとなっている。
【００９３】
たとえば、n=2の場合、d(2)=1,d(1,1)=1で、adapted Gel’fand-Tsetlin Basesは以下のようになる。
【００９４】
【数２４】
2014203182.tif 000026
【００９５】
また、n=3の場合、d(3)=1,d(2,1)=2,d(1,1,1)=1で、adapted Gel’fand-Tsetlin Basesは以下のようになる。
【００９６】
【数２５】
2014203182.tif 000027
【００９７】
［表現の具体例］
上記方法によりSpecht多項式からadapted Gel’fand-Tsetlin Basesを計算することができ、そこから表現行列を具体的に書くことができる。
たとえば、n=2の場合、g0はx1→x1,x2→x2、g1はx2→x1,x2→x1なので、すでに計算したadapted Gel’fand-Tsetlin Basesを用いると、以下のようになる。
【００９８】
【数２６】
2014203182.tif 000028
【００９９】
したがって、i=0,1に対して、
【０１００】
【数２７】
2014203182.tif 000029
【０１０１】
は、
【０１０２】
【数２８】
2014203182.tif 000030
【０１０３】
となる。ここから、ρ(g0)及びρ(g1)を求めると、それぞれ以下のようになることがわかる。
【０１０４】
【数２９】
2014203182.tif 000031
【０１０５】
これらが、1×1行列を2つ並べたブロック対角行列であることに注意のこと。
【０１０６】
また、n=3の場合、i=0,1,…,5に対して、
【０１０７】
【数３０】
2014203182.tif 000032
【０１０８】
を解くことにより、行列ρ(gi)が求まる。このようにして求めたS3の3!×3!表現行列は、1×1, 2×2, 2×2, 1×1のブロック対角行列で以下のようになる。なお、記載の簡略化のため、行列の中の値が０である成分については空白としている。この記載の簡略化は、他の行列についても行う。
【０１０９】
【数３１】
2014203182.tif 000033
【０１１０】
［フーリエ変換］
Sn上のフーリエ変換を以下のように定義する。
【０１１１】
【数３２】
2014203182.tif 000034
【０１１２】
ここで、[λ(g)]q,pは行列λ(g)の(q,p)成分である。上記の定義では、一般の定義と異なり、qとpを反転させている点に注意のこと。このように、フーリエ変換を定義すると、FTnの定義中における係数を[λ(g)]q,pとするよりも少しだけ計算が楽になる。基底ベクトル{|λ,p,q>|λ∈Λn,p,q∈P(λ)}及び{|g>|g∈Sn}の順序を、以前に定義したとおりに選ぶと、量子フーリエ変換は、具体的に以下の通りに書ける。
【０１１３】
【数３３】
2014203182.tif 000035
【０１１４】
FT2の１列目、２列目はそれぞれρ(g0),ρ(g1)に対応し、FT3の１列目から６列目まではそれぞれρ(g0)〜ρ(g5)に対応している。
【０１１５】
［基底変換Tn］
フーリエ変換を効率的に実行するアルゴリズムを考えていく前に、基底順序の変換Tnを導入する。TnはU(Cn!)の基底
【０１１６】
【数３４】
2014203182.tif 000036
【０１１７】
から基底
【０１１８】
【数３５】
2014203182.tif 000037
【０１１９】
への順序変換で、以下のように定義される。
【０１２０】
|λ’,p’,q’>→|λ,p,q>を、q=q’,p=p’|n-2,p∈P(λ)で定義する。ここで、p’=(p1,p2,…,pn-1)に対して、p’|n-2をp’|n-2=(p1,p2,…,pn-2)で定義する。すると、B1→B0の全単射が定義できる。B0,B1はぞれぞれn!個の基底からなるので、B0,B1の基底を前に導入した順序で並べると、この全単射は0,1を要素として持つn!×n!行列で表現できる。この行列をT†nとすると、Tn:B0→B1となる。
【０１２１】
ΛnはSnの既約表現なので、Snの任意の元gは(＋)λ∈∧n(Idλ(×)λ(g))と書ける。Tnの定義から、
【０１２２】
【数３６】
2014203182.tif 000038
【０１２３】
である。
【０１２４】
例えば、n=4の場合、S4の任意の元gは基底B1により図５のように1×1,3×3,2×2,3×3,1×1行列がそれぞれ1,3,2,3,1個並んだブロック対角行列で表わせる。このブロック対角行列を両側からT†4とT4で挟むと図６となり、4×4,8×8,4×4行列がそれぞれ1,2,1個並んだブロック対角行列で表わせる。ただし、図中の行列番号がそれぞれ対応することに注意のこと。
【０１２５】
後に定義するHnの出力側の基底がB0となるのに対して、FTnの出力基底はB1となる。このTnは、それらの出力間の差を解消するために用いられる。
【０１２６】
［フーリエ変換の分解］
FTnを実行する回路を構成するために、次のようにHnを定義する。
【０１２７】
【数３７】
2014203182.tif 000039
【０１２８】
すると、FTn=TnHn(FTn-1(×)In)なので、
【０１２９】
【数３８】
2014203182.tif 000040
【０１３０】
と分解できる。
【０１３１】
小さいnに対してHnは、以下のようになる。
【０１３２】
【数３９】
2014203182.tif 000041
【０１３３】
一般に、Hnはndλ×ndλの行列Hnλを用いて、Hn=Σλ∈Λn-1Idλ(×)Hnλとブロック行列形式で書くことができる。たとえば、Λ1={(1)},d(1)=1なので、
【０１３４】
【数４０】
2014203182.tif 000042
【０１３５】
であり、Λ2={(2),(1,1)},d(2)=1,d(1,1)=1なので、以下のようになる。
【０１３６】
【数４１】
2014203182.tif 000043
【０１３７】
また、Λ3={(3),(2,1),(1,1,1)},d(3)=1,d(2,1)=2,d(1,1,1)=1なので、以下のようになる。
【０１３８】
【数４２】
2014203182.tif 000044
【０１３９】
H4,(3),H4,(2,1),H4,(1,1,1)の行列サイズはそれぞれ4×4,8×8,4×4である。nが大きくなるとHnのブロック行列は指数的に大きくなる。式(3)のように分解できることは、参考文献１等でも知られているが、Hnを構成する各ブロックのサイズが非常に大きいため、行列の乗算に非常にコストがかかってしまう。
〔参考文献１〕P.Diaconis, D.Rockmore, “E-cient computation of the fourier transform on finite groups”, J. AMS, 3(2):297-332, 1990
【０１４０】
また、非特許文献２では、式(2)におけるTnHnをFnとした形を用いており、Fnをそのまま素直に量子回路に変換する方法が提案されている。しかし、上述の通り、nが大きくなるとHnのブロック行列は指数的に大きくなるので、効率の良い量子回路を構成することができない。そこで、Hnを効率的に実行するために、Hnをもっと細かく分解する。
【０１４１】
［H=のU(Cn!)への埋め込み］
すでに述べたとおり、H2,H3,…,Hnが実行できればFTnも実行できる。しかし、H2,H3,…,Hnは複雑な形をしていて、実行するのは容易ではない。
【０１４２】
そこで、簡単に実行できる適当なKn,Pn,AnでHn=AnPnHn-1Knとなるものを探し、Hnを帰納的に実行することを考える。
【０１４３】
以降、順次Kn,Pn,Anを定義していくが、その前に解決しておかなければならない問題がある。すなわち、Hn=AnPnHn-1Knにおいて、Hnの行列サイズはn!×n!、Hn-1の行列サイズは(n-1)!×(n-1)!で、行列のサイズが異なる問題である。この問題を解決するために、Hn-1をHnと同じサイズのユニタリ行列Cn!に埋め込む関数fn-1を導入する。
【０１４４】
f2を以下のように定義する。Λ1={(1)},d(1)=1なのでH2は2×2行列H2,(1)である。一方、Λ2={(2),(1,1)},d(2)=1,d(1,1)=1なので、H3は3×3行列と3×3行列のブロック行列H3,(2)(+)H3,(1,1)である。そこで、H2を次のような2段階により、3×3行列と3×3行列のブロック行列に変換する。まず、第一段階で、H2,(1)→H’2,(1)=I1(+)H2,(1)により（ここで、I1(+)H2,(1)は(0,0)番目の要素が1、(i+1,j+1)番目の要素がH2,(1)の(i,j)番目の要素、残りが0の行列のこと。）H2,(1)を3×3行列に埋め込む（図７の左から中央）。第二段階で、H’2,(1)からH’’2=H’2,(1)(+)H’2,(1)に変換する（図７の中央から右）。この二段階を経た写像がf2である。したがって、f2(H2)=H’’2∈Σλ∈Λ2Idλ(×)U(C3dλ)である。
【０１４５】
f3を以下のように定義する。Λ2={(2),(1,1)},d(2)=1,d(1,1)=1なので、H3は3×3行列H3,(2)と3×3行列H3,(1,1)のブロック行列H3,(2)(＋)H3,(1,1)である。また、Λ3={(3),(2,1),(1,1,1)},d(3)=1,d(2,1)=2,d(1,1,1)=1なので、H4は4×4行列H4,(3),8×8行列H4(2,1), 4×4行列H4,(1,1,1)を組み合わせて作ったブロック行列H4,(3)(＋)(I2(×)H4,(2,1)) (＋)H4,(1,1,1)である。H3=H3,(2)(＋)H3,(1,1)は次のようにして、4×4行列,8×8行列, 8×8行列,4×4行列のブロック行列に変換される。第一段階で、H3,(2)→H’3,(2)=I1(＋)H3,(2),H3,(1,1)→H’3,(1,1)=I1(＋)H3,(1,1),により、H3を4×4行列と4×4行列のブロック行列H’3,(2)(＋)H’3,(1,1)に変換する（図８の左から中央）。第二段階で、H’3,(2)(＋)H’3,(1,1)から、H’’ 3= H’3,(2)(＋)(I2(×)(H’3,(2)(＋)H’3,(1,1))(＋)H’3,(1,1)に変換する（図８の中央から右）。この変換は、Bratteli図の2行目と3行目から決まる。したがって、f3(H3)= H’’3∈Σλ∈Λ3Idλ(×)U(C4dλ)である。
【０１４６】
f4を以下のように定義する。Λ3={(3),(2,1),(1,1,1)},d(3)=1,d(2,1)=2,d(1,1,1)=1なので、H4は4×4,8×8,8×8,4×4行列のブロック行列H4,(3)(＋)(I2(×)H4,(2,1))(＋)H4,(1,1,1)である。（全体の行列サイズは4!×4!。）一方、Λ4={(4),(3,1),(2,2),(2,1,1),(1,1,1,1)},d(4)=1,d(3,1)=3,d(2,2)=2,d(2,1,1)=3,d(1,1,1,1)=1なので、H5は5×5,15×15, 15×15, 15×15,10×10, 10×10, 15×15,15×15,15×15, 5×5行列のブロック行列H5,(4)(＋)(I3(×) H5,(3,1)) (＋) (I2(×) H5,(2,2)) (＋) (I3(×) H5,(2,1,1)) (＋) H5,(1,1,1,1)である。（全体の行列サイズは5!×5!。）H4= H3,(3)(＋) (I2(×) H3,(2,1)) (＋) H3,(1,1,1)は次のような二段階により、H5と同じサイズのブロック行列に変換される。まず、第一段階で、H4,(3)→H’ 4,(3)=I1(＋) H4,(3)、H4,(2,1)→H’ 4,(2,1)=Σi=0d(2,1)-1|4i><4j|＋Σi,j=04d(2,1)-1(H3,(2,1)) i,j|i mоd 4＋1><j mod 4+1|、H4,(1,1,1)→H’4(1,1,1)=I1(＋)H4, (1,1,1)と変換することにより、H4は5×5,10×10,10×10,5×5行列のブロック行列H’4,(3)(＋)(I2(×)H’4,(2,1))(＋)H’4,(1,1,1)に変換される（図９の左から中央）。さらに第二段階で、H’’4=H’4,(3)(＋)(I3(×)(H’4,(3)(＋)H’4,(2,1)))(＋)(I2(×)H’4,(2,1))(＋)(I3(×)(H’4,(2,1))(＋)H’4,(1,1,1)))(＋)H’4,(1,1,1))に変換する（図９の中央から右）。従ってf4(H4)=H’’4∈Σλ∈Λ4Idλ(×)U(C5dλ)である。
【０１４７】
一般に、n≧2に対してHnの基底(Bases)を
【０１４８】
【数４３】
2014203182.tif 000045
【０１４９】
で定義する。ただし、P(λ)は、Bratteli図でλに到達するpathの集合である。例えば、図９の一番左側の図で基底は24個ある。同じp,qの組み合わせに対するm=0,1,2,3の4つの基底が、図の中の各ブロックに含まれる4個の基底に対応している。各ブロックはp,qの組み合わせに対応している。p,qはBratteli図の3行目までのpathで同じヤング図形λを終点としてもつので、［Bratteli図］で導入したコーディング方法を用いれば、|λ,p,q>は、
|(3),(0,0),(0,0)>
|(2,1),(0,1),(0,1)>
|(2,1),(0,1),(1,0)>
|(2,1),(1,0),(0,1)>
|(2,1),(1,0),(1,0)>
|(1,1,1),(1,1),(1,1)>
の6種類である。上図の一番左側の図には縦方向に6個のブロックがあり、それぞれ上記の基底に対応している。
【０１５０】
各基底には、0又は1を成分とするベクトルが対応付けされている。対応付けは、適切な結果が得られるものであればどのようなものであってもよく、事前に決めておく。例えば、参考文献２で用いられている対応付けと同様の対応付けを用いることができる。なお、これらのことは、|λ,p,q,m>以外の他の基底についても同様である。これらの基底は、行列の中の成分の位置を表すために用いられる。
〔参考文献２〕C.Moore, D.Rockmore, A.Russell, “Generic guantum fourier transforms”, ACM Transactions on Algorithms, 2(4):707-723, Octorber 2006
【０１５１】
fnを以下のように二段階で定義する。Hnはブロック行列Σλ∈Λn-1Idλ(×)Hnλである。（全体の行列サイズはn!×n!。）まずfn,1をn!×n!行列から(n＋1)(n−1)!×(n＋1)(n−1)!行列への写像で、
【０１５２】
【数４４】
2014203182.tif 000046
【０１５３】
により定義する。次に、fn,2を(n＋1)(n−1)!×(n＋1)(n−1)!行列から(n＋1)!×(n−1)!行列への写像で、
【０１５４】
【数４５】
2014203182.tif 000047
【０１５５】
とする。ここで、p|n-1はBratteli図のn段目までのpath p のn−1段目までへの制限（すなわちpath pからn番目の成分を除いたもの）、λq|n-1はq|n-1の終端ノードである。fn=fn,2・fn,1によりfnを定義すると、fnはn!×n!行列を(n＋1)!×(n＋1)!行列に写す。特に、fnにより行列のユニタリ性は保存される。n!×n!ユニタリ行列の群をCn!と書き、
【０１５６】
【数４６】
2014203182.tif 000048
【０１５７】
により埋め込みを定義すると、U(C2!),U(C3!),…,U(C(n-1)!)を、U(Cn!)の元と考えることができる。以下、H’n-1=fn-1(Hn-1)と記述する。
なお、別の観点から説明すると、H’’m-1は以下の式により定義される行列ということができる。
【０１５８】
【数４７】
2014203182.tif 000049
【０１５９】
ここで、aを任意の既約表現とし、b,cのそれぞれをaに至るパスとし、dを0以上の整数とし、|a,b,c,d>をa,b,c,dに基づいて定まるベクトルとし、hλ,q,r,i,jを以下の式により定まる値とする。
【０１６０】
【数４８】
2014203182.tif 000050
【０１６１】
［基底変換Pn］
以下、順次Hn=AnPnH’n-1Knを満たすAn,Pn,Knを順次定義していく。
PnはU(Cn!)の基底
【０１６２】
【数４９】
2014203182.tif 000051
【０１６３】
から
【０１６４】
【数５０】
2014203182.tif 000052
【０１６５】
への変換で、図１５を部分的に可換にする基底変換である。
【０１６６】
もう少し正確に言うと、任意のg∈Sn-1に対して、Sn-1におけるadapted Gel’fand-Tsetlin basesでの行列表現をpn-1(g)、Snにおけるadapted Gel’fand-Tsetlin basesでの行列表現をpn(g)とすると、pnfn-1(T†n-1ρn-1(g)Tn-1)P†nとT†nρn(g)Tnがほとんど一致するように基底変換Pnを選ぶ。
例えば、n=5の場合を例にとって説明すると、可換図は図１０のようになる。
【０１６７】
つまり、S4の元は1×1,3×3,2×2,3×3,1×1行列の1,3,2,3,1個のブロック対角行列で書け（図の一番左上）、これをT3とf3で変換すると一番右上のように5×5,15×15,10×10,15×15,5×5行列の1,3,2,3,1個のブロック対角行列に埋め込まれる（図では最初の2個の行列だけを書いた）。ここで、番号2の行列は4つに分解されて埋め込まれる。一方、adapted Gel’fand-Tsetlin basesの性質を利用して、同じ行列を1×1,4×4,5×5,6×6,5×5,4×4,1×1の1,4,5,6,5,4,1個のブロック対角行列で書くこともできる（図の一番左下）。これをT4で変換すると、一番右下のように5×5,15×15,10×10,15×15,5×5行列の1,3,2,3,1個のブロック対角行列に埋め込まれる（図では最初の2個の行列だけを書いた）。右上の図と右下の図を比較すると、最初の行列は全く同じだが、１行目と2行目は同じ成分なので入れ替えることができる。したがって、この行列に関してP3はI5（5×5のIdentity）か
【０１６８】
【数５１】
2014203182.tif 000053
【０１６９】
である。2番目の15×15行列については一見順序が大きく異なるように見えるが、図中の行列番号を見ると、右上の図では0が1個、1が2個、2が1個、3が1個であり、右下の図では0が1個、1が3個、2が1個、3が1個である。つまり、行列番号1のものが一つだけ多くなっている。そこで、2番目の15×15行列については、番号1の行列を一つだけ除いて右下と一致するように行列の順番をうまく入れ替える。このような基底順序の変更がP3である。言い換えれば、Pnfn-1(T†n-1ρn-1(g)Tn-1)P†nとT†nρn(g)Tnとで共通する部分ブロックの出現する順序が同じになるようなPnfn-1(T†n-1ρn-1(g)Tn-1)P†nの行と列の入れ替えを行う行列がPnである。
【０１７０】
なお、右下の2番目の行列において、番号1の行列は3つあるので、P3は3種類考えることができるが、3種類の中のどれを選んでもよい。また、右上の行列は実際には5つ（5×5,15×15,10×10,15×15,5×5）あるが、残りの3つの行列については、それぞれ2種類、3種類、1種類の中からP3を選ぶ。この選択肢の数は、Bratteli図における、各ノードの子ノードの数に一致していることが証明できる。（つまり、P3の選択肢はλ=(4),(3,1),(2,2),(2,1,1),(1,1,1,1)の子ノード数2,3,2,3,2である。）Pnの選択による差異は、後に定義されるAnで吸収される。
【０１７１】
なお、Pnの作り方については以下のように説明することもできる。
基底順序変換Pnはn!×n!行列で、ndλ×ndλ行列Pn, λ(ただし、λ∈Λn-1)を用いてPn=（＋）λ∈Λn-1(Idλ(×)Pn, λ)と書ける。このPn, λは次のように定義される２つの行列の積Pn, λ,1 Pn, λ,2により計算できる。
１．
【０１７２】
【数５２】
2014203182.tif 000054
【０１７３】
ここで、0≦x,y<ndλで、(Pn,λ,1)x,yはPn,λ,1の(x,y)成分を意味する。δはクロネッカーのデルタである。また、括弧[ ]はガウス記号で、[x/n]はx/nを超えない最大の整数である。
２．Pn,λ,2は次のようにBratteli図から定義される。
【０１７４】
λの親の子供全体を列挙し（記号で書くと{λ’|∃μ(μ↓λ∧μ↓λ’)}だが、まずλの親{μ|μ↓λ}を辞書式順序の降順に並べ、次にそれぞれのμの子供{λ’|μ↓λ’}を辞書式順序の降順に並べたものでμを置き換える。同じλ’であっても異なるμの子として列挙された場合、異なるλ’として数える。）、さらに、その先頭にλを加えたものをΩn,λと書く。
【０１７５】
また、λの子供の親全体を列挙し（記号で書くと{λ’|∃μ(λ↓μ∧λ’↓μ)}だが、まずλの子供{μ|λ↓μ}を辞書式順序の降順に並べ、次にそれぞれのμの親{λ’|λ’↓μ}を辞書式順序の降順に並べたものでμを置き換える。同じλ’であっても異なるμの親として列挙された場合、異なるλ’として数える。）、それをΩn,λ’と書く。
【０１７６】
Ωn,λとΩ’n,λは重複を含めて同じ要素を持っている。Ωn,λの要素数を|Ωn,λ|とする。なお、Ωn,λ（Ω’n,λでも同じ）に含まれる重複している要素はλだけで、その個数はλの子供の数に等しい。そこで、関数fλ:{i|1≦i≦|Ωn,λ|}→{i|1≦i≦|Ωn,λ’|}を、Ωn,λのi番目の要素とΩn,λ’のfλ(i)番目の要素が等しくなるような関数とする。Ωn,λに重複する要素があるためfλ:は一意にならないが、小さいiの値から順にfλ(i)を決めるときに、fλ(i)が先に定義した順序において最小になるように選ぶことにすれば、fλは一意に定まる。
【０１７７】
このように定義したfλを用いて、Pn,λ,2を、全てのi (ただし、1≦i≦|Ωn,λ|）に対して、{i,fλ(i)番目に行列Idλiを要素として持つような行列として定義する。ただし、λiはΩn,λのi番目の要素である。
【０１７８】
Pnの例を以下に挙げる。n=4, λ=(2,1)とし、Pn,λ,1を求める。定義により、Pn,λ,1は8×8行列であり、以下のようになる。
【０１７９】
【数５３】
2014203182.tif 000055
【０１８０】
n=4,λ=(2,1)とし、Pn,λ,2を示す。
図１７より、Ωn,λ={(2,1),(3),(2,1),(2,1),(1,1,1)}かつΩn,λ’={(3),(2,1),(2,1),(2,1),(1,1,1)}である。したがって、fλ:1→2,2→1,3→3,4→4,5→5とすれば、以下のような行列になる。この行列は8×8行列である。
【０１８１】
【数５４】
2014203182.tif 000056
【０１８２】
［制御交換ゲートKn］
次に、制御交換ゲートKnを以下の通り定義する。
【０１８３】
【数５５】
2014203182.tif 000057
【０１８４】
ここで、λ(c(j,j+1,…,m-1))は巡回置換c(j,j+1,…,m-1)に対応するλによる既約表現である。|j>はj番目の成分が1であり他の成分が0であるベクトルであり、<j|は|j>の転置である。このように、あるベクトルに対応する基底を|x>として、<x|は|x>のベクトルを転置したベクトルを意味する。
【０１８５】
［調整用ゲートAn］
最後に、An=HnK†nH’†n-1P†nと定義する。定義より明らかにHn=AnPnH’n-1Knである。次の定理から、Anが簡単に実行できることが保証される。
【０１８６】
定理：すべてのg∈Sn-1に対して、p(g)とAnは可換である。ここで、p=(＋)λ∈Λn-1(Idλ(×)((＋)λ↓μμ)):Sn→U(Cn!)はSnの表現である。
【０１８７】
Gel'fand-Tsetlin Basesの定義により、任意のg∈Sn-1に対してμ(g)=(＋)ν↓μν(g)が成り立つ。したがって、任意のg∈Sn-1に対してp(g)=(＋)λ∈Λn-1(Idλ(×)((＋)λ↓μ(＋)ν↓μν(g)))である。ここで、(＋)λ↓μ(＋)ν↓μν(g)は∃μ(λ↓μ∧ν↓μ)となるようなνに対するdν×dν行列の直積である。
一方で、Hn=(＋)λ∈Λn-1(Idλ(×)Hn,λ),K†n=(＋)λ∈Λn-1(Idλ(×)K†n,λ),H’†n-1=(＋)λ∈Λn-1(Idλ(×)H’†n-1,λ),P†n=(＋)λ∈Λn-1(Idλ(×)P†n,λ)と書けるので、A n,λ=H n,λK†n,λH’†n-1,λP†n, λとするとA n=(＋)λ∈Λn-1(Idλ(×)An,λ)である。ここで、An,λはdλ×dλ行列である。
【０１８８】
p(g)とAnが可換であることから、任意のg∈Sn-1に対して(＋)λ↓μ(＋)ν↓μν(g)とAn,λは可換である。eλ,ν=|{μ|λ↓μ∧ν↓μ}|とすると、∃μ(λ↓μ∧ν↓μ)となるλ,νに対して、
【０１８９】
【数５６】
2014203182.tif 000058
【０１９０】
である。(＋)λ↓μ(＋)ν↓μν(g)=(＋)ν(Ieλ,ν(×)ν(g))なので、(＋)λ↓μ(＋)ν↓μν(g)とAn,λが可換であることから、An,λ=(＋)ν(A’n,λ,ν(×)Idν)と書ける。ここで、A’n,λ,νはeλ,ν×eλ,νユニタリ行列である。上のeλ,νの計算から、λ≠νに対してA’n,λ,ν=1であり、A’n,λ,λはeλ, λ×eλ, λ行列である。eλ, λ≦nなので、結局、An,λを実行するにはn×nよりも小さな行列A’n,λ,λが実行できればよいことになる。以下では、A’n,λ,λを省略してA’n,λと表記することとする。このA’n,λを用いれば、An=(＋)λ∈Λn-1(Idλ(×)(A’n,λ(×)Idλ(＋)Ir))と書ける。ここで、Irは足りない次元を補うための余剰項であり、identityなので実行上なにも操作する必要がない。Irのrは、上記の足りない次元数に対応する所定の正の整数である。
【０１９１】
なお、Anは、以下のように定義される。
【０１９２】
【数５７】
2014203182.tif 000059
【０１９３】
ここで、[μ(c(m-1,m))]qμ,ν,qμ,νは巡回置換c(m-1,m)に対応するμによる既約表現μ(c(m-1,m))に至るルートノードからのパスに基づいて定まる値である。また、x,yを任意の既約表現とし、基底|x,y>はx,yに基づいて定まるベクトルであり、<x,y|は|x,y>の転置である。
【０１９４】
［pn(c(m,m+1))の簡単な作り方］
1≦m<nとなるmに対して、m-1とmの互換をc(m-1,m)と記述する。
【０１９５】
c(m-1,m)のSnにおけるn!×n!行列表現ρn(c(m-1,m))を以下のように定義した。
１．Smの既約表現λ∈Λmのそれぞれに対して、
（１）Specht多項式を計算する。
（２）Gram-Schmidtの正規直交化アルゴリズムを使ってSpecht多項式を直交化する。こうして得られた多項式はx1,…,xm-1,xmを変数として持つdλ個の多項式で、Gel’fand-Tsetlin基底となっている。
（３）dλ個の多項式はベクトル空間の基底なので、それぞれの式のxm-1とxmを入れ替えた式は、dλ個の多項式の一次結合となる。この一次結合の係数が作るdλ×dλ行列は(c(m-1,m))の既約表現λにおける表現行列となっている。そこで、この行列を多項式の連立方程式を解くことにより求める。求めた行列をλ(c(m-1,m))と記述する。
【０１９６】
２．ρn(c(m-1,m))は、λ(c(m-1,m))がGel’fand-Tsetlin基底から定義された行列表現であることを用いて、Bratteli図から容易に求められる。すなわち、m≦Ｉ<n,ν∈Λi+1に対して、
【０１９７】
【数５８】
2014203182.tif 000060
【０１９８】
が成り立つので、λ∈Λnに対するλ(c(m-1,m))は帰納的に定義できる。そこで、以ρ下のようにすればよい。
【０１９９】
【数５９】
2014203182.tif 000061
【０２００】
２．の計算はBratteli図から簡単に実行できるが、１．の計算には大変な時間がかかる。コンピュータで定義どおりに計算しても、λ(c(m-1,m))を求めることができるのはせいぜいm≦7くらいまでである。
【０２０１】
しかし、以下のような方法で、もっと簡単にλ(c(m-1,m))を計算することができる。
Bratteli図において、ルートノードからλ∈Λmに至るPathの集合p(λ)の元p∈P(λ)は次の2種類に分類できる。
１．∀ν∈Λm-1(λp|m-3↓ν↓λ→ν=λp|m-2)
２．∃ν∈Λm-1(λp|m-3↓ν↓λ∧ν≠λp|m-2)
すなわち、１．は最終ノードの2つ前で分岐して合流する経路が存在しないもの、２．は最終ノードの2つ前で分岐して合流する経路が存在するものである。なお、２．の場合、Bratteli図の性質から、最終ノードの2つ前では高々2つにしか分岐しないことが証明できる。それぞれを図で書くと図１８のようになる。
【０２０２】
dλ×dλ行列λ(c(m-1,m))は、以下の1×1行列または2×2行列の直和でかける。
Ａ）q∈P(λ)が上記分類の1に含まれている場合、
（１）q[m-2]=q[m-1]、すなわち経路qにおいて、最後の2回で付け加わったヤング図形の箱の行番号が同じ（列番号は必ず1だけ違う）場合は1×1行列(1)とする。正確に書くと、|q><q|である。
（２）q[m-2]+1=q[m-1]、すなわち経路qにおいて、最後の2回で付け加わったヤング図形の箱の行番号が1だけ違う（列番号は必ず同じになる）場合は1×1行列(-1)とする。正確に書くと、-|q><q|である。
p∈P(λ)が上記分類の1に含まれている場合、以上の2つのケース（１）（２）しか起こらない。
【０２０３】
Ｂ）q∈P(λ)が上記分類の2に含まれている場合、λに到達する経路において、2つ前まではqと同じで、1つ前が異なり、最後のλでもう一度合流する経路をq’と書く。経路qにおいて、最後の2回でヤング形に付け加わった箱を(x1,y1),(x2,y2)とすると、経路q’において最後の2回でヤング図形に付け加わる箱は(x2,y2),(x1,y1)である。つまり、付け加わる箱の順番が入れ替わるだけである。ただし、xi,yiはそれぞれ行番号、列番号である。ｌ=|x1-x2|＋|y1-y2|とし、|q>と|q’>が作る2×2行列を以下のように定義する。
【０２０４】
【数６０】
2014203182.tif 000062
【０２０５】
で定義する。すなわち、
【０２０６】
【数６１】
2014203182.tif 000063
【０２０７】
である。
以上の定義により、λ(c(m-1,m))は一意的に定まる。
【０２０８】
以下、λ(c(m-1,m))の計算の例を説明する。λ=(3,1,1)とし、c(4,5)のλにおける表現を計算するとする。ここで、λが5の分割であることに注意。例えば、λ=(3,1)ならば、λは4の分割なので、互換c(3,4)を計算する。dλ=6なので、求めるのは6×6行列である。図１９はBratteli図の一部である。
λに至る経路は{(0,0,1,2),(0,1,0,2),(1,0,0,2),(0,1,2,0)(1,0,2,0),(1,2,0,0)}である。
【０２０９】
ａ）(0,0,1,2)は上記分類の1で、最後の2回で付け加わる箱が縦に並んでいる（列番号が同じ）ので、対応する行列は1×1行列(-1)である。
ｂ）(1,2,0,0)も上記分類の1で、最後の2回で付け加わる箱が横に並んでいる（行番号が同じ）ので、対応する行列は1×1行列(1)である。
ｃ）{(0,1,0,2),(0,1,2,0)}は最後の2回が入れ替わっているペアなので、これらの基底で2×2の行列を作る。lは最後の2回で付け加わる箱の間のマンハッタン距離（図２０の点線で示した経路）なので、l=4である。
したがって、2×2行列は
【０２１０】
【数６２】
2014203182.tif 000064
【０２１１】
ｄ）{(1,0,0,2), (1,0,2,0)}も同じ行列となる。
以上により、λ(c(4,5))は、以下のようになる。
【０２１２】
【数６３】
2014203182.tif 000065
【０２１３】
［対称群上の高速フーリエ変換アルゴリズム］
以下の関係式から、任意のn≧2に対するFTnを帰納的に計算することができる。
＜関係式＞
１．FT1=1
２．FTn=TnHn(FTn-1(×)In) for n>2
３．Hn=AnPnfn-1(Hn-1)Kn  for n≧3
例えば、
【０２１４】
【数６４】
2014203182.tif 000066
【０２１５】
なので、関係式２．から
【０２１６】
【数６５】
2014203182.tif 000067
【０２１７】
である。また、
【０２１８】
【数６６】
2014203182.tif 000068
【０２１９】
【数６７】
2014203182.tif 000069
【０２２０】
より、関係式３．から
【０２２１】
【数６８】
2014203182.tif 000070
【０２２２】
である。T3=I6なので、関係式２．から
【０２２３】
【数６９】
2014203182.tif 000071
【０２２４】
となって、先に計算したFT3と一致する。
【０２２５】
一般のFTnに関しては、図１１のように帰納的に計算される。すなわち、nを３以上の各整数として、An,Pn,Hn-1,KnによりHnが計算され、Hn,FTn-1,TnによりFTnが計算される。
【０２２６】
［対称群上の量子フーリエ変換回路］
このように、対称群Sn上のフーリエ変換FTnを計算するには、H2,FT2,H3,FT3,…,Hn-1,FTn-1,Hnを順次計算していけばよい。この計算はn!×n!ユニタリ行列の積計算により実行できる。
【０２２７】
対応する量子フーリエ変換は、n!次元の量子状態空間でユニタリ変換を行えば実行できる。これをキュービットでナイーブにエンコードする場合、┌n log n┐キュービットあれば十分である。言い換えれば、2┌n log n┐次元の複素空間におけるn!次元の部分空間で、量子変換を実行することになる。しかし、量子回路での実行を容易にするためには、より多くのリソースを用いて量子状態をエンコードするほうがよい。
【０２２８】
この実施形態で構成する量子回路では、上記のフーリエ変換FTnを計算するアルゴリズムにあわせたエンコーディング方法を行う。必要な状態空間の次元数は、2n log n×n!2次元である。したがって、以下に述べる回路では、2n log n×n!2次元の空間におけるn!次元部分空間で量子フーリエ変換を実行する。2n log n×n!2≦23 nlog nなので、冗長なエンコーディングを行っても、ナイーブなコーディングに必要なリソースに比べて定数倍のキュービットリソースがあれば十分である。
【０２２９】
具体的には、図１２の量子回路により量子フーリエ変換を実行する。図１２の量子回路は、入力状態|i>=|i1,i2,・・・,in-1>とし、
(1) 入力状態|i1>を入力レジスタとし、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するH2ゲートと、
(2) m=3,・・・,n-1まで順番に
(2-1)直前のゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとし、入力状態|im>を第４レジスタとし、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するHmゲートと、
(2-2) 上記Hmゲートの出力状態である第１出力レジスタ、第２出力レジスタ、第３出力レジスタをそれぞれ第１レジスタ、第２レジスタ、第３レジスタとして、第１出力レジスタと第２出力レジスタと第３出力レジスタからなる出力状態を出力するTmゲートと、
が交互に配置されたものである。
【０２３０】
ここで、入力側はSnの任意の元gに対して、
【０２３１】
【数７０】
2014203182.tif 000072
によって決まる量子状態|i1,i2,…,in-1>∈C2×3×…×n=Cn!である。また、出力側はヤング図形λと、Bratteli図でルートノードからλに至る経路p,qを用いて|λ,p,q>で表される。ここで、ヤング図形λはnの分割により|λ1,λ2,…,λn>∈Cn×n×…×nとコーディングされる。また、pは|p1,p2,…,pn-1>∈C2×3×…×n、qは|q1,q2,…,qn-1>∈C2×3×…×nでコーディングされる。したがって、|λ,p,q>∈C(n^n)×n!×n!である。
【０２３２】
入力側と出力側の次元数の差は、量子回路の中で量子リソースを追加することによりもたらされる。リソースが追加されるのはH2,T3,T4,…，Tnで、それぞれC(n^2)×2,Cn×3,Cn×4…，C n×nだけリソースが追加される。H3,H4,…，Hnではリソースの追加はない。
【０２３３】
H2,Hn,Tnの量子回路を与えれば、FTnを実行する量子回路も決まる。
【０２３４】
［H2の量子回路］
H2は|0>→1/√2(|(2),(0),(0)>+|(1,1),(1),(1)>),|1>→1/√2(|(2),(0),(0)>-|(1,1),(1),(1)>)なので、図１３の回路で実行できる。ここで、1番目と2番目のラインはn量子状態が表せる量子リソース（qunit）、3番目と4番目のラインはqubitである。また、+1は1加算する回路、つまり入力状態|x>をとしたとき、|x+1 mоd t>（tは|x>の基底の数、qubitならt=2, qtutritならt=3）を出力するゲートである。また、図１３の左端のゲートはよく知られているHadamardゲートである。
【０２３５】
言い換えれば、H2ゲートは、第１レジスタ|x>を入力レジスタとして、以下の(a-1)から(a-4)を備えるゲートであり、上記(a-1)〜(a-4)を適用した後の前記第３補助レジスタと前記第２補助レジスタからなるレジスタを第１出力レジスタ、前記第１補助レジスタを第２出力レジスタ、上記第１入力レジスタを第３出力レジスタとするゲートである。
【０２３６】
(a-1)は、第１入力レジスタ|x>に対するHadamardゲートである。
(a-2)は、第１補助レジスタ|0>を導入して、上記第１入力レジスタを制御ビットとし、第１補助レジスタ|0>を標的ビットとする制御ＮＯＴゲートである。
【０２３７】
(a-3)は、第２補助レジスタ|a1>（ただし初期値は|a1>=|0>）を導入して、前記第１入力レジスタを制御ビットとし、制御ビットが|1>のときに第２補助レジスタ|a1>の状態を|a1+1 mоd t>（ただしtは|a1>の取りうる量子状態の基底の総数）に変換するゲートである。
【０２３８】
(a-4)は、第３補助レジスタ|a2>を導入し、前記第１入力レジスタを制御ビットとし、制御ビットが|0>のときに第３補助レジスタ|a2>（ただし初期値は|a2>=|1>）の状態を|a2+1 mоd t>（ただしtは|a2>の取りうる量子状態の基底の総数）に変換するゲートである。
【０２３９】
[Hmの量子回路]
m=3,4,…,nについてのHmの回路を図１４に示す。
Hm=AmPmfm-1(Hm-1)Kmを利用して、Hm を実行する量子回路を構成する。
入力側レジスタ数：4
出力側レジスタ数：3
量子デバイスリソース：
入力第1レジスタ|λ>  mlogm qubits
入力第2レジスタ|p1,…,pm-2>  qubit, qutrit, …, qu(m-1)it
入力第3レジスタ|q1,…,qm-2>  qubit, qutrit, …, qu(m-1)it
入力第4レジスタ|i>  qunit
ここで、qu(m-1)it はm-1状態量子デバイス、qumitはm状態量子デバイスのことである。
出力第1レジスタ|λ>  mlogm qubits
出力第2レジスタ|p1,…,pm-2>  qubit, qutrit, …,qu(m-1)it
出力第3レジスタ|q1,…,qm-1>  qubit, qutrit, …,qu(m-1)it, qumit
出力第3レジスタは、入力第3第4レジスタをひとまとめにしたものである。
基底：
入力側  {|λ,p,q,i>|λ∈Λm-1∧p,q∈P(λ)∧i<m}
出力側  {|λ,p,q>|λ∈Λm-1∧p,q∈P(λ)}
【０２４０】
m=3,4,・・・,nの各整数として、Hmゲートは、第１レジスタ|λ>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-2>と、第４レジスタ|x>とを入力レジスタとして、以下の(b-1)から(b-8)のゲートを備えたゲートであり、以下の(b-1)から(b-8)適用した後の、第１レジスタを第１出力レジスタ、第２レジスタを第２出力レジスタ、第３レジスタと第４レジスタを合わせたレジスタを第３出力レジスタとするゲートである。
【０２４１】
(b-1)は、第４レジスタ|x>を制御ビットとし、第１、第２、第３レジスタを標的ビットとして、制御ビットの状態がα(α=0,1,・・・,m-1)のとき標的ビットにλ(c(α,α+1,・・・,m-1))を適用するゲートである。
(b-2)は、第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートである。
【０２４２】
(b-3)は、|i>を|i-1 mоd m>に変換する操作を第４レジスタ|x>に適用するゲートである。tは|i>の基底の数である。すなわち、qubitならt=2、qtutritならt=3である。ここでは、t=mである。
(b-4)は、第１レジスタ|λ>、第２レジスタの|p1,・・・,pm-3>、第３レジスタの|q1,・・・,qm-3>、第４レジスタ|x>に対して適用されるHm-1ゲートである。
【０２４３】
(b-5)は、|i>を|i+1 mоd t>に変換する操作を第４レジスタ|x>に適用するゲートである。ここでは、t=mである。
(b-6)は、第３レジスタの|qm-2>を制御ビットとし、第１レジスタ|λ>を標的ビットとするTm,2ゲートである。
【０２４４】
(b-7)は、第１レジスタから第４レジスタに、Pmfm-1(T†m-1ρm-1(g)T m-1)P†mの行と列の入れ替えに対応する量子ビットの交換操作Pmに対応する操作を適用するゲートである。
(b-8)は、第１レジスタ|λ>を制御ビットとし、第３レジスタ|qm-2>を標的ビットとして、以下の式により定義されるA’m,λに対応する操作を適用するゲートである。
【０２４５】
【数７１】
2014203182.tif 000073
【０２４６】
Kmに対応する操作を行うゲートが、(b-1)である。
fm-1(Hm-1)に対応する操作を行うゲートが、(b-3)から(b-5)である。なお、この(b-3)から(b-5)のゲートは、入力|λ,p,q,i>に対して、i=0ならばidentityとなる。
H’’m-1=fm-1(Hm-1)に対応する操作を行うゲートが、(b-2)から(b-6)である。
Pmに対応する操作を行うゲートが(b-7)である。
Amに対応する操作を行うゲートが(b-8)である。
【０２４７】
また、半黒丸は、制御ビットの取りうる各状態に対して量子ゲートを実行するという意味である。なお、黒丸又は半黒丸の直下に範囲が指定されている場合はその各状態に対してゲートを実行することを意味し、特に指定がなければ取りうる全ての状態に対してゲートを実行することを意味する。
【０２４８】
(b-1)のゲートは、図１５に例示するゲートと等価であるため、(b-1)のゲートに代えて、この図１５に例示するゲートを設けてもよい。
【０２４９】
［Tmの量子回路］
Tmの回路を図１６に示す。Tmゲートは、Tm,1ゲート及びTm,2ゲートから構成される。
【０２５０】
Tmゲートは、第１レジスタ|λ>=|λ1,・・・,λm-2>と、第２レジスタ|p>=|p1,・・・,pm-2>と、第３レジスタ|q>=|q1,・・・,qm-1>とを入力レジスタとし、Tm,1ゲート及びTm,2ゲートを適用した後の、第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>を第１出力レジスタ、第２レジスタ|p>=|p1,・・・,pm-1>及び制御ビットを第２出力レジスタ、第３レジスタ|q>=|q1,・・・,qm-1>を第３出力レジスタとする。ここで、|λm-1>の初期値は|0>である。
【０２５１】
Tm,1ゲートは、第２レジスタ|p>と第３レジスタ|q>を制御ビットとして、新たに導入した第１補助レジスタ|0>を
【０２５２】
【数７２】
2014203182.tif 000074
に変換する演算を適用するゲートである。
【０２５３】
Tm,2ゲートは、第３レジスタの|qm-1>を制御ビットとし、Tmゲートの第１レジスタ|λ>=|λ1,・・・,λm-2>及び第２補助レジスタ|λm-1>を標的ビットとするゲートである。第２補助レジスタ|λm-1>の初期値は例えば|0>とする。
【０２５４】
より詳細には、Tm,2ゲートは、制御ビットを|c1>とし、標的ビットを|λ>=|λ1,・・・,λm-1>としたとき、制御ビットの状態がｊのときに標的ビット|λj>を|λj+1 mоd t>（ただしｔは|λj>の取りうる量子状態の基底の総数）に変換するゲートである。
【０２５５】
［フーリエ変換計算装置の機能構成］
フーリエ変換計算装置は、図２１に示すように、入力部１、ブラテリダイアグラム取得部２、正規直交基底計算部３、計算部４及び出力部５を備える。フーリエ変換計算装置は、図２２に例示されたフーリエ変換計算方法の各ステップの処理を行う。
【０２５６】
入力部１は、対称群の次数を取得する。入力部１は、例えばキーボード、マウス等の入力機器であり、それらの入力機器を用いてユーザにより対称群の次数が入力される。Snに対するフーリエ変換FTnの計算を行う場合、次数nが入力される。次数nについての情報は、フーリエ変換計算装置の各部に送信される。
【０２５７】
ブラテリダイアグラム取得部２は、図４に例示示したような対称群Snに対するブラテリダイアグラムについての情報を取得する。ブラテリダイアグラム取得部２は、ブラテリダイアグラムについての情報が予め記憶されたブラテリダイアグラム記憶部２１からブラテリダイアグラムについての情報を読み込んでも良いし、必要に応じてブラテリダイアグラムについての情報を適宜計算してもよい。ブラテリダイアグラムについての情報は、正規直交基底計算部３及び計算部４に送信される。
【０２５８】
正規直交基底計算部３は、アダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)である正規直交基底を計算する（ステップＳ１）。計算された正規直交基底は、表現空間の正規直交基底ベクトルを構成する。計算された正規直交基底についての情報は、計算部４に送信される。
【０２５９】
計算部４は、FTm-1,Tm,Hm,Imに基づいてFTm=TmHm(FTm-1(×)Im)を計算する処理をm=1,2,…,nの各整数について順次行うことにより、FTnを計算する。計算結果は、出力部５に送信される（ステップＳ２）。
【０２６０】
出力部５は、ディスプレイ、プリンタ等の出力装置であり、FTnの計算結果を出力しユーザに知覚させる。
【０２６１】
［変形例等］
フーリエ変換計算装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０２６２】
また、上述の構成をコンピュータによって実現する場合、フーリエ変換計算装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【０２６３】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０２６４】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【産業上の利用可能性】
【０２６５】
フーリエ変換は対象となる群ごとに異なる行列で表現される。信号処理の分野で広く応用されているフーリエ変換は巡回群上のフーリエ変換であり、1変数関数の周期を取り出すことに利用されている。
【０２６６】
一方、この実施形態で示したフーリエ変換は対称群上のフーリエ変換である。上記フーリエ変換とは異なり、より複雑なデータからパターンを抽出するために利用できる。例えば、信号処理や系統樹データの解析や選挙データの解析などへの応用が知られている（例えば、参考文献３、４参照。）。
〔参考文献３〕Stankvic Stankovic Radomir S., Moraga Claudio, Astola Jaakko T., “Fourier Analysis on Finite Groups with Applications in Signal Processing and System Design”, 2005/06
〔参考文献４〕http://www.math.hmc.edu/~orrison/art/
【０２６７】
フーリエ変換の行列成分を確率振幅とする量子変換を量子フーリエ変換と呼ぶ。対称群上の量子フーリエ変換とは、対称群上のフーリエ変換に対応する量子フーリエ変換である。量子フーリエ変換と区別するため、通常のフーリエ変換を古典フーリエ変換と呼ぶこともある。量子フーリエ変換は、隠れ部分群問題と呼ばれる問題群に応用できる。巡回群上の量子フーリエ変換の応用として、因数分解と離散対数問題を高速に解くショーアのアルゴリズムが有名である（例えば、参考文献５参照。）。
〔参考文献５〕Peter W.Shor, “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Sci. Statist. Comput. 26 (1997) 1484
【０２６８】
また、対称群上の量子フーリエ変換の応用として、サイモンの問題を解くアルゴリズムが参考文献６で示されている。
〔参考文献６〕G. Alagic, C. Moore, A. Russell, “Quantum Algorithms for Simon’s Problem over Nonabelian Groups”, ACM Transactions on Algorithms, 6(1), Article 19 (December 2009)
【図１】
2014203182.tif 000082
【図２】
2014203182.tif 000083
【図３】
2014203182.tif 000084
【図４】
2014203182.tif 000085
【図５】
2014203182.tif 000086
【図６】
2014203182.tif 000087
【図７】
2014203182.tif 000088
【図８】
2014203182.tif 000089
【図９】
2014203182.tif 000090
【図１０】
2014203182.tif 000091
【図１１】
2014203182.tif 000092
【図１２】
2014203182.tif 000093
【図１３】
2014203182.tif 000094
【図１４】
2014203182.tif 000095
【図１５】
2014203182.tif 000096
【図１６】
2014203182.tif 000097
【図１７】
2014203182.tif 000098
【図１８】
2014203182.tif 000099
【図１９】
2014203182.tif 000100
【図２０】
2014203182.tif 000101
【図２１】
2014203182.tif 000102
【図２２】
2014203182.tif 000103
【図２３】
2014203182.tif 000104