(57)【要約】【課題】  任意のユニタリ行列をサイズの小さな行列に低い演算コストで分解する。【解決手段】  ユニタリな行列Ｇに対し、Ｇ＝Ｋ・Ｍ，Ｘ＝Ｍ２を満たす行列Ｘを生成する。次に、この行列Ｘをブロック対角化する行列Ｐを生成し、当該行列Ｐの複素共役転置行列Ｐ＊を生成する。そして、行列Ｘと行列Ｐと複素共役転置行列Ｐ＊とからＢ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成し、このブロック対角行列Ｂを行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換する。その後、ブロック対角行列Ｙと行列Ｐと複素共役転置行列Ｐ＊とからＭ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成し、当該行列Ｍの複素共役転置行列Ｍ＊を生成し、行列Ｇと複素共役転置行列Ｍ＊とからＫ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成する。【選択図】        図５
2006195587.tif 000002
【特許請求の範囲】
【請求項１】
ユニタリ行列を分解するユニタリ行列分解装置であって、
ユニタリな行列Ｇが入力され、Ｇ＝Ｋ・Ｍ（ユニタリな行列Ｋ∈κ及び行列Ｍ∈μの積），Ｘ＝Ｍ２を満たす行列Ｘを生成し、当該行列Ｘを出力する行列生成手段と、
上記行列Ｘが入力され、当該行列Ｘをブロック対角化する行列Ｐを生成し、当該行列Ｐを出力する対角化行列生成手段と、
上記行列Ｐが入力され、当該行列Ｐの複素共役転置行列Ｐ＊を生成し、当該複素共役転置行列Ｐ＊を出力する第１の複素共役転置行列生成手段と、
上記行列Ｘと上記行列Ｐと上記複素共役転置行列Ｐ＊とが入力され、Ｂ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成し、当該ブロック対角行列Ｂを出力する第１の行列積演算手段と、
上記ブロック対角行列Ｂが入力され、これを上記行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換し、当該ブロック対角行列Ｙを出力する第１のブロック対角行列変換手段と、
上記ブロック対角行列Ｙと上記行列Ｐと上記複素共役転置行列Ｐ＊とが入力され、Ｍ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成し、当該行列Ｍを出力する第２の行列積演算手段と、
上記行列Ｍが入力され、当該行列Ｍの複素共役転置行列Ｍ＊を生成し、当該複素共役転置行列Ｍ＊を出力する第２の複素共役転置行列生成手段と、
上記行列Ｇと上記複素共役転置行列Ｍ＊とが入力され、Ｋ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成し、当該行列Ｋを出力する第３の行列積演算手段と、
を有することを特徴とするユニタリ行列分解装置。
【請求項２】
請求項１記載のユニタリ行列分解装置であって、
上記ブロック対角行列Ｙが入力され、制御ＮＯＴ演算を表す行列をＵＣＮＯＴとし、ウォルシューアダマール変換を表す行列をＨとし、ｒ×ｒの単位行列をＩｒとし、上記ブロック対角行列Ｙを２ｊ×２ｊ行列とし、
【数１】
2006195587.tif 000022
とし、Ｗ＊を行列Ｗの複素共役転置行列とした場合における、Ｙ’＝Ｗ・Ｙ・Ｗ＊の演算を行い、当該行列Ｙ’を出力する第２のブロック対角行列変換手段を、
さらに有することを特徴とするユニタリ行列分解装置。
【請求項３】
請求項１記載のユニタリ行列分解装置であって、
上記行列生成手段が、
上記行列Ｇが入力され、その複素共役転置行列Ｇ＊を生成し、当該複素共役転置行列Ｇ＊を出力する第３の複素共役転置行列生成手段と、
上記行列Ｇと上記複素共役転置行列Ｇ＊とが入力され、
【数２】
2006195587.tif 000023
とした場合における
Ｘ＝σｊｚ・Ｇ＊・σｊｚ・Ｇ
の演算によって上記行列Ｘを生成し、当該行列Ｘを出力する第４の行列積演算手段と、
を有する手段である、
ことを特徴とするユニタリ行列分解装置。
【請求項４】
請求項１記載のユニタリ行列分解装置であって、
上記対角化行列生成手段が、
上記行列Ｘが入力され、その固有値と固有ベクトルとを算出し、当該固有値と固有ベクトルとを出力する固有値・固有ベクトル算出手段と、
上記固有値・固有ベクトル算出手段において算出された固有ベクトルのうち、対応する固有値が正の虚数である固有ベクトルｕｋ（ｋは自然数）に対し、
【数３】
2006195587.tif 000024
とした場合における、固有ベクトルｕｋ＋σｊｚ・ｕｋを上記行列Ｐの奇数列目の要素として生成し、固有ベクトルｕｋ−σｊｚ・ｕｋを上記行列Ｐの偶数列目の要素として生成し、当該固有ベクトルｕｋ＋σｊｚ・ｕｋ及びｕｋ−σｊｚ・ｕｋを出力する第１の要素生成手段と、
上記固有値・固有ベクトル算出手段において算出された固有ベクトルのうち、対応する固有値が実数である固有ベクトルｖｔ（ｔは自然数）に対し、当該固有ベクトルｖｔがσｊｚ・ｖｔ＝ｖｔ或いはσｊｚ・ｖｔ＝−ｖｔを満たすか否かを判断し、σｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔを上記行列Ｐの奇数列目の要素として出力し、σｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔを上記行列Ｐの偶数列目の要素として出力し、どちらにも属さない場合は、（ｖｔ＋σｊｚ・ｖｔ）／‖ｖｔ＋σｊｚ・ｖｔ‖（‖・‖はノルムを示す）で正規化したベクトルのうち、σｊｚ・ｖｔ’＝ｖｔ’（ｔ’≠ｔ）を満たす固有ベクトルｖｔ’と線形独立なものを上記行列Ｐの奇数列目の要素として出力し、（ｖｔ−σｊｚ・ｖｔ）／‖ｖｔ−σｊｚ・ｖｔ‖で正規化したベクトルのうち、σｊｚ・ｖｔ’＝−ｖｔ’を満たす固有ベクトルｖｔ’と線形独立なものを上記行列Ｐの奇数列目の要素として出力する第２の要素生成手段と、
上記固有ベクトルｕｋ±σｊｚ・ｕｋ及びｖｔが入力され、上記固有ベクトルｕｋ＋σｊｚ・ｕｋとσｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔとを奇数列目の要素とし、上記固有ベクトルｕｋ−σｊｚ・ｕｋとσｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔとを偶数列目の要素として上記行列Ｐを生成し、当該行列Ｐを出力する行列構成手段と、
を有する手段である、
ことを特徴とするユニタリ行列分解装置。
【請求項５】
請求項４記載のユニタリ行列分解装置であって、
上記行列構成手段が、
上記固有ベクトルｕｋ＋σｊｚ・ｕｋを２αｋ−１列目の要素とし（αｋは自然数）、上記固有ベクトルｕｋ−σｊｚ・ｕｋを２αｋ列目の要素として上記行列Ｐを生成する手段である、
ことを特徴とするユニタリ行列分解装置。
【請求項６】
請求項１記載のユニタリ行列分解装置であって、
上記第１のブロック対角行列変換手段が、
上記ブロック対角行列Ｂの対角部分に並んだ正方行列Ｃを、Ｃ＝Ｄ２を満たす正方行列Ｄに置き換えることにより、当該ブロック対角行列Ｂから上記ブロック対角行列Ｙへの変換を行う手段である、
ことを特徴とするユニタリ行列分解装置。
【請求項７】
請求項５記載のユニタリ行列分解装置であって、
上記正方行列Ｃ及びＤが２×２の行列である、
ことを特徴とするユニタリ行列分解装置。
【請求項８】
ユニタリ行列を分解するユニタリ行列分解方法であって、
行列生成手段が、入力されたユニタリな行列Ｇに対し、Ｇ＝Ｋ・Ｍ（ユニタリな行列Ｋ∈κ及び行列Ｍ∈μの積），Ｘ＝Ｍ２を満たす行列Ｘを生成し、当該行列Ｘを出力する手順と、
対角化行列生成手段が、入力された上記行列Ｘをブロック対角化する行列Ｐを生成し、当該行列Ｐを出力する手順と、
第１の複素共役転置行列生成手段が、入力された上記行列Ｐの複素共役転置行列Ｐ＊を生成し、当該複素共役転置行列Ｐ＊を出力する手順と、
第１の行列積演算手段が、入力された上記行列Ｘと上記行列Ｐと上記複素共役転置行列Ｐ＊とを用い、Ｂ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成し、当該ブロック対角行列Ｂを出力する手順と、
第１のブロック対角行列変換手段が、入力された上記ブロック対角行列Ｂを上記行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換し、当該ブロック対角行列Ｙを出力する手順と、
第２の行列積演算手段が、入力された上記ブロック対角行列Ｙと上記行列Ｐと上記複素共役転置行列Ｐ＊に対し、Ｍ＝Ｐ・Ｙ・Ｐ＊の演算を行って行列Ｍを生成し、当該行列Ｍを出力する手順と、
第２の複素共役転置行列生成手段が、入力された上記行列Ｍの複素共役転置行列Ｍ＊を生成し、当該複素共役転置行列Ｍ＊を出力する手順と、
第３の行列積演算手段が、入力された上記行列Ｇと上記複素共役転置行列Ｍ＊とに対し、Ｋ＝Ｇ・Ｍ＊の演算を行って行列Ｋを生成し、当該行列Ｋを出力する手順と、
を有することを特徴とするユニタリ行列分解方法。
【請求項９】
請求項１から７の何れかに記載のユニタリ行列分解装置としてコンピュータを機能させるためのユニタリ行列分解プログラム。
【請求項１０】
請求項９記載のユニタリ行列分解プログラムを格納したコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、任意のユニタリ行列をそれよりもサイズの小さな行列に分解するユニタリ行列分解装置、ユニタリ行列分解方法、その機能をコンピュータで実現するためのユニタリ行列分解プログラム及びそれを格納した記録媒体に関する。
【背景技術】
【０００２】
量子コンピュータにおける各操作はユニタリ行列によって表現されるが、このユニタリ行列によって表現される各操作を実際の量子回路で実現するためには、このユニタリ行列を実現可能な基本ゲート等に分解しなければならない。以下、従来のユニタリ行列の分解手法について説明する。
＜カルタン（Cartan）分解を用いた行列の分解手法（非特許文献１参照）＞
この手法では、リー群に属する２ｊ×２ｊの特殊ユニタリ行列Ｇ∈ＳＵ（２ｊ）を入力として、KhanejaとGlaserによるカルタン分解を用いたユニタリ群の分解の枠組み（非特許文献２）に従ってユニタリ行列を分解する。すなわち、入力行列からＧ＝ｅｘｐ（ｇ）を満たすリー代数ｇ∈ｓｕ（２ｊ）を計算し、それからカルタン分解によってｇをｋとｍという２つの行列に分解し（ｇ＝ｋ＋ｍ）、さらにｋとｍの行列の指数関数Ｋ＝ｅｘｐ（ｋ），Ｍ＝ｅｘｐ（ｍ）を計算することによりＧ＝Ｋ・Ｍへ分解する。そして、これを再帰的に繰り返すことによりサイズ（行数及び列数）の小さなユニタリ行列の積まで分解する。なお、分解された行列が入力行列Ｇよりもサイズの小さなユニタリ行列となるためには、ＫとＭが所定の条件を満たさなければならない。この手法ではリー代数におけるカルタン分解を用いることにより、この条件を満たしたＫとＭへの分解を可能としている。
【０００３】
＜Cosine-Sine分解（非特許文献３〜５参照）＞
Cosine-Sine分解は、行列の特異値分解の一種である（非特許文献３）。これを応用して、ユニタリ行列を次元の小さな行列の積に分解する技術が提案されている（非特許文献４，５）。
【０００４】
まず、以下のように、入力行列Ｇを半分のサイズの４つのブロックに分解する。
【数４】
2006195587.tif 000003
【０００５】
なお、Ｇを２ｊ×２ｊのユニタリ行列とすると、Ａ１，Ａ２，Ｃ１，Ｓ１，Ｂ１，Ｂ２は、２ｊ−１×２ｊ−１のユニタリ行列となる。さらに、Ｃ１，Ｓ１は下記の形の対角行列となる。
【数５】
2006195587.tif 000004
【０００６】
その後、同様の分解をＡ１，Ａ２，Ｂ１，Ｂ２に対して行い、以後、Ａβ，Ｂβが２×２の行列になるまで再帰的に同様の分解を繰り返す。
８×８の行列Ｇを例としてこのCosine-Sine分解を行った場合、この行列Ｇは、図１３のようなパターンの行列の積へと分解される。なお、この図において、白い正方形は入力行列に関係なく必ず０となる成分を表し、色付きの正方形は入力の行列に依存して何らかの値となる成分を表している。
【非特許文献１】村上裕美，河野泰人，関川浩，Cartan分解を用いた量子回路の生成，第10回量子情報技術研究会(QIT10)，予稿集 pp.123-126, 2004.
【非特許文献２】N. Khaneja and S. Glaser, Cartan decomposition of SU(2n), constructive controllability of spin systems and universal quantum computing, Chemical Physics, Vol. 267 (Issues 1-3), pp.11-23, 2001.
【非特許文献３】C. Paige and M. Wei, History and generality of the CS decomposition, Linear Algebra and its Applications, pp.303-326, 1994.
【非特許文献４】M. Mottonen, J. Vartiainen, Ville Bergholm, and M. Salomaa, Quantum circuits for general multi-qubit gates, quant-ph/0404089.
【非特許文献５】R. Tucci，"A Rudimentary Quantum Compiler," [online]，１９９８年５月７日，[２００４年１２月２８日検索]，インターネット＜http://jp.arxiv.org/abs/quant-ph/9805015＞
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかし、カルタン分解を用いた行列の分解手法の場合、行列の指数関数とその逆関数の計算が必要となり、計算コストが非常に大きいという問題点がある。
またこの手法の場合、分解過程においてＧ＝Ｋ・Ｍの分解が成り立つためには、ｋとｍが可換（ｋ・ｍ＝ｍ・ｋ）であるという条件が満たされなければならない。しかし一般のユニタリ行列においてこの性質は成り立たない。そのため、任意のユニタリ行列の分解にこの手法を適用することはできない。
また、ＮＭＲ（Nuclear Magnetic Resonance）量子計算機への実装を前提とした場合、その量子計算機の構成上の利点を十分に得ることができ、結果として量子計算機を高速動作させることができる構成（Khaneja−Glaser分解の定義に合う形）が存在する（M.Nakahara， Y. Kondo, K. Hata， and S. Tanimura， "Demonstrating quantum algorithm acceleration with NMR quantum computer," インターネット＜http://jp.arxiv.org/abs/quant-ph/0405050＞参照）。しかし、Cosine-Sine分解による分解結果をこのようなＮＭＲ量子計算機の実装に適した構成に置き換えるのは容易なことではない。
【０００８】
本発明はこのような点に鑑みてなされたものであり、任意のユニタリ行列をサイズの小さな行列に低い演算コストで分解できるユニタリ行列分解装置、ユニタリ行列分解方法、その機能をコンピュータに実行させるためのユニタリ行列分解プログラム及び記録媒体を提供することを目的とする。
また、本発明の他の目的は、分解結果をＮＭＲ量子計算機の実装に適した構成に容易に置き換え可能なユニタリ行列分解装置、ユニタリ行列分解方法、その機能をコンピュータに実行させるためのユニタリ行列分解プログラム及び記録媒体を提供することである。
【課題を解決するための手段】
【０００９】
本発明では上記課題を解決するために、まず、分解対象であるユニタリな行列Ｇに対し、Ｇ＝Ｋ・Ｍ（ユニタリな行列Ｋ∈κ及び行列Ｍ∈μの積），Ｘ＝Ｍ２を満たす行列Ｘを生成する。なお、κ，μは、以下の関係を満たす集合を意味する。
【数６】
2006195587.tif 000005
【００１０】
次に、この行列Ｘをブロック対角化する行列Ｐを生成し、当該行列Ｐの複素共役転置行列Ｐ＊を生成する。そして、行列Ｘと行列Ｐと複素共役転置行列Ｐ＊とからＢ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成し、このブロック対角行列Ｂを行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換する。なお、ブロック対角行列とは、２×２の行列が対角成分に並び、他の要素が０となる正方行列を意味する。その後、ブロック対角行列Ｙと行列Ｐと複素共役転置行列Ｐ＊とからＭ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成し、当該行列Ｍの複素共役転置行列Ｍ＊を生成し、行列Ｇと複素共役転置行列Ｍ＊とからＫ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成する。以上の処理により、行列Ｇは、行列Ｋ、行列Ｐ、ブロック対角行列Ｙ及び複素共役転置行列Ｐ＊の積（Ｇ＝Ｋ・Ｐ・Ｙ・Ｐ＊）に分解される。
【００１１】
ここで、これらの各処理はリー群における演算のみで容易に実行することができる。すなわち、ＧからＧ＝Ｋ・Ｍ，Ｘ＝Ｍ２を満たす行列Ｘを求めることは容易である（後述）。また、この行列Ｘをブロック対角化する行列Ｐを生成し、当該行列Ｐの複素共役転置行列Ｐ＊を生成し、ブロック対角行列Ｂ＝Ｐ＊・Ｘ・Ｐを求めることも容易である。また、行列Ｐはユニタリ行列となりＰ・Ｐ＊＝Ｉ（Ｉは単位行列）を満たし、Ｂ＝Ｐ＊・Ｘ・Ｐ＝Ｐ＊・Ｍ２・Ｐ＝（Ｐ＊・Ｍ・Ｐ）（Ｐ＊・Ｍ・Ｐ）＝Ｙ２となるから、ブロック対角行列Ｂからブロック対角行列Ｙへは規則的に変換できる。さらに、求められたブロック対角行列Ｙと行列Ｐと複素共役転置行列Ｐ＊とからＭ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成し、当該行列Ｍの複素共役転置行列Ｍ＊を生成し、行列Ｇと複素共役転置行列Ｍ＊とからＫ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成することも容易である。
【００１２】
また、以上の処理によって生成された行列Ｋと行列Ｐとの積Ｋ’＝Ｋ・Ｐ及び複素共役転置行列Ｐ＊は、行列Ｇよりもサイズの小さな行列へ分解できる。すなわち、一般にε，ζ∈κ或いはε，ζ∈μであればε・ζ∈κとなる関係が成り立つため（性質１）、Ｘ＝Ｍ２∈κの関係も成り立つ。また、Ｘ＝Ｐ・Ｂ・Ｐ＊が成り立つが、Ｘ∈κを満たす場合、非特許文献２にあるようにＰ∈κ，Ｐ＊∈κの関係が成り立つ。また、Ｋ∈κであるため、性質１よりＫ’＝Ｋ・Ｐ∈κの関係も成り立つ。そして、非特許文献２にあるように、κの元である行列Ｋ’，Ｐ＊は、それぞれの行列に依存しない０の要素と、それぞれの行列に依存する何らかの値の要素とが市松模様に配列された行列となる。そして、行列Ｋ’，Ｐ＊からこの「行列に依存する何らかの値の要素」を規則的に抜き出すことにより容易にサイズの小さな行列へ分解できる。
【００１３】
さらに、行列ＭはユニタリでありＭ＊・Ｍ＝Ｉを満たすため、上記の演算によって求められたＫ＝Ｇ・Ｍ＊とＭとの積はＫ・Ｍ＝Ｇ・Ｍ＊・Ｍ＝Ｇとなるが、これはＫとＭとが可換でなくても成り立つ。
またさらに、上記の処理によって生成されたブロック対角行列Ｙは、２×２の行列が対角上に配列された行列である。このような行列は、変換行列Ｗとその複素共役転置行列Ｗ*とを用いることにより、容易にＮＭＲ量子計算機への実装に適した構成に変換できる（後述）。
【発明の効果】
【００１４】
以上のように本発明では、リー群の演算のみによってユニタリ行列をサイズの小さな行列に分解できる。そのため、カルタン分解を用いた従来手法のように行列の指数関数やその逆関数の計算を必要としない。その結果、本発明では、カルタン分解を用いた従来手法に比べ低い演算コストでユニタリ行列を分解できる。
また、本発明は、ＫとＭが可換でない行列Ｇにも適用できるため、任意のユニタリ行列の分解に適用することができる。
さらに、本発明では、ブロック対角行列Ｙを含む形で行列Ｇを分解することとしたため、分解結果の一部を容易にＮＭＲ量子計算機の実装に適した構成に置き換えることができる。
【発明を実施するための最良の形態】
【００１５】
以下、本発明を実施するための最良の形態を説明する。
〔第１の実施形態〕
＜使用する記号の定義＞
まず、本形態で使用する記号を以下のように定義する。
ｉ：虚数単位
Ａ*：行列Ａの複素共役転置行列
Ｉｓ：ｓ×ｓの単位行列
０ｓ：ｓ×ｓの全成分が０の行列
ｄｉａｇ（ａ，ｂ，ｃ，ｄ）：対角成分がａ，ｂ，ｃ，ｄの順に並んだ対角行列
∈：左辺が右辺の集合の元
‖・‖：・のノルム
【００１６】
【数７】
2006195587.tif 000006
【００１７】
＜ハードウェア構成＞
図１は、本形態におけるユニタリ行列分解装置１００の構成を例示したブロック図である。
図１に例示するように、この例のユニタリ行列分解装置１００は、ＣＰＵ（Central Processing Unit）１１０、入力部１２０、出力部１３０、補助記憶装置１４０、ＲＡＭ（Random Access Memory）１５０、ＲＯＭ（Read Only Memory）１６０及びバス１７０を有している。
【００１８】
この例のＣＰＵ１１０は、制御部１１１、演算部１１２及びレジスタ１１３を有し、レジスタ１１３に読み込まれた各種プログラムに従って様々な演算処理を実行する。また、入力部１２０は、データが入力される入力ポート、キーボード、マウス等であり、出力部１３０は、データを出力する出力ポート、ディスプレイ等である。補助記憶装置１４０は、例えば、ハードディスク、ＭＯ（Magneto-Optical disc）、半導体メモリ等であり、本形態のユニタリ行列の分解処理を実行するためのユニタリ行列分解プログラムを格納したユニタリ行列分解プログラム領域１４１及び分解対象となるユニタリ行列Ｇ等の各種データが格納されるデータ領域１４２を有している。また、ＲＡＭ１５０は、ＳＲＡＭ (Static Random Access Memory)、ＤＲＡＭ (Dynamic Random Access Memory)等であり、ユニタリ行列分解プログラムが書き込まれるユニタリ行列分解プログラム領域１５１及び分解対象となるユニタリ行列Ｇ等の各種データが格納されるデータ領域１５２を有している。また、バス１７０は、ＣＰＵ１１０、入力部１２０、出力部１３０、補助記憶装置１４０、ＲＡＭ１５０及びＲＯＭ１６０を通信可能に接続している。
【００１９】
＜ソフトウェア構成＞
図２は、図１のユニタリ行列分解プログラム領域１４１，１５１に格納されるユニタリ行列分解プログラム２００の構成を例示した概念図である。
図２に例示するように、この例のユニタリ行列分解プログラム２００は、Ｇ＝Ｋ・Ｍ（ユニタリな行列Ｋ∈κ及び行列Ｍ∈μの積），Ｘ＝Ｍ２を満たす行列Ｘを生成するための行列生成プログラム２１０と、行列Ｘをブロック対角化する行列Ｐを生成するための対角化行列生成プログラム２２０と、行列Ｐの複素共役転置行列Ｐ＊を生成するための第１の複素共役転置行列生成プログラム２３１と、Ｂ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成するための第１の行列積演算プログラム２３２と、ブロック対角行列Ｂを行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換するための第１のブロック対角行列変換プログラム２３３と、Ｍ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成するための第２の行列積演算プログラム２３４と、行列Ｍの複素共役転置行列Ｍ＊を生成するための第２の複素共役転置行列生成プログラム２３５と、Ｋ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成するための第３の行列積演算プログラム２３６と、変換行列ＷについてＹ’＝Ｗ・Ｙ・Ｗ＊の演算を行うための第２のブロック対角行列変換プログラム２３７と、Ｋ’＝Ｋ・ＰやＰ＊をそれらよりもサイズの小さな行列に分解するための行列分解プログラム２３８と、ユニタリ行列分解処理を制御するための制御プログラム２３９とを有している。
【００２０】
また、この例の行列生成プログラム２１０は、行列Ｇの複素共役転置行列Ｇ＊を生成するための第３の複素共役転置行列生成プログラム２１１と、Ｘ＝σｊｚ・Ｇ＊・σｊｚ・Ｇの演算によって行列Ｘを生成するための第４の行列積演算プログラム２１２とを有している。
また、この例の対角化行列生成プログラム２２０は、行列Ｘの固有値と固有ベクトルとを算出するための固有値・固有ベクトル算出プログラム２２１と、対応する固有値が正の虚数である固有ベクトルｕｋ（ｋは自然数）に対し、固有ベクトルｕｋ＋σｊｚ・ｕｋを行列Ｐの奇数列目の要素として生成し、固有ベクトルｕｋ−σｊｚ・ｕｋを行列Ｐの偶数列目の要素として生成するための第１の要素生成プログラム２２２と、対応する固有値が実数である固有ベクトルｖｔ（ｔは自然数）がσｊｚ・ｖｔ＝ｖｔ或いはσｊｚ・ｖｔ＝−ｖｔを満たすか否かを判断し、σｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔを行列Ｐの奇数列目の要素として出力し、σｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔを行列Ｐの偶数列目の要素として出力し、どちらにも属さない場合は、（ｖｔ＋σｊｚ・ｖｔ）／‖ｖｔ＋σｊｚ・ｖｔ‖（‖・‖はノルムを示す）で正規化したベクトルのうち、σｊｚ・ｖｔ’＝ｖｔ’（ｔ’≠ｔ）を満たす固有ベクトルｖｔ’と線形独立なものを上記行列Ｐの奇数列目の要素として出力し、（ｖｔ−σｊｚ・ｖｔ）／‖ｖｔ−σｊｚ・ｖｔ‖で正規化したベクトルのうち、σｊｚ・ｖｔ’＝−ｖｔ’を満たす固有ベクトルｖｔ’と線形独立なものを上記行列Ｐの奇数列目の要素として出力するための第２の要素生成プログラム２２３と、固有ベクトルｕｋ＋σｊｚ・ｕｋとσｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔとを奇数列目の要素とし、固有ベクトルｕｋ−σｊｚ・ｕｋとσｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔとを偶数列目の要素として行列Ｐを生成するための行列構成プログラム２２４とを有している。
【００２１】
なお、各プログラムを構成するモジュールの少なくとも一部を他のプログラムと共用することとしてもよい。
＜ハードウェアとソフトウェアとの協働＞
ＣＰＵ１１０は、読み込まれたＯＳ（Operating System）プログラムに従い、補助記憶装置１４０のユニタリ行列分解プログラム領域１４１に格納されているユニタリ行列分解プログラム２００を、ＲＡＭ１５０のユニタリ行列分解プログラム領域１５１に書き込む。同様にＣＰＵ１１０は、補助記憶装置１４０のデータ領域１４２に格納されている分解対象のユニタリ行列等のデータを、ＲＡＭ１５０のデータ領域１５２に書き込む。そして、このユニタリ行列分解プログラム２００やデータが書き込まれたＲＡＭ１５０上のアドレスがＣＰＵ１１０のレジスタ１１３に格納される。ＣＰＵ１１０の制御部１１１は、レジスタ１１３に格納されたこれらのアドレスを順次読み出し、読み出したアドレスが示すＲＡＭ１５０上の領域からプログラムやデータを読み出し、そのプログラムが示す演算を演算部１１２に順次実行させ、その演算結果をレジスタ１１３に格納していく。
【００２２】
図３は、このようにＣＰＵ１１０にユニタリ行列分解プログラム２００が読み込まれることにより実現される機能構成を例示したブロック図である。なお、図３における矢印はデータの流れを示すが、制御部４９５に出入りするデータの流れに対応する矢印は省略してある。
ここでメモリ３００は、レジスタ１１３、ＲＡＭ１５０のデータ領域１５２、補助記憶装置１４０のデータ領域１４２等に相当する。また、行列生成部４００、対角化行列生成部４１０、第１の複素共役転置行列生成部４２０、第１の行列積演算部４３０、第１のブロック対角行列変換部４４０、第２の行列積演算部４５０、第２の複素共役転置行列生成部４６０、第３の行列積演算部４７０、第２のブロック対角行列変換部４８０、行列分解部４９０及び制御部４９５は、それぞれ、行列生成プログラム２１０、対角化行列生成プログラム２２０、第１の複素共役転置行列生成プログラム２３１、第１の行列積演算プログラム２３２、第１のブロック対角行列変換プログラム２３３、第２の行列積演算プログラム２３４、第２の複素共役転置行列生成プログラム２３５、第３の行列積演算プログラム２３６、第２のブロック対角行列変換プログラム２３７、行列分解プログラム２３８及び制御プログラム２３９が、それぞれＣＰＵ１１０に読み込まれることにより構成されるものである。さらに、第３の複素共役転置行列生成部４０１、第４の行列積演算部４０２、固有値・固有ベクトル算出部４１１、第１の要素生成部４１２、第２の要素生成部４１３及び行列構成部４１４は、第３の複素共役転置行列生成プログラム２１１、第４の行列積演算プログラム２１２、固有値・固有ベクトル算出プログラム２２１、第１の要素生成プログラム２２２、第２の要素生成プログラム２２３及び行列構成プログラム２２４が、それぞれＣＰＵ１１０に読み込まれることにより構成されるものである。
【００２３】
＜処理＞
次に本形態におけるユニタリ行列分解装置１００の処理について説明する。
図４は本形態におけるユニタリ行列分解装置１００の処理の全体を説明するためのフローチャートである。まずこの処理の全体について説明する。なお、以下の各処理は、制御部４９５の制御のもと実行される。
まず前処理として、分解対象のユニタリ行列をリストＬＧの要素としてメモリ３００に格納しておく（ステップＳ１１）。次に、行列生成部４００（図３）が、リストＬＧの先頭に一番近い４次元以上の行列を分解対象のユニタリな行列Ｇとしてメモリ３００から読み出す（ステップＳ１２）。なお、行列Ｇのサイズは２ｊ×２ｊであるものとする。その後、この行列Ｇを以下に述べる処理によってＹ’及びＧ１〜Ｇ４の行列に分解し、これらをそれぞれリストＬＹ及びＬＧの要素としてメモリに格納する（ステップＳ１３）。
【００２４】
［ステップＳ１３の詳細］
図５は図４におけるステップＳ１３の詳細を説明するためのフローチャートである。以下、この図に沿って図４のステップＳ１３の詳細を説明していく。
ステップＳ１２でメモリ３００から読み出されたユニタリな行列Ｇは行列生成部４００に入力される。行列生成部４００は、Ｇ＝Ｋ・Ｍ（ユニタリな行列Ｋ∈κ及び行列Ｍ∈μの積），Ｘ＝Ｍ２を満たす行列Ｘを生成し、この行列Ｘをメモリ３００に出力して格納する（ステップＳ２１）。この例の場合、まず、第３の複素共役転置行列生成部４０１に行列Ｇが入力される。そして、この第３の複素共役転置行列生成部４０１がその複素共役転置行列Ｇ＊を生成し、この複素共役転置行列Ｇ＊をメモリ３００に出力して格納する。次に、第４の行列積演算部４０２がメモリ３００から行列Ｇと複素共役転置行列Ｇ＊とを読み出す。読み出された行列Ｇと複素共役転置行列Ｇ＊とは第４の行列積演算部４０２に入力され、第４の行列積演算部４０２は
Ｘ＝σｊｚ・Ｇ＊・σｊｚ・Ｇ  ・・・(2)
の演算によって行列Ｘを生成し、この行列Ｘをメモリ３００に出力して格納する。
【００２５】
なお、式（２）の演算結果がＭ２となるのは以下から明らかである。
Ｘ＝σｊｚ・Ｇ＊・σｊｚ・Ｇ
＝θ(Ｇ＊) ・Ｇ（（１）の関係より）
＝θ(Ｍ＊・Ｋ*) ・Ｋ・Ｍ
＝θ(Ｍ＊)・θ(Ｋ*) ・Ｋ・Ｍ
＝Ｍ・Ｋ*・Ｋ・Ｍ（（１）の関係より）
＝Ｍ２（Ｋがユニタリ行列でありＫ*・Ｋが単位行列となるため）
ステップＳ２１の処理が終了すると、次に対角化行列生成部４１０が、メモリ３００から行列Ｘを読み出す。この行列Ｘは対角化行列生成部４１０に入力され、対角化行列生成部４１０は、この行列Ｘをブロック対角化する行列Ｐを生成し、生成した行列Ｐをメモリ３００に出力して格納する（ステップＳ２２）。
【００２６】
［ステップＳ２２の詳細］
図６は図５におけるステップＳ２２の詳細をそれぞれ説明するためのフローチャートである。また、図７は図６におけるステップＳ４２の詳細を、図８は図６におけるステップＳ４３の詳細をそれぞれ説明するためのフローチャートである。
まず、固有値・固有ベクトル算出部４１１に行列Ｘが入力され、その固有値と固有ベクトルとを算出し、
リストＥ１＝［［虚の固有値，対応する固有ベクトル］，・・・］
リストＥ２＝［［実の固有値，対応する固有ベクトル］，・・・］
となるリストＥ１，Ｅ２をメモリ３００に出力して格納する（ステップＳ４１）。なお、虚の固有値の数をｉｍとし、実の固有値の数をｒｅとする。
【００２７】
次に、第１の要素生成部４１２が、メモリ３００からリストＥ１を読み出す。このリストＥ１は第１の要素生成部４１２に入力され、第１の要素生成部４１２は、リストＥ１中の正の固有ベクトルｕｋ（ｋは自然数）に対し、固有ベクトルｕｋ＋σｊｚ・ｕｋを行列Ｐの奇数列目の要素として生成し、固有ベクトルｕｋ−σｊｚ・ｕｋを行列Ｐの偶数列目の要素として生成し、当該固有ベクトルｕｋ＋σｊｚ・ｕｋ及びｕｋ−σｊｚ・ｕｋをリストＥ３としてメモリ３００に出力して格納する（ステップＳ４２）。この例の場合（図７）、リストＥ１が入力された第１の要素生成部４１２は、まず、ｃｋ＝０とし（ステップＳ５１）、ｃｋにｃｋ＋１の演算結果を代入し（ステップＳ５２）、リストＥ１からまだ調べていない正の固有値を１つ選び、対応する固有ベクトルｕｋを抽出する（ステップＳ５３）。そして、第１の要素生成部４１２は、この固有ベクトルｕｋに対し、
Ｅ３［２ｃｋ‐１］＝ｕｋ＋σｊｚ・ｕｋ
Ｅ３［２ｃｋ］＝ｕｋ‐σｊｚ・ｕｋ
を計算し、これらをリストＥ３の要素としてメモリ３００に格納する（ステップＳ５４）。その後、この例の第１の要素生成部４１２は、メモリ３００のリストＥ１に、まだ調べていない正の固有値が存在するか否かを判断し、存在すればステップＳ５２以降の処理に戻り、存在しなければステップＳ４２（図６）の処理を終了する。なお、この例の処理の場合、Ｅ３は複素共役な固有値のペアに対応する固有ベクトルのペアを［ｕ１＋σｊｚ・ｕ１，ｕ１‐σｊｚ・ｕ１］［ｕ２＋σｊｚ・ｕ２，ｕ２‐σｊｚ・ｕ２］・・・と配列したリストとなる。
【００２８】
ステップＳ４２の処理が終了すると、次に第２の要素生成部４１３が、メモリ３００からリストＥ２を読み出す。このリストＥ２は第２の要素生成部４１３に入力され、第２の要素生成部４１３は、リストＥ２中の固有ベクトルｖｔ（ｔは自然数）に対し、この固有ベクトルｖｔがσｊｚ・ｖｔ＝ｖｔ或いはσｊｚ・ｖｔ＝−ｖｔを満たすか否かを判断し、σｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔを行列Ｐの奇数列目の要素とし、σｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔを行列Ｐの偶数列目の要素とし、これらをリストＥ４としてメモリ３００に出力して格納する（ステップＳ４３）。この例の場合、この例の場合（図８）、リストＥ２が入力された第２の要素生成部４１３は、まず、ｃｎ＝１，ｃｑ＝１とし（ステップＳ６１）、リストＥ２からまだ調べていない固有ベクトルを１つ選びｖｔとする（ステップＳ６２）。次に、第２の要素生成部４１３は、このｖｔがσｊｚ・ｖｔ＝ｖｔを満たすか否かを判断し（ステップＳ６３）、満たす場合にＥ４［２ｃｎ−１］＝ｖｔをリストＥ４の要素としてメモリ３００に格納し、ｃｎ＝ｃｎ＋１の演算を行い（ステップＳ６４）、満たさない場合にこのｖｔがσｊｚ・ｖｔ＝−ｖｔを満たすか否かを判断する（ステップＳ６５）。そして第２の要素生成部４１３は、σｊｚ・ｖｔ＝−ｖｔを満たす場合にのみ、Ｅ４［２ｃｎ］＝ｖｔをリストＥ４の要素としてメモリ３００に格納し、ｃｑ＝ｃｑ＋１の演算を行う（ステップＳ６６）。また、σｊｚ・ｖｔ＝ｖｔ及びσｊｚ・ｖｔ＝−ｖｔのどちらにも属さない場合、第２の要素生成部４１３は、（ｖｔ＋σｊｚ・ｖｔ）／‖ｖｔ＋σｊｚ・ｖｔ‖を計算し、これをリストＥ４の要素Ｅ４［２ｃｎ−１］としてメモリ３００に格納し、ｃｎ＝ｃｎ＋１の演算を行う（ステップＳ６７）。また、この場合、第２の要素生成部４１３は、（ｖｔ−σｊｚ・ｖｔ）／‖ｖｔ−σｊｚ・ｖｔ‖を計算し、これをリストＥ４の要素Ｅ４［２ｃｑ］としてメモリ３００に格納し、ｃｑ＝ｃｑ＋１の演算を行う（ステップＳ６８）。次に、第２の要素生成部４１３は、メモリ３００のリストＥ４から線形従属な要素を削除する（ステップＳ６９）。
【００２９】
その後、第２の要素生成部４１３は、メモリ３００のリストＥ３に、まだ調べていない固有ベクトルが存在するか否かを判断し（ステップＳ７０）、存在すればステップＳ６２以降の処理に戻り、存在しなければステップＳ４３（図６）の処理を終了する。
ステップＳ４３の処理が終了すると、行列構成部４１４は、メモリ３００からリストＥ３，Ｅ４を読み出し、リストＥ３，Ｅ４に含まれる固有ベクトルを先頭から順に取り出してそれらを列とした行列Ｐ＝（Ｖ１，Ｖ２，…，Ｖｉｍ，Ｗ１，Ｗ２，…，Ｗｒｅ）を生成し（Ｖ１，Ｖ２，…，ＶｉｍはリストＥ３の要素。Ｗ１，Ｗ２，…，ＷｒｅはリストＥ４の要素。）、メモリ３００に格納する（ステップＳ４４）。これは、固有ベクトルｕｋ＋σｊｚ・ｕｋとσｊｚ・ｖｔ＝ｖｔを満たす固有ベクトルｖｔとを奇数列目の要素とし、固有ベクトルｕｋ−σｊｚ・ｕｋとσｊｚ・ｖｔ＝−ｖｔを満たす固有ベクトルｖｔとを偶数列目の要素として行列Ｐを生成することに相当する（［ステップＳ２２の詳細］の説明終了）。
【００３０】
ステップＳ２２の処理が終了すると（図５に戻る）、次に第１の複素共役転置行列生成部４２０がメモリ３００から行列Ｐを読み出す。読み出された行列Ｐは第１の複素共役転置行列生成部４２０に入力され、第１の複素共役転置行列生成部４２０は、この行列Ｐの複素共役転置行列Ｐ＊を生成し、生成した複素共役転置行列Ｐ＊をメモリ３００に出力して格納する（ステップＳ２３）。
次に、第１の行列積演算部４３０が、メモリ３００から行列Ｘ、行列Ｐ及び複素共役転置行列Ｐ＊を読み出す。これらは第１の行列積演算部４３０に入力され、第１の行列積演算部４３０は、Ｂ＝Ｐ＊・Ｘ・Ｐの演算によってブロック対角行列Ｂを生成し、このブロック対角行列Ｂをメモリ３００に出力して格納する（ステップＳ２４）。
【００３１】
このメモリ３００に格納されたブロック対角行列Ｂは、第１のブロック対角行列変換部４４０によって読み取られる。読み出されたブロック対角行列Ｂは第１のブロック対角行列変換部４４０に入力され、第１のブロック対角行列変換部４４０は、これを行列Ｍのブロック対角行列Ｙ（＝Ｐ＊・Ｍ・Ｐ）に変換し、これをメモリ３００に出力して格納する（ステップＳ２５）。なお、ブロック対角行列Ｂからブロック対角行列Ｙへの変換は、例えば、ブロック対角行列Ｂの対角部分に並んだ正方行列Ｃを、Ｃ＝Ｄ２を満たす正方行列Ｄに置き換えることによって行う。すなわち、ブロック対角行列Ｂは、２×２の行列が対角成分に並び他の要素が０のブロック対角行列であるともいえる。また、前述の通りブロック対角行列Ｂとブロック対角行列ＹとはＢ＝Ｐ＊・Ｘ・Ｐ＝Ｐ＊・Ｍ２・Ｐ＝（Ｐ＊・Ｍ・Ｐ）（Ｐ＊・Ｍ・Ｐ）＝Ｙ２の関係を満たす。よって、ブロック対角行列Ｂからブロック対角行列Ｙへの変換は、ブロック対角行列Ｂの対角部分に並んだ正方行列Ｃを正方行列Ｄ（Ｃ＝Ｄ２を満たす）に置き換えることのみによって可能である。これにより、低い演算コストでブロック対角行列Ｂからブロック対角行列Ｙへの変換を行うことができる。なお、この置き換えに使用する正方行列Ｃ，Ｄとしては以下のものを例示できる。
【００３２】
【数８】
2006195587.tif 000007
【００３３】
なお、式（３）〜（６）におけるθはブロック対角行列Ｂの成分によって決まる値である。例えば、Ｂ＝ｄｉａｇ（−１，−１，−１，−１，１，１，１，１）である場合、θ＝πの正方行列Ｃ，Ｄと、θ＝０の正方行列Ｃ，Ｄとでこの置き換えを行うことになる。
また、１つのブロック対角行列Ｂからブロック対角行列Ｙへの変換に、複数種類の正方行列Ｃ，Ｄの組を用いることとしてもよい。例えば、式（３）のＣから式（４）のＤへの置き換えと式（３）のＣから式（５）のＤへの置き換えとを混合して、１つのブロック対角行列Ｂからブロック対角行列Ｙへの変換を行うこととしてもよい。
【００３４】
さらに、ここでは２×２の正方行列Ｃ，Ｄによって置き換えを行う例を示したが、２γ×２γ（γは２以上の自然数）の正方行列Ｃ，Ｄを用いてブロック対角行列Ｂからブロック対角行列Ｙへの変換を行うこととしてもよい。例えば、量子フーリエ変換を示すユニタリ行列の分解の場合、ブロック対角行列Ｂを対角部分にｄｉａｇ（１，−１，−１，１）のブロックを含む行列（例えば、Ｂ＝ｄｉａｇ（１，−１，−１，１，１，−１，−１，１））として生成し、
【００３５】
【数９】
2006195587.tif 000008
によってブロック対角行列Ｂからブロック対角行列Ｙへの変換を行うことが望ましい。この正方行列Ｄは、
【００３６】
【数１０】
2006195587.tif 000009
【００３７】
と表すことができ、このような正方行列Ｄはシンプルな量子回路で実現できることが知られているからである。
しかし、一般的には正方行列Ｃ，Ｄは２×２の行列であることが望ましい。すなわち、図６のステップＳ４１で生成される虚の固有値は必ず複素共役のペアとなり、行列Ｐの虚の固有値に対応する要素数（ｉｍ）は２の倍数となるが、これが２γ（γは２以上の自然数）の倍数となるとは限らない。よって、行列Ｐによってブロック対角化されるブロック対角行列Ｂの虚の固有値に対応する要素数も２の倍数となるが、これが２γの倍数となるとは限らない。これは、実の固有値に対応する要素数も２の倍数となるが、これが２γの倍数となるとは限らないことを意味している。そのため、２γ×２γの正方行列Ｃ，Ｄでブロック対角行列Ｂを置き換えると、虚の固有値に対応する要素及び実の固有値に対応する要素に置き換え残りが生じる場合がある。この場合、この置き換え残り部分を置き換える別のサイズの正方行列Ｃ，Ｄが必要となり処理が煩雑となる。よって、ブロック対角行列Ｂの虚の固有値に対応する要素数及び実の固有値に対応する要素数が明確でない場合には、正方行列Ｃ，Ｄは２×２の行列であることが望ましい。
【００３８】
ステップＳ２５の処理が終了すると、次に第２の行列積演算部４５０が、メモリ３００からブロック対角行列Ｙと行列Ｐと複素共役転置行列Ｐ＊とを読み出す。これらが入力された第２の行列積演算部４５０は、Ｍ＝Ｐ・Ｙ・Ｐ＊の演算によって行列Ｍを生成し、この行列Ｍをメモリ３００に出力して格納する（ステップＳ２６）。
次に、第２の複素共役転置行列生成部４６０が、メモリ３００から行列Ｍを読み出す。この行列Ｍが入力された第２の複素共役転置行列生成部４６０は、この行列Ｍの複素共役転置行列Ｍ＊を生成し、この複素共役転置行列Ｍ＊をメモリ３００に出力して格納する（ステップＳ２７）。
【００３９】
次に、第３の行列積演算部４７０がメモリ３００から行列Ｇと複素共役転置行列Ｍ＊とを読み出す。これらは第３の行列積演算部４７０に入力され、第３の行列積演算部４７０は、Ｋ＝Ｇ・Ｍ＊の演算によって行列Ｋを生成し、この行列Ｋをメモリ３００に出力して格納する（ステップＳ２８）。
次に、第２のブロック対角行列変換部４８０が、メモリからブロック対角行列Ｙを読み出す。このブロック対角行列Ｙは第２のブロック対角行列変換部４８０に入力され、第２のブロック対角行列変換部４８０は、
Ｙ’＝Ｗ・Ｙ・Ｗ＊  ・・・(7)
【００４０】
【数１１】
2006195587.tif 000010
【００４１】
の演算を行い、この行列Ｙ’をメモリ３００に出力し、リストＬＹの要素として格納する（ステップＳ２９）。なお、式（８）が示す変換行列Ｗはブロック対角行列Ｙの値に依存しない。よって低い演算コストによってブロック対角行列Ｙを行列Ｙ’への変換が可能である。そして、この行列Ｙ’は、Khaneja−Glaser分解の定義に合う形となり、ＮＭＲ量子計算機の実装に適した構成となる（M.Nakahara， Y. kondo, K. Hata， and S. Tanimura， "Demonstrating quantum algorithm acceleration with NMR quantum computer," インターネット＜http://jp.arxiv.org/abs/quant-ph/0405050＞参照）。
【００４２】
ここまでの処理により、行列ＧはＫ，Ｐ，Ｙ’，Ｐ*の行列に分解された。ここで、前述のようにＫ，Ｐ，Ｐ*は集合κの元となる。また積Ｋ’＝Ｋ・Ｐも集合κの元となる。よって、行列ＧはＫ’∈κとＹ∈κ’とＰ*∈κとの積に分解できることがわかる。図９（ａ）はこれを示した行列の概念図（ｊ＝３の例）である。なお、この図における空白の正方形は行列の０の要素を示し、色付きの正方形は何らかの値の要素を示す。この図に示すように、任意の行列Ｇは、ＮＭＲ量子計算機の実装に適したＹ’と、市松模様の行列Ｋ’，Ｐ*とに分解できたことになる。
【００４３】
そこで次に、行列分解部４９０がメモリ３００から行列Ｋ，Ｐを読み出し、Ｋ’＝Ｋ・Ｐの要素を規則的に抜き出して、行列Ｋ’を２ｊ−１×２ｊ−１の行列Ｇ１とＧ２の積に分解し、これらをメモリ３００に出力し、リストＬＧの要素として格納する（ステップＳ３０）。図９（ｂ）は、行列Ｋ’におけるこの分解を示した概念図であり（ｊ＝３の例）、図９（ｃ）は、その分解結果に対応する量子回路を示した図である。この図に示すように、行列Ｋ’＝Ｇ１’・Ｇ２’はこれよりもサイズの小さな行列Ｇ１,Ｇ２に容易に分解できる。
【００４４】
また、同様に、行列分解部４９０がメモリ３００から複素共役転置行列Ｐ*を読み出し、その要素を規則的に抜き出して、これを２ｊ−１×２ｊ−１の行列Ｇ３とＧ４の積に分解し、これらをメモリ３００に出力し、リストＬＧの要素として格納する（ステップＳ３１）（［ステップＳ１３の詳細］の説明終了）。
ステップＳ１３の処理が終了すると（図４に戻る）、制御部４９５が、メモリ３００に格納されたリストＬＧを検索し、まだ調べていない行列がリストＬＧに含まれるか否かを判断する（ステップＳ１４）。ここで、リストＬＧにまだ調べていない行列が含まれると判断された場合、制御部４９５は処理をステップＳ１２に戻す。一方、リストＬＧに調べていない行列が存在しないと判断された場合、制御部４９５は処理を終了する。これにより、上述の行列Ｇ１,Ｇ２,Ｇ３,Ｇ４を行列Ｇとした処理が再帰的に繰り返され、最終的に２次元の基本ゲートを示す行列に分解される。
【００４５】
＜実施例＞
次に、３量子ビットの量子フーリエ変換を示すユニタリ行列を分解する場合の実施例を説明する。
リストＬＧの８×８の行列Ｇを分割対象とする（ステップ１２）。ここで、行列Ｇは３量子ビットの量子フーリエ変換を示すユニタリ行列であるから、Ｇの（ｈ，ｋ）成分をＧ［ｈ，ｋ］と書くと
【００４６】
【数１２】
2006195587.tif 000011
となる。
【００４７】
次に、Ｘ＝σ３ｚ・Ｇ＊・σ３ｚ・Ｇを計算する（ステップＳ２１）。ここでσ３ｚ＝ｄｉａｇ（１,−１, １,−１, １,−１, １,−１）となるから、
【数１３】
2006195587.tif 000012
ｄ１＝ｄｉａｇ（１,−１, １,−１）
となる。
【００４８】
Ｘを対角化して、固有値と固有ベクトルを求め、行列Ｐを構成すると（ステップＳ２２,Ｓ４１〜Ｓ４４,Ｓ５１〜Ｓ５５,Ｓ６１〜Ｓ６７）、
【数１４】
2006195587.tif 000013
となる。
【００４９】
次にＢ＝Ｐ・Ｘ・Ｐ*を計算すると（ステップＳ２４）、
Ｂ＝ｄｉａｇ（−１, −１, −１, −１,１, １, １, １,）
となる。
【００５０】
次に、Ｂの対角部分の２×２のブロックを式（３）（４）に従って書き換えたものをＹとする（ステップＳ２５）。この例の場合、式（３）（４）による書き換えは
【数１５】
2006195587.tif 000014
となる。
【００５１】
次に、Ｍ＝Ｐ・Ｙ・Ｐ*を計算すると（ステップＳ２６）、
【数１６】
2006195587.tif 000015
となる。
【００５２】
次に、Ｋ＝Ｇ・Ｍ*を計算すると（ステップＳ２８）、
【数１７】
2006195587.tif 000016
となる。
【００５３】
次に、ＹをＹ’＝Ｗ・Ｙ・Ｗ*に変換する（ステップＳ２９）。
次に、Ｋ’＝Ｋ・Ｐを計算すると、
【数１８】
2006195587.tif 000017
となる。そして、図９（ｂ）のように、
Ｋ’＝Ｇ１’・Ｇ２’
【００５４】
【数１９】
2006195587.tif 000018
【００５５】
と分解し、Ｇ１’とＧ２’から図９（ｂ）のように色付き部分の要素を抜き出して４×４のユニタリ行列Ｇ１,Ｇ２
【００５６】
【数２０】
2006195587.tif 000019
を構成する（ステップＳ３０）。
【００５７】
次に、Ｐ*を図９（ｂ）と同様に、
【数２１】
2006195587.tif 000020
【００５８】
と分解し、Ｇ３’とＧ４’から図９（ｂ）のように色付き部分の要素を抜き出して４×４のユニタリ行列Ｇ３,Ｇ４
【００５９】
【数２２】
2006195587.tif 000021
を構成する。
その後、Ｇ１〜Ｇ４をＧとしてステップＳ１２以降の処理を行う。
【００６０】
〔第２の実施形態〕
次に本発明における第２の実施形態について説明する。
本形態は第１の実施形態の変形例であり、第１の実施の形態でブロック対角行列Ｙを行列Ｙ’に変換した代わりに、ブロック対角行列Ｙをそのまま基本ゲートを示す行列に分解する点のみが第１の実施の形態と相違する。以下では、第１の実施形態との相違点を中心に説明し、第１の実施の形態と共通する事項については説明を省略する。
【００６１】
＜ハードウェア構成＞
第１の実施の形態と同様である。
＜ソフトウェア構成＞
図１０は、本形態のユニタリ行列分解プログラム６００の構成を例示した概念図である。本形態のユニタリ行列分解プログラム６００と第１の実施形態のユニタリ行列分解プログラム２００との相違点は、ユニタリ行列分解プログラム６００が、第２のブロック対角行列変換プログラム２３７（図２）の代わりにブロック対角行列分解プログラム６３７を有する点である。
【００６２】
＜ハードウェアとソフトウェアとの協働＞
図１１は、ＣＰＵにユニタリ行列分解プログラム６００が読み込まれることにより実現される機能構成を例示したブロック図である。第１の実施の形態との相違点は、第２のブロック対角行列変換部（図３）の代わりにブロック対角行列分解部６８０が構成される点である。
＜処理＞
第１の実施の形態との相違点は図５のステップＳ２９の処理のみである。すなわち、本形態では、ステップＳ２９の処理の代わりにブロック対角行列Ｙをそのまま２×２の基本ゲートを示す行列に分解する。
【００６３】
図１２はこの処理を説明するための概念図である（ｊ＝３の例）。
この図に示すように、行列ＧはＫ’＝Ｋ・Ｐとブロック対角行列Ｙと複素共役転置行列Ｐ*に分解され（図１２（ａ））、ブロック対角行列Ｙが図１２（ｂ）（ｃ）に示すように２×２の行列Ｕ１〜Ｕ４に分解される。なお、この分解の一般化については、例えば「上坂吉則著、コロナ社出版、”量子コンピュータの基礎数理”、ＩＳＢＮ４−３３９−０２３７６−０」等参照。
なお、本発明は上述の各実施形態に限定されるものではなく、その他、本発明の趣旨を逸脱しない範囲で適宜変更が可能であることはいうまでもない。また、上述の各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。
【００６４】
また、上述したユニタリ行列分離プログラム２００,６００は、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、例えば、磁気記録装置、光ディスク、光磁気記録媒体、半導体メモリ等どのようなものでもよいが、具体的には、例えば、磁気記録装置として、ハードディスク装置、フレキシブルディスク、磁気テープ等を、光ディスクとして、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ（Random Access Memory）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）等を、光磁気記録媒体として、ＭＯ（Magneto-Optical disc）等を、半導体メモリとしてＥＥＰ−ＲＯＭ（Electronically Erasable and Programmable-Read Only Memory）等を用いることができる。
【００６５】
また、このプログラムの流通は、例えば、そのプログラムを記録したＤＶＤ、ＣＤ−ＲＯＭ等の可搬型記録媒体を販売、譲渡、貸与等することによって行う。さらに、このプログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することにより、このプログラムを流通させる構成としてもよい。
また、上述した実施形態とは別の実行形態として、コンピュータが可搬型記録媒体から直接このプログラムを読み取り、そのプログラムに従った処理を実行することとしてもよく、さらに、このコンピュータにサーバコンピュータからプログラムが転送されるたびに、逐次、受け取ったプログラムに従った処理を実行することとしてもよい。また、サーバコンピュータから、このコンピュータへのプログラムの転送は行わず、その実行指示と結果取得のみによって処理機能を実現する、いわゆるＡＳＰ（Application Service Provider）型のサービスによって、上述の処理を実行する構成としてもよい。なお、本形態におけるプログラムには、電子計算機による処理の用に供する情報であってプログラムに準ずるもの（コンピュータに対する直接の指令ではないがコンピュータの処理を規定する性質を有するデータ等）を含むものとする。
【００６６】
また、この形態では、コンピュータ上で所定のプログラムを実行させることにより、本装置を構成することとしたが、これらの処理内容の少なくとも一部をハードウェア的に実現することとしてもよい。
【産業上の利用可能性】
【００６７】
本発明の産業上の利用分野としては、量子コンピュータを構成する任意のユニタリ変換量子回路の設計支援分野等を例示できる。本発明を適用することにより、容易に任意のユニタリ変換量子回路をＣＮＯＴ等の基本ゲートに分解することができる。
【図面の簡単な説明】
【００６８】
【図１】第１実施形態におけるユニタリ行列分解装置の構成を例示したブロック図。
【図２】ユニタリ行列分解プログラムの構成を例示した概念図。
【図３】ＣＰＵにユニタリ行列分解プログラムが読み込まれることにより実現される機能構成を例示したブロック図。
【図４】第１実施形態におけるユニタリ行列分解装置の処理の全体を説明するためのフローチャート。
【図５】図４におけるステップＳ１２の詳細を説明するためのフローチャート。
【図６】図５におけるステップＳ２２の詳細をそれぞれ説明するためのフローチャート。
【図７】図６におけるステップＳ４２の詳細を説明するためのフローチャート。
【図８】図６におけるステップＳ４３の詳細を説明するためのフローチャート。
【図９】（ａ）は、行列ＧをＫ’∈κとＹ∈κ’とＰ*∈κとの積に分解した様子を示した概念図。（ｂ）は、行列Ｋ’の分解を示した概念図（ｊ＝３の例）。（ｃ）は、その分解結果に対応する量子回路を示した図。
【図１０】第２実施形態のユニタリ行列分解プログラムの構成を例示した概念図。
【図１１】ＣＰＵにユニタリ行列分解プログラムが読み込まれることにより実現される機能構成を例示したブロック図。
【図１２】第２の実施形態におけるブロック対角行列Ｙの分解を説明するための概念図。
【図１３】Cosine-Sine分解を説明するための概念図。
【符号の説明】
【００６９】
１００  ユニタリ行列分解装置
２００,６００  ユニタリ行列分解プログラム
【図１】
2006195587.tif 000025
【図２】
2006195587.tif 000026
【図３】
2006195587.tif 000027
【図４】
2006195587.tif 000028
【図５】
2006195587.tif 000029
【図６】
2006195587.tif 000030
【図７】
2006195587.tif 000031
【図８】
2006195587.tif 000032
【図１０】
2006195587.tif 000033
【図１１】
2006195587.tif 000034
【図９】
2006195587.tif 000035
【図１２】
2006195587.tif 000036
【図１３】
2006195587.tif 000037