説明

量子回路生成装置、方法、プログラム及び記録媒体

【課題】対称群Sn上の量子フーリエ変換Fsnを実行するための多項式サイズの量子回路を生成する技術を提供する。
【解決手段】正規直交基底計算部3が、箱の数がnの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する。量子回路生成部4が、計算された正規直交基底を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とする。

【発明の詳細な説明】
【技術分野】
【0001】
この発明は、対称群上の量子フーリエ変換を多項式時間で実行できる量子回路を生成する技術に関する。
【背景技術】
【0002】
1994年、ショーアにより因数分解を高速に行う量子アルゴリズムが発見されて以降、世界中で量子アルゴリズムの研究が盛んに行われている。特に、ショーアの論文の末尾で提案された未解決問題は注目を集め、多くの研究者たちがそれらの問題に対する高速なアルゴリズムの発見を競ってきた。中でも、もっとも有名な問題はグラフ同型性判定問題である。グラフ同型性判定問題とは、2つのグラフが与えられたときに、それらのグラフの頂点間の写像で、辺を保存するものが存在するかどうかを判定する問題である。例えば、図1の例では、G1とG2は同型だが、それらとG3は同型ではない。グラフ同型性判定問題は、パターンマッチングの一種であり、高速なアルゴリズムが見つかれば、その応用範囲はきわめて広い。
【0003】
グラフ同型性判定問題は、因数分解よりも難しい問題で、現在のコンピュータ上で高速なアルゴリズムは見つかっていない。一方、グラフ同型性判定問題は量子コンピュータでも解くことが困難とされるNP完全問題よりやさしく、高速な量子アルゴリズムが見つかる可能性がある。
【0004】
ショーアのアルゴリズムで最も重要な量子回路は、{0,1,…,n−1}を元としてもつ巡回群であるZn上の量子フーリエ変換である。量子フーリエ変換には効率的な量子回路が存在し、このことが因数分解の効率的な実行に重要な役割を果たす。なぜなら、量子フーリエ変換はZnの部分群の周期情報を取り出す役割を果たすからである。ショーアのアルゴリズムをグラフ同型性判定問題に拡張するための最も素直な方法は、ショーアのアルゴリズムにおけるZn上の量子フーリエ変換を対称群Sn上の量子フーリエ変換で置き換えることである。ここで、対称群Snとは、与えられた自然数nに対して、n個の異なる文字の集合からそれ自身への一対一対応全体を表す。n個の文字に1,2,…,nという数字を割り当てれば、{1,2,…,n−1,n}の置換によって作られる群である。Snはn!個の元をもち、置換の積を群の演算とみなす。
【0005】
Sn上の量子フーリエ変換が多項式時間で実行できることを最初に示したのは、Beals(例えば、非特許文献1参照。)である。
【0006】
後にMooreらが、非可換群上の量子フーリエ変換を含む多くの変換に対して効率的な量子回路の存在を証明した(例えば、非特許文献2参照。)。ここでいう効率的な量子回路とは、入力量子ビット数nに対して多項式サイズO(poly(n))で構成できる量子回路が存在するということを意味する。
【先行技術文献】
【非特許文献】
【0007】
【非特許文献1】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.
【非特許文献2】C. Moore and D. Rockmore, “Generic quantum fourier transforms”, Technical Report quant-ph/0304064, Quantum Physics e-Print Archive, 2003.
【発明の概要】
【発明が解決しようとする課題】
【0008】
しかしながら、非特許文献1及び2では、対称群Sn上の量子フーリエ変換に対して効率的な、すなわち多項式サイズの量子回路が存在することが理論的に示されているものの、具体的な量子回路の構成方法までは示されていない。量子コンピュータ上で演算を実行するためには、具体的な量子回路を構成する必要がある。
【0009】
この発明の目的は、対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成する量子回路生成方法、プログラム及びその記録媒体を提供することである。
【課題を解決するための手段】
【0010】
この発明の一態様による量子回路生成装置は、nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρiijの表現空間の次元数をそれぞれdρi,dρ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とする量子回路生成部と、を含む。
【発明の効果】
【0011】
対称群Sn上の量子フーリエ変換を実行するための多項式サイズの量子回路を生成することができる。
【図面の簡単な説明】
【0012】
【図1】グラフ同型性判定問題を説明するための図。
【図2】ヤング図形を説明するための図。
【図3】ヤング盤を説明するための図。
【図4】標準ヤング図形を説明するための図。
【図5】対称群S3上の量子フーリエ変換Fs3の量子回路を例示する図。
【図6】ブラテリダイアグラムを説明するための図。
【図7】ブラテリダイアグラムの性質を説明するための図。
【図8】Mρiの構成を説明するための図。
【図9】実施形態の量子回路生成装置の構成を説明するためのブロック図。
【図10】Vandermonde行列式を説明するための図。
【図11】正規直交基底の計算の方法を説明するための図。
【図12】正規直交基底の計算の方法を説明するための図。
【図13】正規直交基底の計算の方法を説明するための図。
【図14】正規直交基底の計算の方法を説明するための図。
【図15】正規直交基底の計算の方法を説明するための図。
【図16】正規直交基底の計算の方法を説明するための図。
【図17】Mρiを計算するためのアルゴリズムのフローチャート。
【図18】ρ(gi)の構成を説明するための図。
【図19】G4の構成を説明するための図。
【図20】対称群S4上の量子フーリエ変換Fs4の量子回路を例示する図。
【図21】実施形態の量子回路生成装置を説明するためのフローチャート。
【発明を実施するための形態】
【0013】
まず、この発明を理解するための背景知識について説明する。
【0014】
Sn(nは自然数)上の量子フーリエ変換を定義する前に、S2,S3の場合の例を用いながら対称群の表現論の基礎を解説する。Gを群とする。適当なベクトル空間Vに対して、写像
ρ:G→U(V)
が群の演算と可換になるとき(つまり写像が準同型のとき)、ρを表現と呼び、Vを表現空間と呼ぶ。W⊆Vがρ(G)で不変になるとき、Wを不変部分空間と呼ぶ。V(空間全体)と{0}は明らかに普遍不変なため、自明な不変部分空間と呼ばれる。不変部分空間として自明なものしか存在しないとき、ρを既約表現と呼ぶ。
【0015】
例えば、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に順番を1つずつ後ろにずらす操作を意味する。(a,b)は、aとbを入れ替える操作である。
【0016】
このとき、
【0017】
【数1】

