(57)【特許請求の範囲】
【請求項１】
nを３以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρi,ρijの表現空間の次元数をそれぞれｄρi,ｄρijとして、
箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算部と、
b=0,1,2,…,n-1とし、gb=(1,2,…,n)b∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρij(gb)の直和である行列表現ρ(gb)を生成する処理を各bについて行い、生成された行列表現ρ(g0),ρ(g1),…,ρ(gn-1)を構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρi・n×dρi・nの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1,dρ2個のMρ2,…,dρan-1個のMρan-1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn-1上の量子フーリエ変換をFSn-1とし、(×)をテンソル積とし、Pn-1を(In(×)FSn-1)を(FSn-1(×)In)に変換する置換とし、・†を行列・の共役転置とし、GnPn-1(In(×)FSn-1)Pn-1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成部と、
を含む量子回路生成装置。
【請求項２】
請求項１の量子回路生成装置において、
上記正規直交基底計算部は、各上記標準ヤング盤に対応するシュペヒト多項式を生成し、生成されたシュペヒト多項式をグラムシューミットの正規直交化法で互いに直交させて上記正規直交基底とする、
量子回路生成装置。
【請求項３】
nを３以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρi,ρijの表現空間の次元数をそれぞれｄρi,ｄρijとして、
正規直交基底計算部が、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算ステップと、
量子回路生成部が、b=0,1,2,…,n-1とし、gb=(1,2,…,n)b∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρij(gb)の直和である行列表現ρ(gb)を生成する処理を各bについて行い、生成された行列表現ρ(g0),ρ(g1),…,ρ(gn-1)を構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρi・n×dρi・nの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1,dρ2個のMρ2,…,dρan-1個のMρan-1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn-1上の量子フーリエ変換をFSn-1とし、(×)をテンソル積とし、Pn-1を(In(×)FSn-1)を(FSn-1(×)In)に変換する置換とし、・†を行列・の共役転置とし、GnPn-1(In(×)FSn-1)Pn-1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成ステップと、
を含む量子回路生成方法。
【請求項４】
請求項１又は２の量子回路生成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項５】
請求項４のプログラムが記録されたコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、対称群上の量子フーリエ変換を多項式時間で実行できる量子回路を生成する技術に関する。
【背景技術】
【０００２】
1994年、ショーアにより因数分解を高速に行う量子アルゴリズムが発見されて以降、世界中で量子アルゴリズムの研究が盛んに行われている。特に、ショーアの論文の末尾で提案された未解決問題は注目を集め、多くの研究者たちがそれらの問題に対する高速なアルゴリズムの発見を競ってきた。中でも、もっとも有名な問題はグラフ同型性判定問題である。グラフ同型性判定問題とは、２つのグラフが与えられたときに、それらのグラフの頂点間の写像で、辺を保存するものが存在するかどうかを判定する問題である。例えば、図１の例では、G1とG2は同型だが、それらとG3は同型ではない。グラフ同型性判定問題は、パターンマッチングの一種であり、高速なアルゴリズムが見つかれば、その応用範囲はきわめて広い。
【０００３】
グラフ同型性判定問題は、因数分解よりも難しい問題で、現在のコンピュータ上で高速なアルゴリズムは見つかっていない。一方、グラフ同型性判定問題は量子コンピュータでも解くことが困難とされるNP完全問題よりやさしく、高速な量子アルゴリズムが見つかる可能性がある。
【０００４】
ショーアのアルゴリズムで最も重要な量子回路は、{0,1,…,n−1}を元としてもつ巡回群であるZn上の量子フーリエ変換である。量子フーリエ変換には効率的な量子回路が存在し、このことが因数分解の効率的な実行に重要な役割を果たす。なぜなら、量子フーリエ変換はZnの部分群の周期情報を取り出す役割を果たすからである。ショーアのアルゴリズムをグラフ同型性判定問題に拡張するための最も素直な方法は、ショーアのアルゴリズムにおけるZn上の量子フーリエ変換を対称群Sn上の量子フーリエ変換で置き換えることである。ここで、対称群Snとは、与えられた自然数nに対して、n個の異なる文字の集合からそれ自身への一対一対応全体を表す。n個の文字に1,2,…,nという数字を割り当てれば、{1,2,…,n−1,n}の置換によって作られる群である。Snはn!個の元をもち、置換の積を群の演算とみなす。
【０００５】
Sn上の量子フーリエ変換が多項式時間で実行できることを最初に示したのは、Beals（例えば、非特許文献１参照。）である。
【０００６】
後にMooreらが、非可換群上の量子フーリエ変換を含む多くの変換に対して効率的な量子回路の存在を証明した（例えば、非特許文献２参照。）。ここでいう効率的な量子回路とは、入力量子ビット数ｎに対して多項式サイズO(poly(n))で構成できる量子回路が存在するということを意味する。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Robert Beals, “Quantum computation of Fourier transforms over symmetric groups”, In ACM, editor, Proceedings of the twenty-ninth annual ACM Symposium on the Theory of Computing: El Paso, Texas, May 4--6, 1997, pp. 48--53, New York, NY, USA, 1997. ACM Press.
【非特許文献２】C. Moore and D. Rockmore, “Generic quantum fourier transforms”, Technical Report quant-ph/0304064, Quantum Physics e-Print Archive, 2003.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、非特許文献１及び２では、対称群Sn上の量子フーリエ変換に対して効率的な、すなわち多項式サイズの量子回路が存在することが理論的に示されているものの、具体的な量子回路の構成方法までは示されていない。量子コンピュータ上で演算を実行するためには、具体的な量子回路を構成する必要がある。
【０００９】
この発明の目的は、対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成する量子回路生成方法、プログラム及びその記録媒体を提供することである。
【課題を解決するための手段】
【００１０】
この発明の一態様による量子回路生成装置は、nを３以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρi,ρijの表現空間の次元数をそれぞれｄρi,ｄρijとして、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算部と、b=0,1,2,…,n-1とし、gb=(1,2,…,n)b∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する正規直交基底を用いてgbを表した行列表現ρij(gb)の直和である行列表現ρ(gb)を生成する処理を各bについて行い、生成された行列表現ρ(g0),ρ(g1),…,ρ(gn-1)を構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρi・n×dρi・nの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1,dρ2個のMρ2,…,dρan-1個のMρan-1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn-1上の量子フーリエ変換をFSn-1とし、(×)をテンソル積とし、Pn-1を(In(×)FSn-1)を(FSn-1(×)In)に変換する置換とし、・†を行列・の共役転置とし、GnPn-1(In(×)FSn-1)Pn-1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成部と、を含む。
【発明の効果】
【００１１】
対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成することができる。
【図面の簡単な説明】
【００１２】
【図１】グラフ同型性判定問題を説明するための図。
【図２】ヤング図形を説明するための図。
【図３】ヤング盤を説明するための図。
【図４】標準ヤング図形を説明するための図。
【図５】対称群S3上の量子フーリエ変換Fs3の量子回路を例示する図。
【図６】ブラテリダイアグラムを説明するための図。
【図７】ブラテリダイアグラムの性質を説明するための図。
【図８】Mρiの構成を説明するための図。
【図９】実施形態の量子回路生成装置の構成を説明するためのブロック図。
【図１０】Vandermonde行列式を説明するための図。
【図１１】正規直交基底の計算の方法を説明するための図。
【図１２】正規直交基底の計算の方法を説明するための図。
【図１３】正規直交基底の計算の方法を説明するための図。
【図１４】正規直交基底の計算の方法を説明するための図。
【図１５】正規直交基底の計算の方法を説明するための図。
【図１６】正規直交基底の計算の方法を説明するための図。
【図１７】Mρiを計算するためのアルゴリズムのフローチャート。
【図１８】ρ(gi)の構成を説明するための図。
【図１９】G4の構成を説明するための図。
【図２０】対称群S4上の量子フーリエ変換Fs4の量子回路を例示する図。
【図２１】実施形態の量子回路生成装置を説明するためのフローチャート。
【発明を実施するための形態】
【００１３】
まず、この発明を理解するための背景知識について説明する。
【００１４】
Sn（nは自然数）上の量子フーリエ変換を定義する前に、S2,S3の場合の例を用いながら対称群の表現論の基礎を解説する。Gを群とする。適当なベクトル空間Vに対して、写像
ρ:G→U(V)
が群の演算と可換になるとき（つまり写像が準同型のとき）、ρを表現と呼び、Vを表現空間と呼ぶ。W⊆Vがρ(G)で不変になるとき、Wを不変部分空間と呼ぶ。V（空間全体）と{0}は明らかに普遍不変なため、自明な不変部分空間と呼ばれる。不変部分空間として自明なものしか存在しないとき、ρを既約表現と呼ぶ。
【００１５】
例えば、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を入れ替える操作である。
【００１６】
このとき、
【００１７】
【数１】
0005700827.tif 000002
【００１８】
で定義されるρは、準同型写像であるため表現であるが、既約ではない。なぜなら、
【００１９】
【数２】
0005700827.tif 000003
【００２０】
は非自明な不変部分空間だからである。後に述べるとおりS3の既約表現は3つしかなく、上記の表現はその中には入らない。
【００２１】
一般に、Snの既約表現はヤング図形（Young diagram）によって列挙することができる。ヤング図形を用いたSnの表現論の詳細は専門書に譲り、ここでは発明を理解するために必要な最小限の説明にとどめる。ヤング図形とは、四角い箱を左上づめに並べた図形である。図２に、箱の数が2,3,4の場合のヤング図形をすべて列挙する。図２のλの式で表現されるように、各ヤング図形は上から順に列ごとの箱の数をリスト形式で並べた形で記述される。n=3の例を見ると、λ=(3)は１列に３つの箱が並んだヤング図形に対応し、λ=(2,1)は一列目に2個、二列目に1個の箱が並んだヤング図形に対応し、λ=(1,1,1)は一列目に1個、二列目に1個、3列目に1個の箱を並べたヤング図形に対応する。
【００２２】
Snの既約表現は、箱の数がnのヤング図形に一対一で対応することが知られている。S3の既約表現が３つなのは、n=3の場合のヤング図形が3種類であるためである。
【００２３】
ヤング図形のそれぞれの箱に数字を書き込んだ図形をヤング盤（Young tableau）と呼ぶ。ヤング盤を図３に例示する。ヤング盤の中で、全ての行と列に関して、書き込まれる数字が下に行くほど大きく、かつ右に行くほど大きくなっているものを標準ヤング盤と呼ぶ。標準ヤング盤を図４に例示する。
【００２４】
各ヤング図形に対する標準ヤング盤の数は、ヤング図形に対応する表現の表現空間の次元数に一致することが知られている。表現ρに対する表現空間の次元数をdρで表す。すると、次の式が成立する。
【００２５】
【数３】
0005700827.tif 000004
【００２６】
(＋)ρをSnの表現全体の直和とすると、(＋)ρはΣρdρ次元の空間上のユニタリ行列で表現できる。例えば、n=2の場合、ヤング図形の数は2で、標準ヤング盤の個数は1+1=2なので、S2の各元は2×2行列で表現できる。
【００２７】
【数４】
0005700827.tif 000005
【００２８】
また、n=3の場合、ヤング図形の数は3で、標準ヤング盤の個数は1+2+1=4なので、Snの各元は4×4行列で表現できる。各行列は、1×1、2×2、1×1のブロック行列の直和となっている。
【００２９】
【数５】
0005700827.tif 000006
【００３０】
次に、対称群上の量子フーリエ変換について説明する。上記の4×4で表現されたρ(g1),ρ(g2),…,ρ(g5)の行列の要素に、定数を掛けて並べると、量子フーリエ変換になる。対称群S2上の量子フーリエ変換FS2及び対称群S3上の量子フーリエ変換FS3を具体的に書くと、以下のようになる。
【００３１】
【数６】
0005700827.tif 000007
【００３２】
FS2はアダマール変換に等しい。FS3は以下のように書き換えることができる。
【００３３】
【数７】
0005700827.tif 000008
【００３４】
FS3の量子回路を図５に示す。ここで、１番目の線はqubit、２番目の線はqutritを表す。なお、qubitは１つの素子で|0>と|1>の２状態の重ね合わせ状態を表現する素子であり、qutritは１つの素子で|0>,|1>,|2>の３状態の重ね合わせ状態を表現する素子である。また、図５で白丸で示された２番目のゲートは制御ビットである１番目のビットが|0>のときに標的ビットである２番目のビットに２番目の線上に載っている３×３行列で表わされる演算を施すことを意味する。さらに、図５で黒丸で示された３番目のゲートは、いわゆるControlled rotation gateであり、制御ビットである１番目のビットが|1>のときに標的ビットである２番目のビットに２番目の線上に載っている３×３行列で表わされる演算を施すことを意味する。
【００３５】
４以上のｎに対する量子フーリエ変換Fsnは、ヤング図形の系統を図示したダイアグラムであるブラテリダイアグラムによりの帰納的な定義することができる。
【００３６】
各ヤング図形は、それより１つ箱の数が多いヤング図形を子として持つと考えることにより、１つの箱からできたヤング図形を頂点とし、n段目のノードがn個の箱を持つヤング図形で構成される図で表現できる。これをブラテリダイアグラムと呼んでいる。ブラテリダイアグラムを図６に例示する。
【００３７】
すでに説明したとおり、Snの既約表現はn個の箱を持つヤング図形に一対一に対応している。そこで、ブラテリダイアグラムのn段目を見れば、Snの既約表現が列挙されている。また、図６の各ノードに付された数字は、頂点を１として頂点からたどった各ノードまでの道の総数であり、各ヤング図形の表現空間の次元数に一致することが知られている。そこで、表現ρｉに対応するヤング図形のノードに記された数字を表現空間の次元数と同じ記号であるdρｉで表す。
【００３８】
ブラテリダイアグラムの各ノードの数字に関して、以下のことが成り立つ。
【００３９】
【数８】
0005700827.tif 000009
【００４０】
【数９】
0005700827.tif 000010
【００４１】
n=4の場合を考える。S3の既約表現ρ1，ρ2，ρ3と、それらの子ノードρ11，ρ12，ρ21，ρ22，ρ23，ρ31，ρ32を図７に示す。ρ1の子ノートがρ11，ρ12であり、ρ2の子ノードがρ21，ρ22，ρ23であり、ρ3の子ノードがρ31，ρ32である。ρ2についてみると、式(1)の左辺はdρ2・n＝２・４＝８であり、式(1)の右辺はΣj=13dρ2j＝３＋２＋３＝８であり、両辺の値が一致することが確認できる。
【００４２】
ブラテリダイアグラムの各ノードの数字から、量子フーリエ変換FSnを実行するために必要な行列のサイズ情報が得られる。対称群Sn上の量子フーリエ変換FSnは次のように分解されることが知られている。以下の行列において、空白の部分の成分は０である。このことは他の行列についても同様である。
【００４３】
【数１０】
0005700827.tif 000011
【００４４】
ここで、Gnは、図８のようなブロック対角行列である。Pn-1はIn(×)FSn-1をFSn-1(×)Inに変換する置換である。この式から、量子フーリエ変換FSnは、Gn,…,G3の積で表わせる。Inはn次元の単位行列であり、(×)はテンソル積であり、・†を行列・の共役転置とする。
【００４５】
【数１１】
0005700827.tif 000012
【００４６】
FS2はアダマール変換なので、Gn,Gn-1,…,G3を実行できれば、量子フーリエ変換FSnを実行できる。そこで、この発明では、Gn,Gn-1,...,G3の具体的な行列を構成する。
【００４７】
Gｎの行列表現は、Sｎの元(1,2,…,n)i(i=0,1,…,n-1)の行列表現によって決まる。(1,2,…,n)iは、iだけ右にシフトする巡回置換である。例えば、(1,2,…,n)1=(1,2,3,…,n)であり、nが奇数の場合には(1,2,…,n)2=(1,3,5,…,2,4, …)であり、nが偶数の場合には(1,2,…,n)2=(1,3,5,…,n-1)(2,4,6…,n)である。Gｎの量子回路を構成するためには、まず行列表現を決定しなければならない。そして、Sｎの任意の元を行列で表現するためには、まず、表現空間の正規直交基底ベクトルを決定する必要がある。
【００４８】
量子回路生成装置は、図９に示すように、入力部１、ブラテリダイアグラム取得部２、正規直交基底計算部３、量子回路生成部４、基本ゲート分解部５及び出力部６を備える。量子回路生成装置は、図２１に例示された量子回路生成方法の各ステップの処理を行う。
【００４９】
入力部１は、対称群の次数を取得する。入力部１は、例えばキーボード、マウス等の入力機器であり、それらの入力機器を用いてユーザにより対称群の次数が入力される。Snに対する量子フーリエ変換FSnの量子回路を生成する場合、次数nが入力される。次数nについての情報は、量子回路生成装置の各部に送信される。
【００５０】
ブラテリダイアグラム取得部２は、図６に例示示したような対称群Snに対するブラテリダイアグラムについての情報を取得する。ブラテリダイアグラム取得部２は、ブラテリダイアグラムについての情報が予め記憶されたブラテリダイアグラム２１からブラテリダイアグラムについての情報を読み込んでも良いし、必要に応じてブラテリダイアグラムについての情報を適宜計算してもよい。ブラテリダイアグラムについての情報は、正規直交基底計算部３及び量子回路生成部４に送信される。
【００５１】
正規直交基底計算部３は、アダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)である正規直交基底を計算する（ステップＳ１）。計算された正規直交基底は、表現空間の正規直交基底ベクトルを構成する。計算された正規直交基底についての情報は、量子回路生成部４に送信される。
【００５２】
量子回路生成部４は、正規直交基底計算部３で求めた計算された正規直交基底から行列表現を求め、Gm(m=3,4,…,n)に対する量子回路を生成し、対称群Sn上の量子フーリエ変換FSnの量子回路を生成する（ステップＳ２）。生成された量子回路についての情報は、基本ゲート分解部５に送信される。
【００５３】
基本ゲート分解部５は、量子回路生成部４で求めた量子回路を、量子コンピュータ上の基本演算の系列に変換する（ステップＳ３）。この部分は周知技術を利用することができる。変換された量子コンピュータ上の基本演算の系列についての情報は、出力部６に送信される。
【００５４】
量子回路生成部４で出力される量子回路は、qubit, qutrit, quatritのように複数種類の素子を組み合わせて実現される演算系列となっている。実際の量子コンピュータ上で実行する際には、全てを同じ素子、例えばqubitに統一して、qubit上の1qubit又は2qubit間の演算を行う基本ゲートの系列に変換することが現実的である。Gm(m=3,4,...,n)に対応する制御ユニタリ演算における標的ビットの演算であるdρi・ｎ×dρi・ｎ行列(i=1,2,...,an-1)や上述の通常とは異なる交換演算は、より大きい2m×2m行列に埋め込み、例えば参考文献１に記載されたなどの分解方法を用いて、qubit上の基本ゲートの系列に変換してもよい。
【００５５】
〔参考文献１〕Y. Nakajima, Y. Kawano, and H. Sekigawa, A New Algorithm for Producing Quantum Circuits using KAK Decompositions, Quantum Information and Computation, Vol. 6, No. 1, pp. 67-80, 2006.
出力部６は、ディスプレイ、プリンタ等の出力装置であり、量子コンピュータ上の基本演算の系列についての情報を出力しユーザに知覚させる。
【００５６】
以下、この発明の主要部である正規直交基底計算部３と量子回路生成部４について、詳細に説明する。
【００５７】
まず、正規直交基底計算部３が生成するアダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)について説明する。Snの任意の元の行列表現を確定させるためには、まず、表現空間の正規直交基底ベクトルを定めなければならない。表現空間の正規直交基底ベクトルの取り方は一意ではないので、基底ベクトルの取り方によって異なる行列表現になる。しかし、後に量子回路を構成するときに効率的な量子回路とするためには、アダプテッドゲルファンドツェッテリン基底を選ぶ必要がある。ここで、ρのアダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)とは以下の条件を満たすorthonormal basis v1,…,vdρのことである。
【００５８】
ρはヤング図形と一対一で対応している。ブラテリダイアグラムにおけるρの親ノードに対応する表現を、
【００５９】
【数１２】
0005700827.tif 000013
【００６０】
とする。ブラテリダイアグラムの性質から、
【００６１】
【数１３】
0005700827.tif 000014
【００６２】
が成立する。ρをSnの表現とすると、任意のｇ∈Snは適当な正規直交基底を決めるとdρ・dρ行列で表現される。一方、ρｉ(i=1,2,…,an-1)はSn-1の表現なので、任意のｇ∈Sn-1は適当な正規直交基底を決めるとdρi・dρi行列で表現される。このとき、任意のｇ∈Snに対して、
【００６３】
【数１４】
0005700827.tif 000015
【００６４】
が成立する正規直交基底をアダプテッドゲルファンドツェッテリン基底と呼ぶ。アダプテッドゲルファンドツェッテリン基底の存在は保証されているが、一意ではない。アダプテッドゲルファンドツェッテリン基底を用いると、Sn-1の元はブロック対角行列で表現される。
【００６５】
アダプテッドゲルファンドツェッテリン基底を適当に選ぶことにより、Snの任意の元はdρ・dρ行列で表現される。このように、Snの任意の元の行列表現が定まると、それに応じてSn上の量子フーリエ変換を以下のように定義することができる。[ρ(g)]α，βは、ρ(g)の[α，β]成分である。
【００６６】
【数１５】
0005700827.tif 000016
【００６７】
次に、シュペヒト(Spechet)多項式について説明する。Vandermonde行列式Δ(x1,…,xn)を
【００６８】
【数１６】
0005700827.tif 000017
【００６９】
と定義する。図１０に、１×１の箱から構成されるヤング図形のVandermonde行列式Δ(x1)、２×１の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2)、３×１の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2,x3)及び４×１の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2,x3,x4)を示す。
【００７０】
行の数がm、列の数が1であるヤング盤Tに対し、シュペヒト多項式Δ(T)を、
【００７１】
【数１７】
0005700827.tif 000018
【００７２】
と定義し、行の数がmであり列の数がiである一般のヤング盤Tに対しは、シュペヒト多項式Δ(T)を、
【００７３】
【数１８】
0005700827.tif 000019
【００７４】
と定義する。
【００７５】
ただし、TjはTの第j列を取り出したヤング盤、Δ(Tj)はヤング盤に書かれている数字を添え字としたVandermonde行列式である。例えば、Tが3列からなり、Tに書かれている数字が第1列の上から1、4、5、第2列の上から2、3、第3列の上から6、7なら、
【００７６】
【数１９】
0005700827.tif 000020
【００７７】
となる。
【００７８】
gをSnの元とする。サイズがnのヤング盤Tに対応するシュペヒト多項式Δ(T)に対し、g(Δ(T))を、Δ(T)においてxiの添え字iをg(i)に書き換えたものとする。サイズがnのヤング図形を１つ固定し、それに1からnの数字を記入したヤング盤に対応するシュペヒト多項式全体の、係数を複素とする一次結合で書ける多項式全体は複素数上の有限次元のベクトル空間Vとなる。
【００７９】
Vの基底として、標準ヤング盤に対応するシュペヒト多項式の全体を取ることができることが知られている。また、上記ｇ∈Snの作用はVの線形変換に自然に拡張されるので、SnからU(V)への写像が得られる。この写像は準同型となるので、Vを表現空間とするSnの表現となる。この表現が既約であること、Snの既約表現は、サイズがnのすべてのヤング図形に対してこのように作った表現で尽くされることが知られている。ただし、標準ヤング盤に対応するシュペヒト多項式全体からなる基底は、アダプテッドゲルファンドツェッテリン基底にはなっていない。
【００８０】
この実施形態では、アダプテッドゲルファンドツェッテリン基底を求めるために、以下の手順により、シュペヒト多項式にGram-Schmidtの正規直交化法を適用する。これにより得られる多項式からなる基底はアダプテッドゲルファンドツェッテリン基底となる。
【００８１】
１．正規直交基底計算部３は、箱の数がnであるヤング図形を読み込む。ヤング図形は、以下に示す全順序により一列に並べられているものとする。
【００８２】
２．正規直交基底計算部３は、読み込んだヤング図形を先頭から順次１つずつ取り出し、以下の操作を行う。
（１）取りだしたヤング図形に対する標準ヤング盤を全て展開し、上で定義した全順序により一列にならべる。すなわち、順序が大きいものを後ろにする。
（２）標準ヤング盤を後ろから順に取り、対応するシュペヒト多項式にGram-Schmidtの正規直交化法を適用する。
（３）Gram-Schmidtの正規直交化法により得られた多項式を記憶部に記憶する。これらの多項式が、行列表現ρ(g1),ρ(g2),…,ρ(gn)を生成するための正規直交基底ベクトルを構成する。
【００８３】
このようにして、正規直交基底計算部３は、nの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する。
【００８４】
ヤング図形の全順序について説明する。箱の数がnである同じヤング図形に数字を入れた異なる２つのヤング盤T1,T2に対し、T1<T2であるとは「あるi(1≦i≦n)が存在して、すべてのj(i<j≦n)について、jが属する列はT1とT2で同じであり、T1においてiが属する列はT2においてiが属する列よりも左にあること」と定義する。こうすると、「<」は箱の数がnであるヤング図形に数字を記入したヤング盤の集合の全順序となる。
【００８５】
上記の正規直交基底の計算手法をS4に適用した場合の例について説明する。xiとxj(j≠i)は、互いに独立であるとする。
【００８６】
１．箱の数が４であるヤング図形は図１１に示すように５個ある。それを図１１の順に並べる。
【００８７】
２．まず、λ1に対し、以下の操作を行う。
（１）λ1に対する標準ヤング盤は図１２に図示するようにただ１つ存在する。
（２）これに対応するシュペヒト多項式は１である。これにGram-Schmidtの正規直交化法を適用すると、v1=1となる。
【００８８】
３．次に、λ2に対して以下の操作を行う。
（１）λ2に対する標準ヤング盤は図１３に示すように３個存在する。左の方ほど順序が小さい。
（２）これらに対応するシュペヒト多項式はそれぞれ以下の通り。
【００８９】
【数２０】
0005700827.tif 000021
【００９０】
これらのシュペヒト多項式に対して右から順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【００９１】
【数２１】
0005700827.tif 000022
【００９２】
４．λ3に対する操作は以下の通り。
（１）λ3に対する標準ヤング盤は図１４に示すように２個存在する。左の方ほど順序が小さい。
（２）これらに対応するシュペヒト多項式は以下の通り。
【００９３】
【数２２】
0005700827.tif 000023
【００９４】
これらのシュペヒト多項式に対して右から順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【００９５】
【数２３】
0005700827.tif 000024
【００９６】
５．λ4に対する操作は以下の通り。
（１）λ4に対する標準ヤング盤は図１５に示すように３個存在する。左の方ほど順序が小さい。
【００９７】
【数２４】
0005700827.tif 000025
【００９８】
これらのシュペヒト多項式に対して後ろから順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【００９９】
【数２５】
0005700827.tif 000026
【０１００】
６．最後に、λ5に対する操作は以下の通り。
（１）λ5に対する標準ヤング盤は図１６に示すようにただ１つ存在する。
（２）これに対応するシュペヒト多項式は以下である。
【０１０１】
【数２６】
0005700827.tif 000027
【０１０２】
これにGram-Schmidtの直交化法を適用すると、以下の通りとなる。
【０１０３】
【数２７】
0005700827.tif 000028
【０１０４】
次に、量子回路生成部４について説明する。量子回路生成部４は、以下のようにして、正規直交基底計算部３で求めたSnの正規直交基底を用いてSn上のフーリエ変換FSnの行列Gnの量子回路を構成する。
【０１０５】
Sn-1の各表現を
【０１０６】
【数２８】
0005700827.tif 000029
【０１０７】
とし、(an-1はSn-1の表現の個数）、ブラテリダイアグラム上でのρi（ｉ=1,2,…,an-1)の子ノードを
【０１０８】
【数２９】
0005700827.tif 000030
【０１０９】
とする。図７に示すように、ρij(j=1,2,…,ti)には重複がある。例えば、図７の例では、ブラテリダイアグラムの上から４番目の階層の左から２つ目のノードには、ρ12とρ21の２つの表記が対応付けられている。ρ12とρ21が示すノードは同じである。
【０１１０】
Snの元を、g0=(1,2,3,…,n)0, g1=(1,2,3,…,n)1,g2=(1,2,3,…,n)2,…,gn-1=(1,2,3,…,n)n-1とする。
【０１１１】
このとき、Gnは、図８に例示するように、
【０１１２】
【数３０】
0005700827.tif 000031
【０１１３】
の直和で表現される。また、それぞれのiに対して、
【０１１４】
【数３１】
0005700827.tif 000032
【０１１５】
はすべて同じである。この行列を、Mρiと書くことにする。各iに対するMρiを決定することができれば、Gnが求まる。
【０１１６】
Mρiは、ρ(gb)(b=0,1,…,n-1)により構成される。ρ(gb)は、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρij(gb)の直和である行列表現である。図１８に、n=4の場合のρ(gi)を模式的に表す。なお、図１８では、ρ(gb)のことをρ(gi)と表記している。
【０１１７】
行列表現ρij(gb)は、既約表現ρijについての標準ヤング盤に対応する正規直交基底を用いて構成される。具体的には、行列表現ρij(gb)は、Snの元gbを、既約表現ρij(j=1,2,…,ti)についての標準ヤング盤に対応する正規直交基底が構成するベクトルに作用させることにより構成される。Snの元gbをベクトルに作用させるとは、gnで定義された置換をベクトルに施すことを意味する。例えば、gn=(1,2)であり１と２の互換である場合には、正規直交基底が構成するベクトルの中のx1とx2とを互いに入れ替えることを意味する。既約表現ρijについての標準ヤング盤に対応する正規直交基底をvi,k(k=1,…,K)と表記する。このとき既約表現ρijについての標準ヤング盤に対応する正規直交基底vi,k(k=1,…,K)が構成するベクトルv→は、v→=(vi,1,vi,2,…,vi,K)Tとなる。v→にgbを作用させたベクトルをv→＊とする。このとき、行列表現ρij(gb)は、v→＊=ρij(gb) ・v→の関係を満たす行列である。・Tは行列・の転置行列とする。
【０１１８】
量子回路生成部４は、まず各(i,j)の組についてこの行列表現ρij(gb)を求めて、求まったρij(gb)の直和を取りρ(gb)とする。直和とは例えば図１８に例示するように、左上から右下に向かって行列を加えることを意味する。
【０１１９】
このようにして、量子回路生成部４は、各b(b=0,1,…,n-1)についての行列表現ρ(gb)を生成する。図１９の上段にn=4の場合の各ρ(gb)(b=0,1,…,3)を模式的に表す。
【０１２０】
量子回路生成部４は、生成された行列表現ρ(g0),ρ(g1),…,ρ(gn-1)を構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρi・n×dρi・nの行列Mρiを構成する処理を各iについて行う。
【０１２１】
そして、量子回路生成部４は、dρ1個のMρ1,dρ2個のMρ2,…,dρan-1個のMρan-1の直和を行列Gnとする。
【０１２２】
図１９は、n=4の場合に、ρ(g0),ρ(g1),ρ(g2),ρ(g3)からMρ1,Mρ2,Mρ3を構成し、これらのMρ1,Mρ2,Mρ3からG4を構成する様子を模式的に示した図である。n=4の場合には、図１９のように、G4は、上から順に４×４、８×８、８×８、４×４の行列Mρ1,Mρ2,Mρ2,Mρ3が対角に並んだ形となる。
【０１２３】
図１９に示すように、各Mρiは、4個のハッチングが同じ列行列の組み合わせで構成されている（実際には列行列は所定の値を乗算した後に組み合わせられる。）。Mρiのハッチングが同じ列行列の内一番左の列行列はρ(g0)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内左から２番目の列行列はρ(g1)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内右から２番目の列行列はρ(g2)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内一番右の列行列はρ(g3)の同じハッチングの列行列に由来する。
【０１２４】
例えば、図１９に示すように、Mρ1の第１行目を構成する一番左の列行列はρ(g0)のρ11(g0)に由来し、Mρ1の第１行目を構成する左から２番目の列行列はρ(g1)のρ11(g1)に由来し、Mρ1の第１行目を構成する右から２番目の列行列はρ(g2)のρ11(g2)に由来し、Mρ1の第１行目を構成する一番右の列行列はρ(g3)のρ11(g3)に由来する。
【０１２５】
nが４より大の場合も図１９と同様にしてGnを計算することができる。
【０１２６】
量子回路生成部４は、具体的には、以下のアルゴリズムに基づいて、行列Gnを計算する。
【０１２７】
ρij(gb)(b=0,1,…,n)のx番目の列行列をρij(gb)[x]と書くことにする。ρij(gb)[x]はdρij×1行列である。また、Mρi[k,l]を、Mρiの
【０１２８】
【数３２】
0005700827.tif 000033
【０１２９】
要素を先頭とするdρij×１小行列
【０１３０】
【数３３】
0005700827.tif 000034
【０１３１】
を表すものとする。Mρi[k,l]（i=1,2,…,an-1, k=1,2,…,ti, l=1,2,…dρi・n）は、ρij(gb)[x](i=1,2,…,an-1, j=1,2,…,ti, b=0,1,…,n, x=1,2,…,dρij)から以下のように求めることができる。図１７は、以下の手順に対応するフローチャートである。
【０１３２】
Snの表現ρijに対して、xρijを整数変数とする。
[ステップ1] すべてのρijに対してxρij=1とおく。(i=1,2,…,an-1, j=1,2,…,ti)
[ステップ2] i=1とおく。
[ステップ3] k=1とおく。
[ステップ4] l=1からdρｉ・nまでlの値を1ずつ上げながら、
【０１３３】
【数３４】
0005700827.tif 000035
【０１３４】
かつ、もしlがnで割り切れればxρik=xρik+1。
[ステップ5] もしk<tiならばk=k+1としてステップ4に移動。もしk=tiならばステップ6に移動。
[ステップ6] もしi<an-1ならばi=i+1としてステップ3に移動。もしi=an-1ならば終了。
【０１３５】
n=3のときは、giは4×4のブロック対角行列で表される。
【０１３６】
【数３５】
0005700827.tif 000036
【０１３７】
ここから、上記アルゴリズムを用い、以下のように6×6行列を定義する。
【０１３８】
【数３６】
0005700827.tif 000037
【０１３９】
すると、FS3=G3(FS2(×)I3)を計算すると、対称群S3上の量子フーリエ変換Fs3が求まる。
【０１４０】
式(2)の行列分解が求まると、そこから量子回路を作成することができる。Gnは、
【０１４１】
【数３７】
0005700827.tif 000038
【０１４２】
と表現されるので、制御ユニタリゲートの系列である。ここで、dρiはブラテリダイアグラムのn-1段目の左からi番目の数字であり、iの増加とともに指数的に増大する。
【０１４３】
例えば、図２０に示す回路は、FS4の量子回路の一例である。第一、第二、第三番目の線はそれぞれqubit, qutrit, quatritをあらわす。quatritは、１つの素子で|0>,|1>,|2>,|3>の4状態の重ね合わせ状態を表現する素子である。
【０１４４】
二番目の線の最後の◆は|i2>=|2>の場合の制御オペレーションを意味する。また左側の×―×という記号は、通常の交換演算ではなく、
【０１４５】
【数３８】
0005700827.tif 000039
【０１４６】
という操作、右側の×―×という記号は上記の転置行列で表される操作を意味する。
【０１４７】
［変形例等］
量子回路生成装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【０１４８】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【０１４９】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【０１５０】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１５１】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【図１】
0005700827.tif 000040
【図２】
0005700827.tif 000041
【図３】
0005700827.tif 000042
【図４】
0005700827.tif 000043
【図５】
0005700827.tif 000044
【図６】
0005700827.tif 000045
【図７】
0005700827.tif 000046
【図８】
0005700827.tif 000047
【図９】
0005700827.tif 000048
【図１０】
0005700827.tif 000049
【図１１】
0005700827.tif 000050
【図１２】
0005700827.tif 000051
【図１３】
0005700827.tif 000052
【図１４】
0005700827.tif 000053
【図１５】
0005700827.tif 000054
【図１６】
0005700827.tif 000055
【図１７】
0005700827.tif 000056
【図１８】
0005700827.tif 000057
【図１９】
0005700827.tif 000058
【図２０】
0005700827.tif 000059
【図２１】
0005700827.tif 000060