(57)【要約】【課題】１つの補助量子ビットを使い、１種類の１量子ビット観測量及び１種類の２量子ビット観測量を基本構成要素とする観測ベース量子回路により、所望のグラフ状態を出力する。【解決手段】上記の課題を解決するために、頂点の集合Ｖ＝｛１，…，ｎ｝と、辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝とから構成されるグラフＧ＝（Ｖ，Ｅ）に対応するグラフ状態を生成するために、１種類の１量子ビット観測量Ｙ及び１種類の２量子ビット観測量Ｚ（×）Ｘを基本構成要素として、σｚ，σｘ，Ｈ，（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ），（Ｐ−１（×）Ｐ−１）ΛＺを実行するための観測ベース量子回路を構成する。これらのＹ及びＺ（×）Ｘで構成された観測ベース量子回路を用いて、所望のグラフ状態を出力する。【選択図】図１
2011150655.tif 000002
【特許請求の範囲】
【請求項１】
頂点の集合Ｖ＝｛１，…，ｎ｝と、辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝とから構成されるグラフＧ＝（Ｖ，Ｅ）に対応するグラフ状態を生成するグラフ状態生成装置において、
ｎ個の頂点にそれぞれ対応する初期状態の量子ビットを｜０＞１｜０＞２…｜０＞ｎとし、補助量子ビットを｜０＞ｎ＋１として、
頂点の次数をその頂点に接続している辺の数として、ｋ＝１，２，…，ｎ−１について昇順で、頂点ｋの次数をカウントし、頂点ｋの次数が奇数の場合には頂点ｋに対応する量子ビットをＹ観測しその観測結果をｔｋとし、頂点ｋの次数が偶数の場合には頂点ｋ＋１に対応する量子ビットをＹ観測し頂点ｋ及び頂点ｋ＋１に対応する量子ビットをＺ（×）Ｘ観測しその観測結果をｕｋとし、頂点ｋに対応する量子ビットをＹ観測する第一頂点演算部と、
Ｐ−１とΛＺをそれぞれ下記の行列で表現されるオペレータとし、
【数１３】
2011150655.tif 000019
ｋ＝１，２，…，ｍについて、上記補助量子ビットを用いて、辺ｅｆを結ぶ２つの頂点に対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成される（Ｐ−１（×）Ｐ−１）ΛＺを実行する辺演算部と、
ｋ＝１，２，…，ｎ−１について、頂点ｋの次数を４で割った余りが０であり上記観測結果ｕｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが１であり上記観測結果ｔｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが２であり上記観測結果ｕｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが３であり上記観測結果ｔｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する第二頂点演算部と、
を含むグラフ状態生成装置。
【請求項２】
請求項１のグラフ状態生成装置において、
上記補助量子ビットをＹ観測しその観測結果をｓｚ１とし、対象量子ビット及び上記補助量子ビットをＺ（×）Ｘ観測しその観測結果をｓｚ２とし、上記補助量子ビットをＹ観測しその観測結果をｓｚ３とする操作を、観測結果の組（ｓｚ１，ｓｚ２，ｓｚ３）が（１，１，−１），（１，−１，−１），（−１，１，１），（−１，−１，１）の何れかになるまで、繰り返すことにより上記補助量子ビットを用いた対象量子ビットに対するσｚが実行されるとし、
上記補助量子ビットをＹ観測しその観測結果をｓｘ１とし、上記補助量子ビット及び対象量子ビットをＺ（×）Ｘ観測しその観測結果をｓｘ２とし、上記補助量子ビットをＹ観測しその観測結果をｓｘ３とする操作を、観測結果の組（ｓｘ１，ｓｘ２，ｓｘ３）が（１，１，−１），（１，−１，−１），（−１，１，１），（−１，−１，１）の何れかになるまで、繰り返すことにより上記補助量子ビットを用いた対象量子ビットに対するσｘが実行されるとし、
上記補助量子ビットをＹ観測しその観測結果をｓｈ１とし、対象量子ビット及び上記補助量子ビットをＺ（×）Ｘ観測しその観測結果をｓｈ２とし、対象量子ビットをＹ観測しその観測結果をｓｈ３とし、観測結果の組（ｓｈ１，ｓｈ２，ｓｈ３）が（１，−１，１）又は（−１，−１，−１）である場合には上記補助量子ビットに対してσｚを実行し、観測結果の組（ｓｈ１，ｓｈ２，ｓｈ３）が（１，１，１）又は（−１，１，−１）である場合には上記補助量子ビットに対してσｘを実行し、観測結果の組（ｓｈ１，ｓｈ２，ｓｈ３）が（１，１，−１）又は（−１，１，−１）である場合には、上記対象量子ビットを用いて上記補助量子ビットに対してσｚσｘを実行することにより、上記補助量子ビットを用いた対象量子ビットに対するＨが実行されるとし、
上記補助量子ビットをＹ観測しその観測結果をｓｐ１とし、第一対象量子ビット及び上記補助量子ビットをＺ（×）Ｘ観測しその観測結果をｓｐ２とし、上記補助量子ビット及び第二対象量子ビットをＺ（×）Ｘ観測しその観測結果をｓｐ３とし、上記補助量子ビットをＹ観測しその観測結果をｓｐ４とし、観測結果の組（ｓｐ１，ｓｐ２，ｓｐ３，ｓｐ４）が（１，１，−１，−１），（１，−１，１，−１），（−１，１，１，１），（−１，−１，−１，１）の何れかである場合には上記補助量子ビットを用いて第一対象量子ビットに対してσｚを実行し、観測結果の組（ｓｐ１，ｓｐ２，ｓｐ３，ｓｐ４）が（１，１，１，−１），（１，−１，−１，−１），（−１，１，−１，１），（−１，−１，１，１）の何れかである場合には上記補助量子ビットを用いて第二対象量子ビットにσｘを実行し、観測結果の組（ｓｐ１，ｓｐ２，ｓｐ３，ｓｐ４）が（１，１，−１，１），（１，−１，１，１），（−１，１，１，−１），（−１，−１，−１，−１）の何れかである場合には上記補助量子ビットを用いて第一対象量子ビットにσｚを実行し第二対象量子ビットにσｘを実行することにより、上記補助量子ビットを用いた第一対象量子ビット及び第二対象量子ビットに対するＰ−１（×）ＰＨＰＨＡＺ（Ｉ（×）Ｈ）が実行されるとし、
上記補助量子ビットを用いて第二対象量子ビットに対してＨを実行し、上記第二対象量子ビットを用いて上記第一対象量子ビット及び上記補助量子ビットに対してＰ−１（×）ＰＨＰＨＡＺ（Ｉ（×）Ｈ）を実行し、上記第二対象量子ビットを用いて上記補助量子ビットに対してＨを実行することにより、補助量子ビットを用いた第一対象量子ビット及び第二対象量子ビットに対する（Ｐ−１（×）Ｐ−１）ΛＺが実行される、
ことを特徴とするグラフ状態生成装置。
【請求項３】
頂点の集合Ｖ＝｛１，…，ｎ｝と、辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝とから構成されるグラフＧ＝（Ｖ，Ｅ）に対応するグラフ状態を生成するグラフ状態生成装置において、
ｎ個の頂点にそれぞれ対応する初期状態の量子ビットを｜０＞１｜０＞２…｜０＞ｎとし、補助量子ビットを｜０＞ｎ＋１として、
第一頂点演算部が、頂点の次数をその頂点に接続している辺の数として、ｋ＝１，２，…，ｎ−１について昇順で、頂点ｋの次数をカウントし、頂点ｋの次数が奇数の場合には頂点ｋに対応する量子ビットをＹ観測しその観測結果をｔｋとし、頂点ｋの次数が偶数の場合には頂点ｋ＋１に対応する量子ビットをＹ観測し頂点ｋ及び頂点ｋ＋１に対応する量子ビットをＺ（×）Ｘ観測しその観測結果をｕｋとし、頂点ｋに対応する量子ビットをＹ観測する第一頂点演算ステップと、
辺演算部が、Ｐ−１とΛＺをそれぞれ下記の行列で表現されるオペレータとし、
【数１４】
2011150655.tif 000020
ｋ＝１，２，…，ｍについて、上記補助量子ビットを用いて、辺ｅｆを結ぶ２つの頂点に対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成される（Ｐ−１（×）Ｐ−１）ΛＺを実行する辺演算ステップと、
第二頂点演算部が、ｋ＝１，２，…，ｎ−１について、頂点ｋの次数を４で割った余りが０であり上記観測結果ｕｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが１であり上記観測結果ｔｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが２であり上記観測結果ｕｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが３であり上記観測結果ｔｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する第二頂点演算ステップと、
を含むグラフ状態生成方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、観測ベース量子計算モデルに基づく量子コンピュータにおいて、所望のグラフ状態を生成する技術に関する。
【背景技術】
【０００２】
グラフ状態｜Ｇ〉は、頂点の集合Ｖと辺の集合Ｅの組からなるグラフＧ＝（Ｖ，Ｅ）に対して、次のステップ１からステップ３の処理により定まる量子状態である。このように、任意のグラフ状態は、アダマール変換Ｈ及び制御位相シフト演算ΛＺにより構成することができる。
【０００３】
１．Ｖに含まれる各頂点に対応して｜０〉を用意する。
【０００４】
２．用意した全ての｜０〉に対し、アダマール変換Ｈを適用する。
【０００５】
３．Ｅに含まれる各辺に対応して、制御位相シフト演算ΛＺを適用する。
【０００６】
図１８に例示するようにグラフＧが、Ｇ＝（Ｖ，Ｅ）＝（｛１，２，３，４｝，｛（１，４），（２，３），（２，４），（３，４）｝）であるとする。頂点ｉに対応する量子状態を｜０〉ｉと表記すると、ステップ１により生成された量子状態｜０〉１｜０〉２｜０〉３｜０〉４は、ステップ２のアダマール変換ＨによりＨ（×）Ｈ（×）Ｈ（×）Ｈ｜０〉１｜０〉２｜０〉３｜０〉４＝｜＋〉１｜＋〉２｜＋〉３｜＋〉４となり、ステップ３の制御位相シフト演算ΛＺによりΛＺ１４ΛＺ２３ΛＺ２４ΛＺ３４｜＋〉１｜＋〉２｜＋〉３｜＋〉４＝（１／２）（｜＋〉１｜＋〉２｜０〉３｜０〉４＋｜＋〉１｜−〉２｜１〉３｜０〉４＋｜−〉１｜−〉２｜０〉３｜１〉４−｜−〉１｜＋〉２｜１〉３｜１〉４）となる。
【０００７】
ステップ３において、ΛＺを適用する順番は、出力される状態に関係ないことに注意する。ここで、ＨとΛＺは、それぞれ下記のユニタリ行列に対応する。
【０００８】
【数１】
2011150655.tif 000003
【０００９】
非特許文献１において、１つの補助量子ビットを使い、２種類の１量子ビット観測量Ｚ，（Ｘ−Ｙ）／√２と１種類の２量子ビット観測量Ｚ（×）Ｘを基本構成要素とし、Ｈ及びΛＺを含む任意のユニタリ変換を実行する観測ベース量子回路の構成方法が示されている。（×）はテンソル積を表し、観測量Ｘ，Ｙ，Ｚは、それぞれ下記のエルミート行列に対応する（これらは１量子ビットユニタリ演算とも考えられ，その場合には，σｘ，σｙ，σｚと書く）。
【００１０】
【数２】
2011150655.tif 000004
【００１１】
したがって、非特許文献１に記載された、１つの補助量子ビットを使い、２種類の１量子ビット観測量Ｚ，（Ｘ−Ｙ）／√２及び１種類の２量子ビット観測量Ｚ（×）Ｘを基本構成要素とする観測ベース量子回路により、Ｈ及びΛＺを構成し、上記ステップ１．からステップ３．により所望のグラフ状態を出力する観測ベース量子回路を構成することができる。
【００１２】
なお、観測ベース量子回路は、観測ベース量子計算モデルにおける計算手順を表したものである。この回路は、観測を記述する１量子ビット観測量や複数量子ビット観測量を基本構成要素とする。
【先行技術文献】
【非特許文献】
【００１３】
【非特許文献１】Simon Perdrix, Towards minimal resources of measurement-based quantum coｍputation, New Journal of Physics 9 (2007) 206.
【発明の概要】
【発明が解決しようとする課題】
【００１４】
しかしながら、１つの補助量子ビットを使い、１種類の１量子ビット観測量及び１種類の２量子ビット観測量を基本構成要素とする観測ベース量子回路により、所望のグラフ状態を出力する技術は知られていないという課題がある。
【課題を解決するための手段】
【００１５】
上記の課題を解決するために、請求項１のグラフ状態生成装置は、頂点の集合Ｖ＝｛１，…，ｎ｝と、辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝とから構成されるグラフＧ＝（Ｖ，Ｅ）に対応するグラフ状態を生成するために、ｎ個の頂点にそれぞれ対応する初期状態の量子ビットを｜０＞１｜０＞２…｜０＞ｎとし、補助量子ビットを｜０＞ｎ＋１として、頂点の次数をその頂点に接続している辺の数として、ｋ＝１，２，…，ｎ−１について昇順で、頂点ｋの次数をカウントし、頂点ｋの次数が奇数の場合には頂点ｋに対応する量子ビットをＹ観測しその観測結果をｔｋとし、頂点ｋの次数が偶数の場合には頂点ｋ＋１に対応する量子ビットをＹ観測し頂点ｋ及び頂点ｋ＋１に対応する量子ビットをＺ（×）Ｘ観測しその観測結果をｕｋとし、頂点ｋに対応する量子ビットをＹ観測する第一頂点演算部と、Ｐ−１とΛＺをそれぞれ下記の行列で表現されるオペレータとし、
【００１６】
【数３】
2011150655.tif 000005
【００１７】
ｋ＝１，２，…，ｍについて、上記補助量子ビットを用いて、辺ｅｆを結ぶ２つの頂点に対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成される（Ｐ−１（×）Ｐ−１）ΛＺを実行する辺演算部と、ｋ＝１，２，…，ｎ−１について、頂点ｋの次数を４で割った余りが０であり上記観測結果ｕｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが１であり上記観測結果ｔｋ＝−１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが２であり上記観測結果ｕｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが３であり上記観測結果ｔｋ＝１の場合には上記補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する第二頂点演算部と、を含む。
【発明の効果】
【００１８】
１つの補助量子ビットを使い、１種類の１量子ビット観測量Ｙ及び１種類の２量子ビット観測量Ｚ（×）Ｘを基本構成要素とする観測ベース量子回路により、所望のグラフ状態を出力することができる。
【図面の簡単な説明】
【００１９】
【図１】グラフ状態生成装置の例の機能ブロック図。
【図２】第一頂点演算部の例の機能ブロック図。
【図３】辺演算部の例の機能ブロック図。
【図４】第二頂点選択部の例の機能ブロック図。
【図５】グラフ状態生成方法の流れ図の例。
【図６】第一頂点演算部の流れ図の例。
【図７】辺演算部の流れ図の例。
【図８】第二頂点選択部の例の機能ブロック図。
【図９】σｚを実行するための観測ベース量子回路。
【図１０】σｘを実行するための観測ベース量子回路。
【図１１】Ｈを実行するための観測ベース量子回路。
【図１２】（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）を実行するための観測ベース量子回路。
【図１３】（Ｐ−１（×）Ｐ−１）ΛＺを実行するための観測ベース量子回路の例。
【図１４】グラフ状態の例を示す図。
【図１５】図１４のグラフ状態に対して第一頂点演算部が行う観測ベース量子回路の例。
【図１６】図１４のグラフ状態に対して辺演算部が行う観測ベース量子回路の例。
【図１７】図１４のグラフ状態に対して第二頂点演算部が行う観測ベース量子回路の例。
【図１８】グラフ状態の例を示す図。
【発明を実施するための形態】
【００２０】
以下、この発明によるグラフ状態生成装置一実施形態を詳細に説明する。
【００２１】
グラフ状態生成装置は、図１に示すように、入力部１、初期状態生成部２、第一頂点演算部３、辺演算部４及び第二頂点演算部５を例えば含む。
【００２２】
入力部１は、グラフＧ＝（Ｖ，Ｅ）についての情報を受け付ける（ステップＳ１）。グラフＧ＝（Ｖ，Ｅ）についての情報は、初期状態生成部２に送られる。Ｇはｎ個の頂点からなるとし、各頂点に１からｎまでの番号を付ける。すなわち、Ｖ＝｛１，…，ｎ｝とする。また、Ｇはｍ個の辺からなるとし、各辺にｅ１，…，ｅｍと名前を付ける。すなわち、Ｅ＝｛ｅ１，…，ｅｍ｝とする。各辺ｅｊは、頂点の組により、（ｐ，ｑ）のように表現できる。
【００２３】
初期状態生成部２は、ｎ＋１個の量子ビットからなる初期状態｜０〉１・・・｜０〉ｎ｜０〉ｎ＋１を用意する（ステップＳ２）。各｜０〉ｊは頂点ｊに対応する量子ビットであり、｜０〉ｎ＋１は補助量子ビットである。
【００２４】
量子ビットとしては例えば光子を用いることができる。どのようにして、光子に対してどのように量子演算を行うのかの物理的実現については、下記の参考文献に詳しい。
〔参考文献〕徳永裕己，“光量子もつれクラスター状態を用いた量子演算の実装実験”，光学，第３７巻，第１２号，ｐｐ．７０６−７１１．
【００２５】
第一頂点演算部３は、ｋ＝１，２，…，ｎ−１について昇順で、頂点ｋの次数をカウントし、頂点ｋの次数が奇数の場合には頂点ｋに対応する量子ビットをＹ観測しその観測結果をｔｋとし、頂点ｋの次数が偶数の場合には頂点ｋ＋１に対応する量子ビットをＹ観測し頂点ｋ及び頂点ｋ＋１に対応する量子ビットをＺ（×）Ｘ観測しその観測結果をｕｋとし頂点ｋに対応する量子ビットをＹ観測する（ステップＳ３）。ここで、頂点の次数とは、その頂点に接続している辺の数である。例えば、図１４に示すグラフ状態だと、頂点１の次数は１、頂点２の次数は２、頂点３の次数は２、頂点４の次数は３である。
【００２６】
具体的には、第一頂点演算部３は、図２に示すように、第一頂点選択部３１、次数カウント部３２、第一観測部３３、第一量子演算部３４及び第一頂点選択制御部３５を例えば含み、これらの各部が以下の処理を行う。
【００２７】
第一頂点選択部３１は、まだ選択していない頂点のうち、最も番号の小さい頂点を選択する（ステップＳ３１）。以下、選択した頂点をｋとする。選択した頂点ｋについての情報は、次数カウント部３２に送られる。
【００２８】
次数カウント部３２は、頂点ｋの次数をカウントする（ステップＳ３２）。
【００２９】
制御部８は、頂点ｋの次数が奇数か偶数かを判断し（ステップＳ３３）、頂点ｋの次数が奇数の場合には、第一観測部３３の処理を頂点ｋに対応する量子ビットに行わせる。また、頂点ｋの次数が偶数の場合には、第一量子演算部３４の処理を頂点ｋに対応する量子ビットに行わせる。
【００３０】
第一観測部３３は、ｋに接続している辺の数が奇数の場合に、頂点ｋに対応する量子ビットをＹ観測し、その観測結果ｔｋを取得する（ステップＳ３４）。観測結果ｔｋ＝１の場合、頂点ｋに対応する量子ビットの状態は｜＋ｙ〉となり、観測結果ｔｋ＝−１の場合、頂点ｋに対応する量子ビットの状態は｜−ｙ〉となる。
【００３１】
第一量子演算部３４は、ｋの次数が偶数の場合に、頂点ｋに対応する量子ビットを補助量子ビットとして頂点ｋ＋１に対応する量子ビットをＹ観測し頂点ｋ及び頂点ｋ＋１に対応する量子ビットをＺ（×）Ｘ観測しその観測結果をｕｋとする（ステップＳ３５）。観測結果ｕｋ＝１の場合、ｋに対応する量子ビットの状態は｜＋〉となる。ｕｋ＝−１の場合、ｋに対応する量子ビットの状態は｜−〉となる。
【００３２】
第一頂点選択制御部３５は、選択している頂点ｋが最も番号の大きい頂点（ｋ＝ｎ）であるか否かを判定し（ステップＳ３６）、ｋ＜ｎの場合には第一頂点選択部３１によるステップＳ３１の処理に移行する。ｋ＝ｎの場合は、辺演算部４によるステップＳ４の処理に移行する。
【００３３】
グラフ状態が図１４に示すものである場合には、第一頂点演算部３により図１５に例示する処理が行われる。
【００３４】
辺演算部４は、Ｐ−１とΛＺをそれぞれ下記の行列で表現されるオペレータとし、
【００３５】
【数４】
2011150655.tif 000006
【００３６】
ｋ＝１，２，…，ｍについて、補助量子ビットを用いて、辺ｅｆを結ぶ２つの頂点に対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成される（Ｐ−１（×）Ｐ−１）ΛＺを実行する（ステップＳ４）。
【００３７】
具体的には、辺演算部４は、図３に例示するように、辺選択部４１、第二量子演算部４２及び辺選択制御部４３を例えば含み、これらの各部が以下の処理を行う。
【００３８】
辺選択部４１は，辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝の中からまだ選択していない辺を選択する（ステップＳ４１）。以下の説明では、選択した辺をＬとおき、Ｌを頂点の組により表現したものを（ｐ，ｑ）とおく。選択された辺についての情報は、第二量子演算部４２に送られる。
【００３９】
第二量子演算部４２は、頂点ｐに対応する量子ビット及び頂点ｑに対応する量子ビットに対して、Ｙ観測及びＺ（×）Ｘ観測で構成される（Ｐ−１（×）Ｐ−１）ΛＺを実行する（ステップＳ４２）。（Ｐ−１（×）Ｐ−１）ΛＺがどのようにして、Ｙ観測及びＺ（×）Ｘ観測で構成されるのかについては後述する。
【００４０】
辺選択制御部４３は，辺の集合Ｅ＝｛ｅ１，…，ｅｍ｝の中からまだ選択していない辺があるか否かを判定し（ステップＳ４３）、まだ選択していない辺があれば、辺選択部４１によるステップＳ４１の処理に移行する。また、全ての辺を選択し終わっている場合には，第二頂点演算部５によるステップＳ５の処理に移行する。
【００４１】
グラフ状態が図１４に示すものである場合には、辺演算部４により図１６に例示する処理が行われる。
【００４２】
第二頂点演算部５は、ｋ＝１，２，…，ｎ−１について、頂点ｋの次数を４で割った余りが０であり観測結果ｕｋ＝−１の場合には補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが１であり観測結果ｔｋ＝−１の場合には補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが２であり観測結果ｕｋ＝１の場合には補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行し、頂点ｋの次数を４で割った余りが３であり観測結果ｔｋ＝１の場合には補助量子ビットを用いて頂点ｋに対応する量子ビットに対してＹ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する（ステップＳ５）。
【００４３】
具体的には、第二頂点演算部５は、図４に例示するように、第二頂点選択部５１、剰余演算部５２、第三量子演算部５３、第二頂点選択制御部５４を含み、これらの各部が以下の処理を行う。
【００４４】
第二頂点選択部５１は、頂点集合Ｖ＝｛１，・・・，ｎ｝の中から、まだ選択していない頂点を１つ選択する（ステップＳ５１）。以下の説明では、選択した頂点をｋとする。既に次数カウント部３２において頂点ｋの次数はカウントされている。選択された頂点ｋの次数についての情報は、剰余演算部５２に送られる。
【００４５】
剰余演算部５２は、頂点ｋの次数を４で割ったときの余りを算出する（ステップＳ５２）。余りについての情報は、第三量子演算部５３に送られる。
【００４６】
第三量子演算部５３は、剰余演算部５２で算出した余りに応じて以下のような処理を行う（ステップＳ５３）。
（１）頂点ｋの次数が４で割り切れる場合
（ｉ）ｕｋ＝１の場合⇒頂点ｋに対応する量子ビットに何も適用しない。
【００４７】
（ｉｉ）ｕｋ＝−１の場合⇒６．補助量子ビットを用いて頂点ｋに対応する量子ビットに対して、Ｙ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する。σｚがどのようにＹ観測及びＺ（×）Ｘ観測で構成されるかについては後述する。
（２）頂点ｋの次数が４で割って１余る場合
（ｉ）ｔｋ＝１の場合⇒頂点ｋに対応する量子ビットに何も適用しない。
【００４８】
（ｉｉ）ｔｋ＝−１の場合⇒補助量子ビットを用いて頂点ｋに対応する量子ビットに対して、Ｙ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する。
（３）頂点ｋの次数が４で割って２余る場合
（ｉ）ｕｋ＝１の場合⇒補助量子ビットを用いて頂点ｋに対応する量子ビットに対して、Ｙ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する。
【００４９】
（ｉｉ）ｕｋ＝−１の場合⇒頂点ｋに対応する量子ビットに何も適用しない．
（４）頂点ｋの次数が４で割って３余る場合
（ｉ）ｔｋ＝１の場合⇒補助量子ビットを用いて頂点ｋに対応する量子ビットに対して、Ｙ観測及びＺ（×）Ｘ観測で構成されるσｚを実行する。
【００５０】
（ｉｉ）ｔｋ＝−１の場合⇒頂点ｋに対応する量子ビットに何も適用しない。
【００５１】
第二頂点選択制御部５４は、頂点集合Ｖ＝｛１，・・・，ｎ｝の中から、まだ選択していない頂点があるか否かを判定し（ステップＳ５４）、まだ選択していない頂点があれば第二頂点選択部５１によるステップＳ５１に処理を移行する。すべての頂点を選択し終わっている場合は、終了する。
【００５２】
終了後の量子ビットｑ１・・・ｑｎ＋１の状態は，入力のグラフＧに対するグラフ状態｜Ｇ〉となる。
【００５３】
グラフ状態が図１４に示すものである場合には、第二頂点演算部５により図１７に例示する処理が行われる。
【００５４】
なお、同じ量子ビットを連続してＹ観測する場合が多数ある。連続してＹ観測しても問題ないが、１つ目のＹ観測の結果を次のＹ観測の結果として使うことにより、連続するＹ観測を行わずに全く同じ演算を実行することができ、観測ベース量子回路はより単純になる。換言すれば、グラフ状態生成装置及び方法の処理負担を軽減することができる。
【００５５】
この発明は、上述の実施形態に限定されるものではなく、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。例えば、上記の実施形態では、初期状態生成部２、第一頂点演算部３、辺演算部４及び第二頂点演算部５のそれぞれが、量子ビット７に対して量子演算または観測操作を行っているが、図１に破線で示す量子操作部６を介して量子ビット７に対して量子演算または観測操作を行ってもよい。
【００５６】
以下では、１つの補助量子ビットを使い、１種類の１量子ビット観測量Ｙ及び１種類の２量子ビット観測量Ｚ（×）Ｘを用いてσｚ及びσｘを実行する観測ベース量子回路が構成できることを説明する。次に、これらの基本構成要素により、Ｈ、（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）及び（Ｐ−１（×）Ｐ−１）ΛＺを実行する観測ベース量子回路を構成できることを説明する。ただし、Ｐは下記のユニタリ行列に対応する。また、Ｐ−１＝σｚＰであることに注意する。
【００５７】
【数５】
2011150655.tif 000007
【００５８】
《σｚ（図９参照）》
対象量子ビットとして任意の入力量子状態｜φ〉が与えられ、補助量子ビットとして使われる状態｜ψ〉が与えられたとする。σｚ｜φ〉を出力する観測ベース量子回路は次のように構成される。
【００５９】
１．補助量子ビットをＹ観測する。観測結果をｓｚ１とする。
【００６０】
２．対象量子ビット及び補助量子ビットをＺ（×）Ｘ観測する。観測結果をｓｚ２とする。
【００６１】
３．補助量子ビットをＹ観測する。観測結果をｓｚ３とする。
【００６２】
観測結果の組（ｓｚ１，ｓｚ２，ｓｚ３）に応じて対象量子ビットに次の状態が出力される。
【００６３】
【表１】
2011150655.tif 000008
確率１／２でσｚが実行されないことがわかるが、もし実行されなかった場合は、実行されるまで上の１．から３．の操作を繰り返す。
【００６４】
《σｘ（図１０参照）》
対象量子ビットとして任意の入力量子状態｜φ〉が与えられ、補助量子ビットとして使われる状態｜ψ〉が与えられたとする。σｘ｜φ〉を出力する観測ベース量子回路は次のように構成される。
【００６５】
１．補助量子ビットをＹ観測する。観測結果をｓｘ１とする。
【００６６】
２．補助量子ビット及び対象量子ビットをＺ（×）Ｘ観測する。観測結果をｓｘ２とする。
【００６７】
３．対象量子ビットをＹ観測する。観測結果をｓｘ３とする。
【００６８】
観測結果の組（ｓｘ１，ｓｘ２，ｓｘ３）に応じて、対象量子ビットに次の状態が出力される。
【００６９】
【表２】
2011150655.tif 000009
確率１／２でσｘが実行されないことがわかるが、もし実行されなかった場合は、実行されるまで上の１．から３．の操作を繰り返す。
【００７０】
《Ｈ（図１１参照）》
対象量子ビットとして任意の入力量子状態｜φ〉が与えられ、補助量子ビットとして使われる状態｜ψ〉が与えられたとする。Ｈ｜φ〉を出力する観測ベース量子回路は次のように構成される。
【００７１】
１．補助量子ビットをＹ観測する。観測結果をｓｈ１とする。
【００７２】
２．対象量子ビット及び補助量子ビットをＺ（×）Ｘ観測する。観測結果をｓｈ２とする。
【００７３】
３．対象量子ビットをＹ観測する。観測結果をｓｈ３とする。
【００７４】
観測結果の組（ｓｈ１，ｓｈ２，ｓｈ３）に応じて、対象量子ビットを用いて、補助量子ビットに対して次の表に基づいて１量子ビットユニタリ演算σｘ，σｚ，σｚσｘの何れかを適用することにより、補助量子ビットにＨ｜φ〉が出力される。
【００７５】
【表３】
2011150655.tif 000010
《（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）｜φ〉（図１２参照）》
第一対象量子ビットと第二対象量子ビットに任意の入力量子状態｜φ〉が与えられ、補助量子ビットとして使われる状態｜ψ〉が与えられたとする。（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）｜φ〉を出力する観測ベース量子回路は次のように構成される。
【００７６】
１．補助量子ビットをＹ観測する。観測結果をｓｐ１とする。
【００７７】
２．第一量子ビット及び補助量子ビットをＺ（×）Ｘ観測する。観測結果をｓｐ２とする。
【００７８】
３．補助量子ビット及び第二量子ビットをＺ（×）Ｘ観測する。観測結果をｓｐ３とする。
【００７９】
４．補助量子ビットをＹ観測する。観測結果をｓｐ４とする。
【００８０】
観測結果の組（ｓｐ１，ｓｐ２，ｓｐ３，ｓｐ４）に応じて、第一対象量子ビットと第二対象量子ビットに、次の表に基づいて１量子ビットユニタリ演算を適用することにより、第一対象量子ビットと第二対象量子ビットに（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）｜φ〉が出力される。
【００８１】
【表４】
2011150655.tif 000011
《（Ｐ−１（×）Ｐ−１）ΛＺ（図１３参照）》
ＨＰＨＰＨ＝ｅｉπ／４Ｐ−１であるから、（Ｉ（×）Ｈ）（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）（Ｉ（×）Ｈ）＝ｅｉπ／４（Ｐ−１（×）Ｐ−１）ΛＺとなる。グローバル位相ｅｉπ／４は無視できるので、Ｈと（Ｐ−１（×）ＰＨＰＨ）ΛＺ（Ｉ（×）Ｈ）を組み合わせることにより、図１３に例示するように、（Ｐ−１（×）Ｐ−１）ΛＺを実行する観測ベース量子回路が構成できる。
【００８２】
具体的には、第一対象量子ビットと第二対象量子ビットに任意の入力量子状態｜φ〉が与えられ、補助量子ビットとして使われる状態｜ψ〉が与えられたとして、（Ｐ−１（×）Ｐ−１）ΛＺを出力する観測ベース量子回路は次のように構成される。
【００８３】
１．補助量子ビットを用いて第二対象量子ビットに対してＨを実行する。
【００８４】
２．第二対象量子ビットを用いて第一対象量子ビット及び補助量子ビットに対してＰ−１（×）ＰＨＰＨＡＺ（Ｉ（×）Ｈ）を実行する。
【００８５】
３．第二対象量子ビットを用いて補助量子ビットに対してＨを実行する。
【００８６】
このようにして、補助量子ビットを用いた第一対象量子ビット及び第二対象量子ビットに対する（Ｐ−１（×）Ｐ−１）ΛＺが実行される。なお、図１３には記載されていないが、Ｈを実行する際の観測結果の組（ｓｈ１，ｓｈ２，ｓｈ３）に応じて、また、Ｐ−１（×）ＰＨＰＨＡＺ（Ｉ（×）Ｈ）を実行する際の観測結果の組（ｓｐ１，ｓｐ２，ｓｐ３，ｓｐ４）に応じて、上記表に示したように、σｚ，σｘ，σｚσｘが適宜実行される。
【００８７】
[補足]
以下、この発明の理解を容易にするために、射影測定について説明する。
【００８８】
観測ベース量子計算モデルでは、初期状態に対し、観測だけを使って、初期状態を所望の状態に遷移させる。観測として考えるのは、射影測定と呼ばれる観測である。初めに射影測定について述べ、次に射影測定を使ったユニタリ演算の適用について説明する。
【００８９】
射影測定は、観測されるシステムの状態空間上のエルミート行列Ｍ(観測量と呼ばれる)により記述される。この観測をＭ観測と呼ぶことにする。Ｍ観測は次のように規定される。まず、Ｍはエルミートであるために、下記のようにスペクトル分解される。
【００９０】
【数６】
2011150655.tif 000012
【００９１】
ただし、ｍはＭの固有値であり、Ｐｍは固有値ｍを持つＭの固有空間への射影オペレータである。システムの状態が｜ψ〉であるときに、Ｍ観測を行うと、観測量の固有値ｍが確率ｐ(ｍ)=〈ψ |Ｐｍ |ψ〉で得られる。観測結果ｍが得られると、観測直後のシステムの状態は、次のようになる。
【００９２】
【数７】
2011150655.tif 000013
【００９３】
例えば、システムの状態空間が１量子ビット空間Ｃ２(2次元の複素ヒルベルト空間)であるとし、この空間上のエルミート行列Ｚを考える。このとき、Ｚは次のようにスペクトル分解される。
【００９４】
Ｚ＝１・｜０〉〈０|＋（−１）｜１〉〈１｜
すなわち、ｍ＝１，−１であり、Ｐ１＝｜０〉〈０|,Ｐ−１=|１〉〈１|である。システムの状態が|ψ〉=α｜０〉＋β|１〉であるとし、Ｚ観測を行うと、観測量の固有値１が確率
【００９５】
【数８】
2011150655.tif 000014
【００９６】
で得られ、観測直後のシステムの状態は、
【００９７】
【数９】
2011150655.tif 000015
【００９８】
となる。グローバル位相α/|α|は無視できるので、観測直後の状態は｜０〉となる。同様に、観測量の固有値−１が確率|β|２で得られ、観測直後のシステムの状態は|１〉となる。上のことから、Ｚ観測は、{｜０〉,|１〉}基底についての観測と呼ばれることもある。
【００９９】
さらに、例えば、Ｘ,Ｙは次のようにスペクトル分解され、これにより定まる射影測定を記述する。
【０１００】
Ｘ＝１・|＋〉〈 ＋| ＋ (−１)・|＋〉〈＋|
Ｙ＝１・|＋ｙ〉〈 ＋ｙ| ＋ (−１)・|−ｙ〉〈−ｙ|
ただし、
【０１０１】
【数１０】
2011150655.tif 000016
【０１０２】
である。
【０１０３】
上では，１量子ビットに対する射影測定について述べたが、複数量子ビットに対する射影測定も同様である。例えば、エルミート行列Ｚ（×）Ｘは2量子ビットに対する射影測定を記述している。実際、Ｚ（×）Ｘは、
【０１０４】
【数１１】
2011150655.tif 000017
【０１０５】
とスペクトル分解され、これにより上と同様に観測が規定される。
【０１０６】
上で述べた射影測定を適切に使うと、入力状態に所望のユニタリ演算を適用できる。例えば、σｚを適用する方法を考える。まず、対象量子ビットに任意の入力状態|φ〉＝α｜０〉＋β|１〉、補助量子ビットに状態|ψ〉＝γ｜０〉＋ δ|１〉が与えられたとする。すなわち、初期状態は|φ〉|ψ〉=(α｜０〉＋β|１〉)(γ｜０〉＋δ|１〉)である。
【０１０７】
上記《σｚ》のステップ１．において、補助量子ビットをＹ観測すると、γ，δに依存する確率ｐ１（γ，δ）で観測結果ｓｚ１＝１が得られ、観測直後のシステムの状態は、（α｜０〉＋β｜１〉）｜＋ｙ〉となる。また、確率ｐ−１（γ，δ）で観測結果ｓｚ１＝−１が得られ、観測直後のシステムの状態は、（α｜０〉＋β｜１〉）｜−ｙ〉となる。ただし、ｐ−１（γ，δ）＋ｐ−１（γ，δ）＝１である。ここでは，観測結果ｓｚ１＝−１が得られたとする。システムの状態は、
【０１０８】
【数１２】
2011150655.tif 000018
【０１０９】
となっている。
【０１１０】
上記《σｚ》のステップ２．において、対象量子ビット及び補助量子ビットをＺ（×）Ｘ観測をする。上で述べたＺ（×）Ｘのスペクトル分解を使うと、確率１／２で観測結果１が得られ、観測直後のシステムの状態は、α｜０〉｜＋〉＋βｉ｜１〉｜−〉となる。また、確率１／２で観測結果−１が得られ、観測直後のシステムの状態は、α｜０〉｜−〉−βｉ｜１〉｜＋〉となる。ここでは，観測結果ｓｚ２＝１が得られたとする。システムの状態は、α｜０〉｜＋〉＋βｉ｜１〉｜−〉となっている。
【０１１１】
上記《σｚ》のステップ３．において、補助量子ビットをＹ観測すると、確率１／２で観測結果１が得られ、観測直後のシステムの状態は、（α｜０〉−β｜１〉）｜＋ｙ〉＝σｚ｜φ〉｜＋ｙ〉となる。また、確率１／２で観測結果−１が得られ、観測直後のシステムの状態は、（α｜０〉＋β｜１〉）｜−ｙ〉＝｜φ〉｜−ｙ〉となる。ここでは、ｓｚ３＝１が得られたとする。システムの状態は、σｚ｜φ〉｜＋ｙ〉となっており，対象量子ビットにσｚが適用されたことになる。
【０１１２】
上では、ｓｚ１＝−１，ｓｚ２＝１，ｓｚ３＝１のときを考えたが、実際には、全ての場合（上の例では８通り）を考える必要があり、それをまとめたものが上記《σｚ》の欄の表である。このように、入力量子状態と補助量子状態を用意し、どの量子ビットに対し、どのような観測（観測量を与えることにより規定される）をどの時点で行うかを規定することにより、入力量子状態にユニタリ変換を適用できる。入力量子状態を左に示し、右に出力状態を示し、時間は左から右へ流れるとし、どの量子ビットにどのような観測をどの時点で行うかを表した図を観測ベース量子回路と呼ぶことにする。基本構成要素とは，観測ベース量子回路で使われる観測量のことであり、本発明における基本構成要素はＹとＺ（×）Ｘである。
【産業上の利用可能性】
【０１１３】
グラフ状態は、観測ベース量子計算（measurement based quantum computing）と呼ばれる量子計算の方式において、初期状態として要求される状態である。観測ベース量子計算は、１．最初に所定のグラフ状態（量子ビットがエンタングルされた状態）を準備し、２．所定の量子ビットを所定の基底で観測していくことにより、任意の量子計算の結果を得る方式である。どの順番にどの基底で量子ビットを観測するかを変えることで、様々な演算を実現することができる。
【０１１４】
グラフ状態の一種であるクラスタ状態（量子ビットを格子状に配置して、隣接する量子ビット間を全てエンタングルした状態）を初期状態とすると、任意の量子計算が実現できることが既に知られている。ここで、実行したいアルゴリズムや実現したい演算によって、別のグラフ状態を初期値とすることができれば、クラスタ状態を初期値にする場合と比べて、量子ビット数や観測の数が削減できる効果を得ることができる。この発明により、任意のグラフ状態を効率的に（少ない基本要素で）実現することができ、観測ベース量子計算の効率化に役立つ。
【符号の説明】
【０１１５】
１     入力部
２     初期状態生成部
３     第一頂点演算部
４     辺演算部
５     第二頂点演算部
６     量子操作部
７     量子ビット
８     制御部
【図１】
2011150655.tif 000021
【図２】
2011150655.tif 000022
【図３】
2011150655.tif 000023
【図４】
2011150655.tif 000024
【図５】
2011150655.tif 000025
【図６】
2011150655.tif 000026
【図７】
2011150655.tif 000027
【図８】
2011150655.tif 000028
【図９】
2011150655.tif 000029
【図１０】
2011150655.tif 000030
【図１１】
2011150655.tif 000031
【図１２】
2011150655.tif 000032
【図１３】
2011150655.tif 000033
【図１４】
2011150655.tif 000034
【図１５】
2011150655.tif 000035
【図１６】
2011150655.tif 000036
【図１７】
2011150655.tif 000037
【図１８】
2011150655.tif 000038