【0018】
で定義されるρは、準同型写像であるため表現であるが、既約ではない。なぜなら、
【0019】
【数2】

【0020】
は非自明な不変部分空間だからである。後に述べるとおりS3の既約表現は3つしかなく、上記の表現はその中には入らない。
【0021】
一般に、Snの既約表現はヤング図形(Young diagram)によって列挙することができる。ヤング図形を用いたSnの表現論の詳細は専門書に譲り、ここでは発明を理解するために必要な最小限の説明にとどめる。ヤング図形とは、四角い箱を左上づめに並べた図形である。図2に、箱の数が2,3,4の場合のヤング図形をすべて列挙する。図2のλの式で表現されるように、各ヤング図形は上から順に列ごとの箱の数をリスト形式で並べた形で記述される。n=3の例を見ると、λ=(3)は1列に3つの箱が並んだヤング図形に対応し、λ=(2,1)は一列目に2個、二列目に1個の箱が並んだヤング図形に対応し、λ=(1,1,1)は一列目に1個、二列目に1個、3列目に1個の箱を並べたヤング図形に対応する。
【0022】
Snの既約表現は、箱の数がnのヤング図形に一対一で対応することが知られている。S3の既約表現が3つなのは、n=3の場合のヤング図形が3種類であるためである。
【0023】
ヤング図形のそれぞれの箱に数字を書き込んだ図形をヤング盤(Young tableau)と呼ぶ。ヤング盤を図3に例示する。ヤング盤の中で、全ての行と列に関して、書き込まれる数字が下に行くほど大きく、かつ右に行くほど大きくなっているものを標準ヤング盤と呼ぶ。標準ヤング盤を図4に例示する。
【0024】
各ヤング図形に対する標準ヤング盤の数は、ヤング図形に対応する表現の表現空間の次元数に一致することが知られている。表現ρに対する表現空間の次元数をdρで表す。すると、次の式が成立する。
【0025】
【数3】

