"nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn1番目の階層のan1個ノードにそれぞれ対応するan1個の既約表現をρiとし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρijとし、既約表現ρiρijの表現空間の次元数をそれぞれdρidρijとして、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算部と、b012...n1とし、gbb∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρijの直和である行列表現ρを生成する処理を各bについて行い、生成された行列表現ρρ...ρを構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρin×dρinの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1dρ2個のMρ2...dρan1個のMρan1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn1上の量子フーリエ変換をFSn1とし、をテンソル積とし、Pn1をFSn1をInに変換する置換とし、†を行列の共役転置とし、GnPn1FSn1Pn1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成部と、を含む量子回路生成装置。請求項1の量子回路生成装置において、上記正規直交基底計算部は、各上記標準ヤング盤に対応するシュペヒト多項式を生成し、生成されたシュペヒト多項式をグラムシューミットの正規直交化法で互いに直交させて上記正規直交規定とする、量子回路生成装置。nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn1番目の階層のan1個ノードにそれぞれ対応するan1個の既約表現をρiとし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρijとし、既約表現ρiρijの表現空間の次元数をそれぞれdρidρijとして、正規直交基底計算部が、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算ステップと、量子回路生成部が、b012...n1とし、gbb∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρijの直和である行列表現ρを生成する処理を各bについて行い、生成された行列表現ρρ...ρを構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρin×dρinの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1dρ2個のMρ2...dρan1個のMρan1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn1上の量子フーリエ変換をFSn1とし、をテンソル積とし、Pn1をFSn1をInに変換する置換とし、†を行列の共役転置とし、GnPn1FSn1Pn1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成ステップと、を含む量子回路生成方法。請求項1又は2の量子回路生成装置の各部としてコンピュータを機能させるためのプログラム。請求項4のプログラムが記録されたコンピュータ読み取り可能な記録媒体。しかしながら、非特許文献1及び2では、対称群Sn上の量子フーリエ変換に対して効率的な、すなわち多項式サイズの量子回路が存在することが理論的に示されているものの、具体的な量子回路の構成方法までは示されていない。量子コンピュータ上で演算を実行するためには、具体的な量子回路を構成する必要がある。この発明の目的は、対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成する量子回路生成方法、プログラム及びその記録媒体を提供することである。この発明の一態様による量子回路生成装置は、nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn1番目の階層のan1個ノードにそれぞれ対応するan1個の既約表現をρiとし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρijとし、既約表現ρiρijの表現空間の次元数をそれぞれdρidρijとして、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する正規直交基底計算部と、b012...n1とし、gbb∈Snとして、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する正規直交基底を用いてgbを表した行列表現ρijの直和である行列表現ρを生成する処理を各bについて行い、生成された行列表現ρρ...ρを構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρin×dρinの行列Mρiを構成する処理を各iについて行い、dρ1個のMρ1dρ2個のMρ2...dρan1個のMρan1の直和を行列Gnとし、n次正方行列をInとし、対称群Sn1上の量子フーリエ変換をFSn1とし、をテンソル積とし、Pn1をFSn1をInに変換する置換とし、†を行列の共役転置とし、GnPn1FSn1Pn1†を対称群Sn上の量子フーリエ変換FSnとする量子回路生成部と、を含む。対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成することができる。まず、この発明を理解するための背景知識について説明する。Snnは自然数上の量子フーリエ変換を定義する前に、S2S3の場合の例を用いながら対称群の表現論の基礎を解説する。Gを群とする。適当なベクトル空間Vに対して、写像ρG→Uが群の演算と可換になるときつまり写像が準同型のとき、ρを表現と呼び、Vを表現空間と呼ぶ。W⊆Vがρで不変になるとき、Wを不変部分空間と呼ぶ。V空間全体と0は明らかに普遍不変なため、自明な不変部分空間と呼ばれる。不変部分空間として自明なものしか存在しないとき、ρを既約表現と呼ぶ。例えば、S3の元をg0g1g2g3g4g5と表記する。対称群は、全ての並べ替えの操作を元とする集合である。g0は単位元、つまり、順番を何も変えない操作を表す。は、aをbに、bをcに、cをaに順番を1つずつ後ろにずらす操作を意味する。は、aとbを入れ替える操作である。このとき、で定義されるρは、準同型写像であるため表現であるが、既約ではない。なぜなら、は非自明な不変部分空間だからである。後に述べるとおりS3の既約表現は3つしかなく、上記の表現はその中には入らない。一般に、Snの既約表現はヤング図形Youngdiagramによって列挙することができる。ヤング図形を用いたSnの表現論の詳細は専門書に譲り、ここでは発明を理解するために必要な最小限の説明にとどめる。ヤング図形とは、四角い箱を左上づめに並べた図形である。図2に、箱の数が234の場合のヤング図形をすべて列挙する。図2のλの式で表現されるように、各ヤング図形は上から順に列ごとの箱の数をリスト形式で並べた形で記述される。n3の例を見ると、λは1列に3つの箱が並んだヤング図形に対応し、λは一列目に2個、二列目に1個の箱が並んだヤング図形に対応し、λは一列目に1個、二列目に1個、3列目に1個の箱を並べたヤング図形に対応する。Snの既約表現は、箱の数がnのヤング図形に一対一で対応することが知られている。S3の既約表現が3つなのは、n3の場合のヤング図形が3種類であるためである。ヤング図形のそれぞれの箱に数字を書き込んだ図形をヤング盤Youngtableauと呼ぶ。ヤング盤を図3に例示する。ヤング盤の中で、全ての行と列に関して、書き込まれる数字が下に行くほど大きく、かつ右に行くほど大きくなっているものを標準ヤング盤と呼ぶ。標準ヤング盤を図4に例示する。各ヤング図形に対する標準ヤング盤の数は、ヤング図形に対応する表現の表現空間の次元数に一致することが知られている。表現ρに対する表現空間の次元数をdρで表す。すると、次の式が成立する。ρをSnの表現全体の直和とすると、ρはΣρdρ次元の空間上のユニタリ行列で表現できる。例えば、n2の場合、ヤング図形の数は2で、標準ヤング盤の個数は112なので、S2の各元は2×2行列で表現できる。また、n3の場合、ヤング図形の数は3で、標準ヤング盤の個数は1214なので、Snの各元は4×4行列で表現できる。各行列は、1×1、2×2、1×1のブロック行列の直和となっている。次に、対称群上の量子フーリエ変換について説明する。上記の4×4で表現されたρρ...ρの行列の要素に、定数を掛けて並べると、量子フーリエ変換になる。対称群S2上の量子フーリエ変換FS2及び対称群S3上の量子フーリエ変換FS3を具体的に書くと、以下のようになる。FS2はアダマール変換に等しい。FS3は以下のように書き換えることができる。FS3の量子回路を図5に示す。ここで、1番目の線はqubit、2番目の線はqutritを表す。なお、qubitは1つの素子で0と1の2状態の重ね合わせ状態を表現する素子であり、qutritは1つの素子で012の3状態の重ね合わせ状態を表現する素子である。また、図5で白丸で示された2番目のゲートは制御ビットである1番目のビットが0のときに標的ビットである2番目のビットに2番目の線上に載っている3×3行列で表わされる演算を施すことを意味する。さらに、図5で黒丸で示された3番目のゲートは、いわゆるControlledrotationgateであり、制御ビットである1番目のビットが1のときに標的ビットである2番目のビットに2番目の線上に載っている3×3行列で表わされる演算を施すことを意味する。4以上のnに対する量子フーリエ変換Fsnは、ヤング図形の系統を図示したダイアグラムであるブラテリダイアグラムによりの帰納的な定義することができる。各ヤング図形は、それより1つ箱の数が多いヤング図形を子として持つと考えることにより、1つの箱からできたヤング図形を頂点とし、n段目のノードがn個の箱を持つヤング図形で構成される図で表現できる。これをブラテリダイアグラムと呼んでいる。ブラテリダイアグラムを図6に例示する。すでに説明したとおり、Snの既約表現はn個の箱を持つヤング図形に一対一に対応している。そこで、ブラテリダイアグラムのn段目を見れば、Snの既約表現が列挙されている。また、図6の各ノードに付された数字は、頂点を1として頂点からたどった各ノードまでの道の総数であり、各ヤング図形の表現空間の次元数に一致することが知られている。そこで、表現ρiに対応するヤング図形のノードに記された数字を表現空間の次元数と同じ記号であるdρiで表す。ブラテリダイアグラムの各ノードの数字に関して、以下のことが成り立つ。n4の場合を考える。S3の既約表現ρ1,ρ2,ρ3と、それらの子ノードρ11,ρ12,ρ21,ρ22,ρ23,ρ31,ρ32を図7に示す。ρ1の子ノートがρ11,ρ12であり、ρ2の子ノードがρ21,ρ22,ρ23であり、ρ3の子ノードがρ31,ρ32である。ρ2についてみると、式の左辺はdρ2n=24=8であり、式の右辺はΣj13dρ2j=323=8であり、両辺の値が一致することが確認できる。ブラテリダイアグラムの各ノードの数字から、量子フーリエ変換FSnを実行するために必要な行列のサイズ情報が得られる。対称群Sn上の量子フーリエ変換FSnは次のように分解されることが知られている。以下の行列において、空白の部分の成分は0である。このことは他の行列についても同様である。ここで、Gnは、図8のようなブロック対角行列である。Pn1はInFSn1をFSn1Inに変換する置換である。この式から、量子フーリエ変換FSnは、Gn...G3の積で表わせる。Inはn次元の単位行列であり、はテンソル積であり、†を行列の共役転置とする。FS2はアダマール変換なので、GnGn1...G3を実行できれば、量子フーリエ変換FSnを実行できる。そこで、この発明では、GnGn1G3の具体的な行列を構成する。Gnの行列表現は、Snの元iの行列表現によって決まる。iは、iだけ右にシフトする巡回置換である。例えば、1であり、nが奇数の場合には2であり、nが偶数の場合には2である。Gnの量子回路を構成するためには、まず行列表現を決定しなければならない。そして、Snの任意の元を行列で表現するためには、まず、表現空間の正規直交基底ベクトルを決定する必要がある。量子回路生成装置は、図9に示すように、入力部1、ブラテリダイアグラム取得部2、正規直交基底計算部3、量子回路生成部4、基本ゲート分解部5及び出力部6を備える。量子回路生成装置は、図21に例示された量子回路生成方法の各ステップの処理を行う。入力部1は、対称群の次数を取得する。入力部1は、例えばキーボード、マウス等の入力機器であり、それらの入力機器を用いてユーザにより対称群の次数が入力される。Snに対する量子フーリエ変換FSnの量子回路を生成する場合、次数nが入力される。次数nについての情報は、量子回路生成装置の各部に送信される。ブラテリダイアグラム取得部2は、図6に例示示したような対称群Snに対するブラテリダイアグラムについての情報を取得する。ブラテリダイアグラム取得部2は、ブラテリダイアグラムについての情報が予め記憶されたブラテリダイアグラム21からブラテリダイアグラムについての情報を読み込んでも良いし、必要に応じてブラテリダイアグラムについての情報を適宜計算してもよい。ブラテリダイアグラムについての情報は、正規直交基底計算部3及び量子回路生成部4に送信される。正規直交基底計算部3は、アダプテッドゲルファンドツェッテリン基底である正規直交基底を計算するステップS1。計算された正規直交基底は、表現空間の正規直交基底ベクトルを構成する。計算された正規直交基底についての情報は、量子回路生成部4に送信される。量子回路生成部4は、正規直交基底計算部3で求めた計算された正規直交基底から行列表現を求め、Gmに対する量子回路を生成し、対称群Sn上の量子フーリエ変換FSnの量子回路を生成するステップS2。生成された量子回路についての情報は、基本ゲート分解部5に送信される。基本ゲート分解部5は、量子回路生成部4で求めた量子回路を、量子コンピュータ上の基本演算の系列に変換するステップS3。この部分は周知技術を利用することができる。変換された量子コンピュータ上の基本演算の系列についての情報は、出力部6に送信される。量子回路生成部4で出力される量子回路は、qubitqutritquatritのように複数種類の素子を組み合わせて実現される演算系列となっている。実際の量子コンピュータ上で実行する際には、全てを同じ素子、例えばqubitに統一して、qubit上の1qubit又は2qubit間の演算を行う基本ゲートの系列に変換することが現実的である。Gmに対応する制御ユニタリ演算における標的ビットの演算であるdρin×dρin行列や上述の通常とは異なる交換演算は、より大きい2m×2m行列に埋め込み、例えば参考文献1に記載されたなどの分解方法を用いて、qubit上の基本ゲートの系列に変換してもよい。参考文献1YNakajimaYKawanoandHSekigawaANewAlgorithmforProducingQuantumCircuitsusingKAKDecompositionsQuantumInformationandComputationVol6No1pp67802006出力部6は、ディスプレイ、プリンタ等の出力装置であり、量子コンピュータ上の基本演算の系列についての情報を出力しユーザに知覚させる。以下、この発明の主要部である正規直交基底計算部3と量子回路生成部4について、詳細に説明する。まず、正規直交基底計算部3が生成するアダプテッドゲルファンドツェッテリン基底について説明する。Snの任意の元の行列表現を確定させるためには、まず、表現空間の正規直交基底ベクトルを定めなければならない。表現空間の正規直交基底ベクトルの取り方は一意ではないので、基底ベクトルの取り方によって異なる行列表現になる。しかし、後に量子回路を構成するときに効率的な量子回路とするためには、アダプテッドゲルファンドツェッテリン基底を選ぶ必要がある。ここで、ρのアダプテッドゲルファンドツェッテリン基底とは以下の条件を満たすorthonormalbasisv1...vdρのことである。ρはヤング図形と一対一で対応している。ブラテリダイアグラムにおけるρの親ノードに対応する表現を、とする。ブラテリダイアグラムの性質から、が成立する。ρをSnの表現とすると、任意のg∈Snは適当な正規直交基底を決めるとdρdρ行列で表現される。一方、ρiはSn1の表現なので、任意のg∈Sn1は適当な正規直交基底を決めるとdρidρi行列で表現される。このとき、任意のg∈Snに対して、が成立する正規直交基底をアダプテッドゲルファンドツェッテリン基底と呼ぶ。アダプテッドゲルファンドツェッテリン基底の存在は保証されているが、一意ではない。アダプテッドゲルファンドツェッテリン基底を用いると、Sn1の元はブロック対角行列で表現される。アダプテッドゲルファンドツェッテリン基底を適当に選ぶことにより、Snの任意の元はdρdρ行列で表現される。このように、Snの任意の元の行列表現が定まると、それに応じてSn上の量子フーリエ変換を以下のように定義することができる。ρα,βは、ρのα,β成分である。次に、シュペヒト多項式について説明する。Vandermonde行列式Δをと定義する。図10に、1×1の箱から構成されるヤング図形のVandermonde行列式Δ、2×1の箱から構成されるヤング図形のVandermonde行列式Δ、3×1の箱から構成されるヤング図形のVandermonde行列式Δ及び4×1の箱から構成されるヤング図形のVandermonde行列式Δを示す。行の数がm、列の数が1であるヤング盤Tに対し、シュペヒト多項式Δを、と定義し、行の数がmであり列の数がiである一般のヤング盤Tに対しは、シュペヒト多項式Δを、と定義する。ただし、TjはTの第j列を取り出したヤング盤、Δはヤング盤に書かれている数字を添え字としたVandermonde行列式である。例えば、Tが3列からなり、Tに書かれている数字が第1列の上から1、4、5、第2列の上から2、3、第3列の上から6、7なら、となる。gをSnの元とする。サイズがnのヤング盤Tに対応するシュペヒト多項式Δに対し、gを、Δにおいてxiの添え字iをgに書き換えたものとする。サイズがnのヤング図形を1つ固定し、それに1からnの数字を記入したヤング盤に対応するシュペヒト多項式全体の、係数を複素とする一次結合で書ける多項式全体は複素数上の有限次元のベクトル空間Vとなる。Vの基底として、標準ヤング盤に対応するシュペヒト多項式の全体を取ることができることが知られている。また、上記g∈Snの作用はVの線形変換に自然に拡張されるので、SnからUへの写像が得られる。この写像は準同型となるので、Vを表現空間とするSnの表現となる。この表現が既約であること、Snの既約表現は、サイズがnのすべてのヤング図形に対してこのように作った表現で尽くされることが知られている。ただし、標準ヤング盤に対応するシュペヒト多項式全体からなる基底は、アダプテッドゲルファンドツェッテリン基底にはなっていない。この実施形態では、アダプテッドゲルファンドツェッテリン基底を求めるために、以下の手順により、シュペヒト多項式にGramSchmidtの正規直交化法を適用する。これにより得られる多項式からなる基底はアダプテッドゲルファンドツェッテリン基底となる。1.正規直交基底計算部3は、箱の数がnであるヤング図形を読み込む。ヤング図形は、以下に示す全順序により一列に並べられているものとする。2.正規直交基底計算部3は、読み込んだヤング図形を先頭から順次1つずつ取り出し、以下の操作を行う。1取りだしたヤング図形に対する標準ヤング盤を全て展開し、上で定義した全順序により一列にならべる。すなわち、順序が大きいものを後ろにする。2標準ヤング盤を後ろから順に取り、対応するシュペヒト多項式にGramSchmidtの正規直交化法を適用する。3GramSchmidtの正規直交化法により得られた多項式を記憶部に記憶する。これらの多項式が、行列表現ρρ...ρを生成するための正規直交基底ベクトルを構成する。このようにして、正規直交基底計算部3は、nの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する。ヤング図形の全順序について説明する。箱の数がnである同じヤング図形に数字を入れた異なる2つのヤング盤T1T2に対し、T1123の4状態の重ね合わせ状態を表現する素子である。二番目の線の最後の◆はi22の場合の制御オペレーションを意味する。また左側の×―×という記号は、通常の交換演算ではなく、という操作、右側の×―×という記号は上記の転置行列で表される操作を意味する。[変形例等]量子回路生成装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。"