(57)【要約】【課題】  予め相関関係を持つ量子ビットを各ホスト間で共有しておくことにより、ネットワークの形状によらず、ホスト数の上限Ｚに対し、高々ＺlogＺに比例する時間内に確率１でリーダを決定する。【解決手段】  量子計算能力及び通信能力を持つノード（ホスト）が通信リンクにより接続されており、当該接続された複数のノードにおいて相関関係にある複数の量子ビットを各々の該ノードが１つずつ有する匿名分散システムにおいて、前記量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する。【選択図】      図１
2005198247.tif 000002
【特許請求の範囲】
【請求項１】
量子計算能力及び通信能力を持つノードが、通信リンクにより接続されており、当該接続された複数のノードにおいて相関関係にある複数の量子ビットを各々の該ノードが１つずつ有する匿名分散システムにおいて、
前記量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する、
ことを特徴とするノード選択方法。
【請求項２】
前記匿名分散システムにおける複数の前記ノードが、キャット状態の量子ビットを１つずつ有し、
前記ノードの各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記ノードの各々において、前記共有された量子ビットを所定のユニタリ変換によって変換し、
当該変換された量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、
当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項１に記載のノード選択方法。
【請求項３】
前記量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該ラベルを用いて１つのノードをリーダとして選出する過程を、
２またはノード数の下限数からノード数の上限数までのそれぞれの仮定ノード数について行い、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノードを前記匿名分散システムのリーダとして選出する、
ことを特徴とする請求項１に記載のノード選択方法。
【請求項４】
前記匿名分散システムにおける複数の前記ノードが、キャット状態の量子ビットを１つずつ有し、
前記ノードの各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記ノードの各々において、前記共有された量子ビットを所定のユニタリ変換によって変換し、
当該変換された量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、
当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項３に記載のノード選択方法。
【請求項５】
前記匿名分散システムのビューを構築し、当該構築したビューから前記仮定ノード数が正当ではないと判断したときにはリーダ選出の失敗を出力し、
前記絞込み操作の繰返しにおいて、繰返し回数が前記仮定ノード数から想定される回数より多いときにはリーダ選出の失敗を出力する、
ことを特徴とする請求項４に記載のノード選択方法。
【請求項６】
前記絞り込み操作において、
キャット状態が共有されるノード数である第１ノード数と、リーダ候補のグループに含まれるノード数である第２ノード数とが異なる時、
前記第１ノード数と前記第２ノード数との差であるノード数個の前記ノードにおいて、アダマール基底を用いて量子ビットを観測する、
ことを特徴とする請求項２または請求項４に記載のノード選択方法。
【請求項７】
前記匿名分散システムにおける複数の前記ノードが、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、
前記ノードの各々が、前記量子ビットを少なくとも１組有する時、
当該量子ビットを観測する、
ことを特徴とする請求項１または請求項３に記載のノード選択方法。
【請求項８】
前記匿名分散システムにおける複数の前記ノードが、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、
前記ノードの各々が、前記量子ビットを少なくとも１組有する時、
当該量子ビットを観測する、
ことを特徴とする請求項１または請求項３に記載のノード選択方法。
【請求項９】
量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置であって、
前記量子ビットを観測する観測手段と、
当該観測された値に基づきラベルを付与するラベル付与手段と、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するアルゴリズム制御手段と、
を備えることを特徴とするノード選択装置。
【請求項１０】
前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、
前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記共有された量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、
前記観測手段は、当該変換された前記量子ビットを観測し、
前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、
前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項９に記載のノード選択装置。
【請求項１１】
２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について、前記ラベルを用いて１つのノード選択装置をリーダとして選出する部分アルゴリズム制御手段をさらに備え、
前記アルゴリズム制御手段は、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出する、
ことを特徴とする請求項９に記載のノード選択装置。
【請求項１２】
前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、
前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記共有された量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、
前記観測手段は、当該変換された前記量子ビットを観測し、
前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、
前記部分アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項１１に記載のノード選択装置。
【請求項１３】
前記匿名分散システムのビューを構築し、当該構築したビューから前記仮定ノード数が正当ではないと判断したときには失敗を出力するビュー生成手段をさらに備え、
前記部分アルゴリズム制御手段は、前記絞り込み操作の繰返し回数が、前記仮定ノード数から想定される回数より多いときには失敗を出力する、
ことを特徴とする請求項１２に記載のノード選択装置。
【請求項１４】
前記アルゴリズム制御手段における絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いて量子ビットを観測する状態調整手段、
をさらに備えることを特徴とする請求項１０に記載のノード選択装置。
【請求項１５】
前記部分アルゴリズム制御手段における絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いて量子ビットを観測する状態調整手段、
をさらに備えることを特徴とする請求項１２に記載のノード選択装置。
【請求項１６】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組有する時、
前記観測手段は、当該量子ビットを観測する、
ことを特徴とする請求項９または請求項１１に記載のノード選択装置。
【請求項１７】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組有する時、
前記観測手段は、当該量子ビットを観測する、
ことを特徴とする請求項９または請求項１１に記載のノード選択装置。
【請求項１８】
量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置に用いられるノード選択プログラムであって、
前記量子ビットの観測を制御するステップと、
当該観測された値に基づきラベルを付与するステップと、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、
をコンピュータに実行させることを特徴とするノード選択プログラム。
【請求項１９】
前記量子ビットの観測を制御する前記ステップと、
当該観測された値に基づきラベルを付与する前記ステップと、
当該ラベルを用いて１つのノード選択装置をリーダとして選出する前記ステップとを、２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について行うステップと、
リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出するステップと、
をコンピュータに実行させることを特徴とする請求項１８に記載のノード選択プログラム。
【請求項２０】
前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、
前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記共有された量子ビットへの所定のユニタリ変換を制御するステップと、
当該変換された量子ビットの観測を制御するステップと、
前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返すステップと、
をコンピュータに実行させることを特徴とする請求項１８または請求項１９に記載のノード選択プログラム。
【請求項２１】
前記絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いた量子ビットの観測を制御するステップ、
をコンピュータに実行させることを特徴とする請求項２０に記載のノード選択プログラム。
【請求項２２】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、
当該量子ビットの観測を制御するステップ、
をコンピュータに実行させることを特徴とする請求項１８または請求項１９に記載のノード選択プログラム。
【請求項２３】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、
当該量子ビットの観測を制御するステップ、
をコンピュータに実行させることを特徴とする請求項１８または請求項１９に記載のノード選択プログラム。
【請求項２４】
量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置に用いられるノード選択プログラムを記緑したコンピュータ読み取り可能な記録媒体であって、
前記量子ビットの観測を制御するステップと、
当該観測された値に基づきラベルを付与するステップと、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、
をコンピュータに実行させるノード選択プログラムを記録した記録媒体。
【請求項２５】
前記量子ビットの観測を制御する前記ステップと、
当該観測された値に基づきラベルを付与する前記ステップと、
当該ラベルを用いて１つのノード選択装置をリーダとして選出する前記ステップとを、２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について行うステップと、
リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出するステップと、
をコンピュータに実行させるノード選択プログラムを記録した請求項２４に記載の記録媒体。
【請求項２６】
前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、
前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、
前記共有された量子ビットへの所定のユニタリ変換を制御するステップと、
当該変換された量子ビットの観測を制御するステップと、
前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返すステップと、
をコンピュータに実行させるノード選択プログラムを記録した請求項２４または請求項２５に記載の記録媒体。
【請求項２７】
前記絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いた量子ビットの観測を制御するステップ、
をコンピュータに実行させるノード選択プログラムを記録した請求項２６に記載の記録媒体。
【請求項２８】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、
当該量子ビットの観測を制御するステップ、
をコンピュータに実行させるノード選択プログラムを記録した請求項２４または請求項２５に記載の記録媒体。
【請求項２９】
前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、
前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、
当該量子ビットの観測を制御するステップ、
をコンピュータに実行させるノード選択プログラムを記録した請求項２４または請求項２５に記載の記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のノード（ホスト）がネットワークを通じて接続されている同期型分散システムにおいて、各ノードに一意性のある識別子が与えられていない場合に、各ノードが自律的に協調して、該分散処理システムを構成するノードの内の１台をリーダとして選出するノード選択方法、ノード選択装置、ノード選択プログラム及びそのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
複数のホストがネットワークを通じて接続されている同期型分散システムにおける計算の技術的な困難性は、計算に用いるデータが各ホストに分散して配置されていることにある。このため、ある特定のホスト（リーダ）に全ホストのデータを集めて計算した後、計算結果を他のホストに分配する方法を用いられるが多い。最も単純な方法は、一意に特定できる識別子を各ホストに予め手動で付与しておくことである。識別子の中で最大（または最小）の識別子を持つホストをシステムが自律的に決定する効率的な方法が存在する（例えば、非特許文献１に代表的な手法が紹介されている）ので、この方法を用いて最大（または最小）の識別子を持つホストをリーダとすれば良い。特許文献１は、アドホックネットワークシステムにおいて、専用の親機を持たない場合、電源残容量や通信レートによりリーダを選出しているが、リーダとなる端末を特定するのに、一意性のある識別子が全ホストに付与されていることを前堤としている。しかし、ホスト数が多い場合には、最初に与える識別子の一意性を保つための管理コストが膨大になるという問題がある。
これに対し、一意とは限らない識別子が与えられている場合や、全く識別子が与えられていない場合でも、ホストを接続するネットワークが特定の形状であれば、リーダを決定できることが知られている。非特許文献２によれば識別子ｉを持っているホストの数をｎｉ，ｊ本の通信リンクに接続されているホストの数をｄｊとすると、全てのｉ及びｊに対する、ｎｉ及びｄｊの間に２以上の共通因数がなければ、ホスト数ｎに依存する時間内に必ずリーダを決定することができる。
また、確率的にリーダを決定する方法がある（例えば、非特許文献３）。
【特許文献１】特開平１０−１４５２７６号公報
【非特許文献１】Ｎ．Ａ．リンチ（N. A. Lynch），「分散アルゴリズム（Distributed Algorithms）」，アメリカ，モーガン・コーフマン・パブリッシャーズ（Morgan Kaufman Publishers），１９９６年
【非特許文献２】亀田恒彦、山下雅史，「分散アルゴリズム」，近代科学社，１９９４年
【非特許文献３】イタリ、ロデ（A，Itai and M. Rodeh）,「分散ネットワークにおけるシンメトリー・ブレーキング（Symmetry breaking in distributive networks）」,第２２回ＩＥＥＥコンピュータサイエンス基盤シンポジウム会報（In Proceeding of the 22nd IEEE Symposium on Foundation on Computer Science）,ｐ．１５０−１５８,ＩＥＥＥ（Institute of Electrical and Electronics Engineers：電気電子技術者協会）,１９８１年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献２の方法でリーダを決定できるのは、特定の場合にすぎず、一般に（例えば、識別子をもっていないホストがリング状に接続されている場合）、最悪の場合に要する時間を保証するリーダ決定手法は原理的に存在しないことが示されている（すなわち、最悪の場合、終了しない可能性のある手法しか存在しない）。これは、ネットワークの同期／非同期によらず、また、システム内ホスト数やネットワーク形状が予め各ホストに知らされていても同様である。
非特許文献３は、確率的にリーダを決定する方法であるが、リーダが決定するまでの時間は、平均値として保証されるだけであって、最悪の場合に要する時間は保証されない。
【０００４】
本発明は、このような事情を考慮してなされたもので、その目的は、同期ネットワークでかつホスト数の上限さえ各ホストに知らされていれば、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことにより、ネットワークの形状によらず、ネットワークを構成するホスト数の上限Ｚに対し、高々ＺlogＺに比例する時間内に確率１でリーダを決定することができるノード選択方法、ノード選択装置、ノード選択プログラム及びそのプログラムを記録した記録媒体を提供することにある。
【課題を解決するための手段】
【０００５】
前記課題を解決するために、請求項１記載の発明は、量子計算能力及び通信能力を持つノードが、通信リンクにより接続されており、当該接続された複数のノードにおいて相関関係にある複数の量子ビットを各々の該ノードが１つずつ有する匿名分散システムにおいて、前記量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する、ことを特徴とするノード選択方法である。
【０００６】
請求項２に記載の発明は、請求項１に記載のノード選択方法であって、前記匿名分散システムにおける複数の前記ノードが、キャット状態の量子ビットを１つずつ有し、前記ノードの各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記ノードの各々において、前記共有された量子ビットを所定のユニタリ変換によって変換し、当該変換された量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【０００７】
請求項３に記載の発明は、請求項１に記載のノード選択方法であって、前記量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該ラベルを用いて１つのノードをリーダとして選出する過程を、２またはノード数の下限数からノード数の上限数までのそれぞれの仮定ノード数について行い、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノードを前記匿名分散システムのリーダとして選出する、ことを特徴とする。
【０００８】
請求項４に記載の発明は、請求項３に記載のノード選択方法であって、前記匿名分散システムにおける複数の前記ノードが、キャット状態の量子ビットを１つずつ有し、前記ノードの各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記ノードの各々において、前記共有された量子ビットを所定のユニタリ変換によって変換し、当該変換された量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【０００９】
請求項５に記載の発明は、請求項４に記載のノード選択方法であって、前記匿名分散システムのビューを構築し、当該構築したビューから前記仮定ノード数が正当ではないと判断したときにはリーダ選出の失敗を出力し、前記絞込み操作の繰返しにおいて、繰返し回数が前記仮定ノード数から想定される回数より多いときにはリーダ選出の失敗を出力する、ことを特徴とする。
【００１０】
請求項６に記載の発明は、請求項２または請求項４に記載のノード選択方法であって、前記絞り込み操作において、キャット状態が共有されるノード数である第１ノード数と、リーダ候補のグループに含まれるノード数である第２ノード数とが異なる時、前記第１ノード数と前記第２ノード数との差であるノード数個の前記ノードにおいて、アダマール基底を用いて量子ビットを観測する、ことを特徴とする。
【００１１】
請求項７に記載の発明は、請求項１または請求項３に記載のノード選択方法であって、前記匿名分散システムにおける複数の前記ノードが、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、前記ノードの各々が、前記量子ビットを少なくとも１組有する時、当該量子ビットを観測する、ことを特徴とする。
【００１２】
請求項８に記載の発明は、請求項１または請求項３に記載のノード選択方法であって、前記匿名分散システムにおける複数の前記ノードが、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、前記ノードの各々が、前記量子ビットを少なくとも１組有する時、当該量子ビットを観測する、ことを特徴とする。
【００１３】
請求項９に記載の発明は、量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置であって、前記量子ビットを観測する観測手段と、当該観測された値に基づきラベルを付与するラベル付与手段と、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するアルゴリズム制御手段と、を備えることを特徴とするノード選択装置である。
【００１４】
請求項１０に記載の発明は、請求項９に記載のノード選択装置であって、前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記共有された量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、前記観測手段は、当該変換された前記量子ビットを観測し、前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【００１５】
請求項１１に記載の発明は、請求項９に記載のノード選択装置であって、２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について、前記ラベルを用いて１つのノード選択装置をリーダとして選出する部分アルゴリズム制御手段をさらに備え、前記アルゴリズム制御手段は、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出する、ことを特徴とする。
【００１６】
請求項１２に記載の発明は、請求項１１に記載のノード選択装置であって、前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記共有された量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、前記観測手段は、当該変換された前記量子ビットを観測し、前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、前記部分アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【００１７】
請求項１３に記載の発明は、請求項１２に記載のノード選択装置であって、前記匿名分散システムのビューを構築し、当該構築したビューから前記仮定ノード数が正当ではないと判断したときには失敗を出力するビュー生成手段をさらに備え、前記部分アルゴリズム制御手段は、前記絞り込み操作の繰返し回数が、前記仮定ノード数から想定される回数より多いときには失敗を出力する、ことを特徴とする。
【００１８】
請求項１４に記載の発明は、請求項１０に記載のノード選択装置であって、前記アルゴリズム制御手段における絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いて量子ビットを観測する状態調整手段、をさらに備えることを特徴とする。
【００１９】
請求項１５に記載の発明は、請求項１２に記載のノード選択装置であって、前記部分アルゴリズム制御手段における絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いて量子ビットを観測する状態調整手段、をさらに備えることを特徴とする。
【００２０】
請求項１６に記載の発明は、請求項９または請求項１１に記載のノード選択装置であって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組有する時、前記観測手段は、当該量子ビットを観測する、ことを特徴とする。
【００２１】
請求項１７に記載の発明は、請求項９または請求項１１に記載のノード選択装置であって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組有する時、前記観測手段は、当該量子ビットを観測する、ことを特徴とする。
【００２２】
請求項１８に記載の発明は、量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置に用いられるノード選択プログラムであって、前記量子ビットの観測を制御するステップと、当該観測された値に基づきラベルを付与するステップと、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、をコンピュータに実行させることを特徴とするノード選択プログラムである。
【００２３】
請求項１９に記載の発明は、請求項１８に記載のノード選択プログラムであって、前記量子ビットの観測を制御する前記ステップと、当該観測された値に基づきラベルを付与する前記ステップと、当該ラベルを用いて１つのノード選択装置をリーダとして選出する前記ステップとを、２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について行うステップと、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出するステップと、をコンピュータに実行させることを特徴とする。
【００２４】
請求項２０に記載の発明は、請求項１８または請求項１９に記載のノード選択プログラムであって、前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記共有された量子ビットへの所定のユニタリ変換を制御するステップと、当該変換された量子ビットの観測を制御するステップと、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返すステップと、をコンピュータに実行させることを特徴とする。
【００２５】
請求項２１に記載の発明は、請求項２０に記載のノード選択プログラムであって、前記絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いた量子ビットの観測を制御するステップ、をコンピュータに実行させることを特徴とする。
【００２６】
請求項２２に記載の発明は、請求項１８または請求項１９に記載のノード選択プログラムであって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又０である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、当該量子ビットの観測を制御するステップ、をコンピュータに実行させることを特徴とする。
【００２７】
請求項２３に記載の発明は、請求項１８または請求項１９に記載のノード選択プログラムであって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、当該量子ビットの観測を制御するステップ、をコンピュータに実行させることを特徴とする。
【００２８】
請求項２４に記載の発明は、量子計算能力及び通信能力を持つノード選択装置が、通信リンクにより接続されており、当該接続された複数の前記ノード選択装置において相関関係にある複数の量子ビットを各々の前記ノード選択装置が１つずつ有する匿名分散システムにおける前記ノード選択装置に用いられるノード選択プログラムを記緑したコンピュータ読み取り可能な記録媒体であって、前記量子ビットの観測を制御するステップと、当該観測された値に基づきラベルを付与するステップと、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、をコンピュータに実行させるノード選択プログラムを記録した記録媒体である。
【００２９】
請求項２５に記載の発明は、請求項２４に記載の記録媒体であって、前記量子ビットの観測を制御する前記ステップと、当該観測された値に基づきラベルを付与する前記ステップと、当該ラベルを用いて１つのノード選択装置をリーダとして選出する前記ステップとを、２またはノード選択装置数の下限数からノード選択装置数の上限数までのそれぞれの仮定ノード数について行うステップと、リーダの選出が成功した仮定ノード数のうち最大の仮定ノード数について選出したノード選択装置を前記匿名分散システムのリーダとして選出するステップと、をコンピュータに実行させるノード選択プログラムを記録したことを特徴とする。
【００３０】
請求項２６に記載の発明は、請求項２４または請求項２５に記載の記録媒体であって、前記匿名分散システムにおける複数の前記ノード選択装置が、キャット状態の量子ビットを１つずつ有し、前記ノード選択装置の各々が、互いに無相関の前記キャット状態の量子ビットを複数組有する時、前記共有された量子ビットへの所定のユニタリ変換を制御するステップと、当該変換された量子ビットの観測を制御するステップと、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返すステップと、をコンピュータに実行させるノード選択プログラムを記録したことを特徴とする。
【００３１】
請求項２７に記載の発明は、請求項２６に記載の記録媒体であって、前記絞り込み操作において、キャット状態が共有されるノード選択装置数と、リーダ候補のグループに含まれるノード選択装置数とが異なる時、自身がリーダ候補のグループに属さない場合にアダマール基底を用いた量子ビットの観測を制御するステップ、をコンピュータに実行させるノード選択プログラムを記録したことを特徴とする。
【００３２】
請求項２８に記載の発明は、請求項２４または請求項２５に記載の記録媒体であって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、１つの基底のみが１である又は０である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、当該量子ビットの観測を制御するステップ、をコンピュータに実行させるノード選択プログラムを記録したことを特徴とする。
【００３３】
請求項２９に記載の発明は、請求項２４または請求項２５に記載の記録媒体であって、前記匿名分散システムにおける複数の前記ノード選択装置が、基底状態を任意に重ね合わせた状態であり、当該基底状態を構成する複数の基底の内、０の基底の数と１の基底の数とが互いに素である量子ビットを１つずつ有し、前記ノード選択装置の各々が、前記量子ビットを少なくとも１組記憶する時、当該量子ビットの観測を制御するステップ、をコンピュータに実行させるノード選択プログラムを記録したことを特徴とする。
【発明の効果】
【００３４】
本発明によれば、同期ネットワークでかつホスト数の上限が各ホストに知らされている場合に、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことにより、ホストに予め一意性を保つための識別子を与える必要がなく、また、ネットワークの形状によらず、ホスト数の上限Ｚに対して、高々ＺlogＺに比例する時間内に確率１でリーダを決定することができる。
【発明を実施するための最良の形態】
【００３５】
本発明は、識別子が予め付与されていない同種の上限Ｚ個のノードを有する任意形状のネットワークにおいて、ＺlogＺに比例するステップによって、或る１つのノードを選択する。ここでノードとは、量子計算能力を含む計算能力があり、他のノードと通信能力があるものをいう。なお、ノードとしては、物理的実体を伴うホストや、物理的実体を伴わないプロセスなどがある。
【００３６】
現在広く使われている計算機は、計算の単位として「０」または「１」を値としてとるビットが用いられている。しかし、量子力学の原理である量子重ね合わせ状態を利用すると、「０」及び「１」に加えて、「０」と「１」の重ね合わせを表現できる計算の単位を物理的に実現できることが実験的に確かめられている。この計算の単位を量子ビットと呼び、量子ビットに基づいた演算により計算を行う計算機を量子計算機と呼ぶ。上記の量子計算能力とは、量子計算機が持つ計算能力のことである。この、量子計算機を実現するための種々の基本素子は現在研究開発が行われており、本実施の形態では、これらの素子を用いて量子ビットに基づいた演算を行う量子計算能力を実現する。また、量子ビットとは、通常の計算機におけるビットと同様に、特定の物理実体に依存するものではなく、概念的なものである。しかし、原子の核スピンを量子ビットと見なす方法は、量子ビットの物理的実現方法の代表例である。
【００３７】
上述するように、量子ビットは、「０」と「１」とを重ね合わせた状態をとることができ、観測したときに「０」と「１」のどちらであるかが決まる。そして、従来の「０」または「１」の値のみをもつビット（「古典ビット」とよぶ）の「０」を示す量子ビットを|0〉、「１」を示す量子ビットを|1〉と表す。また、「０」または「１」の値をもつ量子ビット|0〉、|1〉を行列で表すと、下記のようになる。
【００３８】
【数１】
2005198247.tif 000003
【００３９】
また、「０」と「１」とを重ね合わせた状態は、以下のように表現される。
α|0〉＋β|1〉
ただし、α,βは複素数、かつ、|α|2+|β|2＝１であり、確率|α|2で「０」が、確率|β|2で「１」が観測されることを示している。また、重ね合わせの状態により「＋」以外に「−」もとりうる。そして、「０」または「１」が観測された場合、重ね合わせ状態は、|0〉または|1〉の状態に収縮する。
【００４０】
また、|00...0〉は、複数の量子ビット|0〉,|0〉,・・・, |0〉の直積を示す。すなわち、下記のようになる。
【００４１】
【数２】
2005198247.tif 000004
【００４２】
また、本明細書中では、便宜上、
【００４３】
【数３】
2005198247.tif 000005
をＸyzと記載する場合がある。
【００４４】
Ｉ．発明の実施の形態１
＜概要＞
本実施の形態の概要は以下のとおりである。前述したネットワーク上の各ノードが、相関関係のあるｎ個の量子ビットのうちの１つを保有している。ただし、ｎは、ノードの数とする。各ノードは、ｎを知らないことは前述の通りである。このｎ個の量子ビットが全て|0〉または全て|1〉である確率が同じであるキャット状態（ｎキャット状態）にある場合、これを一組の「共有されたキャット状態」と呼ぶ。そして、前述したネットワーク上のｎ個のノードは、少なくとも「共有されたキャット状態」を少なくとも(Ｚ−１)logＺ組有する構成、即ち、同一ノード上においては互いに相関のない前記１個の量子ビットを少なくとも(Ｚ−１)logＺ組有する構成をとっている。このとき、仮定するノード数（以下、「仮定ノード数」）をｍとすると、正しいノード数ｍが分かっていた場合にｍlogｍに比例する時間内に、確率１でリーダを選出するアルゴリズムを、ｍ＝２からｍ＝Ｚまでの（ホストは２台以上あるときを考えるので、ｍ＝１の場合は、実行しない）Ｚ種類のノード数に対して、並列に動作させる。これらの並列に動作するアルゴリズムの各々を、部分アルゴリズムと呼ぶことにする。実際のノード数ｎに対して、ｍ＞ｎのときは、部分アルゴリズムの出力により、これを検出することが出来る。このため、実際のノード数ｎがわかるので、ｍ＝ｎに対する部分アルゴリズムによって選出されたリーダを、正しいリーダとすることで、リーダを正しく選出することができる。
【００４５】
各部分アルゴリズムは、各ノードにおいて、１組のｎキャット状態にある量子ビットに所定の変換（ユニタリ操作、または、ユニタリ変換と言う）を行い、観測することによって得られた値に依存してノードにラベルを付与し、このラベルからリーダ候補を選択する。ｍ＝ｎの場合は、１回のリーダ候補の選択により、リーダ候補は、選択前の半分以下となり、共有されたキャット状態が１組消費される。このリーダ候補の選択を再帰的に行っていくことによりリーダが選出される。
【００４６】
該部分アルゴリズムの内、ノード数としてｍを仮定した部分アルゴリズムを、手続きLeaderSub(ｍ)と表すことにすると、各ノードにおける手続きLeaderSub(ｍ)は、他のノードの手続きLeaderSub(ｍ)と情報を交換する必要がある。これは、該情報に対して、手続きLeaderSub(ｍ)が仮定ノード数ｍをラベルとして付加することで、他ノードにおいて、手続きLeaderSub(ｍ)に該情報を受信させることが可能である。従って、ある手続きLeaderSub(ｍ)が送信した情報を、ｍ'≠ｍに対して、送信先ノードにおける手続きLeaderSub(ｍ')が受信処理するというような混乱は避けることができる。
【００４７】
＜詳細＞
本実施の形態においては、物理的実体を伴うノードとしてのホスト（ノード選択装置）ｖが通信リンクによって相互に接続されることにより構成される、分散システムを扱う。分散システムは、ネットワークとも言う。図１に分散システムの例を示す。同図においては、６個のホストｖ（これらをｖ１〜ｖ６とする）が通信リンクによって相互に接続されている。なお、ノードは、物理実体を伴う必要性はないため、例えば、ホストをプロセスと置き換え、ホスト間の通信をプロセス間の通信と考えても良い。この場合、システムを構成するプロセスの内のいくつかが物理的には同一のホスト内にあり、これらのプロセス同士の通信は、同一ホスト内でのプロセス間通信で行われる。以下では、ホストに限って、実施の形態の説明を行うが、同様の説明がホストをプロセスに置き換えた場合にも成立することは明白である。
【００４８】
図２に各ホストｖの構成例を示す（より詳細な構成は後述）。各ホストｖは、例えば、量子計算機であり、キャット状態量子ビット格納装置（量子ビット格納手段）１０と、リーダ選出手段２０と、ポート３０とを備える。各ホストｖは、ポート３０によって、該ホストｖに接続する通信リンクを識別することができる。これには、例えば、各通信リンクに対応するポート３０を自然数により番号付けしておけばよい。ただし、この番号付けは、各ホストｖによって独立に行われていてもよいものとする。各ホストｖは、キャット状態量子ビット格納装置１０内に、ｎ個のホストｖ間においてキャット状態にある１個の量子ビットをそれぞれ有しており、互いに相関のない前記１個の量子ビットを少なくとも(Ｚ−１)logＺ組持っている。すなわち、各ホストｖは、キャット状態にある量子ビットを少なくとも(Ｚ−１)logＺ組持っていることになる。ただし、ｎ個の量子ビットからなるキャット状態とは、(|00...0〉＋|11...1〉)／21/2（以下、「21/2」を「√2」と記載する）で表される状態を言う。これは、すなわち、全ての量子ビットが|0〉である確率と、全ての量子ビットが|1〉である確率とが１／２ずつであることを示している。図２に示すように、リーダ選出手段２０は、上記キャット状態にある量子ビットと他ホストｖとの通信を利用することにより、分散システム内のホストｖの中から１台のホストｖをリーダとして選出する。各ホストｖは、識別子等は一切もっていないものとする。この意味で、ホストｖ間の差異は全くない。このようなホストからなる、分散システムを匿名分散システムまたは匿名ネットワークと言う。
匿名ネットワーク上でリーダ選挙問題を解く(リーダを選出する）ためには、ネットワークを構成するホストｖのうちの一つの状態を他のホストｖの状態と異なる状態にする必要がある。
【００４９】
以下に示す、手続きLeaderSub(ｍ)は、(i)上記(Ｚ−１)個の部分アルゴリズムが必ずＺlogＺに比例する時間内で終了するように、また、(ii)上記(Ｚ−１)個の部分アルゴリズムのうちどれが正しいホスト数に対するアルゴリズムかを出力を見て特定出来ることを保証する。
次に示す、手続きLeaderMain(Ｚ)は、ホスト数（ノード数）の上限Ｚを入力として、リーダを選出するアルゴリズムである。手続きLeaderSub(ｍ)は、手続きLeaderMain(Ｚ)の中で呼ばれる。
【００５０】
[手続きLeaderMain(Ｚ)]
図３は、ホストｖにおいてホスト数の上限Ｚを入力としてリーダを選出するための手続きLeaderMain(Ｚ)のフローチャートである。
（１）各ホストｖは、仮定ホスト数ｍ＝２，…，Ｚに対して、手続きLeaderSub(ｍ)を並列に動作させる（ステップＳｍ１１０−２〜Ｓｍ１１０−Ｚ）。
（２）Ｍを、「成功」を出力した手続きLeaderSub(ｍ)が仮定ホスト数ｍの中で最大の値であるとする（ステップＳｍ１２０）。このとき、最大値Ｍを仮定した手続きLeaderSub(Ｍ)が選出したリーダのホストｖを正しいリーダとする（ステップＳｍ１３０）。
【００５１】
上述するように、手続きLeaderMain(Ｚ)の中で、ホスト数ｍ＝２，…，Ｚを仮定したリーダ選挙手続きLeaderSub(ｍ)が並列に動作する。仮定ホスト数ｍが実際のホスト数ｎより大きい場合、手続きLeaderSub(ｍ)は、必ず「失敗」を出力する（理由は後述）。また、仮定ホスト数ｍが実際のホスト数ｎと等しいときは、必ず「成功」を出力する。従って、「成功」を出力した手続きLeaderSub(ｍ)が仮定ホスト数ｍの中で最大値をＭとすると、手続きLeaderSub(Ｍ)が選出したリーダを採用すればよい。仮定ホスト数ｍが実際のホスト数ｎより小さい場合は、「失敗」を出力する場合と「成功」を出力する場合の両方が考えられるが、上記のように手続きLeaderSub(Ｍ)が選出したリーダを採用すれば問題はない。
次に手続きLeaderSub(ｍ)を示す。
【００５２】
[手続きLeaderSub(ｍ)]
図４は、ホストｖにおいて、仮定ホスト数ｍについてリーダを選出するための手続きLeaderSub(ｍ)のフローチャートである。各ホストｖは、３つの変数、phase(ｖ)、ｋ(ｖ)、flag(ｖ)を持つ。phase(ｖ)は、以下に示す（２）〜（８）の手順の繰返し回数を表す。ｋ(ｖ)は、リーダ候補の数を表す。flag(ｖ)＝１のときは、ホストｖがリーダ候補に残っていることを示し、flag(ｖ)＝０のときは、そうでないことを示す。また、
【００５３】
【数４】
2005198247.tif 000006
は、Ｘを下まわらない最小の整数を表す。
【００５４】
（１）  ホストｖは、phase(ｖ)＝１、ｋ(ｖ)＝ｍ、flag(ｖ)＝１を設定する（ステップＳｓ１１０）。
（２）  後述する手続きＡ(ｍ)によりリーダ候補の続りこみを行う（ステップＳｓ１２０）。
（３）  手続きＡ(ｍ)によりにより得たリーダ候補の数ｋ(ｖ)が自然数でなければ（ステップＳｓ１３０：ＮＯ）、「失敗」を出力し停止する（ステップＳｓ１４０）。
（４）  手続きＡ(ｍ)によりにより得たリーダ候補の数ｋ(ｖ)が自然数であり（ステップＳｓ１３０：ＹＳＥ）、かつ、ｋ(ｖ)＝１ならば（ステップＳｓ１５０：ＹＥＳ）、「成功」を出力し終了する（ステップＳｓ１６０）。
（５）  ｋ(ｖ)≠１ならば（ステップＳｓ１５０：ＮＯ）、後述する手続きＤ(ｍ)を行う（ステップＳｓ１７０）。
（６）  phase(ｖ)の値を１増加させる（ステップＳｓ１８０）。
（７）  
【００５５】
【数５】
2005198247.tif 000007
ならば（ステップＳｓ１９０：ＹＥＳ）、「失敗」を出力して停止する（ステップＳｓ２００）。
（８）  
【００５６】
【数６】
2005198247.tif 000008
でなければ（ステップＳｓ１９０：Ｎｏ）、（２）に戻る。
【００５７】
上記手順において、最初は、全てのホストｖがリーダ候補であるとする。すなわち、全てのホストｖに対して、flag(ｖ)＝１である。ｍ＝ｎの場合、手続きＡ(ｍ)（後述）はリーダ候補を半分以下に絞りこむ。よって、（２）〜（８）の手順を高々
【００５８】
【数７】
2005198247.tif 000009
回だけ繰りかえせば、リーダを一つに決定し、停止する。手続きＡ(ｍ)は、リーダ候補に含まれるホストｖが、そのホストｖ間だけでキャット状態の量子ビットを共有していることを前堤とする。最初に手続きＡ(ｍ)が呼ばれたときは、全てのホストｖがリーダ候補であり、全てのホストｖの間でキャット状態量子ビットが共有されているので、問題はない。しかし、リーダ候補が絞りこまれ、リーダ候補の数ｋ(ｖ)が全ホスト数ｎより少ない場合には、ｎノード間で共有しているｎキャット状態の量子ビットから、リーダ候補に含まれるｋ(ｖ)個のノード間だけで共有するキャット状態の量子ビットを生成する必要がある。これを行うのが手続きＤ(ｍ)である。以上が、手続きLeaderSub(ｍ)の働きである。ただし、これは、ｍ＝ｎの場合である。
【００５９】
次に、ｍ≠ｎの場合も含めて、手続きLeaderSub(ｍ)について詳細に説明する。
仮定ホスト数ｍが実際のホスト数ｎと等しくない場合、手続きＡ(ｍ)で更新されるｋ(ｖ)は、正しくリーダ候補のホスト数を表していない可能性がある。特に、ｋ(ｖ)が自然数でない場合は、明らかにリーダ候補のホスト数を表していないので、（３）において「失敗」を出力して、正しくリーダを選出していない旨を明かにした上で、停止させる。
【００６０】
さらに、ｍ≠ｎの場合、手続きＤ(ｍ)で処理した後、得られる状態は、キャット状態になっていない可能性がある（しかし、手続きＤ(ｍ)自体は実行可能である）。このため、手続きLeaderSub(ｍ)の（３）または（４）における条件が満たされず、停止しない可能性がある。仮定ホスト数ｍが正しいホスト数を表していれば、手続きLeaderSub(ｍ)は、（２）〜（８）の手順を高々
【００６１】
【数８】
2005198247.tif 000010
回だけ繰り返せば停止する。逆に、手続きLeaderSub(ｍ)の（２）〜（５）の手順のくり返し回数が
【００６２】
【数９】
2005198247.tif 000011
回を越えても停止していない場合は、ｍ≠ｎであるから、（７）で強制的に停止させる。
【００６３】
次に、手続きＡ(ｍ)の説明を行う。
匿名ネットワーク上でリーダ選挙問題を解く（リーダを選出する）ためには、ネットワークを構成するホストｖのうちの一つの状態を他のホストｖの状態と異なる状態にする必要がある。本方法の基本アイデアは、ｎキャット状態の量子ビットを観測して、その観測値に依存してホストｖの状態を定義するパラメータを決定することである。
【００６４】
しかし、ｎキャット状態にある量子ビットを各ホストｖがそのまま観測すれば、同じ観測値を得ることになるので、ホストの状態はやはり全て同じになってしまいリーダが決定できない。これを避けるための手法としては、各ホストｖが持つｎキャット状態の量子ビットにローカルなユニタリ操作を行うことである。ユニタリ操作とは、ユニタリ行列を作用させることであり、これにより、ある重ね合わせ状態を、別の重ね合わせ状態に変換することができる。しかし、単にユニタリ操作を行えば良いと言うことではない。例えば、ユニタリ操作を行った結果、システム内のｎ量子ビットが、基底状態|00...0〉や|11...1〉が重ね合わされた状態であると、観測を行った結果、全てのホストｖが同じ値を得る可能性がある。別のｎキャット状態の量子ビットに対して、同様の操作及び観測を繰りかえし行っても、再び、全てのホストｖが同じ値を得る可能性があるので、リーダ選出に要する最悪の場合の時間が保証できないことになる。
【００６５】
以下で２つのローカルなユニタリ操作ＵｎおよびＶｎを定義する。これらを、各ホストｖ内で、ｎキャット状態の量子ビットに作用させることで、全てのホストｖが同じ値を観測する確率を０にできる。これを用いて、最悪計算時間を保証するアルゴリズムが構成することができる。
予め決められた実数ψと整数ｍに対して、
【００６６】
【数１０】
2005198247.tif 000012
と定義する。Ｕｎの共役転置行列を
【００６７】
【数１１】
2005198247.tif 000013
で表し、単位行列Ｉとすると、
【００６８】
【数１２】
2005198247.tif 000014
が成り立つことからＵｎがユニタリであることがわかる。また、ｎが偶数のときに、各ホストｖが、ｎキャット状態にある量子ビットにＵｎを作用させると、システム内のｎ量子ビットの状態に重ね合わされている基底状態|00...0〉と|11...1〉の振幅は０になることが計算によりわかる。つまり、Ｕｎを作用させたのち各ホストｖが観測により得る値を考えると、全てのホストｖが０を観測する場合と、全てのホストｖが１を観測する場合はともにあり得ない。つまり、ｎ個のホストｖの中に、０を観測するホストと１を観測するホストがともに存在する。ただし、以上が成り立つのは、ｎが偶数の場合に限る。
【００６９】
次に、ユニタリ操作Ｖｎを定義する。
【００７０】
【数１３】
2005198247.tif 000015
【００７１】
Ｖｎは、計算により
【００７２】
【数１４】
2005198247.tif 000016
を満たすことから、確かにユニタリ操作であることがわかる。Ｖｎは、４×４の行列である。つまり、２量子ビットに対して、同時に作用するものである。しかし、各ホストｖは、各組のｎキャット状態の量子ビットを一つ（ａと呼ぶ）ずつしか持っていない。そこで、各ホストｖは、|0>に初期化された新たな量子ビットを一つ（ｂと呼ぶ）用意し、ａを制御量子ビットとし、ｂを標的（ターゲット）量子ビットとする、制御ＮＯＴ（ＣＮＯＴ）操作を行う。この結果、システム全体として、量子ビット数が２倍の２ｎ個になり、これらが、２ｎキャット状態(|00...0〉＋|11...1〉)／√2を形成する。各ホストｖは、該２量子ビットに対して、Ｖｎを作用させる。この結果生じる、システム内の２ｎ量子ビットの状態に、重ね合わせられている、４つの基底状態|00...00〉，|01... 01〉，|10...10〉，及び|11...11〉の振幅は、ｎが奇数ならば０になることが計算により確かめられる（ただし、該４つの基底状態の式では、となり合う２つの量子ビットを各ホストｖが保持していることを仮定している）。すなわち、各ホストｖがａ及びｂを観測して得られた値を２ビット値として見ると（ａとｂのうちどちらを上位ビットにするかは各ホストｖで共通させるものとする）、全てのホストｖが同じ２ビット値を観測する可能性は無いことを意味している。
【００７３】
アルゴリズムは、ＵｎまたはＶｎをｎキャット状態にある量子ビットに適用して得られた観測値を、各ホストｖの仮のラベルとする。当該ラベルと後述するラベルから仮識別子を生成する方法とを用いて、各ホストｖに仮識別子を付与する。ただし、ｎ個のホストの中には、同じ仮識別子を持つホストｖが複数存在する可能性がある。そこで、同じ仮識別子を持つホストごとにグループ化し、最小の仮識別子を持つグループをリーダの候補として、このグループの中でリーダを選ぶアルゴリズムを続行する。例えば、ｎ個のホストｖ（以下、「ｎホスト」とも記載）の中で、ｋ個のホストｖ（以下、「ｋホスト」とも記載）がリーダ候補として残れば、ｋキャット状態の量子ビットを該ｋホストに持たせ(この手続は後述)、ＵｋまたはＶｋを適用して、上記と同様にリーダ候補をさらに絞っていく。ただし、ＵｋまたはＶｋは、それぞれＵｎまたはＶｎの行列におけるｎの文字をｋで置き換えて得られる行列を表す。この絞りこみの、各繰りかえしをフェーズと呼ぶことにする。各フェーズにおいて、全てのリーダ候補が同じ仮識別子を持つことはないので、必ずリーダ候補は減っていくことが保証される。
【００７４】
［ラベルから仮識別子を生成する方法（非特許文献２、ｐ．１６９−１８０）］
各ホストｖが、必ずしもホスト毎に異なるとは限らないラベルを持っているとする。各ホストｖを節点（すなわち、分散システムにおけるノードに対応）、ホストｖ（節点）間の通信リンクを枝と見なすと、システム全体は、グラフと見なすことが出来る。このグラフをＧとする。以下、グラフＧの節点とホスト、及び、グラフＧの枝と通信リンクを、混乱の無い限り、区別せずに用いる。また、前述の通り、各ホストｖにおいて、通信リンクのポート３０は番号付けされているものとする。グラフＧの節点であるホストｖのポート番号付けを表す写像をσ[ｖ]で表すことにする。すなわち、σ[ｖ]は、他のホストｖに接続されている通信リンク（枝）からホストｖ内での該通信リンク（枝）に対応するポート３０の番号を表す。例えば、グラフＧの節点であるホストｖおよびホストｕに対して、枝である通信リンク(ｖ，ｕ)が存在したとき、ホストｖにおける通信リンク(ｖ，ｕ)に対応するポート番号は、σ[ｖ](ｖ，ｕ)で表される。
【００７５】
グラフＧの節点であるホストｖに対して、ホストｖのビューＴσ(ｖ)とは、次のように再帰的に定義される、節点（ホスト）と枝（通信リンク）にラベル付けされた、無限の高さを持つ根付き木である。
・ビューＴσ(ｖ)は、ホストｖに対応する根ｘを持つ。
・ホストｖに隣接するグラフＧの各ホストｖｉに対して、ビューＴσ(ｖ)は、節点ｘｉと、枝(ｘ，ｘｉ)を持つ。ただし、節点ｘｉは、ホストｖｉが持つ値をラベルとして持ち、枝(ｘ，ｘｉ)は、ｌ(ｖ，ｖｉ)をラベルとして持つ。ただし、ｌ(ｖ，ｖｉ)＝(σ[ｖ](ｖ，ｖｉ)，σ[ｖｉ](ｖ，ｖｉ))である。
・ホストｘｉは、ビューＴσ(ｖｉ)の根である。
【００７６】
例えば、図５に示される分散システムを考える。各ホストｖは、１から３までの自然数値でラベル付けされており、各ホストｖを接続する通信リンクの両端には、各ホストｖでのポート番号が記されている。例えば、値１をもつホストｖ１と値２を持つホストｖ２を接続する通信リンクは、値１をもつホストｖ１側ではポート番号１を持ち、値２を持つホストｖ２側では、ポート番号２を持っていることを表している。σを用いて表すと、σ[ｖ１](ｖ１，ｖ２)＝１及びσ[ｖ２](ｖ１，ｖ２)＝２となる。図５に示す分散システムにおいて、値１を持つホストｖ１のビューを、図６に示す。ビューの節点の深さは、根からの距離（根から該節点に至るために通るべき枝の数）によって定義される。根は、深さ０とする。ビューの節点の内、深さ３以上の節点は図６では省略されている。ビューの節点に付けられた数値は、該節点に対応するホストｖのラベルを表す。また、ビューの枝の両端に付けられた数値は、図５と同様、両端のホストｖでのポート番号を表している。ビューの枝の両端の数値の内、根に近い数値から順に両端の数値の組をつくることで、枝のラベルを表すことができる。例えば、ｌ(ｖ１，ｖ２)＝(σ[ｖ１](ｖ１，ｖ２)，σ[ｖ２](ｖ１，ｖ２))＝(１，２)となる。ポート番号付けがσであるときの、ホストｖのビューをＴσ(ｖ)で表すものとする。
【００７７】
もし、二つのビューＴσ(ｕ)とビューＴσ(ｖ)が同型（節点と枝のラベルも含めて）ならば、この二つのビューは等しいということにすると(Ｔσ(ｕ)≡Ｔσ(ｖ)と表す)、グラフＧの節点の内、等しいビューを持つ節点同士を一つのグループとすることにより、グラフＧの節点集合を複数のグループに分割することができる。深さ（ｎ−１）までの部分に、任意のホストｖに対応する節点が存在する。よって、
【００７８】
【数１５】
2005198247.tif 000017
（以下、「Ｔσ2(n-1)(ｖ)」と記載）の中に、任意のホストｕに対する、深さ（ｎ−１）のビューが存在する。ただし、ビューＴσ(ｖ)の深さｒまでの部分を
【００７９】
【数１６】
2005198247.tif 000018
（以下、「Ｔσr(ｖ)」と記載）
と表す。非特許文献２によれば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【００８０】
【数１７】
2005198247.tif 000019
のとき、またそのときに限り成り立つ。以下ではビューの同型性だけを問題にするので、深さｎ−１のビューを、無限の深さを持つビューの代わりとして用いる。ビューＴσ2(n-1)(ｖ)を構築できれば、システム内の全ホストｖの互いに同型でないビューの集合Гを計算することができる。等しいビューを持つ節点同士で作られた各グループの要素数は、互いに等しいから、この要素数ｃσは、ｎ／|Γ|で計算することができる。ただし、|Γ|は、Гの要素数を表す。
次に、一回のフェーズに行われるリーダ候補の絞込みの手続をまとめる。
【００８１】
［手続きＡ：リーダ候補の絞りこみの手続き]
各ホストｖは変数ｋとflag(ｖ)をもっており、ｋには、現在のリーダ候補のホスト数が設定されている。flag(ｖ)は、ホストｖ自身がリーダ候補に入っていれば、値１をとり、そうでなければ、値０を取るものとする。
【００８２】
（１）  flag(ｖ)＝１である各ホストｖは、現在のリーダ候補の数ｋが偶数ならば、各自のｋキャット状態にある量子ビットにＵｋを作用させる。ｋが奇数ならば、flag(ｖ)＝１である該ホストｖは、（i）新しい量子ビットを用意して|0〉に初期化し、（ii）各自のｋキャット状態にある量子ビット（ａとする）を制御ビット、新しく用意した量子ビット(ｂとする)を標的ビットとしてＣＮＯＴ操作を行い（この結果、２ｋキャット状態にある量子ビットを二つずつ、ｋ個のホストｖが共有する）、（iii）二つの量子ビットａ，ｂにＶｋを作用させる。
【００８３】
（２）  flag(ｖ)＝１である各ホストｖは、|0〉及び|1〉を基底として、量子ビットを観測する。これは、|0〉は|0〉のまま、|1〉は|1〉のまま観測することを意味する。
（３）  観測値を該ホストｖのラベルとする。ただし、ｋが偶数のときは、ａｂを２進表現とする値をホストｖのラベルとする。flag(ｖ)＝０であるリーダ候補ではないｎ−ｋ個のホストｖは、flag(ｖ)＝１である（リーダ候補の）ホストｖの値が取り得ない特別な値（例えば、４）を各ホストｖのラベルとする。
【００８４】
（４）  各ホストｖは、ビューＴσ2(n-1)(ｖ)を構築する（手続きＢとする）。なお、ビューＴσ2(n-1)(ｖ)の代わりに、（ｎ−１）以上の任意の値ｒ対して、
【００８５】
【数１８】
2005198247.tif 000020
（以下、「ビューＴσ2r(ｖ)」と記載）を使ってもよい。
【００８６】
（５）  flag(ｖ)＝１である（リーダ候補の）ホストｖは、各（リーダ候補の）ホストｖのビューを２進符号化した場合に、もっとも小さい２進数値になるビューに同型なビューを持つホスト数を計算する。該２進数値に関しては、互いに同型でないビューの集合Γを計算し（手続きＣとする）、Γの各要素について２進符号化することにより最小の２進数値となる（リーダ候補の）ビューを求める。また、最小の２進数値となるビューを持つホスト数ｃσ（即ち、リーダ候補数ｋ）に関しては、やはり手続きＣにより計算する。
【００８７】
（６）  flag(ｖ)＝１であるリーダ候補の各ホストｖは、自らのビューを２進符号化した値と該最小の２進数値を比べる。同一であれば、次のフェーズでもリーダ候補に入り（flag(ｖ)の値は１のままにし）、同一でなければ、次のフェーズではリーダ候補に入らない（flag(ｖ)の値を０に変化させる）。これにより、リーダ候補は半分以下に絞られる。
【００８８】
上述する手続きＡをもとに以下のように手続きＡ(ｍ)を記述することが出来る。ただし、互いに同型でないビューの集合Γを構成するビューの深さが仮定ホスト数ｍに依存するので、次の記法を導入する。すなわち、全ホストｖの集合Ｗに属するホストｖが持つ深さｍ−１のビューの内、互いに同型でないものの集合を
【００８９】
【数１９】
2005198247.tif 000021
で表す。
【００９０】
[手続きＡ(ｍ)：リーダ候補の絞りこみの手続き]
図７は、ホストｖにおいて、仮定ホスト数ｍについてリーダ候補の絞込みを行う手続Ａ（ｍ）の動作を示すフローチャートである。
各ホストｖは変数ｋ(ｖ)とflag(ｖ)をもっており、変数ｋには、手続きＡ（ｍ）が呼ばれたときの変数ｋ（ｖ）が引き継がれ、呼出元にもどるときには、変数ｋが変数ｋ（ｖ）として引き継がれる。ｋには、現在のリーダ候補のホスト数が設定される。flag(ｖ)は、ホストｖ自身がリーダ候補に入っていれば、値１をとり、そうでなければ、値０を取るものとする。
【００９１】
（１）  flag(ｖ)＝１である各ホストｖは（ステップＳａ１１０：ＹＥＳ）、現在のリーダ候補の数ｋが偶数ならば（ステップＳａ１２０：ＹＥＳ）、各自のｋキャット状態にある量子ビットにＵｋを作用させる（ステップＳａ１３０）。ｋが奇数ならば（ステップＳａ１２０：ＮＯ）、flag(ｖ)＝１である該ホストｖは、（i）新しい量子ビットを用意して|0〉に初期化し、（ii）各自のｋキャット状態にある量子ビット（ａとする）を制御ビット、新しく用意した量子ビット（ｂとする）を標的ビットとしてＣＮＯＴ操作を行い（この結果、２ｋキャット状態にある量子ビットを二つずつ、ｋ個のホストｖが共有する）、（iii）二つの量子ビットａ，ｂにＶｋを作用させる（ステップＳａ１４０、ステップＳａ１５０）。
（２）  flag(ｖ)＝１である各ホストｖは、|0〉及び|1〉を基底として、量子ビットを観測する（ステップＳａ１６０）。
（３）  観測値を該ホストｖのラベルとする（ステップＳａ１７０）。ただし、ｋが偶数のときは、ａｂを２進表現とする値をホストｖのラベルとする。flag(ｖ)＝０であるリーダ候補ではないｎ−ｋ個のホストｖは（ステップＳａ１１０：ＮＯ）、flag(ｖ)＝１である（リーダ候補の）ホストｖの値が取り得ない特別な値（例えば、４）を各ホストｖのラベルとする（ステップＳａ１８０）。
【００９２】
（４）  各ホストｖは、手続きＢ(ｍ)(後述)により、
【００９３】
【数２０】
2005198247.tif 000022
（以下、「ビューＴσ2(m-1)(ｖ)」と記載）を構築する（ステップＳａ１９０）。なお、ビューＴσ2(m-1)(ｖ)の代わりに、（ｍ−１）以上の任意の値ｒ対して、ビューＴσ2r(ｖ)を使ってもよい。
（５）  flag(ｖ)＝１である(リーダ候補の)ホストｖは、各（リーダ候補の）ホストｖのビューを２進符号化した場合に、もっとも小さい２進数値になるビューに同型なビューを持つホスト数を計算する（ステップＳａ２００）。該２進数値に関しては、手続きＣ(ｍ)(後述)により、互いに同型でないビューの集合Γm-1を計算し、Γm-1の各要素について２進符号化することにより最小の２進数値となる（リーダ候補の）ビューを求める。また、最小の２進数値となるビューを持つホスト数ｃσ（即ち、リーダ候補数ｋ(ｖ)）に関しては、やはり手続きＣ(ｍ)(後述)により計算する。
（６）  flag(ｖ)＝１であるリーダ候補の各ホストｖは（ステップＳａ２２０：ＹＥＳ）、自らのビューを２進符号化した値と該最小の２進数値を比べる（ステップＳａ２３０）。同一であれば、次のフェーズでもリーダ候補に入り（flag(ｖ)の値は１のままにし）（ステップＳａ２４０）、同一でなければ、次のフェーズではリーダ候補に入らない（flag(ｖ)の値を０に変化させる）（ステップＳａ２５０）。これにより、リーダ候補は半分以下に絞られる。
（７）  ホストｖは、ｋに、ｃσ＝ｍ／|Γm-1|をセットする（Ｓａ２６０）。
【００９４】
図８にホストｖの詳細な構成例を示す。同図において、図２におけるホストｖのリーダ選出手段２０は、状態調整手段２１、量子ビット付加手段２２、状態変換手段２３、観測手段２４、ビュー生成手段（ラベル付与手段）２５、アルゴリズム制御手段２６、及び、部分アルゴリズム制御手段２７からなる。上記手続きLeaderMain(Ｚ）は、アルゴリズム制御手段２６で行われる。手続きLeaderSub(ｍ)は、部分アルゴリズム制御手段２７を中心に行われる。具体的には、以下の通りである。上記手続きＡ(ｍ)において、（１）の実行前に、キャット状態量子ビットを一つ取り出し、状態調整手段２１により、後述の手続きＤ(ｍ)が行われ、その結果、ｋキャット状態にある量子ビットが生成されている。ｋが奇数の場合は、量子ビット付加手段２２により、新たな量子ビットが付け加えられる。その後、状態変換手段２３により、ＵｋまたはＶｋが作用される。（２）は、観測手段２４で行われ、（３）及び（４）は、ビュー生成手段２５により行われる。その後、構築したビューを用いて、（５）及び（６）は、部分アルゴリズム制御手段２７により行われ、この結果により手続きＤ(ｍ)（後述）を行う状態調整手段２１や、次のフェーズでの量子ビット付加手段２２と状態変換手段２３が制御される。
【００９５】
各ホストｖは次に示す手続きＢ(ｍ)により、ビューを構築する。手続きＢ(ｍ)では、隣接ホスト間で通信リンクを用いて、ビューの部分木を送信する必要がある。このとき、送信側では、ビューを２進符号化して、２進数の系列に変換し、受信側では、受信した２進数の系列から、元のビューを構築（復号化）しなければならない。ビューは、節点と枝にラベル付けされた根付き木であるが、この２進表現は、数多く知られている。
【００９６】
[手続きＢ(ｍ)：深さｍのビューの構築法]
図９は、ホストｖにおいて、仮定ホスト数ｍについて深さｍのビューを構築する手続Ｂ(ｍ)の動作を示すフローチャートである。
（１）  ｉに１を代入する（ステップＳｂ１１０）。なお、ｉは現在のラウンドを意味する。なお、ラウンドとは、同期ネットワークにおいて全ホストｖが一斉に下記の（２）の演算を行い、（３）においてその結果を通信し合うことをいう。
（２）  各ホストｖは、ビューの根ｘを作り、これを
【００９７】
【数２１】
2005198247.tif 000023
とする（ステップＳｂ１２０）。
（３）  各ホストｖは、
【００９８】
【数２２】
2005198247.tif 000024
（以下、「ビューＴσｉ−１(ｖ)」と記載）を２進符号で表したものを、ホストｖに接続する全ての通信リンクから送信する（ステップＳｂ１３０）。
（４）  ｉを１増加させる（ステップＳｂ１４０）。
（５）  各ホストｖは、各通信リンクから受信したビューをｘの子のホストｖを根とする部分木にして、受信したビューより、深さが１だけ大きい新たなビューＴσｉ−１(ｖ)を構築する（ステップＳｂ１５０）。
（６）  ｉ−１＝ｍならば、終了する（ステップＳｂ１６０：ＹＥＳ）。ｉ−１＜ｍならば（ステップＳｂ１６０：ＮＯ）、（３）へ移る。
【００９９】
３ラウンド目までの手続きＢ(ｍ)の動作を、ｍ＝ｒの場合に、例を使って説明する。図１０は、１ラウンド目の状況である。１ラウンド目では、各ホストｖは、ビューの根節点を作り、自己のラベルを、該根節点のラベルとする。図１１は２ラウンド目の状況である。各ホストｖは、１ラウンド目で構築した根節点からなるビューを各通信リンクから送信する。各ホストｖは、受信後、１ラウンド目で構築した根節点の子として、受信した隣接ホストｖのビューを挿入する。その結果、深さ１のビューが構築される。同図においては、各ホストｖが構築した深さ１のビューを示している。枝（通信リンク）の両端には、両端のホストｖでのポート番号が記されている。同様に３ラウンド目には、各ホストｖは深さ２のビューを構築することができる。例えば、値１を持つホストｖ１の深さ２のビューは、図１２のようになる。ただし、図１２では、他のホストｖのビューは略記されている。手続きＢ(ｍ)は、図８におけるビュー生成手段２５により行われる。
【０１００】
任意のフェーズにおいて、リーダ候補の数が偶数または奇数に応じて、それぞれ、ＵｋまたはＶｋを適用し、観測して得た値をそのホスト（節点）ｖのラベルとする。すでにリーダ候補から外れたホスト（節点）ｖは、０及び１の何れとも区別可能な特別な値をラベルとする。次に、非特許文献２（ｐ．１６９−１８０）によれば、ｍ＝ｎならば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【０１０１】
【数２３】
2005198247.tif 000025
のとき、またそのときに限り成り立つ。この性質を用いることにより、各ホストｖは、ビューＴσ2(n-1)(ｖ)から、全ホストｖのビュー及びその種類数を計算することができる。つまり、ｍ＝ｎのとき、全ホストｖのビューの種類数は、|Γm-1|に等しくなる。ところで、非特許文献２（ｐ．１６９−１８０）によれば、ｍ＝ｎのときは、等しいビューを持つ節点同士で作られるグループの各々は、互いに等しい要素数を持つことが保証される。そこで、各グループの要素数ｃσは、ｎ／|Γm-1|＝ｃσ（ｍ＝ｎ）によって、計算することができる。ｍ≠ｎのときは、以上のことは保証されない。ｃσが自然数でない場合もありうる。このような場合は、明らかにｍ≠ｎであるので「失敗」を出力して停止する。Γm-1及びｃσを計算する手続きをまとめると、以下に示す手続Ｃ(ｍ)のようになる。
【０１０２】
[手続きＣ(ｍ)：Γm-1及びｃσの計算方法]
図１３は、ホストｖにおける互いに同型でないビューの集合Γm-1及びグループの要素数ｃσを計算する手続Ｃ(ｍ)の動作を示すフローチャートである。
（１）  各ホストｖは、ビューＴσ2(m-1)(ｖ)の深さ（ｍ−１）までの節点（ホストｖ）を根とする、深さ（ｍ−１）の部分木で、互いに同型でないものの集合を求め、これをΓm-1とする（ステップＳｃ１１０）。
（２）  ｃσ＝ｍ／|Γm-1|を計算する（ステップＳｃ１２０）。
（３）  ｃσが自然数でなければ（ステップＳｃ１３０：ＮＯ）、「失敗」を出力して停止する（ステップＳｃ１４０）。
【０１０３】
例えば、図１４のようにホストｖが深さ２（ｍ−１）のビューＴσ2(m-1)(ｖ)を構築したとすると、深さ（ｍ−１）以下の節点（ホストｖ）を根とする深さ（ｍ−１）の木は、ビューＴσ2(m-1)(ｖ)の部分木になっている。よって、深さ（ｍ−１）以下の節点（ホストｖ）を根とする深さ（ｍ−１）の全ての木の内、互いに同型でないものを集めたものがΓm-1であるが、これは、ビューＴσ2(m-1)(ｖ)が得られれば計算することができる。尚、ホストｖが得るビューが、ｍ−１以上の任意のｒに対して、ビューＴσ2r(ｖ)であっても、Γm-1が計算できることは言うまでもない。手続きＣ(ｍ)は、ビュー生成手段２５により生成されたビューを用いて、図８におけるアルゴリズム制御手段２６により行われる。
【０１０４】
手続きＤ(ｍ)は、予め持っているｎキャット状態から、flag(ｖ)＝１であるホストｖが持つ量子ビット間のみ相関関係を持つ状態を生成する手続きである。仮定ホスト数ｍが正しいホスト数ｎに等しい場合、flag(ｖ)＝１であるホストｖの数は、ｋに等しく、手続きＤ(ｍ)適用後は、flag(ｖ)＝１であるホストｖが持つ量子ビットがｋキャット状態を構成している。しかし、ｍ≠ｎで有る場合は、flag(ｖ)＝１であるホストｖの数は、ｋと等しいとは限らない。さらに、このとき、手続きＤ(ｍ)適用後は、flag(ｖ)＝０であるホストｖの量子ビットは、観測が行われた結果、他のホストｖの量子ビットと相関関係を持たなくなるが、残りのflag(ｖ)＝１であるホストｖが持つ量子ビット間でキャット状態にあるとは限らない。しかし、手続自体は、ｍ≠ｎのときでも、実施することが可能である。ｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する方法である手続きＤ(ｍ)は、以下のようになる。
【０１０５】
[手続きＤ(ｍ)]
図１５は、ホストｖにおける手続Ｄ(ｍ)の動作を示すフローチャートである。
（１）  リーダ候補ではない、すなわち、flag(ｖ)≠１であるホストｖが（ステップＳｄ１１０：ＮＯ）、
【０１０６】
【数２４】
2005198247.tif 000026
により、各自が持っている量子ビットを観測する（ステップＳｄ１２０）。これは、すなわち、量子ビットを
【０１０７】
【数２５】
2005198247.tif 000027
として観測することを示す。
【０１０８】
（２）  flag(ｖ)≠１であるホストｖは、観測した値が、(|0>+|1>)／√２であれば、０を、(|0>-|1>)／√２であれば、１を各ホスト自身のラベルとする（ステップＳｄ１３０）。また、観測していないホストｖ、すなわち、flag(ｖ)＝１のリーダ候補のホストｖは（ステップＳｄ１１０：ＹＥＳ）、０及び１とは異なる特別な値（例えば２）を各ホスト自身のラベルとする（ステップＳｄ１４０）。
【０１０９】
（３）  各ホストｖは、手続きＢ(ｍ)によりビューＴσ2(m-1)(ｖ)を構築する（ステップＳｄ１５０）。
（４）  flag(ｖ)＝１である各ホストｖは（ステップＳｄ１６０：ＹＥＳ）、グループの要素数ｃσを手続きＣ(ｍ)により求める（ステップＳｄ１７０）。そして、ビューＴσ2(m-1)(ｖ)の節点の内、深さ（ｍ−１）以下にありラベル１を持つ各節点（ホストｖ）に対し、該節点（ホストｖ）を根とする深さ（ｍ−１）のビューで互いに同型でないビューの集合をΓm-1(1)を計算する（ステップＳｄ１８０）。さらに、ｃσ×|Γm-1(1)|を計算する。この値は、仮定ホスト数ｍが正しいホスト数ｎに等しい場合は、１を観測したホスト数を意味する。
【０１１０】
（５）  flag(ｖ)＝１であるホストｖは、１を値として持つホストの数が奇数であれば、|0>→|0>及び|1〉→ｅiπ/k|1〉で表されるユニタリ変換を各自の量子ビットに作用させる（ステップＳｄ１９０、ステップＳｄ２００）。
なお、ステップＳｄ１９０において、１を値として持つホストｖの数が奇数であるか否かは、以下による求める。
ｑ＝ｃσ×|Γ(1)m-1|（ｍｏｄ２）
ただし、ｍｏｄは、剰余演算子であり、除算の余りを求めることを示す。ｑが０であれば偶数、１であれば奇数である。従って、ステップＳｄ２００において、ホストの数が奇数の場合に量子ビットに作用させるユニタリ変換|1〉→ｅiπ/k|1〉は、|1〉→ｅiπq/k|1〉と同値である。
【０１１１】
（５）の手順は、（２）において、flag(ｖ)≠１であるホストｖが量子ビットを観測後、残りのflag(ｖ)＝１であるホストｖが持っている量子ビットの間の相関関係は、(|0...0>＋|1...1>)/√2と(|0...0>−|1...1>)/√2の２種類が考えられることによる。これらの内いずれか決定するには、flag(ｖ)≠１であるホストｖの内、１を観測したホストの個数が偶数か奇数かを知ることができればよい。すなわち、偶数ならば前者、奇数ならば後者と決定することができる。従って、（３）、（４）により、flag(ｖ)≠１であるホストの内、１を観測したホストの個数を求め、この結果、flag(ｖ)＝１であるホストｖが持っている量子ビットの間の相関関係が(|0...0>−|1...1>)/√2だった場合は、（５）においてｋキャット状態に変換している。
【０１１２】
図８を用いて、手続きＤ(ｍ)の流れを説明する。上記（１）において、リーダ候補ではないホストｖは、キャット状態量子ビット格納装置１０から、量子ビットを取り出したあと、状態調整手段２１、量子ビット付加手段２２、状態変換手段２３を動作させずに、観測手段２４まで通過させ、観測手段２４において、該量子ビットの観測を行う。その結果をもとに、ビュー生成手段２５において、上記（３）を行う。それ以外のリーダ候補であるホストｖは、ビュー生成手段２５により上記（２）及び（３）を行い、状態調整手段２１により、上記（４）及び（５）を行う。
【０１１３】
手続きLeaderMain(Ｚ)が、ＺlogＺに比例するステップ数で動作し、正しくリーダを選出できる理由を以下に述べる。
手続きLeaderMain(Ｚ)は、手続きLeaderSub(ｍ)を並列に動作させるので、手続きLeaderSub(ｍ)が、ＺlogＺに比例するステップ数で動作すれば（停止すれば）、手続きLeaderMain(Ｚ)は、ＺlogＺに比例するステップ数で動作することになる。手続きLeaderSub(ｍ)は、（２）から（８）までの手順を高々、
【０１１４】
【数２６】
2005198247.tif 000028
回繰りかえす。
【０１１５】
【数２７】
2005198247.tif 000029
であるため、手続きＡ(ｍ)と手続きＤ(ｍ)が、それぞれ、仮定ホスト数ｍに比例するステップ数で終了することを言えば、ＺlogＺに比例するステップ数で停止することになる。手続きＡ(ｍ)の（４）でビューＴσ2(m-1)(ｖ)を構築するのに、仮定ホスト数ｍに比例するステップ数かかり、（５）では、手続きＣ(ｍ)が呼ばれるが、定数ステップで処理できる。また、（４）及び（５）以外では、それぞれ単位ステップを要する。従って、手続きＡ(ｍ)全体は、仮定ホスト数ｍに比例するステップ数で終了する。手続きＤ(ｍ)は、（３）でビューＴσ2(m-1)(ｖ)を構築するのに、仮定ホスト数ｍに比例するステップ数かかり、（４）では、手続きＣ(ｍ)が呼ばれるが、定数ステップで処理できる。（３）及び（４）以外では、それぞれ単位ステップを要する。従って、手続きＤ(ｍ)全体は、仮定ホスト数ｍに比例するステップ数で終了する。以上により、手続きLeaderMain(Ｚ)は、ＺlogＺに比例するステップ数で動作する。
【０１１６】
ｍ＝ｎならば、常に、「成功」を出力して停止することは明かである。
ｍ＞ｎの場合、「成功」を出力して停止することがないことを言えばよい。手続きLeaderSub(ｍ)の（４）でｋ(ｖ)＝１が満たされたときのみ、「成功」を出力する。ｋ(ｖ)は、手続きＡ(ｍ)の（７）により、ｃσ＝ｍ／|Γm-1|と設定される。互いに同型でないビューの集合Γm-1は、手続きＣ(ｍ)により、計算されるが、常に|Γm-1|≦ｎが言える（理由は後述）ので、ｍ＞ｎの場合、ｋ(ｖ)＝ｋ＝ｍ／|Γm-1|＞１となり、ｋ(ｖ)＝１を満たさない。|Γm-1|≦ｎである理由は、以下の通りである。ｎを正しいホスト数とすると、手続きＣ(ｍ)を行う直前、ｎ個のホストは、各々、ラベルを持っている。ｍ＞ｎの場合は、分散システム内の各ホストｖのビューの内、互いに同型でないものの集合の数|Γ|＝|Γm-1|を正しく求めることができる。|Γ|≦ｎなので、|Γm-1|≦ｎが成り立つ。
【０１１７】
＜手続きＤ(ｍ)を|0〉と|1〉を基底状態とする基底による観測で行う方法＞
全部でｎホストある内、ｌ＜ｎ個のホストｖがHadamard基底で行う観測は、次の手順で代替できる。
（１）  各量子ビットに|0〉→(|0>＋|1>)/√2と|1〉→(|0>-|1>)/√2で表されるユニタリ変換（Hadamard（アダマール）変換と言う）を作用させる。
（２）  ｌ個のホストｖが|0〉と|1〉を基底状態とする基底で観測を行う。
（３）  観測していないホストｖが、量子ビットにHadamard(アダマール)変換を作用させる。
従って、手続きＤ(ｍ)は、次の手続きＤ'(ｍ)により代替出来る。
【０１１８】
[手続きＤ'(ｍ)]
図１６は、手続きＤ'(ｍ)のフローチャートである．
（１）  各ホストｖは、量子ビットに|0〉→(|0>＋|1>)/√2と|1〉→(|0>-|1>)/√2で表されるユニタリ変換(Hadamard（アダマール）変換と言う)を作用させる（ステップＳｄ３１０）。
（２）  flag(ｖ)≠１であるホストｖは（ステップＳｄ３２０：ＮＯ）、各自が持っている量子ビットを|0〉と|1〉を基底状態とする(|0〉,|1〉)基底で観測を行う（ステップＳｄ３３０）。
（３）  flag(ｖ)＝１である各ホストｖは（ステップＳｄ３２０：ＹＥＳ）、量子ビットにHadamard（アダマール）変換を作用させる（ステップＳｄ３４０）。
（４）  flag(ｖ)≠１であるホストｖは、観測した値を自身のラベルとする（ステップＳｄ３５０）。また、観測していないホストｖ（flag(ｖ)＝１であるホストｖ）は、０及び１とは異なる特別な値（例えば２）をホストｖ自身のラベルとする（ステップＳｄ３６０）。
（５）  各ホストｖが手続きＢ(ｍ)によりビューＴσ2(m-1)(ｖ)を構築する（ステップＳｄ３７０）。
（６）  flag(ｖ)＝１である各ホストｖは（ステップＳｄ３８０：ＹＥＳ）、グループの要素数ｃσを手続きＣ(ｍ)により求める（ステップＳｄ３９０）。そして、ビューＴσ2(m-1)(ｖ)の節点の内、深さ（ｍ−１）以下にありラベル１を持つ各節点（ホストｖ）に対し、該節点（ホストｖ）を根とする深さ（ｍ−１）のビューで互いに同型でないビューの集合Γm-1(1)を計算する（ステップＳｄ４００）。さらに、ｃσ×|Γ(1) m-1|を計算する。この値は、仮定ホスト数ｍが正しいホスト数に等しい場合は、１を観測したホスト数を意味する。
（７）  flag(ｖ)＝１であるホストｖは、１を値として持つホストｖの数が奇数であれば、|0〉→|0〉及び|1〉→ｅiπ/k|1〉で表されるユニタリ変換を各自の量子ビットに作用させる（ステップＳｄ４１０、ステップＳｄ４２０）。
なお、ステップＳｄ４１０において、１を値として持つホストｖの数が奇数であるか否かは、以下による求める。
ｑ＝ｃσ×|Γ(1)m-1|（ｍｏｄ２）
【０１１９】
＜ホスト数の上限と下限がともにわかっている場合＞
各ノードｖが事前に、分散システム内のホスト数の上限Ｚに加えて下限Ｙが分かっている場合、手続きLeaderMain(Ｚ)は、ｍ＝Ｙ，Ｙ＋１，...，Ｚ−１，Ｚとして、Ｚ−Ｙ＋１個の手続きLeaderMain(Ｚ)を並列に動作させればよい。すなわち、次のように表すことが出来る。
【０１２０】
[手続きLeaderMain(Ｚ)]
（１）  図３におけるLeaderMain(Ｚ)において、仮定ホスト数ｍ＝Ｙ，...，Ｚに対して、手続きLeaderSub(ｍ)を並列に動作させる。
（２）  Ｍを「成功」を出力したLeaderSub(ｍ)が仮定ホスト数ｍの中で最大の値であるとする。このとき、手続きLeaderSub(Ｍ)が選出したリーダを正しいリーダとする。
このとき、動作時間は、Ｚのみが分かっている場合と同様に、ＺlogＺに比例する時間であるが、使用する共有されたキャット状態は、(Ｚ−Ｙ＋１)logＺ組となる。このため、下限Ｙが分かることにより、より少ない組の、共有されたキャット状態で、リーダを選出することができる。また、並列数が少なくなる分、通信量も削減することができる。
【０１２１】
＜キャット状態以外から始める方法＞
上記の手法は、キャット状態を事前に共有していることを仮定しているが、各ホストｖが事前に、ｎ量子ビットからなる状態|ψ〉を共有している場合でも、各ホストｖがある共通のユニタリ変換を施すことで、キャット状態に変換出来れば、実質的に上記の手法を使うことができる。
例えば、ｎ個のホストｖが、状態
|ψ〉＝(eiθ|00...0〉＋eiψ|11...1〉)／√2
にあるｎ量子ビットを１量子ビットずつ持っているとき、次のユニタリ変換
【０１２２】
【数２８】
2005198247.tif 000030
を各ホストｖが該量子ビットに作用させることで、|ψ〉をキャット状態に変換することができる。同様にして、各ホストｖがある共通のユニタリ変換で、下記の（状態Ａ）、（状態Ｂ）のうちいずれかの状態に変換できるような状態を事前に共有していた場合でも、ホストｖを選択することができる。
【０１２３】
（状態Ａ）ｎ個のホストｖが、１量子ビットずつを持ち、それら合計ｎ個の量子ビットが、
【０１２４】
【数２９】
2005198247.tif 000031
で表されるような基底状態を任意に重ね合わせた状態にある。ただし、１からｎまでの任意の整数ｉに関してｂｉは、０または１であり、ｂ１，ｂ２，・・・，ｂｎのうち、ちょうど一つだけ１で残りは０であるものとする。この、ｂ１，ｂ２，・・・，ｂｎは、基底である。このような状態においては、以下のようにリーダを選出することができる。
【０１２５】
例えば、ｎ＝４の場合、全ホストｖが持っている（合計４つの）量子ビットが、(|1000>＋|0100〉＋|0010〉＋|0001〉)／２の状態にある場合を考える。全ホストｖが|0〉及|1〉を基底として観測をすると、４ホストのうち１ホストだけ値１を得る。従って、値１を得た、ホストｖをリーダとすれば良い。ｎ＝４以外の場合も同様の説明ができる。この場合、各ホストｖとの通信は必要なく、また、ユニタリ操作を行う必要もない。
なお、ｂ１，ｂ２，・・・ｂｎのうち、一つだけ０で残りは１であってもよい。ことのき、値０を得たホストｖをリーダとする。
【０１２６】
（状態Ｂ）ｎ個のホストｖが、１量子ビットずつを持ち、それら合計ｎ個の量子ビットが、
【０１２７】
【数３０】
2005198247.tif 000032
で表されるような基底状態を任意に重ね合わせた状態にある。ただし、１からｎまでの任意の整数ｉに関してｂｉが、０または１であり、ｂ１,ｂ２,...ｂｎのうち、０の数と１の数が互いに素である（すなわち、１以外に共通因数を持たない）ものとする。このような状態においては、以下のようにリーダを選出することができる。
【０１２８】
非特許文献２(ｐ．１６９−１８０)によれば、値ｊをラベルとして持っているホストの数をｎｊで表すとき、全てのｊに対するｎｊ間に２以上の共通因数がなければ、深さ（ｎ−１）ビューを識別子に用いることで、１つのホストを選出することができる。各ホストｖが量子ビットを観測し、これをもとに、手続きＢ(ｍ)により深さ２(ｎ−ｌ)のビューを構築する。このビューを用いて、各ホストｖの深さ（ｎ−１）のビューを知ることが出来るので、２進表現にしたときに最小の２進数値をとる深さ（ｎ−１）のビューを持つホストｖをリーダとして選出すればよい。
【０１２９】
従って、各ホストｖ間における事前に共有された初期状態と変換により、上述する（状態Ａ）、（状態Ｂ）のような初期状態に一致させることができればよい。
【０１３０】
＜Ｖｎの一般化＞
前記のユニタリ変換Ｖｎは、各ホストｖで２つの量子ビットに同時に作用し、その結果、観測した場合に得られる値が、全てのホストｖで同じになる確率が０であることを保証する。このような、ユニタリ変換は他にも存在する。いま、上記の条件を満たすユニタリ変換を、以下のように仮定する。ただし、ａｊ，ｂｊ，ｃｊ，ｄｊ（ｊ＝０，１，２，３）は複素数である。
【０１３１】
【数３１】
2005198247.tif 000033
【０１３２】
ｎ個のホストｖが、この変換を、２ｎキャット状態にある量子ビット２つずつに作用させた結果、４つの基底状態|00...00〉，|01... 01〉，|10...10〉，及び|11...11〉の振幅が０になる必要がある。４つの基底状態の振幅は、ｊ＝０，１，２，３として、
【０１３３】
【数３２】
2005198247.tif 000034
であるから、
【０１３４】
【数３３】
2005198247.tif 000035
である必要がある。上記の式より、以下が成り立つ。
【０１３５】
【数３４】
2005198247.tif 000036
ただし、φｊは、（２ｌ＋１）π／ｎ(ｌは任意の整数、ｎは奇数）と表現できる数である。よって、所望の変換は次のように表すことができる。
【０１３６】
【数３５】
2005198247.tif 000037
【０１３７】
次に、上記変換を表す４行４列の行列がユニタリ行列の制約を満たすように、各変数を定めればよい。このようにして、得られた４行４列の行列が表す変換は、Ｖｎの代替をすることができる。ユニタリ行列になるための必要条件は、各列ベクトルのノルムが１でありかつ、任意の２つの列ベクトルの内積が０になることである。例えば２つのベクトルｘ＝(ｘ０，ｘ１，ｘ２，ｘ３）とｙ＝(ｙ０，ｙ１，ｙ２，ｙ３）の内積（ｘ，ｙ）とは、
【０１３８】
【数３６】
2005198247.tif 000038
の値のことである。ただし、
【０１３９】
【数３７】
2005198247.tif 000039
とは、ｘｊの共役複素数を表す。ベクトルｘのノルム|ｘ|とは、
【０１４０】
【数３８】
2005198247.tif 000040
のことである。
【０１４１】
【数３９】
2005198247.tif 000041
と表すことにする。
|ａ|２＝|ｄ|２＝１であること、及び、（ａ，ｄ)＝０から、以下となる。
【０１４２】
【数４０】
2005198247.tif 000042
【０１４３】
各列ベクトルは、４次元の複素ベクトル空間であるため、上記の式を満たす任意のａ及びｄに対して、ユニタリ行列の制約を満たすｂ及びｃが存在する。
上記の式を満たす、ａとｄの組は、複数存在する。ａ及びｄの組をそれらの内の一つに固定しても、対応するｂ及びｃの組は無数に存在する。よって、その中で、適当なものを一つ選べばよい。
Ｖｎは、上記の式を満たしかつ、ユニタリ行列の制約を満たすものの一つに過ぎない。
【０１４４】
また、Ｖｎは、各ホストｖにおいて、２つの量子ビットに対して、作用しているが、これを拡張して、各ホストｖにおいて、ｔ個の量子ビットに対して、作用するようにしてもよい。その際、ユニタリ変換を行う前に、ｎキャット状態を、ｔ・ｎキャット状態に変換しておく。変換の仕方は、２ｎキャット状態に変換する場合と同様である。すなわち、各ホストｖは、各組のｎキャット状態の量子ビットを一つ（ａと呼ぶ）ずつしか持っていないので、各ホストｖは、|0〉に初期化された新たな量子ビットを（ｔ−１）個（ｂと呼ぶ）用意し、ａを制御量子ビットとし、ｂを標的量子ビットとする、制御ＮＯＴ(ＣＮＯＴ)操作を（ｔ−１）回行う。この結果、システム全体として、量子ビット数がｔ倍のｔ・ｎ個になり、これらが、ｔ・ｎキャット状態(|00...0〉＋|11...1〉)／√2を形成する。各ホストｖは、ｔ個の量子ビットに対して、Ｖｎを作用させる。ただし、ここでのＶｎは、２ｔ行２ｔ列のユニタリ行列で表される。
【０１４５】
Ｖｎの作り方は、４行４列のときと同様にできる。すなわち以下のようになる。
もとめるユニタリ変換を
【０１４６】
【数４１】
2005198247.tif 000043
とおく。
ｎ個のホストｖが、この変換を、ｔ・ｎキャット状態にある量子ビットｔ個ずつに作用させた結果、全てのホストｖが同じｔビットの値を観測してしまうことに対応する基底状態の振幅が０になるようにする。
従って、ｊ＝０，１，・・・，２ｔ−１に対して、該基底状態の振幅は、
【０１４７】
【数４２】
2005198247.tif 000044
であるから、
【０１４８】
【数４３】
2005198247.tif 000045
である必要がある。上記の式より、以下が成り立つ。
【０１４９】
【数４４】
2005198247.tif 000046
ただし、φｊは、（２ｌ＋１）π／ｎ(ｌは任意の整数、ｎは奇数）と表現できる数である。よって、所望の変換は次のように表すことができる。
【０１５０】
【数４５】
2005198247.tif 000047
【０１５１】
２ｎ量子ビットの場合と同様、
【０１５２】
【数４６】
2005198247.tif 000048
を満たすａｊ及びφｊを求め、次にユニタリ行列の制約を満たすように、他の列ベクトルを求めればよい。
【０１５３】
＜Ｕｎの一般化＞
ユニタリ変換Ｕｎについても、Ｖｎと同様に、ｔ・ｎキャット状態にしてから、各ノードにおいてｔ個の量子ビットに同時に作用し、その結果、観測した場合に得られる値が、全てのホストｖで同じになる確率が０であることを保証するような、一種の拡張を考えることができる。
もとめるユニタリ変換を
【０１５４】
【数４７】
2005198247.tif 000049
とおく。
ｎ個のノードが、この変換を、ｔ・ｎキャット状態にある量子ビットｔ個ずつに作用させた結果、全てのノードが同じｔビットの値を観測してしまうことに対応する基底状態の振幅が０になるようにする。
【０１５５】
従って、ｊ＝０，１，・・・，２ｔ−１に対して、該基底状態の振幅は、
【０１５６】
【数４８】
2005198247.tif 000050
であるから、
【０１５７】
【数４９】
2005198247.tif 000051
である必要がある。上記の式および、以下が成り立つ。
【０１５８】
【数５０】
2005198247.tif 000052
ただし、φｊは、（２ｌ＋１）π／ｎ(ｌは任意の整数、ｎは奇数）と表現できる数である。ところで、πにかかる係数（２ｌ＋１）／ｎは、ｎが偶数の場合と奇数の場合とでは、ｌをそれぞれの場合に独立に選んでも、一致することはない。このため、ｎが偶数の場合と奇数の場合とでは、必然的に求めるユニタリ変換は異なる。所望の変換は次のように表すことができる。
【０１５９】
【数５１】
2005198247.tif 000053
【０１６０】
Ｖｎのときと同様に、
【０１６１】
【数５２】
2005198247.tif 000054
を満たすａｊ及びφｊを求め、次にユニタリ行列の制約を満たすように、他の列ベクトルを求めればよい。
【０１６２】
II．発明の実施の形態２
第２の発明の実施の形態は、ｎ個のホストｖが、１量子ビットずつを持ち、それら合計ｎ個の量子ビットが、
【０１６３】
【数５３】
2005198247.tif 000055
で表されるような基底状態を任意に重ね合わせた状態にあることを前堤とする。ただし、１からｎまでの任意の整数ｉに関してｂｉが、０または１であり、ｂ１,ｂ２,...ｂｎのうち、０の数と１の数が互いに素である（すなわち、１以外に共通因数を持たない）ものとする。
【０１６４】
非特許文献２(ｐ．１６９−１８０)によれば、値ｊをラベルとして持っているホストの数をｎｊで表すとき、全てのｊに対するｎｊの間に２以上の共通因数がなければ、深さ（ｎ−１）のビューを識別子に用いることで、１つのホストを選出することができる。即ち、|Γn-1|＝ｎとなる。
そこで、「発明の実施の形態１」の手続きLeaderSub(ｍ)の（２）において、手続きＡ(ｍ)を呼ぶ代わりに、各ホストｖが量子ビットを観測し、これをもとに、手続きＢ(ｍ)により深さ２(ｍ−ｌ)のビューを構築する。このビューを用いて、各ホストｖの深さ（ｍ−１）のビューの集合Γm-1を計算する。Γm-1の要素を２進表現にしたときに最小の値をとるビューを持つホストｖをリーダとする。また、ｋ(ｖ）＝ｍ／|Γm-1|とする。flag(ｖ)は更新しない。
ｍ＞ｎならば、|Γn-1|＝|Γm-1|＝ｎとなる。よって、常にｋ(ｖ)＞１なので、手続きLeaderSub(ｍ)の（４）で「成功」を出力することはない。
一方、ｍ＝ｎの場合は、最初の観測でｋ＝１となり、「成功」を出力する。
よって、LeaderMain(Ｚ)は、正しくリーダを選出する。
【０１６５】
この手法は、観測とビューを構成する手段があればよい。従って、ホストｖの構成は、図８より簡略化でき、図１７のようになる。すなわち、ホストｖは、リーダ選出手段２０として、観測手段２４、ビュー生成手段２５，アルゴリズム制御手段２６、及び、部分アルゴリズム制御手段２７のみを備えればよい。
【０１６６】
なお、ホストｖ内のキャット状態量子ビット格納装置１０は、例えば、量子ビットとして原子の核スピンを用いるならば、極低温での保存装置が想定される。
また、状態調整手段２１、量子ビット付加手段２２、状態変換手段２３は、量子ビットに演算を加えることにより実現される。これは、例えば、量子ビットとして原子の核スピンを用いた場合、特定の波長のレーザを照射することが想定される。また、観測手段２４は、例えば、原子の核スピンの方向を測定する装置を用いることにより行う。
【０１６７】
また、上述のホストｖは、内部にコンピュータシステムを有している。そして、上述した状態調整手段２１、量子ビット付加手段２２、状態変換手段２３、及び、観測手段２４における演算や観測にかかわる制御、ならびに、ビュー生成手段２５、アルゴリズム制御手段２６、及び、部分アルゴリズム制御手段２７の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウェアを含むものである。
【０１６８】
また、「コンピュータ読み取り可能な記録媒体」とは、ＲＯＭの他に、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１６９】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【図面の簡単な説明】
【０１７０】
【図１】本発明が適用される分散システムの例を示す図である。
【図２】本発明の第１の実施の形態によるホストの構成例を示すブロック図である。
【図３】同実施の形態による手続きLeaderMain(Ｚ）におけるホストの動作を示すフローチャートである。
【図４】同実施の形態による手続きLeaderSub(Ｚ）におけるホストの動作を示すフローチャートである。
【図５】同実施の形態による分散システムへのラベル付けを説明するための図である。
【図６】図５に示す分散システムにおけるホストのビューを示す図である。
【図７】同実施の形態によるリーダ候補の絞りこみの手続（手続きＡ(ｍ)）におけるホストの動作を示すフローチャートである。
【図８】同実施の形態によるホストの詳細な構成例を示すブロック図である。
【図９】同実施の形態による深さｍのビューの構築（手続きＢ(ｍ)）におけるホストの動作を示すフローチャートである。
【図１０】同実施の形態による手続きＢ(ｍ)の１ラウンド目の状況を説明するための図である。
【図１１】同実施の形態による手続きＢ(ｍ)の２ラウンド目の状況を説明するための図である。
【図１２】同実施の形態による手続きＢ(ｍ)の３ラウンド目の状況を説明するための図である。
【図１３】同実施の形態による互いに同型でないビューの集合Γm-1及び各グループの要素数ｃσの計算（手続きＣ）におけるホストの動作を示すフローチャートである。
【図１４】同実施の形態による手続きＣ(ｍ)の手順を説明するための図である。
【図１５】同実施の形態によるｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する方法（手続きＤ(ｍ)）におけるホストの動作を示すフローチャートである。
【図１６】同実施の形態による手続きＤ'(ｍ)におけるホストの動作を示すフローチャートである。
【図１７】本発明の第２の実施の形態によるホストの構成例を示すブロック図である。
【符号の説明】
【０１７１】
ｖ、ｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６…ホスト（ノード選択装置）
１０…キャット状態量子ビット格納装置（量子ビット格納手段）
２０…リーダ選出手段
２１…状態調整手段（状態調整手段）
２２…量子ビット付加手段
２３…状態変換手段
２４…観測手段
２５…ビュー生成手段（ラベル付与手段）
２６…アルゴリズム制御手段
２７…部分アルゴリズム制御手段
３０…ポート
【図１】
2005198247.tif 000056
【図２】
2005198247.tif 000057
【図３】
2005198247.tif 000058
【図４】
2005198247.tif 000059
【図５】
2005198247.tif 000060
【図６】
2005198247.tif 000061
【図７】
2005198247.tif 000062
【図８】
2005198247.tif 000063
【図９】
2005198247.tif 000064
【図１０】
2005198247.tif 000065
【図１１】
2005198247.tif 000066
【図１２】
2005198247.tif 000067
【図１３】
2005198247.tif 000068
【図１４】
2005198247.tif 000069
【図１５】
2005198247.tif 000070
【図１６】
2005198247.tif 000071
【図１７】
2005198247.tif 000072