【0026】
(+)ρをSnの表現全体の直和とすると、(+)ρはΣρdρ次元の空間上のユニタリ行列で表現できる。例えば、n=2の場合、ヤング図形の数は2で、標準ヤング盤の個数は1+1=2なので、S2の各元は2×2行列で表現できる。
【0027】
【数4】

【0028】
また、n=3の場合、ヤング図形の数は3で、標準ヤング盤の個数は1+2+1=4なので、Snの各元は4×4行列で表現できる。各行列は、1×1、2×2、1×1のブロック行列の直和となっている。
【0029】
【数5】

【0030】
次に、対称群上の量子フーリエ変換について説明する。上記の4×4で表現されたρ(g1),ρ(g2),…,ρ(g5)の行列の要素に、定数を掛けて並べると、量子フーリエ変換になる。対称群S2上の量子フーリエ変換FS2及び対称群S3上の量子フーリエ変換FS3を具体的に書くと、以下のようになる。
【0031】
【数6】

【0032】
FS2はアダマール変換に等しい。FS3は以下のように書き換えることができる。
【0033】
【数7】

【0034】
FS3の量子回路を図5に示す。ここで、1番目の線はqubit、2番目の線はqutritを表す。なお、qubitは1つの素子で|0>と|1>の2状態の重ね合わせ状態を表現する素子であり、qutritは1つの素子で|0>,|1>,|2>の3状態の重ね合わせ状態を表現する素子である。また、図5で白丸で示された2番目のゲートは制御ビットである1番目のビットが|0>のときに標的ビットである2番目のビットに2番目の線上に載っている3×3行列で表わされる演算を施すことを意味する。さらに、図5で黒丸で示された3番目のゲートは、いわゆるControlled rotation gateであり、制御ビットである1番目のビットが|1>のときに標的ビットである2番目のビットに2番目の線上に載っている3×3行列で表わされる演算を施すことを意味する。
【0035】
4以上のnに対する量子フーリエ変換Fsnは、ヤング図形の系統を図示したダイアグラムであるブラテリダイアグラムによりの帰納的な定義することができる。
【0036】
各ヤング図形は、それより1つ箱の数が多いヤング図形を子として持つと考えることにより、1つの箱からできたヤング図形を頂点とし、n段目のノードがn個の箱を持つヤング図形で構成される図で表現できる。これをブラテリダイアグラムと呼んでいる。ブラテリダイアグラムを図6に例示する。
【0037】
すでに説明したとおり、Snの既約表現はn個の箱を持つヤング図形に一対一に対応している。そこで、ブラテリダイアグラムのn段目を見れば、Snの既約表現が列挙されている。また、図6の各ノードに付された数字は、頂点を1として頂点からたどった各ノードまでの道の総数であり、各ヤング図形の表現空間の次元数に一致することが知られている。そこで、表現ρに対応するヤング図形のノードに記された数字を表現空間の次元数と同じ記号であるdρiで表す。
【0038】
ブラテリダイアグラムの各ノードの数字に関して、以下のことが成り立つ。
【0039】
【数8】

【0040】
【数9】

【0041】
n=4の場合を考える。S3の既約表現ρ1,ρ2,ρ3と、それらの子ノードρ11,ρ12,ρ21,ρ22,ρ23,ρ31,ρ32を図7に示す。ρ1の子ノートがρ11,ρ12であり、ρ2の子ノードがρ21,ρ22,ρ23であり、ρ3の子ノードがρ31,ρ32である。ρ2についてみると、式(1)の左辺はdρ2・n=2・4=8であり、式(1)の右辺はΣj=13dρ2j=3+2+3=8であり、両辺の値が一致することが確認できる。
【0042】
ブラテリダイアグラムの各ノードの数字から、量子フーリエ変換FSnを実行するために必要な行列のサイズ情報が得られる。対称群Sn上の量子フーリエ変換FSnは次のように分解されることが知られている。以下の行列において、空白の部分の成分は0である。このことは他の行列についても同様である。
【0043】
【数10】

