(57)【要約】【課題】分解対象の行列よりもサイズが小さな行列の演算のみで、当該分解対象の行列ブロック対角行列又はそれに変換可能な行列に分解する。【解決手段】行列Gから部分行列G(11),G(22)を抽出し、行列積G(11)*・G(11),...,G(22)・G(22)*の固有値y(1),...,y(d)と固有ベクトルV(11),...,V(1d),...,V(21),...,V(2d)とを求め、Y(1)=diag(√y(1),...,√y(d)),Y(2)=diag(i√(1-y(1)),...,i√(1-y(d))),P(1)=(ei・θ(11)・V(11),...,ei・θ(1d)・V(1d)),P(2)=(ei・θ(21)・V(21),...,ei・θ(2d)・V(2d)),K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d)),K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))を生成する。【選択図】図４
2011090497.tif 000002
【特許請求の範囲】
【請求項１】
2d×2d（dは正整数）のユニタリな行列Gを入力とし、当該行列Gから、
【数１８】
2011090497.tif 000020
を満たすd×dの部分行列G(11),G(22)を抽出し、当該部分行列G(11),G(22)を出力する入力行列分割部と、
前記部分行列G(11),G(22)を入力とし、行列Aの共役転置行列をA*とした場合における、G(11)*とG(11)との行列積G(11)*・G(11)と、G(22)*とG(22)との行列積G(22)*・G(22)とを生成し、当該行列積G(11)*・G(11),G(22)*・G(22)を出力する第１行列積計算部と、
前記行列積G(11)*・G(11),G(22)*・G(22)を入力とし、前記行列積G(11)*・G(11),G(22)*・G(22)に対して共通の固有値y(1),...,y(d)と、当該固有値y(1),...,y(d)に対応する前記行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)と、当該固有値y(1),...,y(d)に対応する前記行列積G(22)*・G(22)の固有ベクトルV(21),...,V(2d)とを求め、前記固有値y(1),...,y(d)と前記固有ベクトルV(11),...,V(1d),V(21),...,V(2d)とを出力する固有値・固有ベクトル計算部と、
前記固有値y(1),...,y(d)を入力とし、y(1),...,y(d)の平方根√y(1),...,√y(d)を対角成分に持つd×dの対角行列Y(1)=diag(√y(1),...,√y(d))と、1-y(1),...,1-y(d)の平方根√(1-y(1)),...,√(1-y(d))に虚数単位iを乗じたi√(1-y(1)),...,i√(1-y(d))を対角成分に持つd×dの対角行列Y(2)=diag(i√(1-y(1)),...,i√(1-y(d)))とを生成し、当該対角行列Y(1)，Y(2)を出力する対角行列計算部と、
前記固有ベクトルV(11),...,V(1d),V(21),...,V(2d)を入力とし、eをネイピア数とし、θ(11),...,θ(1d),θ(21),...,θ(2d)を実数とした場合における、行列P(1)=(ei・θ(11)・V(11),...,ei・θ(1d)・V(1d)),P(2)=(ei・θ(21)・V(21),...,ei・θ(2d)・V(2d))を生成し、当該行列P(1)，P(2)を出力する行列構成部と、
前記固有値y(1),...,y(d)に対応する行列積G(11)・G(11)*の固有ベクトルをW(11),...,W(1d)とし、前記固有値y(1),...,y(d)に対応する行列積G(22)・G(22)*の固有ベクトルをW(21),...,W(2d)とし、φ(11),...,φ(1d),φ(21),...,φ(2d)を実数とした場合における、K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d)),K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))を満たす行列積K(1)・P(1),K(2)・P(2)を生成し、当該行列積K(1)・P(1),K(2)・P(2)を出力する第２行列積計算部と、
を有する行列分解装置。
【請求項２】
請求項１の行列分解装置であって、
前記第１行列積計算部は、さらに、G(11)とG(11)*との前記行列積G(11)・G(11)*と、G(22)とG(22)*とのG(22)・G(22)*を生成し、当該行列積G(11)・G(11)*，G(22)・G(22)*を出力し、
前記固有値・固有ベクトル計算部は、さらに、前記行列積G(11)・G(11)*,G(22)・G(22)*を入力とし、前記固有ベクトルW(11),...,W(1d),W(21),...,W(2d)を求め、当該固有ベクトルW(11),...,W(1d),W(21),...,W(2d)を出力し、
前記第２行列積計算部は、前記固有ベクトルW(11),...,W(1d),W(21),...,W(2d)を入力とし、前記行列積K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d)),K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))を生成し、当該行列積K(1)・P(1)，K(2)・P(2)を出力し、
当該行列分解装置は、さらに、
G(11)=(K(1)・P(1))・Y(1)・P(1)*，
G(22)=(K(2)・P(2))・Y(1)・P(2)*，
G(12)=(K(1)・P(1))・Y(2)・P(2)*，
G(21)=(K(2)・P(2))・Y(2)・P(1)*，
を満たす、前記実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)の値をそれぞれ選択し、選択した各値を出力する未知数算出部を有する、
ことを特徴とする行列分解装置。
【請求項３】
請求項１の行列分解装置であって、
前記第２行列積計算部は、前記部分行列G(11)，G(22)と前記行列P(1)，P(2)とを入力とし、行列積G(11)・P(1),G(22)・P(2)の各列ベクトルがすべてゼロベクトル以外である場合に、前記行列積G(11)・P(1)の各列ベクトルの大きさがそれぞれ１になるように当該行列積G(11)・P(1)を正規化した行列を前記行列積K(1)・P(1)として生成し、前記行列積G(22)・P(2)の各列ベクトルの大きさがそれぞれ１になるように当該行列積G(22)・P(2)を正規化した行列を前記行列積K(2)・P(2)として生成し、
当該行列分解装置は、さらに、
G(12)=(K(1)・P(1))・Y(2)・P(2)*，
G(21)=(K(2)・P(2))・Y(2)・P(1)*，
を満たすように前記実数θ(11),...,θ(1d),θ(21),...,θ(2d)の値をそれぞれ選択し、選択した各値を出力する未知数算出部を有する、
ことを特徴とする行列分解装置。
【請求項４】
請求項１又は３の行列分解装置であって、
前記第２行列積計算部は、前記部分行列G(11)，G(22)と前記行列P(1)，P(2)と前記対角行列Y(1)とを入力とし、前記対角行列Y(1)の各対角要素√y(1),...,√y(d)がすべて０以外である場合に、行列積G(11)・P(1)・Y(1)-1を前記行列積K(1)・P(1)として生成し、行列積G(22)・P(2)・Y(1)-1を前記行列積K(2)・P(2)として生成し、
当該行列分解装置は、さらに、
G(12)=(K(1)・P(1))・Y(2)・P(2)*，
G(21)=(K(2)・P(2))・Y(2)・P(1)*，
を満たすように前記実数θ(11),...,θ(1d)及びθ(21),...,θ(2d)の値をそれぞれ選択し、選択した各値を出力する未知数算出部を有する、
ことを特徴とする行列分解装置。
【請求項５】
第１行列積計算部と固有値・固有ベクトル計算部と対角行列計算部と行列構成部と第２行列積計算部とを有する行列分解装置が実行する行列分解方法であって、
前記入力行列分割部が、2d×2d（dは正整数）のユニタリな行列Gを入力とし、当該行列Gから、
【数１９】
2011090497.tif 000021
を満たすd×dの部分行列G(11),G(22)を抽出し、当該部分行列G(11)，G(22)を出力するステップと、
前記第１行列積計算部が、前記部分行列G(11),G(22)を入力とし、行列Aの共役転置行列をA*とした場合における、G(11)*とG(11)との行列積G(11)*・G(11)と、G(22)*とG(22)との行列積G(22)*・G(22)とを生成し、当該行列積G(11)*・G(11),G(22)*・G(22)を出力するステップと、
前記固有値・固有ベクトル計算部が、前記行列積G(11)*・G(11),G(22)*・G(22)を入力とし、前記行列積G(11)*・G(11),G(22)*・G(22)に対して共通の固有値y(1),...,y(d)と、当該固有値y(1),...,y(d)に対応する前記行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)と、当該固有値y(1),...,y(d)に対応する前記行列積G(22)*・G(22)の固有ベクトルV(21),...,V(2d)とを求め、前記固有値y(1),...,y(d)と前記固有ベクトルV(11),...,V(1d),V(21),...,V(2d)とを出力するステップと、
前記対角行列計算部が、前記固有値y(1),...,y(d)を入力とし、y(1),...,y(d)の平方根√y(1),...,√y(d)を対角成分に持つd×dの対角行列Y(1)=diag(√y(1),...,√y(d))と、1-y(1),...,1-y(d)の平方根√(1-y(1)),...,√(1-y(d))に虚数単位iを乗じたi√(1-y(1)),...,i√(1-y(d))を対角成分に持つd×dの対角行列Y(2)=diag(i√(1-y(1)),...,i√(1-y(d)))とを生成し、当該対角行列Y(1)，Y(2)を出力するステップと、
前記行列構成部が、前記固有ベクトルV(11),...,V(1d),V(21),...,V(2d)を入力とし、eをネイピア数とし、θ(11),...,θ(1d),θ(21),...,θ(2d)を実数とした場合における、行列P(1)=(ei・θ(11)・V(11),...,ei・θ(1d)・V(1d)),P(2)=(ei・θ(21)・V(21),...,ei・θ(2d)・V(2d))を生成し、当該行列P(1)，P(2)を出力するステップと、
前記第２行列積計算部が、前記固有値y(1),...,y(d)に対応する行列積G(11)・G(11)*の固有ベクトルをW(11),...,W(1d)とし、前記固有値y(1),...,y(d)に対応する行列積G(22)・G(22)*の固有ベクトルをW(21),...,W(2d)とし、φ(11),...,φ(1d),φ(21),...,φ(2d)を実数とした場合における、K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d)),K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))を満たす行列積K(1)・P(1),K(2)・P(2)を生成し、当該行列積K(1)・P(1),K(2)・P(2)を出力するステップと、
を有する行列分解方法。
【請求項６】
請求項１から４の何れかの行列分解装置としてコンピュータを機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意のユニタリな行列をブロック対角行列又はそれに変換可能な行列に分解する行列分解技術に関する。
【背景技術】
【０００２】
量子コンピュータにおける各操作はユニタリ行列によって表現されるが、このユニタリ行列によって表現される各操作を実際の量子回路で実現するためには、このユニタリ行列を実現可能な基本ゲート等に分解しなければならない。ユニタリ行列を基本ゲート等に変換する手法として、入力のユニタリ行列を、ブロック対角行列の積に分解する手法が知られている（例えば、特許文献１参照）。
【０００３】
特許文献１の手法は、2n×2nのユニタリな行列（ｎは正整数）Gが入力されたときに、
【０００４】
【数１】
2011090497.tif 000003
【０００５】
を満たす部分行列K(1),K(2),P(1),P(2),Y(1),Y(2)を求める手法である。ここで、
【０００６】
【数２】
2011090497.tif 000004
【０００７】
は、入力された行列Gよりもサイズが小さな部分行列K(1),K(2),P(1),P(2),P(1)*,P(2)*をブロック成分としたブロック対角行列である。また、Y(1)とY(2)は入力された行列Gよりもサイズが小さな対角行列であり、
【０００８】
【数３】
2011090497.tif 000005
【０００９】
は、ブロック対角行列に変換可能な行列である。なお、A*は行列Aの共役転置行列を示し、0は0成分からなる行列を示す。各部分行列K(1),K(2),P(1),P(2), Y(1),Y(2)について再帰的に上記の行列分解を行うことにより、よりサイズの小さな部分行列から構成されるブロック対角行列又はそれに変換可能な行列の積を得ることができ、最終的には、これらのブロック対角行列が基本ゲートを行列表現したものと対応する。また、部分行列Y(1),Y(2)については、再帰的な処理を行うことなくトフォリゲートを示す行列の積に変換することもできる。なお、ここでのトフォリゲートは、通常のトフォリゲート（制御−制御−ＮＯＴゲート）を一般化したものであり、ｋ個（ｋは１以上の整数）の制御量子ビットと１個の標的量子ビットからなり、標的量子ビットの演算として任意の２×２のユニタリ行列に対応する演算を許したものとする。
【００１０】
行列Gから上記式(1)を算出するために、まず行列
X=σnz・G*・σnz・G        …(2)
が算出される。ここで、
【００１１】
【数４】
2011090497.tif 000006
である。また、
【００１２】
【数５】
2011090497.tif 000007
【００１３】
とした場合、
X=M2        …(4)
の関係を満たす。
【００１４】
次に、行列Xを固有値分解して、行列Xをブロック対角化するための行列
【００１５】
【数６】
2011090497.tif 000008
【００１６】
が求められ、行列Xをブロック対角化した行列
【００１７】
【数７】
2011090497.tif 000009
が生成される。行列X,Bは
【００１８】
【数８】
2011090497.tif 000010
【００１９】
の関係を満たす。式(3)-(5)の関係より、
B=D2
の関係を満たす行列Dを求めることにより、上記式(1)のY(1)とY(2)が求まる。
【００２０】
次に、式(3)によって行列Mが算出され、最後に行列
【００２１】
【数９】
2011090497.tif 000011
【００２２】
が求められる。これにより、式(1)右辺の各部分行列が算出される。
【先行技術文献】
【特許文献】
【００２３】
【特許文献１】特開2006-195587号公報
【発明の概要】
【発明が解決しようとする課題】
【００２４】
しかし、特許文献１の技術では、上記式(2)を計算する際に、入力された行列Gと同じサイズの行列の積を計算しなければならない。また、その後の各ステップの計算においても、行列Gと同じサイズの行列の固有値分解や行列積の計算を行わなければならない。そのため、特許文献１の技術では、計算時間が大きく、また、メモリ消費量も大きくなってしまうという問題があった。
【００２５】
本発明は、このような点に鑑みてなされたものであり、分解対象の行列よりもサイズが小さな行列の演算のみで、当該分解対象の行列をブロック対角行列又はそれに変換可能な行列に分解することが可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００２６】
本発明では、まず、2d×2d（dは正整数）のユニタリな行列Gを入力とし、当該行列Gから、
【００２７】
【数１０】
2011090497.tif 000012
【００２８】
を満たすd×dの部分行列G(11),G(22)を抽出し、行列Aの共役転置行列をA*とした場合における、G(11)*とG(11)との行列積G(11)*・G(11)と、G(22)*とG(22)との行列積G(22)*・G(22)とを生成する。次に、行列積G(11)*・G(11),G(22)*・G(22)に対して共通の固有値y(1),...,y(d)と、当該固有値y(1),...,y(d)に対応する行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)と、当該固有値y(1),...,y(d)に対応する行列積G(22)*・G(22)の固有ベクトルV(21),...,V(2d)とを求める。その後、y(1),...,y(d)の平方根√y(1),...,√y(d)を対角成分に持つd×dの対角行列Y(1)=diag(√y(1),...,√y(d))と、1-y(1),...,1-y(d)の平方根√(1-y(1)),...,√(1-y(d))に虚数単位iを乗じたi√(1-y(1)),...,i√(1-y(d))を対角成分に持つd×dの対角行列Y(2)=diag(i√(1-y(1)),...,i√(1-y(d)))とを生成する。また、eをネイピア数とし、θ(11),...,θ(1d),θ(21),...,θ(2d)を実数とした場合における、行列P(1)=(ei・θ(11)・V(11),...,ei・θ(1d)・V(1d)),P(2)=(ei・θ(21)・V(21),...,ei・θ(2d)・V(2d))を生成し、固有値y(1),...,y(d)に対応する行列積G(11)・G(11)*の固有ベクトルをW(11),...,W(1d)とし、固有値y(1),...,y(d)に対応する行列積G(22)・G(22)*の固有ベクトルをW(21),...,W(2d)とし、φ(11),...,φ(1d),φ(21),...,φ(2d)を実数とした場合における、K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d)),K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))を満たす行列積K(1)・P(1),K(2)・P(2)を生成する。
【００２９】
ここで、以上のように生成されたK(1)・P(1),K(2)・P(2),Y(1),Y(2),P(1),P(2)は、或る実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)に対して
【００３０】
【数１１】
2011090497.tif 000013
の関係を満たす。ここで、
【００３１】
【数１２】
2011090497.tif 000014
【００３２】
は、ブロック対角行列に変換可能な行列である。また、本発明では、サイズ2d×2dの行列Gを式(7)のように４分割して得られる、サイズd×dの部分行列G(11),G(22)の情報から行列の分解を行う。そのため、分解対象の行列Gのサイズが2d×2dであるのに対して、各処理で必要となる演算はサイズd×dの行列の演算である。
【発明の効果】
【００３３】
以上のように本発明では、分解対象の行列よりもサイズが小さな行列の演算のみで、当該分解対象の行列をブロック対角行列又はそれに変換可能な行列に分解することができる。
【図面の簡単な説明】
【００３４】
【図１】量子回路設計装置の機能構成を例示するための図。
【図２】第１実施形態の行列分解装置の機能構成を説明するための図。
【図３】全体処理を例示するためのフローチャート。
【図４】図３のステップＳ１１の処理を詳細に説明するためのフローチャート。
【図５】行列分解装置の機能構成を例示するための図。
【図６】第２実施形態のステップＳ２１の処理を詳細に説明するためのフローチャート。
【図７】第３実施形態のステップＳ３１の処理を詳細に説明するためのフローチャート。
【発明を実施するための形態】
【００３５】
以下、図面を参照して本発明の実施形態を説明する。
【００３６】
〔基本原理〕
まず、本形態の基本原理を説明する。
【００３７】
本形態では、2d×2d（dは正整数）のユニタリな行列Gを
【００３８】
【数１３】
2011090497.tif 000015
【００３９】
のように、ユニタリな行列K(1)・P(1), K(2)・P(2)を対角成分に持つブロック対角行列と、ブロック対角行列に変換可能な対角行列Y(1),Y(2)を成分に持つ行列と、P(1)*, P(2)*を対角成分に持つブロック対角行列との積に分解することである。ここで、K(1)・P(1), K(2)・P(2)を対角成分に持つブロック対角行列については、K(1)・P(1)及びK(2)・P(2)さえ求まれば、K(1), K(2)がそれぞれ特定できなくても不都合は生じない。なお、行列K(1), P(1), K(2), P(2)もそれぞれユニタリな行列となる。また、A・Bは、行列Aの右側から行列Bを掛ける演算を意味する。
ここで、上記式(7),(8)から、
【００４０】
【数１４】
2011090497.tif 000016
【００４１】
となる。行列K(1), P(1), K(2), P(2)はユニタリな行列であるため、この式から以下の４つの関係式が得られる。
【００４２】
G(11)*・G(11)={P(1)・Y(1)*・P(1)*・K(1)*}・{K(1)・P(1)・Y(1)・P(1)*}
=P(1)・Y(1)2・P(1)*        …(10)
G(11)・G(11)*={K(1)・P(1)・Y(1)・P(1)*}・{P(1)・Y(1)*・P(1)*・K(1)*}
=K(1)・P(1)・Y(1)2・P(1)*・K(1)*
=K(1)・G(11)*・G(11)・K(1)*        …(11)
G(22)*・G(22)={P(2)・Y(1)*・P(2)*・K(2)*}・{K(2)・P(2)・Y(1)・P(2)*}
=P(2)・Y(1) 2・P(2)*        …(12)
G(22)・G(22)*={K(2)・P(2)・Y(1)・P(2)*}・{P(2)・Y(1) *・P(2)*・K(2)*}
=K(2)・P(2)・Y(1) 2・P(2)*・K(2)*
=K(2)・G(22)*・G(22)・K(2)*         …(13)
ここでY(1)は対角行列なので、Y(1)2も対角行列である。よって、式(10),(12)は、行列G(11)*・G(11), G(22)*・G(22)の対角化処理を示している。つまり、行列G(11)*・G(11), G(22)*・G(22)は、それぞれ、行列P(1),P(2)を対角化行列とすることで対角行列Y(1)2に対角化できる関係にある。同様に、式(11),(13)は、行列G(11)・G(11)*, G(22)・G(22)*の対角化処理を示している。つまり、行列G(11)・G(11) *, G(22)・G(22)*は、それぞれ、行列K(1)・P(1), K(2)・P(2)を対角化行列とすることで対角行列Y(1)2に対角化できる関係にある。正方行列の対角化行列とそれによって得られる対角行列は、当該正方行列を固有値分解することで求めることができる。よって、行列G(11)*・G(11), G(22)*・G(22)の固有値分解に基づいて行列P(1),P(2)を求めることができ、行列G(11)・G(11) *, G(22)・G(22)*の固有値分解に基づいて行列K(1)・P(1), K(2)・P(2)を求めることができる。これらの固有値分解は、入力された行列Gよりもサイズが小さな行列G(11)*・G(11), G(22)*・G(22), G(11)・G(11)*, G(22)・G(22)*についての演算である。そのため、本形態では、入力された行列Gよりも小さなサイズの行列の演算のみで行列Gを式(8)のように分解できる。
【００４３】
〔第１実施形態〕
次に、本発明の第１実施形態を説明する。
【００４４】
＜構成＞
図１は、量子回路設計装置の機能構成を例示するための図である。また、図２は、第１実施形態の行列分解装置の機能構成を説明するための図である。
【００４５】
図１に例示するように、本形態の量子回路設計装置１は、行列分解装置１１と、トフォリゲート分解部１２と、制御部１３と、再帰処理部１４と、記憶部１５とを有する。また、図２に例示するように、行列分解装置１１は、入力部１１０１と、入力行列分割部１１０２と、第１行列積計算部１１０３と、固有値・固有ベクトル計算部１１０４と、対角行列計算部１１０５と、行列構成部１１０６と、第２行列積計算部１１０７と、未知数算出部１１０８と、出力部１１０９と、記憶部１１１０とを有する。
【００４６】
なお、量子回路設計装置１は、CPU(central processing unit),RAM(random-access memory),ROM(read-only memory)等を含む公知のコンピュータに所定のプログラムが読込まれ、実行されることによって構成されるものである。例えば、トフォリゲート分解部１２、制御部１３、再帰処理部１４、入力行列分割部１１０２、第１行列積計算部１１０３、固有値・固有ベクトル計算部１１０４、対角行列計算部１１０５、行列構成部１１０６、第２行列積計算部１１０７、未知数算出部１１０８は、CPUが所定のプログラムを実行することで構成される処理部であり、記憶部１５，１１１０は、補助記憶装置、ＲＡＭ，レジスタ或いはキャッシュメモリ、又は、それらの少なくとも一部を結合した記憶領域等である。また、量子回路設計装置１は、制御部１３の制御に基づいて各処理を実行する。
【００４７】
＜処理＞
次に、本形態の処理を説明する。
【００４８】
図３は、全体処理を例示するためのフローチャートである。また、図４は、図３のステップＳ１１の処理を詳細に説明するためのフローチャートである。
【００４９】
［全体処理］
まず、図１−３を用いて、第１実施形態の全体処理を説明する。
【００５０】
まず、行列分解装置１１の入力部１１０１（図２）に、2d×2dのユニタリな行列Gが入力される（ステップＳ１０）。dは正整数であり、本形態の例では、2d=2n（nは正整数）を満たす。また、d≧1であればよいが、実質的に行列分解処理が実行されるのはd≧2の場合である。また、本形態の行列Gは、例えば、特殊ユニタリ行列（行列式が１のユニタリ行列）である。入力された行列Gは、行列分解装置１１の記憶部１１１０に格納される。
【００５１】
次に、行列分解装置１１が、行列Gの行列分解処理を実行し、それによって得られた対角行列Y(1),Y(2)、行列P(1),P(2)、行列積K(1)・P(1),K(2)・P(2)、実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)の値θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)を出力する（ステップＳ１１）。ステップＳ１１の処理の詳細は後述する。
【００５２】
次に、トフォリゲート分解部１２にステップＳ１１で得られた対角行列Y(1),Y(2)が入力され、トフォリゲート分解部１２が行列
【００５３】
【数１５】
2011090497.tif 000017
【００５４】
から所定の成分を抜き出した行列を組み合わせることにより、式(14)に示す行列を、それぞれがトフォリゲートを示すd個の行列TGの積に分解し、各行列TGを記憶部１５に格納する（ステップＳ１２）。例えば、トフォリゲート分解部１２は、式(14)に示す行列を以下のようなd個の行列TGに分解する。ここで、詳細は後述の<<ステップＳ１１０４の具体例>>および対角行列計算部１１０５の処理にて説明を行うが、y(1),・・・,y(d)は行列G(11)*・G(11)のd個の固有値であり、√y(1), ・・・，√y(d)は行列Y(1)の対角成分、i√(1-y(1)),・・・,i√(1-y(d))は行列Y(2)の対角成分である。
【００５５】
【数１６】
2011090497.tif 000018
【００５６】
次に、制御部１３が、ステップＳ１１で得られたP(1),P(2),K(1)・P(1),K(2)・P(2)のサイズが2×2よりも大きいか否かを判定する（ステップＳ１３）。ここで、P(1),P(2),K(1)・P(1),K(2)・P(2)のサイズが2×2よりも大きいと判定された場合、再帰処理部１４に、ステップＳ１１で得られたP(1),P(2),K(1)・P(1),K(2)・P(2)、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)が入力される。再帰処理部１４は、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)によって未知の実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)の値が定められたP(1),P(2),K(1)・P(1),K(2)・P(2)のそれぞれを新たな行列Gに設定して記憶部１１１０に格納し、dを新たな2dとして更新して（ステップＳ１４）、ステップＳ１１の処理に戻る。
【００５７】
一方、ステップＳ１３の判定で、P(1),P(2),K(1)・P(1),K(2)・P(2)のサイズが2×2以下であると判定された場合、再帰処理部１４に、ステップＳ１１で得られたP(1),P(2),K(1)・P(1),K(2)・P(2)、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)が入力される。再帰処理部１４は、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)によって未知の実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)の値が定められたP(1),P(2),K(1)・P(1),K(2)・P(2)のそれぞれを、基本ゲートを示す行列BGとして記憶部１１１０に格納する（ステップＳ１５）。
【００５８】
［行列分解処理（ステップＳ１１）の詳細］
次に、ステップＳ１１の行列分解処理の詳細を説明する。
【００５９】
まず、行列分解装置１１（図２）の入力行列分割部１１０２が、記憶部１１１０から分解処理対象の行列Gを抽出し、当該行列Gが入力行列分割部１１０２に入力される（ステップＳ１１０１）。入力行列分割部１１０２は、入力された行列Gを式(16)のように４つのブロックに分割し、当該行列Gから式(16)を満たすd×dの部分行列G(11),G(22)を抽出する。
【００６０】
【数１７】
2011090497.tif 000019
【００６１】
抽出された部分行列G(11),G(22)は記憶部１１１０に出力され、そこに格納される（ステップＳ１１０２）。
【００６２】
次に、第１行列積計算部２１０３に、記憶部１１１０に格納された部分行列G(11),G(22)が入力される。第１行列積計算部２１０３は、部分行列G(11),G(22)それぞれの共役転置行列G(11)*,G(22)*を生成し、さらに、G(11)*とG(11)との行列積G(11)*・G(11)と、G(22)*とG(22)との行列積G(22)*・G(22)と、G(11)とG(11)*との行列積G(11)・G(11)*と、G(22)とG(22)*との行列積G(22)・G(22)*とを生成し、当該行列積G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*を記憶部１１１０に出力する。出力された行列積G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*は、記憶部１１１０に格納される（ステップＳ１１０３）。
【００６３】
次に、固有値・固有ベクトル計算部１１０４に、記憶部１１１０に格納された行列積G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*が入力される。固有値・固有ベクトル計算部１１０４は、行列積G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*それぞれに対して共通の固有値y(1),...,y(d)と、固有値y(1),...,y(d)に対応する行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)と、固有値y(1),...,y(d)に対応する行列積G(22)*・G(22)の固有ベクトルV(21),...,V(2d)と、固有値y(1),...,y(d)に対応する行列積G(11)・G(11)*の固有ベクトルW(11),...,W(1d)と、固有値y(1),...,y(d)に対応する行列積G(22)・G(22)*の固有ベクトルW(21),...,W(2d)とを算出する。算出された各値は記憶部１１１０に出力され、そこに格納される（ステップＳ１１０４）。
【００６４】
《ステップＳ１１０４の具体例》
固有値・固有ベクトル計算部１１０４は、まず、行列積G(11)*・G(11)の固有値y(1),...,y(d)と固有ベクトルV(11),...,V(1d)とを計算する。ここで、G(11)*・G(11)はエルミート行列なので、y(1),...,y(d)は実数となる。また、エルミート行列の異なる固有値に対する固有ベクトルは直交するので、V(11),...,V(1d)は正規直交ベクトルと考えてよい。
【００６５】
次に、固有値・固有ベクトル計算部１１０４は、行列積G(11)・G(11)*の固有値y(1),...,y(d)（G(11)・G(11)*の固有値がG(11)*・G(11)の固有値と常に等しいことは容易に証明できる）に対する固有ベクトルW(11),...,W(1d)を算出する。G(11)・G(11)*もエルミート行列なので、W(11),...,W(1d)は正規直交ベクトルと考えてよい。
【００６６】
次に、固有値・固有ベクトル計算部１１０４は、行列積G(22)*・G(22)の固有値y(1),...,y(d)（G(22)*・G(22)の固有値がG(11)*・G(11)の固有値と常に等しいことは容易に証明できる）に対する固有ベクトルV(21),...,V(2d)を算出する。G(22)*・G(22)もエルミート行列なので、V(21),...,V(2d)は正規直交ベクトルと考えてよい。
【００６７】
次に、固有値・固有ベクトル計算部１１０４は、行列積G(22)・G(22)*の固有値y(1),...,y(d)（G(22)・G(22)*の固有値がG(11)*・G(11)の固有値と常に等しいことは容易に証明できる）に対する固有ベクトルW(21),...,W(2d)を算出する。G(22)・G(22)*もエルミート行列なので、W(21),...,W(2d)は正規直交ベクトルと考えてよい。
【００６８】
なお、固有値及び固有ベクトルは、周知の計算手法により計算することができる。特に、G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*はエルミート行列であるため、その取り扱いは容易である。すなわち、対象のエルミート行列をHouseholder変換やLanczosの方法等を用いて三重対角行列（三重対角エルミート行列）に変換し、それにQR法やSturm法を適用すれば、その固有値及び固有ベクトルを求めることができる（例えば、参考文献１，２参照）。また、参考文献３などに示される公知の方法によって固有値及び固有ベクトルを求めてもよい。
【００６９】
参考文献１：森正武，杉原正顕，室田一雄著，「岩波講座応用数学  線形計算」，岩波書店，1994.
参考文献２：F. シャトラン著，伊理正夫，伊理由美訳，「行列の固有値」，シュプリンガー・フェアラーク東京，1993.
参考文献３：特許第04260725号（特開2006-139575）固有値計算装置、固有値計算方法、固有値計算プログラム及び記録媒体（日本電信電話株式会社）
また、G(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*の固有値は全て等しいので、上記固有値と固有ベクトルを算出する順序は問わない。すなわち、必ずしも上述したようにG(11)*・G(11),G(22)*・G(22),G(11)・G(11)*,G(22)・G(22)*の順に固有値と固有ベクトルを算出する必要はない（《ステップＳ１１０４の具体例》の説明終わり）。
【００７０】
次に、対角行列計算部１１０５に、記憶部１１１０に格納された固有値y(1),...,y(d)が入力される。対角行列計算部１１０５は、式(14)の行列を構成する部分行列である対角行列Y(1),Y(2)を生成する。すなわち、対角行列計算部１１０５は、y(1),...,y(d)の平方根√y(1),...,√y(d)を対角成分に持つd×dの対角行列
Y(1)=diag(√y(1),...,√y(d))         …(17)
と、1-y(1),...,1-y(d)の平方根√(1-y(1)),...,√(1-y(d))に虚数単位iを乗じたi√(1-y(1)),...,i√(1-y(d))を対角成分に持つd×dの対角行列
Y(2)=diag(i√(1-y(1)),...,i√(1-y(d)))         …(18)
とを生成し、当該対角行列Y(1)，Y(2)を記憶部１１１０に出力する。記憶部１１１０に出力された対角行列Y(1)，Y(2)は、そこに格納される（ステップＳ１１０５）。なお、diag(A,B,...)は、A,B,...を対角成分とする対角行列を意味する。
【００７１】
次に、行列構成部１１０６に、記憶部１１１０に格納された固有ベクトルV(11),...,V(1d),V(21),...,V(2d)が入力される。行列構成部１１０６は、行列
P(1)=(ei・θ(11)・V(11),...,ei・θ(1d)・V(1d))         …(19)
P(2)=(ei・θ(21)・V(21),...,ei・θ(2d)・V(2d))         …(20)
を生成し、当該行列P(1)，P(2)を記憶部１１１０に出力する。なお、eはネイピア数であり、eAはネイピア数eを底とした指数関数を意味する。また、(α,β,...）は、ベクトルα，β，...をそれぞれ列ベクトルとする行列を意味する。さらに、θ(11),...,θ(1d),θ(21),...,θ(2d)は未知の実数である。記憶部１１１０に出力された行列P(1)，P(2)は、そこに格納される（ステップＳ１１０６）。
【００７２】
次に、第２行列積計算部２１０７に、記憶部１１１０に格納された固有ベクトルW(11),...,W(1d),W(21),...,W(2d)が入力される。第２行列積計算部２１０７は、行列積
K(1)・P(1)=(ei・φ(11)・W(11),...,ei・φ(1d)・W(1d))         …(21)
K(2)・P(2)=(ei・φ(21)・W(21),...,ei・φ(2d)・W(2d))         …(22)
を生成し、当該行列積K(1)・P(1),K(2)・P(2)を記憶部１１１０に出力する。なお、φ(11),...,φ(1d),φ(21),...,φ(2d)は未知の実数である。記憶部１１１０に出力された行列積K(1)・P(1),K(2)・P(2)は、そこに格納される（ステップＳ１１０７）。
【００７３】
次に、未知数算出部１１０８に、記憶部１１１０に格納されたY(1),Y(2),P(1),P(2),K(1)・P(1),K(2)・P(2)が入力される。未知数算出部１１０８は、これらを用い
G(11)=(K(1)・P(1))・Y(1)・P(1)*        …(23)
G(22)=(K(2)・P(2))・Y(1)・P(2)*        …(24)
G(12)=(K(1)・P(1))・Y(2)・P(2)*        …(25)
G(21)=(K(2)・P(2))・Y(2)・P(1)*        …(26)
を満たす、実数θ(11),...,θ(1d),θ(21),...,θ(2d),φ(11),...,φ(1d),φ(21),...,φ(2d)の値θ'(11),...,θ'(1d),θ'(21),...,θ'(2d),φ'(11),...,φ'(1d),φ'(21),...,φ'(2d)をそれぞれ選択し、選択した各値を記憶部１１１０に出力する（ステップＳ１１０８）。
【００７４】
《ステップＳ１１０８の具体例》
例えば、未知数算出部１１０８は、上記4つの関係式(23)-(26)から得られる、
Y(1)・diag(ei(-θ(11)+φ(11)),...,ei(-θ(1d)+φ(1d)))=Y(1)・(W(11),...,W(1d))*・G(11)・(V(11),...,V(1d))         …(27)
Y(1)・diag(ei(-θ(21)+φ(21)),...,ei(-θ(2d)+φ(2d)))=Y(1)・(W(21),...,W(2d))*・G(22）・(V(21),...,V(2d))         …(28)
Y(2)・diag(ei(-θ(21)+φ(11)),...,ei(-θ(2d)+φ(1d)))=Y(2)・(W(11),...,W(1d))*・G(12)・(V(21),...,V(2d))         …(29)
Y(2)・diag(ei(-θ(11)+φ(21)),...,ei(-θ(1d)+φ(2d)))=Y(2)・(W(21),...,W(2d))*・G(21)・(V(11),...,V(1d))         …(30)
を満たす、実数θ(11)=θ'(11),...,θ(1d)=θ'(1d),θ(21)=θ'(21),...,θ(2d)=θ'(2d),φ(11)=φ'(11),...,φ(1d)=φ'(1d),φ(21)=φ'(21),...,φ(2d)=φ'(2d)を選ぶ。例えば、未知数算出部１１０８は、θ(11)=・・・=θ(1d)=0とおき、式(27)(30)の左辺と右辺との行列成分を比較することにより、φ(11),...,φ(1d),φ(21),...,φ(2d)の値求め、次に、式(28)又は(30)からθ(21),...,θ(2d)の値を求めることができる。なお、式(28)又は(30)のどちらの式を用いても答えは同じになる（《ステップＳ１１０８の具体例》の説明終わり）。
【００７５】
次に、出力部１１０９に、記憶部１１１０に格納された
Y(1),Y(2)
P(1),P(2)
K(1)・P(1),K(2)・P(2)
θ’(11),...,θ’(1d),θ’(21),...,θ’(2d)
φ’(11),...,φ’(1d),φ’(21),...,φ’(2d)
が入力され、これらが出力される（ステップＳ１１０９）。
【００７６】
以上のように出力部１１０９から出力される各値によって、式(8)の右辺に含まれる全ての部分行列Y(1),Y(2),P(1),P(2),K(1)・P(1),K(2)・P(2)を特定することができる。なお、K(1)とK(2)はK(1)・P(1)及びK(2)・P(2)の形でしか利用されないため、K(1)とK(2)が求まらなくても行列積K(1)・P(1)とK(2)・P(2)が求められれば問題はない。
【００７７】
なお、上記実施形態では、第１行列積計算部１１０３、固有値・固有ベクトル計算部１１０４、対角行列計算部１１０５、行列構成部１１０６、第２行列積計算部１１０７、未知数算出部１１０８の各部において、G(11)*・G(11), G(11)・G(11)*, G(22)*・G(22), G(22)・G(22)*に関する計算を同時に行っているが、G(11)*・G(11), G(11)・G(11)*, G(22)*・G(22), G(22)・G(22)*の各行列毎に別の処理部で処理を行っても良いし、逐次実行しても良い。また、図４では、Ｓ１１０５〜Ｓ１１０７が逐次実行されるように書かれているが、Ｓ１１０５〜Ｓ１１０７の処理は互いに独立である。そのため、Ｓ１１０５〜Ｓ１１０７の処理が異なる順序で実行されてもよいし、Ｓ１１０５〜Ｓ１１０７の処理の少なくとも一部が並列に実行されてもよい。また、本形態では、2d=2nとし、行列分解装置１１を量子回路の設計に利用するために、行列分解装置１１で生成される部分行列のサイズが2×2になるまで、行列分解装置１１の処理を再帰的に適用することとした。しかし、行列分解装置１１の処理を再帰的に適用しない構成であってもよく、その場合には、2d=2nを満たさなくてもよい。
【００７８】
〔第２実施形態〕
次に、本発明の第２実施形態を説明する。本形態は第１実施形態の変形例であり、K(1)・P(1),K(2)・P(2)の生成方法が第１実施形態と相違する。本形態の手法は、行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)に対し、G(11)・V(11),...,G(11)・V(1d)がそれぞれ、行列積G(11)・G(11)*の固有ベクトルW(11),...,W(1d)となるという事実に基づく。また、本形態の手法は、行列積G(11)・P(1)及びG(22)・P(2)のすべての列ベクトルがゼロベクトルでない場合に適用できる。よって、行列積G(11)・P(1)又はG(22)・P(2)がゼロベクトルとなる列ベクトルを含む場合には、第１実施形態の手法が適用される。以下では、第１実施形態との相違点を中心に説明する。
【００７９】
＜構成＞
図１に例示するように、第２実施形態の量子回路設計装置２は、行列分解装置２１と、トフォリゲート分解部１２と、制御部１３と、再帰処理部２４と、記憶部１５とを有する。なお、量子回路設計装置２は、公知のコンピュータに所定のプログラムが読込まれ、実行されることによって構成されるものである。
【００８０】
図５は、行列分解装置の機能構成を例示するための図である。
【００８１】
図５に例示するように、行列分解装置２１は、入力部１１０１と、入力行列分割部１１０２と、第１行列積計算部２１０３と、固有値・固有ベクトル計算部１１０４と、対角行列計算部１１０５と、行列構成部１１０６と、第２行列積計算部２１０７と、未知数算出部２１０８と、出力部２１０９と、記憶部１１１０とを有する。
【００８２】
［処理］
図３に例示するように、第２実施形態の処理は、第１実施形態のステップＳ１１の処理がステップＳ２１の処理に置換され、ステップＳ１４の処理がステップＳ２４の処理に置換され、ステップＳ１５の処理がステップＳ２５の処理に置換されたものである。以下に、本形態のステップＳ２１の処理と、ステップＳ２４の処理と、ステップＳ２５の処理とを説明する。
【００８３】
《ステップＳ２１の処理》
図６は、第２実施形態のステップＳ２１の処理を詳細に説明するためのフローチャートである。
【００８４】
ステップＳ２１では、まず、第１実施形態で説明したステップＳ１１０１−Ｓ１１０６の処理が実行された後、第２行列積計算部２１０７（図５）に、記憶部１１１０に格納されたG(11),G(22),P(1),P(2)が入力される。第２行列積計算部２１０７は、行列積G(11)・P(1)又はG(22)・P(2)がゼロベクトルとなる列ベクトルを含むか否かを判定する（ステップＳ２１０６）。
【００８５】
ここで、行列積G(11)・P(1)又はG(22)・P(2)がゼロベクトルとなる列ベクトルを含むと判定された場合には、第１実施形態で説明したステップＳ１１０７−Ｓ１１０９の処理が実行される。一方、行列積G(11)・P(1)又はG(22)・P(2)がゼロベクトルとなる列ベクトルを含まないと判定された場合（行列積G(11)・P(1),G(22)・P(2)の各列ベクトルがすべてゼロベクトル以外であると判定された場合）、第２行列積計算部２１０７（図５）が、行列積G(11)・P(1)の各列ベクトルの大きさがそれぞれ１になるように当該行列積G(11)・P(1)を正規化した行列を行列積K(1)・P(1)として生成し、行列積G(22)・P(2)の各列ベクトルの大きさがそれぞれ１になるように当該行列積G(22)・P(2)を正規化した行列を行列積K(2)・P(2)として生成する（ステップＳ２１０７）。なお、第２行列積計算部２１０７は、行列積G(11)・P(1)の各列ベクトルの大きさでその列ベクトルの要素を除することによって行列積G(11)・P(1)の各列ベクトルの大きさがそれぞれ１になるように正規化し、行列積G(22)・P(2)の各列ベクトルの大きさでその列ベクトルの要素を除することによって行列積G(22)・P(2)の各列ベクトルの大きさがそれぞれ１になるように正規化する。なお、ステップＳ２１０７の処理が実行されるのは、行列積G(11)・P(1)及びG(11)・P(1)のすべての列ベクトルの大きさがゼロベクトル以外である場合であるため、このような正規化は可能である。また、列ベクトルの大きさは、その列ベクトルの各要素の二乗和の平方根として求めることができる。
【００８６】
次に、未知数算出部２１０８に、記憶部１１１０に格納されたY(1),Y(2),P(1),P(2),K(1)・P(1),K(2)・P(2)が入力される。未知数算出部２１０８は、これらを用い
G(12)=(K(1)・P(1))・Y(2)・P(2)*        …(25)
G(21)=(K(2)・P(2))・Y(2)・P(1)*        …(26)
を満たす、実数θ(11),...,θ(1d),θ(21),...,θ(2d)の値θ'(11),...,θ'(1d),θ'(21),...,θ'(2d)をそれぞれ選択し、選択した各値を記憶部１１１０に出力する（ステップＳ２１０８）。
【００８７】
次に、出力部２１０９に、記憶部１１１０に格納された
Y(1),Y(2)
P(1),P(2)
K(1)・P(1),K(2)・P(2)
θ’(11),...,θ’(1d),θ’(21),...,θ’(2d)
が入力され、これらが出力される（ステップＳ２１０９）。
【００８８】
《ステップＳ２４の処理》
ステップＳ１３の判定で、P(1),P(2),K(1)・P(1),K(2)・P(2)のサイズが2×2よりも大きいと判定された場合、再帰処理部２４（図１）に、ステップＳ２１で得られたP(1),P(2),K(1)・P(1),K(2)・P(2)、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d)が入力される。再帰処理部１４は、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d)によって未知の実数θ(11),...,θ(1d),θ(21),...,θ(2d)の値が定められたP(1),P(2),K(1)・P(1),K(2)・P(2)のそれぞれを新たな行列Gに設定して記憶部１１１０に格納し、dを新たな2dとして更新して（ステップＳ２４）、ステップＳ２１の処理に戻る。
【００８９】
《ステップＳ２５の処理》
ステップＳ１３の判定で、P(1),P(2),K(1)・P(1),K(2)・P(2)のサイズが2×2以下であると判定された場合、再帰処理部２４（図１）に、ステップＳ２１で得られたP(1),P(2),K(1)・P(1),K(2)・P(2)、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d)が入力される。再帰処理部２４は、θ'(11),...,θ'(1d),θ'(21),...,θ'(2d)によって未知の実数θ(11),...,θ(1d),θ(21),...,θ(2d)の値が定められたP(1),P(2),K(1)・P(1),K(2)・P(2)のそれぞれを、基本ゲートを示す行列BGとして記憶部１１１０に格納する（ステップＳ２５）。
【００９０】
以上のように、本形態では、行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)に対し、G(11)・V(11),...,G(11)・V(1d)がそれぞれ、行列積G(11)・G(11)*の固有ベクトルW(11),...,W(1d)となるという事実に基づき、第１実施形態よりも演算量を削減できる。
【００９１】
なお、上記実施形態でも、G(11)*・G(11), G(11)・G(11)*, G(22)*・G(22), G(22)・G(22)*の各行列毎に別の処理部で処理が行われてもよいし、逐次実行されても良い。また、行列分解装置２１の処理を再帰的に適用しない構成であってもよく、その場合には、2d=2nを満たさなくてもよい。
【００９２】
〔第３実施形態〕
次に、本発明の第３実施形態を説明する。本形態は第１，２実施形態の変形例であり、K(1)・P(1),K(2)・P(2)の生成方法が第１，２実施形態と相違する。本形態の手法は、行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)に対し、G(11)・V(11),...,G(11)・V(1d)がそれぞれ、行列積G(11)・G(11)*の固有ベクトルW(11),...,W(1d)となるという事実、行列積G(11)・P(1)の各列ベクトルの大きさがそれぞれ対角行列Y(1)の各対角要素√y(1),...,√y(d)となり、行列積G(22)・P(2)の各列ベクトルの大きさがそれぞれ√y(1),...,√y(d)となるという事実に基づく。また、本形態の手法は、対角行列Y(1)の各対角要素√y(1),...,√y(d)がすべて０以外である場合に適用できる。よって、√y(1),...,√y(d)の何れかが０となる場合には第１実施形態の手法が適用される。以下では、第１，２実施形態との相違点を中心に説明する。
【００９３】
＜構成＞
図１に例示するように、第３実施形態の量子回路設計装置３は、行列分解装置３１と、トフォリゲート分解部１２と、制御部１３と、再帰処理部２４と、記憶部１５とを有する。なお、量子回路設計装置３は、公知のコンピュータに所定のプログラムが読込まれ、実行されることによって構成されるものである。
【００９４】
また、図５に例示するように、行列分解装置２１は、入力部１１０１と、入力行列分割部１１０２と、第１行列積計算部２１０３と、固有値・固有ベクトル計算部１１０４と、対角行列計算部１１０５と、行列構成部１１０６と、第２行列積計算部３１０７と、未知数算出部２１０８と、出力部２１０９と、記憶部１１１０とを有する。
【００９５】
［処理］
図３に例示するように、第３実施形態の処理は、第１実施形態のステップＳ１１の処理がステップＳ３１の処理に置換され、ステップＳ１４の処理がステップＳ２４の処理に置換され、ステップＳ１５の処理がステップＳ２５の処理に置換されたものである。ステップＳ２４，Ｓ２５の処理については第２実施形態で説明したため、以下ではステップＳ３１の処理のみを説明する。
【００９６】
《ステップＳ３１の処理》
図７は、第３実施形態のステップＳ３１の処理を詳細に説明するためのフローチャートである。
【００９７】
ステップＳ３１では、まず、第１実施形態で説明したステップＳ１１０１−Ｓ１１０６の処理が実行された後、第２行列積計算部３１０７（図５）に、記憶部１１１０に格納された対角行列Y(1)が入力される。第２行列積計算部３１０７は、対角行列Y(1)の対角要素√y(1),...,√y(d)の何れかが０であるか否かを判定する（ステップＳ３１０６）。
【００９８】
ここで、対角行列Y(1)の対角要素√y(1),...,√y(d)の何れかが０であった場合には、第１実施形態で説明したステップＳ１１０７−Ｓ１１０９の処理が実行される。一方、対角行列Y(1)の各対角要素√y(1),...,√y(d)がすべて０以外であった場合、第２行列積計算部３１０７は、行列積G(11)・P(1)・Y(1)-1を行列積K(1)・P(1)として生成し、行列積G(22)・P(2)・Y(1)-1を行列積K(2)・P(2)として生成し、当該行列積K(1)・P(1)，K(2)・P(2)を記憶部１１１０に出力する。出力された行列積K(1)・P(1)，K(2)・P(2)は、記憶部１１１０に格納される（ステップＳ３１０７）。なお、Y(1)-1はY(1)の逆行列を示す。また、ステップＳ３１０７の処理が実行されるのは対角行列Y(1)の対角要素√y(1),...,√y(d)のすべてが０以外の場合であるため、このY(1)-1は必ず存在する。
【００９９】
その後、第２実施形態で説明したステップＳ２１０８及びＳ２１０９が実行される。
【０１００】
以上のように、本形態では、行列積G(11)*・G(11)の固有ベクトルV(11),...,V(1d)に対し、G(11)・V(11),...,G(11)・V(1d)がそれぞれ、行列積G(11)・G(11)*の固有ベクトルW(11),...,W(1d)となるという事実、行列積G(11)・P(1)の各列ベクトルの大きさがそれぞれ対角行列Y(1)の各対角要素√y(1),...,√y(d)となり、行列積G(22)・P(2)の各列ベクトルの大きさがそれぞれ√y(1),...,√y(d)となるという事実に基づき、第１，２実施形態よりも演算量を削減できる。
【０１０１】
なお、上記実施形態でも、G(11)*・G(11), G(11)・G(11)*, G(22)*・G(22), G(22)・G(22)*の各行列毎に別の処理部で処理が行われてもよいし、逐次実行されても良い。また、行列分解装置２１の処理を再帰的に適用しない構成であってもよく、その場合には、2d=2nを満たさなくてもよい。
【０１０２】
〔その他の変形例等〕
なお、本発明は上述の実施の形態に限定されるものではない。例えば、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。
【０１０３】
また、上述の構成をコンピュータによって実現する場合、各装置が有すべき機能の処理内容はプログラムによって記述される。そして、このプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。
【０１０４】
この処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよい。
【０１０５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
【０１０６】
このようなプログラムを実行するコンピュータは、例えば、まず、可搬型記録媒体に記録されたプログラムもしくはサーバコンピュータから転送されたプログラムを、一旦、自己の記憶装置に格納する。そして、処理の実行時、このコンピュータは、自己の記録媒体に格納されたプログラムを読み取り、読み取ったプログラムに従った処理を実行する。また、このプログラムの別の実行形態として、コンピュータが可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【０１０７】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【０１０８】
本発明は、例えば、量子コンピュータの量子回路設計に利用できる。
【符号の説明】
【０１０９】
１−３  量子回路設計装置
１１，２１，３１  行列分解装置
【図１】
2011090497.tif 000022
【図２】
2011090497.tif 000023
【図３】
2011090497.tif 000024
【図４】
2011090497.tif 000025
【図５】
2011090497.tif 000026
【図６】
2011090497.tif 000027
【図７】
2011090497.tif 000028