【0044】
ここで、Gnは、図8のようなブロック対角行列である。Pn-1はIn(×)FSn-1をFSn-1(×)Inに変換する置換である。この式から、量子フーリエ変換FSnは、Gn,…,G3の積で表わせる。Inはn次元の単位行列であり、(×)はテンソル積であり、・を行列・の共役転置とする。
【0045】
【数11】

【0046】
FS2はアダマール変換なので、Gn,Gn-1,…,G3を実行できれば、量子フーリエ変換FSnを実行できる。そこで、この発明では、Gn,Gn-1,...,G3の具体的な行列を構成する。
【0047】
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の任意の元を行列で表現するためには、まず、表現空間の正規直交基底ベクトルを決定する必要がある。
【0048】
量子回路生成装置は、図9に示すように、入力部1、ブラテリダイアグラム取得部2、正規直交基底計算部3、量子回路生成部4、基本ゲート分解部5及び出力部6を備える。量子回路生成装置は、図21に例示された量子回路生成方法の各ステップの処理を行う。
【0049】
入力部1は、対称群の次数を取得する。入力部1は、例えばキーボード、マウス等の入力機器であり、それらの入力機器を用いてユーザにより対称群の次数が入力される。Snに対する量子フーリエ変換FSnの量子回路を生成する場合、次数nが入力される。次数nについての情報は、量子回路生成装置の各部に送信される。
【0050】
ブラテリダイアグラム取得部2は、図6に例示示したような対称群Snに対するブラテリダイアグラムについての情報を取得する。ブラテリダイアグラム取得部2は、ブラテリダイアグラムについての情報が予め記憶されたブラテリダイアグラム21からブラテリダイアグラムについての情報を読み込んでも良いし、必要に応じてブラテリダイアグラムについての情報を適宜計算してもよい。ブラテリダイアグラムについての情報は、正規直交基底計算部3及び量子回路生成部4に送信される。
【0051】
正規直交基底計算部3は、アダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)である正規直交基底を計算する(ステップS1)。計算された正規直交基底は、表現空間の正規直交基底ベクトルを構成する。計算された正規直交基底についての情報は、量子回路生成部4に送信される。
【0052】
量子回路生成部4は、正規直交基底計算部3で求めた計算された正規直交基底から行列表現を求め、Gm(m=3,4,…,n)に対する量子回路を生成し、対称群Sn上の量子フーリエ変換FSnの量子回路を生成する(ステップS2)。生成された量子回路についての情報は、基本ゲート分解部5に送信される。
【0053】
基本ゲート分解部5は、量子回路生成部4で求めた量子回路を、量子コンピュータ上の基本演算の系列に変換する(ステップS3)。この部分は周知技術を利用することができる。変換された量子コンピュータ上の基本演算の系列についての情報は、出力部6に送信される。
【0054】
量子回路生成部4で出力される量子回路は、qubit, qutrit, quatritのように複数種類の素子を組み合わせて実現される演算系列となっている。実際の量子コンピュータ上で実行する際には、全てを同じ素子、例えばqubitに統一して、qubit上の1qubit又は2qubit間の演算を行う基本ゲートの系列に変換することが現実的である。Gm(m=3,4,...,n)に対応する制御ユニタリ演算における標的ビットの演算であるdρi・n×dρi・n行列(i=1,2,...,an-1)や上述の通常とは異なる交換演算は、より大きい2m×2m行列に埋め込み、例えば参考文献1に記載されたなどの分解方法を用いて、qubit上の基本ゲートの系列に変換してもよい。
【0055】
〔参考文献1〕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.
出力部6は、ディスプレイ、プリンタ等の出力装置であり、量子コンピュータ上の基本演算の系列についての情報を出力しユーザに知覚させる。
【0056】
以下、この発明の主要部である正規直交基底計算部3と量子回路生成部4について、詳細に説明する。
【0057】
まず、正規直交基底計算部3が生成するアダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)について説明する。Snの任意の元の行列表現を確定させるためには、まず、表現空間の正規直交基底ベクトルを定めなければならない。表現空間の正規直交基底ベクトルの取り方は一意ではないので、基底ベクトルの取り方によって異なる行列表現になる。しかし、後に量子回路を構成するときに効率的な量子回路とするためには、アダプテッドゲルファンドツェッテリン基底を選ぶ必要がある。ここで、ρのアダプテッドゲルファンドツェッテリン基底(adapted Gel’fand-Tsetlin Basis)とは以下の条件を満たすorthonormal basis v1,…,vのことである。
【0058】
ρはヤング図形と一対一で対応している。ブラテリダイアグラムにおけるρの親ノードに対応する表現を、
【0059】
【数12】

【0060】
とする。ブラテリダイアグラムの性質から、
【0061】
【数13】

【0062】
が成立する。ρをSnの表現とすると、任意のg∈Snは適当な正規直交基底を決めるとdρ・dρ行列で表現される。一方、ρ(i=1,2,…,an-1)はSn-1の表現なので、任意のg∈Sn-1は適当な正規直交基底を決めるとdρi・dρi行列で表現される。このとき、任意のg∈Snに対して、
【0063】
【数14】

【0064】
が成立する正規直交基底をアダプテッドゲルファンドツェッテリン基底と呼ぶ。アダプテッドゲルファンドツェッテリン基底の存在は保証されているが、一意ではない。アダプテッドゲルファンドツェッテリン基底を用いると、Sn-1の元はブロック対角行列で表現される。
【0065】
アダプテッドゲルファンドツェッテリン基底を適当に選ぶことにより、Snの任意の元はdρ・dρ行列で表現される。このように、Snの任意の元の行列表現が定まると、それに応じてSn上の量子フーリエ変換を以下のように定義することができる。[ρ(g)]α,βは、ρ(g)の[α,β]成分である。
【0066】
【数15】

【0067】
次に、シュペヒト(Spechet)多項式について説明する。Vandermonde行列式Δ(x1,…,xn)を
【0068】
【数16】

【0069】
と定義する。図10に、1×1の箱から構成されるヤング図形のVandermonde行列式Δ(x1)、2×1の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2)、3×1の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2,x3)及び4×1の箱から構成されるヤング図形のVandermonde行列式Δ(x1,x2,x3,x4)を示す。
【0070】
行の数がm、列の数が1であるヤング盤Tに対し、シュペヒト多項式Δ(T)を、
【0071】
【数17】

【0072】
と定義し、行の数がmであり列の数がiである一般のヤング盤Tに対しは、シュペヒト多項式Δ(T)を、
【0073】
【数18】

【0074】
と定義する。
【0075】
ただし、TjはTの第j列を取り出したヤング盤、Δ(Tj)はヤング盤に書かれている数字を添え字としたVandermonde行列式である。例えば、Tが3列からなり、Tに書かれている数字が第1列の上から1、4、5、第2列の上から2、3、第3列の上から6、7なら、
【0076】
【数19】

【0077】
となる。
【0078】
gをSnの元とする。サイズがnのヤング盤Tに対応するシュペヒト多項式Δ(T)に対し、g(Δ(T))を、Δ(T)においてxiの添え字iをg(i)に書き換えたものとする。サイズがnのヤング図形を1つ固定し、それに1からnの数字を記入したヤング盤に対応するシュペヒト多項式全体の、係数を複素とする一次結合で書ける多項式全体は複素数上の有限次元のベクトル空間Vとなる。
【0079】
Vの基底として、標準ヤング盤に対応するシュペヒト多項式の全体を取ることができることが知られている。また、上記g∈Snの作用はVの線形変換に自然に拡張されるので、SnからU(V)への写像が得られる。この写像は準同型となるので、Vを表現空間とするSnの表現となる。この表現が既約であること、Snの既約表現は、サイズがnのすべてのヤング図形に対してこのように作った表現で尽くされることが知られている。ただし、標準ヤング盤に対応するシュペヒト多項式全体からなる基底は、アダプテッドゲルファンドツェッテリン基底にはなっていない。
【0080】
この実施形態では、アダプテッドゲルファンドツェッテリン基底を求めるために、以下の手順により、シュペヒト多項式にGram-Schmidtの正規直交化法を適用する。これにより得られる多項式からなる基底はアダプテッドゲルファンドツェッテリン基底となる。
【0081】
1.正規直交基底計算部3は、箱の数がnであるヤング図形を読み込む。ヤング図形は、以下に示す全順序により一列に並べられているものとする。
【0082】
2.正規直交基底計算部3は、読み込んだヤング図形を先頭から順次1つずつ取り出し、以下の操作を行う。
(1)取りだしたヤング図形に対する標準ヤング盤を全て展開し、上で定義した全順序により一列にならべる。すなわち、順序が大きいものを後ろにする。
(2)標準ヤング盤を後ろから順に取り、対応するシュペヒト多項式にGram-Schmidtの正規直交化法を適用する。
(3)Gram-Schmidtの正規直交化法により得られた多項式を記憶部に記憶する。これらの多項式が、行列表現ρ(g1),ρ(g2),…,ρ(gn)を生成するための正規直交基底ベクトルを構成する。
【0083】
このようにして、正規直交基底計算部3は、nの標準ヤング盤のそれぞれに対応するアダプテッドゲルファンドツェッテリン基底である正規直交基底を計算する。
【0084】
ヤング図形の全順序について説明する。箱の数がnである同じヤング図形に数字を入れた異なる2つのヤング盤T1,T2に対し、T1<T2であるとは「あるi(1≦i≦n)が存在して、すべてのj(i<j≦n)について、jが属する列はT1とT2で同じであり、T1においてiが属する列はT2においてiが属する列よりも左にあること」と定義する。こうすると、「<」は箱の数がnであるヤング図形に数字を記入したヤング盤の集合の全順序となる。
【0085】
上記の正規直交基底の計算手法をS4に適用した場合の例について説明する。xiとxj(j≠i)は、互いに独立であるとする。
【0086】
1.箱の数が4であるヤング図形は図11に示すように5個ある。それを図11の順に並べる。
【0087】
2.まず、λ1に対し、以下の操作を行う。
(1)λ1に対する標準ヤング盤は図12に図示するようにただ1つ存在する。
(2)これに対応するシュペヒト多項式は1である。これにGram-Schmidtの正規直交化法を適用すると、v1=1となる。
【0088】
3.次に、λ2に対して以下の操作を行う。
(1)λ2に対する標準ヤング盤は図13に示すように3個存在する。左の方ほど順序が小さい。
(2)これらに対応するシュペヒト多項式はそれぞれ以下の通り。
【0089】
【数20】

【0090】
これらのシュペヒト多項式に対して右から順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【0091】
【数21】

【0092】
4.λ3に対する操作は以下の通り。
(1)λ3に対する標準ヤング盤は図14に示すように2個存在する。左の方ほど順序が小さい。
(2)これらに対応するシュペヒト多項式は以下の通り。
【0093】
【数22】

【0094】
これらのシュペヒト多項式に対して右から順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【0095】
【数23】

【0096】
5.λ4に対する操作は以下の通り。
(1)λ4に対する標準ヤング盤は図15に示すように3個存在する。左の方ほど順序が小さい。
【0097】
【数24】

【0098】
これらのシュペヒト多項式に対して後ろから順にGram-Schmidtの正規直交化法を適用すると、以下の通りとなる。
【0099】
【数25】

【0100】
6.最後に、λ5に対する操作は以下の通り。
(1)λ5に対する標準ヤング盤は図16に示すようにただ1つ存在する。
(2)これに対応するシュペヒト多項式は以下である。
【0101】
【数26】

【0102】
これにGram-Schmidtの直交化法を適用すると、以下の通りとなる。
【0103】
【数27】

【0104】
次に、量子回路生成部4について説明する。量子回路生成部4は、以下のようにして、正規直交基底計算部3で求めたSnの正規直交基底を用いてSn上のフーリエ変換FSnの行列Gnの量子回路を構成する。
【0105】
Sn-1の各表現を
【0106】
【数28】

【0107】
とし、(an-1はSn-1の表現の個数)、ブラテリダイアグラム上でのρi(i=1,2,…,an-1)の子ノードを
【0108】
【数29】

【0109】
とする。図7に示すように、ρij(j=1,2,…,ti)には重複がある。例えば、図7の例では、ブラテリダイアグラムの上から4番目の階層の左から2つ目のノードには、ρ12とρ21の2つの表記が対応付けられている。ρ12とρ21が示すノードは同じである。
【0110】
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とする。
【0111】
このとき、Gnは、図8に例示するように、
【0112】
【数30】

【0113】
の直和で表現される。また、それぞれのiに対して、
【0114】
【数31】

【0115】
はすべて同じである。この行列を、Mρiと書くことにする。各iに対するMρiを決定することができれば、Gnが求まる。
【0116】
Mρiは、ρ(gb)(b=0,1,…,n-1)により構成される。ρ(gb)は、ブラテリダイアグラムにおけるn番目の階層のn個ノードにそれぞれ対応するn個の既約表現ρijの標準ヤング盤に対応する上記正規直交基底を用いてgbを表した行列表現ρij(gb)の直和である行列表現である。図18に、n=4の場合のρ(gi)を模式的に表す。なお、図18では、ρ(gb)のことをρ(gi)と表記している。
【0117】
行列表現ρij(gb)は、既約表現ρijについての標準ヤング盤に対応する正規直交基底を用いて構成される。具体的には、行列表現ρij(gb)は、Snの元gbを、既約表現ρij(j=1,2,…,ti)についての標準ヤング盤に対応する正規直交基底が構成するベクトルに作用させることにより構成される。Snの元gbをベクトルに作用させるとは、gnで定義された置換をベクトルに施すことを意味する。例えば、gn=(1,2)であり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は行列・の転置行列とする。
【0118】
量子回路生成部4は、まず各(i,j)の組についてこの行列表現ρij(gb)を求めて、求まったρij(gb)の直和を取りρ(gb)とする。直和とは例えば図18に例示するように、左上から右下に向かって行列を加えることを意味する。
【0119】
このようにして、量子回路生成部4は、各b(b=0,1,…,n-1)についての行列表現ρ(gb)を生成する。図19の上段にn=4の場合の各ρ(gb)(b=0,1,…,3)を模式的に表す。
【0120】
量子回路生成部4は、生成された行列表現ρ(g0),ρ(g1),…,ρ(gn-1)を構成する列行列を左上に位置する列行列から順次所定の値を乗算して組み合わせてdρi・n×dρi・nの行列Mρiを構成する処理を各iについて行う。
【0121】
そして、量子回路生成部4は、dρ1個のMρ1,dρ2個のMρ2,…,dρan-1個のMρan-1の直和を行列Gnとする。
【0122】
図19は、n=4の場合に、ρ(g0),ρ(g1),ρ(g2),ρ(g3)からMρ1,Mρ2,Mρ3を構成し、これらのMρ1,Mρ2,Mρ3からG4を構成する様子を模式的に示した図である。n=4の場合には、図19のように、G4は、上から順に4×4、8×8、8×8、4×4の行列Mρ1,Mρ2,Mρ2,Mρ3が対角に並んだ形となる。
【0123】
図19に示すように、各Mρiは、4個のハッチングが同じ列行列の組み合わせで構成されている(実際には列行列は所定の値を乗算した後に組み合わせられる。)。Mρiのハッチングが同じ列行列の内一番左の列行列はρ(g0)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内左から2番目の列行列はρ(g1)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内右から2番目の列行列はρ(g2)の同じハッチングの列行列に由来し、Mρiのハッチングが同じ列行列の内一番右の列行列はρ(g3)の同じハッチングの列行列に由来する。
【0124】
例えば、図19に示すように、Mρ1の第1行目を構成する一番左の列行列はρ(g0)のρ11(g0)に由来し、Mρ1の第1行目を構成する左から2番目の列行列はρ(g1)のρ11(g1)に由来し、Mρ1の第1行目を構成する右から2番目の列行列はρ(g2)のρ11(g2)に由来し、Mρ1の第1行目を構成する一番右の列行列はρ(g3)のρ11(g3)に由来する。
【0125】
nが4より大の場合も図19と同様にしてGnを計算することができる。
【0126】
量子回路生成部4は、具体的には、以下のアルゴリズムに基づいて、行列Gnを計算する。
【0127】
ρij(gb)(b=0,1,…,n)のx番目の列行列をρij(gb)[x]と書くことにする。ρij(gb)[x]はdρij×1行列である。また、Mρi[k,l]を、Mρi
【0128】
【数32】

【0129】
要素を先頭とするdρij×1小行列
【0130】
【数33】

【0131】
を表すものとする。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)から以下のように求めることができる。図17は、以下の手順に対応するフローチャートである。
【0132】
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ρi・nまでlの値を1ずつ上げながら、
【0133】
【数34】

【0134】
かつ、もし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ならば終了。
【0135】
n=3のときは、giは4×4のブロック対角行列で表される。
【0136】
【数35】

【0137】
ここから、上記アルゴリズムを用い、以下のように6×6行列を定義する。
【0138】
【数36】

【0139】
すると、FS3=G3(FS2(×)I3)を計算すると、対称群S3上の量子フーリエ変換Fs3が求まる。
【0140】
式(2)の行列分解が求まると、そこから量子回路を作成することができる。Gnは、
【0141】
【数37】

【0142】
と表現されるので、制御ユニタリゲートの系列である。ここで、dρiはブラテリダイアグラムのn-1段目の左からi番目の数字であり、iの増加とともに指数的に増大する。
【0143】
例えば、図20に示す回路は、FS4の量子回路の一例である。第一、第二、第三番目の線はそれぞれqubit, qutrit, quatritをあらわす。quatritは、1つの素子で|0>,|1>,|2>,|3>の4状態の重ね合わせ状態を表現する素子である。
【0144】
二番目の線の最後の◆は|i2>=|2>の場合の制御オペレーションを意味する。また左側の×―×という記号は、通常の交換演算ではなく、
【0145】
【数38】

【0146】
という操作、右側の×―×という記号は上記の転置行列で表される操作を意味する。
【0147】
[変形例等]
量子回路生成装置の各部間のデータのやり取りは直接行われてもよいし、図示していない記憶部を介して行われてもよい。
【0148】
その他、この発明は上述の実施形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【0149】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき各部の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、各部がコンピュータ上で実現される。
【0150】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【0151】
その他、この発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。

【特許請求の範囲】
【請求項1】
nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρiijの表現空間の次元数をそれぞれdρi,dρ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とする量子回路生成部と、
を含む量子回路生成装置。
【請求項2】
請求項1の量子回路生成装置において、
上記正規直交基底計算部は、各上記標準ヤング盤に対応するシュペヒト多項式を生成し、生成されたシュペヒト多項式をグラムシューミットの正規直交化法で互いに直交させて上記正規直交規定とする、
量子回路生成装置。
【請求項3】
nを3以上の予め定められた整数とし、ブラテリダイアグラムにおけるn-1番目の階層のan-1個ノードにそれぞれ対応するan-1個の既約表現をρi(i=1,2,…,an-1)とし、既約表現ρiのti個の子ノードにそれぞれ対応するti個の既約表現をρij(j=1,2,…,ti)とし、既約表現ρiijの表現空間の次元数をそれぞれdρi,dρ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とする量子回路生成ステップと、
を含む量子回路生成方法。
【請求項4】
請求項1又は2の量子回路生成装置の各部としてコンピュータを機能させるためのプログラム。
【請求項5】
請求項4のプログラムが記録されたコンピュータ読み取り可能な記録媒体。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate


【公開番号】特開2013−33385(P2013−33385A)
【公開日】平成25年2月14日(2013.2.14)
【国際特許分類】
【出願番号】特願2011−169081(P2011−169081)
【出願日】平成23年8月2日(2011.8.2)
【出願人】(000004226)日本電信電話株式会社 (13,992)
【出願人】(000125369)学校法人東海大学 (352)
【Fターム(参考)】