(57)【要約】【課題】  分散システムを構成する各ホストにホスト数が知らされている場合に、ネットワークの形状によらず、また、予め相関関係を持つ量子ビットを各ホスト間で共有することなく、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定する。【解決手段】  量子計算能力を持つノード（ホストｖ）が量子通信リンクにより接続されている匿名分散システムにおいて、前記ノードの各々が、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットを生成して自身と接続されているノードと交換し、当該交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、相関関係にある量子ビットを生成し、当該相関関係にある量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する。【選択図】      図１
2006086765.tif 000002
【特許請求の範囲】
【請求項１】
量子計算能力を持つノードが、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムにおいて、
前記ノードの各々が、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットを生成して自身と接続されているノードと交換し、
当該交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、相関関係にある量子ビットを生成し、
当該相関関係にある量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する、
ことを特徴とするノード選択方法。
【請求項２】
前記ノードの各々が、自身と接続されているノードの数に１を加えた数の量子ビットからなるキャット状態の量子ビットを生成して１量子ビットずつ自身と接続されているノードと交換し、
前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態あるいは非対称状態の量子ビットを生成し、
非対称状態にある量子ビットを生成した場合は、当該量子ビットを観測し、キャット状態にある量子ビットを生成した場合は、当該量子ビットを所定のユニタリ変換によって変換して、この変換された量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、
当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項１に記載のノード選択方法。
【請求項３】
前記ノードの各々が、１量子ビットからなるキャット状態の量子ビットを生成し、自身と接続されているノードの数だけコピーして自身と接続されているノードと交換し、
前記交換した量子ビットのコピー及び自身と接続されているノードとの交換を繰返し、
前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態にある量子ビットを生成し、
当該生成した量子ビットを所定のユニタリ変換によって変換して、この変換された量子ビットを観測し、
当該観測された値に基づき前記ノードにラベルを付与し、
当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、
当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項１に記載のノード選択方法。
【請求項４】
量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムにおける前記ノード選択装置であって、
全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットを生成するキャット状態生成手段と、
当該生成した量子ビットを自身と接続されているノード選択装置と交換し、この交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットを生成する相関量子ビット生成手段と、
当該相関関係にある量子ビットを観測する観測手段と、
当該観測された値に基づきラベルを付与するラベル付与手段と、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するアルゴリズム制御手段と、
を備えることを特徴とするノード選択装置。
【請求項５】
前記キャット状態生成手段は、自身と接続されているノード選択装置の数に１を加えた数の量子ビットからなるキャット状態の量子ビットを生成し、
前記相関量子ビット生成手段は、当該生成した量子ビットを１量子ビットずつ自身と接続されているノード選択装置と交換し、前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態あるいは非対称状態の量子ビットを生成し、
前記相関量子ビット生成手段がキャット状態にある量子ビットを生成した場合は、当該量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、
前記観測手段は、前記相関量子ビット生成手段が生成した非対称状態の量子ビットまたは前記状態変換手段により変換された前記量子ビットを観測し、
前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、
前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項４に記載のノード選択装置。
【請求項６】
前記キャット状態生成手段は、１量子ビットからなるキャット状態の量子ビットを生成して自身と接続されているノード選択装置の数だけコピーし、
前記相関量子ビット生成手段は、当該コピーした量子ビットを自身と接続されているノード選択装置と交換し、さらに、前記交換した量子ビットのコピー及び自身と接続されているノード選択装置との交換を繰返し、前記自身が生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態にある量子ビットを生成し、
当該キャット状態にある量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、
前記観測手段は、前記状態変換手段により変換された前記量子ビットを観測し、
前記ラベル付与手段は、前記観測された値に基づきラベルを付与し、
前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、
ことを特徴とする請求項４に記載のノード選択装置。
【請求項７】
量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムの前記ノード選択装置に用いられるノード選択プログラムであって、
全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットの生成を制御するステップと、
自身と接続されているノード選択装置との生成した量子ビットの交換を制御するステップと、
当該交換した量子ビットからの、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットの生成を制御するステップと、
当該相関関係にある量子ビットの観測を制御するステップと、
当該観測された値に基づき前記ノード選択装置にラベルを付与するステップと、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、
をコンピュータに実行させることを特徴とするノード選択プログラム。
【請求項８】
量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムの前記ノード選択装置に用いられるノード選択プログラムを記緑したコンピュータ読み取り可能な記録媒体であって、
全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットの生成を制御するステップと、
自身と接続されているノード選択装置との生成した量子ビットの交換を制御するステップと、
当該交換した量子ビットからの、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットの生成を制御するステップと、
当該相関関係にある量子ビットの観測を制御するステップと、
当該観測された値に基づき前記ノード選択装置にラベルを付与するステップと、
当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、
をコンピュータに実行させるノード選択プログラムを記録した記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークのノードの中から１つのノードを選択する技術に関し、特に、量子アルゴリズムを用いてノードを選択するノード選択方法、ノード選択装置、ノード選択プログラム及びそのプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
複数のホストがネットワークを通じて接続されている分散システムにおける計算の技術的な困難性は、計算に用いるデータが各ホストに分散して配置されていることにある。このため、ある特定のホスト（リーダ）に全ホストのデータを集めて計算した後、計算結果を他のホストに分配する方法を用いられることが多い。最も単純な方法は、一意に特定できる識別子を各ホストに予め手動で付与しておくことである。識別子の中で最大（または最小）の識別子を持つホストをシステムが自律的に決定する効率的な方法が存在する（例えば、非特許文献１に代表的な手法が紹介されている）ので、この方法を用いて最大（または最小）の識別子を持つホストをリーダとすれば良い。
これに対し、一意とは限らない識別子が与えられている場合や、全く識別子が与えられていない場合でも、ホストを接続するネットワークが特定の形状であれば、リーダを決定できることが知られている。非特許文献２によれば識別子ｉを持っているホストの数をｎｉ，ｊ本の通信リンクに接続されているホストの数をｄｊとすると、全てのｉ及びｊに対する、ｎｉ及びｄｊの間に２以上の共通因数がなければ、ホスト数ｎに依存する時間内に必ずリーダを決定することができる。
【非特許文献１】Ｎ．Ａ．リンチ（N. A. Lynch），「分散アルゴリズム（Distributed Algorithms）」，アメリカ，モーガン・コーフマン・パブリッシャーズ（Morgan Kaufman Publishers），１９９６年
【非特許文献２】亀田恒彦、山下雅史，「分散アルゴリズム」，近代科学社，１９９４年
【発明の開示】
【発明が解決しようとする課題】
【０００３】
非特許文献２の方法でリーダを決定できるのは、特定の場合にすぎず、一般に（例えば、識別子をもっていないホストがリング状に接続されている場合）、最悪の場合に要する時間を保証するリーダ決定手法は原理的に存在しないことが示されている（すなわち、最悪の場合、終了しない可能性のある手法しか存在しない）。これは、ネットワークの同期／非同期によらず、また、システム内ホスト数やネットワーク形状が予め各ホストに知らされていても同様である。
また、量子通信路は構築可能であるが、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことが困難な場合がある。
【０００４】
本発明は、このような事情を考慮してなされたもので、その目的は、量子ビットを送受信できる量子通信路で接続された分散システムにおいて、ホスト数が各ホストに知らされている場合に、ネットワークの形状によらず、また、予め相関関係を持つ量子ビットを各ホスト間で共有することなく、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定することができるノード選択方法、ノード選択装置、ノード選択プログラム及びそのプログラムを記録した記録媒体を提供することにある。
【課題を解決するための手段】
【０００５】
前記課題を解決するために、本発明は、量子計算能力を持つノードが、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムにおいて、前記ノードの各々が、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットを生成して自身と接続されているノードと交換し、当該交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、相関関係にある量子ビットを生成し、当該相関関係にある量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該ラベルを用いて前記匿名分散システムから１つのノードをリーダとして選出する、ことを特徴とするノード選択方法である。
【０００６】
また、本発明は、上述するノード選択方法であって、前記ノードの各々が、自身と接続されているノードの数に１を加えた数の量子ビットからなるキャット状態の量子ビットを生成して１量子ビットずつ自身と接続されているノードと交換し、前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態あるいは非対称状態の量子ビットを生成し、非対称状態にある量子ビットを生成した場合は、当該量子ビットを観測し、キャット状態にある量子ビットを生成した場合は、当該量子ビットを所定のユニタリ変換によって変換して、この変換された量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【０００７】
また、本発明は、上述するノード選択方法であって、前記ノードの各々が、１量子ビットからなるキャット状態の量子ビットを生成し、自身と接続されているノードの数だけコピーして自身と接続されているノードと交換し、前記交換した量子ビットのコピー及び自身と接続されているノードとの交換を繰返し、前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノードが１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態にある量子ビットを生成し、当該生成した量子ビットを所定のユニタリ変換によって変換して、この変換された量子ビットを観測し、当該観測された値に基づき前記ノードにラベルを付与し、当該付与されたラベルに基づき計算された識別子が同一であるノードによって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノードの１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【０００８】
また、本発明は、量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムにおける前記ノード選択装置であって、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットを生成するキャット状態生成手段と、当該生成した量子ビットを自身と接続されているノード選択装置と交換し、この交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットを生成する相関量子ビット生成手段と、当該相関関係にある量子ビットを観測する観測手段と、当該観測された値に基づきラベルを付与するラベル付与手段と、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するアルゴリズム制御手段と、を備えることを特徴とするノード選択装置である。
【０００９】
また、本発明は、上述するノード選択装置であって、前記キャット状態生成手段は、自身と接続されているノード選択装置の数に１を加えた数の量子ビットからなるキャット状態の量子ビットを生成し、前記相関量子ビット生成手段は、当該生成した量子ビットを１量子ビットずつ自身と接続されているノード選択装置と交換し、前記自身の生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態あるいは非対称状態の量子ビットを生成し、前記相関量子ビット生成手段がキャット状態にある量子ビットを生成した場合は、当該量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、前記観測手段は、前記相関量子ビット生成手段が生成した非対称状態の量子ビットまたは前記状態変換手段により変換された前記量子ビットを観測し、前記ラベル付与手段は、当該観測された値に基づきラベルを付与し、前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【００１０】
また、本発明は、上述するノード選択装置であって、前記キャット状態生成手段は、１量子ビットからなるキャット状態の量子ビットを生成して自身と接続されているノード選択装置の数だけコピーし、前記相関量子ビット生成手段は、当該コピーした量子ビットを自身と接続されているノード選択装置と交換し、さらに、前記交換した量子ビットのコピー及び自身と接続されているノード選択装置との交換を繰返し、前記自身が生成した量子ビット及び前記交換した量子ビットから、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、前記匿名分散システムにおいてキャット状態にある量子ビットを生成し、当該キャット状態にある量子ビットを所定のユニタリ変換によって変換する状態変換手段を備え、前記観測手段は、前記状態変換手段により変換された前記量子ビットを観測し、前記ラベル付与手段は、前記観測された値に基づきラベルを付与し、前記アルゴリズム制御手段は、前記付与されたラベルに基づき計算された識別子が同一であるノード選択装置によって構成されたグループの内、前記識別子が最小のグループをリーダ候補のグループとして絞り込み、当該絞り込み操作をノード選択装置の１つがリーダとして選出されるまで繰り返す、ことを特徴とする。
【００１１】
また、本発明は、量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムの前記ノード選択装置に用いられるノード選択プログラムであって、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットの生成を制御するステップと、自身と接続されているノード選択装置との生成した量子ビットの交換を制御するステップと、当該交換した量子ビットからの、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットの生成を制御するステップと、当該相関関係にある量子ビットの観測を制御するステップと、当該観測された値に基づき前記ノード選択装置にラベルを付与するステップと、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、をコンピュータに実行させることを特徴とするノード選択プログラムである。
【００１２】
また、本発明は、量子計算能力を持つノード選択装置が、量子ビットを送受信する量子通信リンクにより接続されている匿名分散システムの前記ノード選択装置に用いられるノード選択プログラムを記緑したコンピュータ読み取り可能な記録媒体であって、全ての量子ビットが１または０である確率が同じであるキャット状態の量子ビットの生成を制御するステップと、自身と接続されているノード選択装置との生成した量子ビットの交換を制御するステップと、当該交換した量子ビットからの、前記匿名分散システムを構成する複数のノード選択装置が１つずつ有し、かつ、相関関係にある量子ビットの生成を制御するステップと、当該相関関係にある量子ビットの観測を制御するステップと、当該観測された値に基づき前記ノード選択装置にラベルを付与するステップと、当該ラベルを用いて前記匿名分散システムから１つのノード選択装置をリーダとして選出するステップと、をコンピュータに実行させるノード選択プログラムを記録した記録媒体である。
【発明の効果】
【００１３】
本発明によれば、量子ビットを送受信できる量子通信路で接続された分散システムにおいて、ホスト数が各ホストに知らされている場合に、ネットワークの形状によらず、また、予め相関関係を持つ量子ビットを各ホスト間で共有することなく、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定することができる。
【発明を実施するための最良の形態】
【００１４】
本発明は、識別子が予め付与されていない同種のｎ個（｛ｎ|ｎ∈自然数、ｎ＞１）のノードを有する任意形状のネットワークにおいて、ｎlogｎに比例するステップ数以内のステップ数によって、或る１つのノードを選択する。ここでノードとは、量子計算能力を含む計算能力があり、他のノードと通信能力があるものをいう。なお、ノードとしては、物理的実体を伴うホストや、物理的実体を伴わないプロセスなどがある。
本実施の形態においては、（Ａ）ノード間は量子ビットを送受信できる量子通信回路により接続可能、（Ｂ）予め相関を有する量子ビットをノード間で共有することは不要、（Ｃ）ノード数ｎが既知、（Ｄ）ノードは識別子が予め付与されていない同種ノード、という（Ａ），（Ｂ），（Ｃ），（Ｄ）の４つの制約を満たすネットワークを対象とし、量子アルゴリズムを用いてノードを選択する。
【００１５】
現在広く使われている計算機は、計算の単位として「０」または「１」を値としてとるビットが用いられている。しかし、量子力学の原理である量子重ね合わせ状態を利用すると、「０」及び「１」に加えて、「０」と「１」の重ね合わせを表現できる計算の単位を物理的に実現できることが実験的に確かめられている。この計算の単位を量子ビットと呼び、量子ビットに基づいた演算により計算を行う計算機を量子計算機と呼ぶ。上記の量子計算能力とは、量子計算機が持つ計算能力のことである。この、量子計算機を実現するための種々の基本素子は現在研究開発が行われており、本実施の形態では、これらの素子を用いて量子ビットに基づいた演算を行う量子計算能力を実現する。また、量子ビットとは、通常の計算機におけるビットと同様に、特定の物理実体に依存するものではなく、概念的なものである。しかし、原子の核スピンを量子ビットと見なす方法は、量子ビットの物理的実現方法の代表例である。また、光子を用いた方法や、半導体のエネルギー準位を用いた方法もある。
【００１６】
上述するように、量子ビットは、「０」と「１」とを重ね合わせた状態をとることができ、観測したときに「０」と「１」のどちらであるかが決まる。そして、従来の「０」または「１」の値のみをもつビット（「古典ビット」とよぶ）の「０」を示す量子ビットを|0〉、「１」を示す量子ビットを|1〉と表す。また、「０」または「１」の値をもつ量子ビット|0〉、|1〉を行列で表すと、下記のようになる。
【００１７】
【数１】
2006086765.tif 000003
【００１８】
また、「０」と「１」とを重ね合わせた状態は、以下のように表現される。
α|0〉＋β|1〉
ただし、α,βは複素数、かつ、|α|2+|β|2＝１であり、確率|α|2で「０」が、確率|β|2で「１」が観測されることを示している。また、重ね合わせの状態により「＋」以外に「−」もとりうる。そして、「０」または「１」が観測された場合、重ね合わせ状態は、|0〉または|1〉の状態に収縮する。
【００１９】
また、|00...0〉は、複数の量子ビット|0〉,|0〉,・・・, |0〉のテンソル積を示す。すなわち、下記のようになる。
【００２０】
【数２】
2006086765.tif 000004
【００２１】
また、本明細書中では、便宜上、
【００２２】
【数３】
2006086765.tif 000005
をＸyzと記載する場合がある。
【００２３】
Ｉ．発明の実施の形態１
本実施の形態においては、物理的実体を伴うノードの例として、ホストを用いる。分散システムであるネットワークは、ホストｖが量子ビットを送受信できる量子通信路（または量子通信リンクとも言う）によって相互に接続されることにより構成される。図１に分散システムの例を示す。同図においては、６個のホストｖ（これらをｖ１〜ｖ６とする）が量子通信リンクによって相互に接続されている。なお、ノードは、物理実体を伴う必要性はないため、例えば、ホストをプロセスと置き換え、ホスト間の通信をプロセス間の通信と考えても良い。この場合、システムを構成するプロセスの内のいくつかが物理的には同一のホスト内にあり、これらのプロセス同士の通信は、同一ホスト内でのプロセス間通信で行われる。以下では、ホストに限って、実施の形態の説明を行うが、同様の説明がホストをプロセスに置き換えた場合にも成立することは明白である。
【００２４】
図２に各ホストｖの構成例を示す（より詳細な構成は後述）。各ホストｖは、例えば、量子計算機であり、リーダ選出手段５０と、ポート７０とを備える。各ホストｖは、ポート７０によって、該ホストｖに接続する量子通信リンクを識別することができる。これには、例えば、各量子通信リンクに対応するポート７０を自然数により番号付けしておけばよい。ただし、この番号付けは、各ホストｖによって独立に行われていてもよいものとする。
各ホストｖは、識別子等は一切もっていないものとする。この意味で、ホストｖ間の差異は全くない。このようなホストからなる、分散システムを匿名分散システムまたは匿名ネットワークと言う。
【００２５】
匿名ネットワーク上でリーダ選挙問題を解く（リーダを選出する）ためには、ネットワークを構成するホストｖのうちの一つの状態を他のホストｖの状態と異なる状態にする必要がある。
本実施の形態のアルゴリズムの概要は以下の通りである。
最初、全てのホストｖがリーダ候補である。アルゴリズムは、ステージ１とステージ２からなる。ステージ１終了後、ｎ個のノードが量子ビットを一つずつもち、これらｎ量子ビットは、次に示す（ｉ）または（ii）のような２つ状態の内の一つにある。
【００２６】
（ｉ）キャット状態：ｎ個の量子ビットが全て|0〉または全て|1〉である確率が同じである状態をキャット状態（ｎキャット状態）という。すなわち、ｎ個の量子ビットからなるキャット状態とは、(|00...0〉＋|11...1〉)／21/2（以下、「21/2」を「√2」と記載する）で表される状態を言う。これは、全ての量子ビットが|0〉である確率と、全ての量子ビットが|1〉である確率とが１／２ずつであることを示している。前述したネットワーク上の各ノードが、相関関係のあるｎ個の量子ビットのうちの１つを保有しており、この相関関係のあるｎ個の量子ビットがキャット状態にある場合、これを一組の「共有されたキャット状態」と呼ぶ。
（ii）観測したときリーダ候補が全て同じ値をとることはないようなある状態（非対称状態とよぶ）（詳しくは後述）。
【００２７】
(ｉ)のときは、ステージ２にうつり、キャット状態から非対称状態を作る。(ii)のときは、上記状態をただちに観測して、その結果をもとにリーダ候補を半分以下に減らす。
残ったリーダ候補に同じ手続きを繰り返し、最終的にリーダ候補を一つにして、アルゴリズムが終了する。１回の繰り返しで、少なくとも半分にリーダが減るので、高々logｎ回繰り返せば、リーダが一つにきまる。
後述のように、ステージ１、２、及び、観測値をもとにリーダを減らす手段は、それぞれ、高々ｎに比例するラウンド数の後に終了する。
従って、全体では、ｎlogｎに比例するラウンド数の後に、必ず、リーダが一意に定まる。以下では、まず、ステージ２、及び、非対象状態ができた後の、リーダ候補を減らす手続きについて説明し、次にステージ１を含めたアルゴリズム全体の説明を行う。
【００２８】
１．ステージ２の説明
ステージ２では、量子通信リンクを用いないリーダ選出方法を適用してｎキャット状態から非対象状態を作る。
量子通信リンクを用いないリーダ選出方法では、同期ネットワークでかつホスト数が各ホストに知らされている場合に、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことにより、ネットワークの形状によらず、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定する。すなわち、ネットワーク上のｎ個のノードは、少なくとも「共有されたキャット状態」をlogｎ組有する構成をとっている。このとき、各ノードにおいて、１組のｎキャット状態にある量子ビットに所定の変換（ユニタリ操作）を行い、観測することによって得られた値に依存してノードにラベルを付与し、このラベルからリーダ候補を選択する。１回のリーダ候補の選択により、リーダ候補は選択前の半分以下となり、共有されたキャット状態が１組消費される。このリーダ候補の選択を再帰的に行っていくことによりリーダが選出される。
【００２９】
＜量子通信リンクを用いないリーダ選出方法＞
この量子通信リンクを用いないリーダ選出方法においては、物理的実体を伴うノードであるとしてのホストｖが、量子ビットを送受信できない従来の通信リンクによって相互に接続されることにより構成される分散システムを扱う。ここでは、図１と同様に、６個のホストｖ（これらをｖ１〜ｖ６とする）が通信リンクによって相互に接続されている構成を想定する。
【００３０】
ｎキャット状態にある量子ビットを各ホストｖがそのまま観測すれば、同じ観測値を得ることになるので、ホストの状態はやはり全て同じになってしまいリーダが決定できない。これを避けるための手法としては、各ホストｖが持つｎキャット状態の量子ビットにローカルなユニタリ操作を行うことである。ユニタリ操作とは、ユニタリ行列を作用させることであり、これにより、ある重ね合わせ状態を、別の重ね合わせ状態に変換することができる。しかし、単にユニタリ操作を行えば良いと言うことではない。例えば、ユニタリ操作を行った結果、システム内のｎ量子ビットが、基底状態|00...0〉や|11...1〉が重ね合わされた状態であると、観測を行った結果、全てのホストｖが同じ値を得る可能性がある。別のｎキャット状態の量子ビットに対して、同様の操作及び観測を繰りかえし行っても、再び、全てのホストｖが同じ値を得る可能性があるので、リーダ選出に要する最悪の場合の時間が保証できないことになる。
【００３１】
以下で２つのローカルなユニタリ操作ＵｎおよびＶｎを定義する。これらを、各ホストｖ内で、ｎキャット状態の量子ビットに作用させることで、全てのホストｖが同じ値を観測する確率を０にできる。これを用いて、最悪計算時間を保証するアルゴリズムを構成することができる。
予め決められた実数ψと整数ｍに対して、
【００３２】
【数４】
2006086765.tif 000006
と定義する。Ｕｎの共役転置行列を
【００３３】
【数５】
2006086765.tif 000007
で表し、単位行列Ｉとすると、
【００３４】
【数６】
2006086765.tif 000008
が成り立つことからＵｎがユニタリであることがわかる。また、ｎが偶数のときに、各ホストｖが、ｎキャット状態にある量子ビットにＵｎを作用させると、システム内のｎ量子ビットの状態に重ね合わされている基底状態|00...0〉と|11...1〉の振幅は０になることが計算によりわかる。つまり、Ｕｎを作用させたのち各ホストｖが観測により得る値を考えると、全てのホストｖが０を観測する場合と、全てのホストｖが１を観測する場合はともにあり得ない。つまり、ｎ個のホストｖの中に、０を観測するホストと１を観測するホストがともに存在する。ただし、以上が成り立つのは、ｎが偶数の場合に限る。
【００３５】
次に、ユニタリ操作Ｖｎを定義する。
【００３６】
【数７】
2006086765.tif 000009
【００３７】
Ｖｎは、計算により
【００３８】
【数８】
2006086765.tif 000010
を満たすことから、確かにユニタリ操作であることがわかる。Ｖｎは、４×４の行列である。つまり、２量子ビットに対して、同時に作用するものである。しかし、各ホストｖは、各組のｎキャット状態の量子ビットを一つ（ａと呼ぶ）ずつしか持っていない。そこで、各ホストｖは、新たな量子ビットを一つ（ｂと呼ぶ）用意し、ａを制御量子ビットとし、ｂを標的量子ビットとする制御ＮＯＴ（ＣＮＯＴ）操作を行う。この結果、システム全体として、量子ビット数が２倍の２ｎ個になり、これらが、２ｎキャット状態(|00...0〉＋|11...1〉)／√2を形成する。各ホストｖは、該２量子ビットに対して、Ｖｎを作用させる。この結果生じる、システム内の２ｎ量子ビットの状態に、重ね合わせられている、４つの基底状態|00...00〉，|01... 01〉，|10...10〉，及び|11...11〉の振幅は、ｎが奇数ならば０になることが計算により確かめられる。すなわち、各ホストｖがａ及びｂを観測して得られた値を２ビット値として見ると（ａとｂのうちどちらを上位ビットにするかは各ホストｖで共通させるものとする）、全てのホストｖが同じ２ビット値を観測する可能性は無いことを意味している。
【００３９】
アルゴリズムは、ＵｎまたはＶｎをｎキャット状態にある量子ビットに適用して得られた観測値を、各ホストｖの仮のラベルとする。当該ラベルと後述するラベルから仮識別子を生成する方法とを用いて、各ホストｖに仮識別子を付与する。ただし、ｎ個のホストの中には、同じ仮識別子を持つホストｖが複数存在する可能性がある。そこで、同じ仮識別子を持つホストごとにグループ化し、最小の仮識別子を持つグループをリーダの候補として、このグループの中でリーダを選ぶアルゴリズムを続行する。例えば、ｎ個のホストｖ（以下、「ｎホスト」とも記載）の中で、ｋ個のホストｖ（以下、「ｋホスト」とも記載）がリーダ候補として残れば、ｋキャット状態の量子ビットを該ｋホストに持たせ(この手続は後述)、ＵｋまたはＶｋを適用して、上記と同様にリーダ候補をさらに絞っていく。ただし、ＵｋまたはＶｋは、それぞれＵｎまたはＶｎの行列におけるｎの文字をｋで置き換えて得られる行列を表す。この絞りこみの、各繰りかえしをフェーズと呼ぶことにする。各フェーズにおいて、全てのリーダ候補が同じ仮識別子を持つことはないので、必ずリーダ候補は減っていくことが保証される。
【００４０】
［ラベルから仮識別子を生成する方法（非特許文献２、ｐ．１６９−１８０）］
各ホストｖが、必ずしもホスト毎に異なるとは限らないラベルを持っているとする。各ホストｖを節点（すなわち、分散システムにおけるノードに対応）、ホストｖ（節点）間の通信リンクを枝と見なすと、システム全体は、グラフと見なすことが出来る。このグラフをＧとする。以下、グラフＧの節点とホスト、及び、グラフＧの枝と通信リンクを、混乱の無い限り、区別せずに用いる。また、各ホストｖにおいて、通信リンクのポートは、各ホストｖで自然数によって独立に番号付けされているものとする。グラフＧの節点であるホストｖのポート番号付けを表す写像をσ[ｖ]で表すことにする。すなわち、σ[ｖ]は、他のホストｖに接続されているホストｖ内での該通信リンク（枝）に対応するポートの番号を表す。例えば、グラフＧの節点であるホストｖおよびホストｕに対して、枝である通信リンク(ｖ，ｕ)が存在したとき、ホストｖにおける通信リンク(ｖ，ｕ)に対応するポート番号は、σ[ｖ](ｖ，ｕ)で表される。
【００４１】
グラフＧの節点であるホストｖに対して、ホストｖのビューＴσ(ｖ)とは、次のように再帰的に定義される、節点（ホスト）と枝（通信リンク）にラベル付けされた、無限の高さを持つ根付き木である。
・ビューＴσ(ｖ)は、ホストｖに対応する根ｘを持つ。
・ホストｖに隣接するグラフＧの各ホストｖｉに対して、ビューＴσ(ｖ)は、節点ｘｉと、枝(ｘ，ｘｉ)を持つ。ただし、節点ｘｉは、ホストｖｉが持つ値をラベルとして持ち、枝(ｘ，ｘｉ)は、ｌ(ｖ，ｖｉ)をラベルとして持つ。ただし、ｌ(ｖ，ｖｉ)＝(σ[ｖ](ｖ，ｖｉ)，σ[ｖｉ](ｖ，ｖｉ))である。
・ホストｘｉは、ビューＴσ(ｖｉ)の根である。
【００４２】
例えば、図３に示される分散システムを考える。各ホストｖは、１から３までの自然数値でラベル付けされており、各ホストｖを接続する通信リンクの両端には、各ホストｖでのポート番号が記されている。例えば、値１をもつホストｖ１と値２を持つホストｖ２を接続する通信リンクは、値１をもつホストｖ１側ではポート番号１を持ち、値２を持つホストｖ２側では、ポート番号２を持っていることを表している。σを用いて表すと、σ[ｖ１](ｖ１，ｖ２)＝１及びσ[ｖ２](ｖ１，ｖ２)＝２となる。図３に示す分散システムにおいて、値１を持つホストｖ１のビューを、図４に示す。ビューの節点の深さは、根から距離（根から該節点に至るために通るべき枝の数）によって定義される。根は、深さ０とする。ビューの節点の内、深さ３以上の節点は図４では省略されている。ビューの節点に付けられた数値は、該節点に対応するホストｖのラベルを表す。また、ビューの枝の両端に付けられた数値は、図３と同様、両端のホストｖでのポート番号を表している。ビューの枝の両端の数値の内、根に近い数値から順に両端の数値の組をつくることで、枝のラベルを表すことができる。例えば、ｌ(ｖ１，ｖ２)＝(σ[ｖ１](ｖ１，ｖ２)，σ[ｖ２](ｖ１，ｖ２))＝(１，２)となる。ポート番号付けがσであるときの、ホストｖのビューをＴσ(ｖ)で表すものとする。
【００４３】
もし、二つのビューＴσ(ｕ)とビューＴσ(ｖ)が同型（節点と枝のラベルも含めて）ならば、この二つのビューは等しいということにすると(Ｔσ(ｕ)≡Ｔσ(ｖ)と表す)、グラフＧの節点の内、等しいビューを持つ節点同士を一つのグループとすることによグラフＧの節点集合を複数のグループに分割することができる。システム内で互いに同型でないビューの集合をГとする。深さ（ｎ−１）までの部分に、任意のホストｖに対応する節点が存在する。よって、
【００４４】
【数９】
2006086765.tif 000011
（以下、「Ｔσ2(n-1)(ｖ)」と記載）の中に、任意のホストｕに対する、深さ（ｎ−１）のビューが存在する。ただし、ビューＴσ(ｖ)の深さｒまでの部分を
【００４５】
【数１０】
2006086765.tif 000012
（以下、「Ｔσr(ｖ)」と記載）
と表す。参考文献[1]によれば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【００４６】
【数１１】
2006086765.tif 000013
のとき、またそのときに限り成り立つ。よって、ビューＴσ2(n-1)(ｖ)を構築できれば、システム内の全ホストｖの互いに同型でないビューの集合Гの要素数|Γ|＝|Γ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)(ｖ)の代わりに、（ｎ−１）以上の任意の値ｒ対して、
【００５１】
【数１２】
2006086765.tif 000014
（以下、「ビューＴσ2r(ｖ)」と記載）を使ってもよい。
【００５２】
（５）  flag(ｖ)＝１である（リーダ候補の）ホストｖは（ステップＳａ１０：ＹＥＳ）、各ホストｖのビューを２進符号化した場合に、もっとも小さい２進数値になるビューに同型なビューを持つホスト数を計算する（ステップＳａ１１）。該２進数値に関しては、手続きＣ（後述）により、互いに同型でないビューの集合Γを計算し、Γの各要素について２進符号化することにより最小の２進数値となるビューを求める。また、flag(ｖ)＝１であるリーダ候補のホストｖの中で最小の２進数値となるビューを持つホスト数ｃσ（すなわちリーダ候補として残るホスト数）に関しては、やはり手続きＣ（後述）により計算する。
【００５３】
（６）  flag(ｖ)＝１であるリーダ候補の各ホストｖは、自らのビューを２進符号化した値と該最小の２進数値を比べる（ステップＳａ１２）。同一であれば、次のフェーズでもリーダ候補に入り（flag(ｖ)の値は１のままにし）（ステップＳａ１３）、同一でなければ、次のフェーズではリーダ候補に入らない（flag(ｖ)の値を０に変化させる）（ステップＳａ１４）。これにより、リーダ候補は半分以下に絞られる。
【００５４】
図６にホストｖの詳細な構成例を示す。同図において、ホストｖは、キャット状態量子ビット格納装置１０と、リーダ選出手段２０と、ポート３０とを備える。リーダ選出手段２０は、キャット状態調整手段２１、量子ビット付加手段２２、状態変換手段２３、観測手段２４、ビュー生成手段２５、及び、アルゴリズム制御手段２６からなる。上記手続きＡにおいて、（１）の実行前に、キャット状態量子ビット格納手段１０からキャット状態量子ビットを一つ取り出し、キャット状態調整手段２１により、後述の手続きＤが行われ、その結果、ｋキャット状態にある量子ビットが生成されている。ｋが奇数の場合は、量子ビット付加手段２２により、新たな量子ビットが付け加えられる。その後、状態変換手段２３により、ＵｋまたはＶｋが作用される。（２）は、観測手段２４で行われ、（２）、（３）及び（４）は、ビュー生成手段２５により行われる。その後、構築したビューを用いて、（５）及び（６）は、アルゴリズム制御手段２６により行われ、この結果により手続きＤ（後述）を行うキャット状態調整手段２１や、量子ビット付加手段２２と状態変換手段２３が制御される。
【００５５】
上記の手法がうまく動作するには、全ホストｖの中で最小の仮識別子を特定できなくてはならない。また、次のフェーズでリーダ候補に、ＵｋまたはＶｋを適用しなくてはならないので、次のフェーズでのリーダ候補の数が奇数か偶数かを判別出来なくてはならない。
以下では、全ホストｖの中で最小の仮識別子と、その識別子を持つホスト数を各ホストｖで算出する方法を示し（手続きＢ及びＣ）、さらに、ｎ以下の任意の整数ｋに対して、ｎキャット状態からｋキャット状態を生成する方法（手続きＤ）を示す。最後に、アルゴリズム全体（手続きＥ）を示す。
【００５６】
各ホストｖは次に示す手続きＢにより、ビューを構築する。手続きＢでは、隣接ホスト間で通信リンクを用いて、ビューの部分木を送信する必要がある。このとき、送信側では、ビューを２進符号化して、２進数の系列に変換し、受信側では、受信した２進数の系列から、元のビューを構築（復号化）しなければならない。ビューは、節点と枝にラベル付けされた根付き木であるが、この２進表現は、数多く知られている。本発明では、特定の２進表現方法に依存しないので、特に仮定は設けない。
【００５７】
[手続きＢ：深さｒのビューの構築法]
図７は、ホストｖにおける深さｒのビューを構築する手続きＢの動作を示すフローチャートである。
（１）  ｉに１を代入する（ステップＳｂ１）。ｉは現在のラウンドを意味する。なお、ラウンドとは、同期ネットワークにおいて全ホストｖが一斉に下記の（２）の演算を行い、（３）においてその結果を通信し合うことをいう。
（２）  各ホストｖは、ビューの根ｘを作り、これを
【００５８】
【数１３】
2006086765.tif 000015
（以下、「ビューＴσ0(ｖ)」と記載）とする（ステップＳｂ２）。
（３）  各ホストｖは、
【００５９】
【数１４】
2006086765.tif 000016
（以下、「ビューＴσｉ−１(ｖ)」と記載）を２進符号で表したものを、ホストｖに接続する全てのリンクから送信する（ステップＳｂ３）。
（４）  ｉを１増加させる（ステップＳｂ４）。
（５）  各ホストｖは、各リンクから受信したビューをｘの子のホストｖを根とする部分木にして、受信したビューより、深さが１だけ大きい新たなビューＴσｉ−１(ｖ)を構築する（ステップＳｂ５）。
（６）  ｉ−１＝ｒならば、終了する（ステップＳｂ６：ＹＥＳ）。ｉ−１＜ｒならば（ステップＳｂ６：ＮＯ）、（３）へ移る。ただし、ｒは、２（ｎ−１）あるいは（ｎ−１）以上の任意の値である。
【００６０】
３ラウンド目までの手続きＢの動作を、例を使って説明する。図８は、１ラウンド目の状況である。１ラウンド目では、各ホストｖは、ビューの根節点を作り、自己のラベルを、該根節点のラベルとする。図９は２ラウンド目の状況である。各ホストｖは、１ラウンド目で構築した根節点からなるビューを各通信リンクから送信する。各ホストｖは、受信後、１ラウンド目で構築した根節点の子として、受信した隣接ホストｖのビューを挿入する。その結果、深さ１のビューが構築される。同図においては、各ホストｖが構築した深さ１のビューを示している。枝（通信リンク）の両端には、両端のホストｖでのポート番号が記されている。同様に３ラウンド目には、各ホストｖは深さ２のビューを構築することができる。例えば、値１を持つホストｖ１の深さ２のビューは、図１０のようになる。ただし、図１０では、他のホストｖのビューは略記されている。この例の場合、節点のラベルは１〜３が付けられている。しかし、実際には、ホスト数ｎ（＝６）は偶数であるため、Ｕｎが適用され、観測値であるラベルは「０」又は「１」になる。手続きＢは、図６におけるビュー生成手段２５により行われる。
【００６１】
任意のフェーズにおいて、リーダ候補の数が偶数または奇数に応じて、それぞれ、ＵｋまたはＶｋを適用し、観測して得た値をそのホストｖのラベルとする。すでにリーダ候補から外れたホスト（節点）ｖは、０と１との何れとも区別可能な特別な値をラベルとする。次に、参考文献[1]によれば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【００６２】
【数１５】
2006086765.tif 000017
のとき、またそのときに限り成り立つ。この性質を用いることにより、各ホストｖは、ビューＴσ2(n-1)(ｖ)から、全ホストｖのビュー及びその種類数を計算することができる。つまり、Ｗを全ホストｖの集合とすると、Γn-1＝｛Ｔσn-1(ｖ)|ｖ∈Ｗ｝と置けば、全ホストｖのビューの種類数|Γ|は、Γn-1に等しい。ところで、非特許文献２（ｐ．１６９−１８０）によれば、各グループの要素数は互いに等しいことが保証される。そこで、各グループの要素数ｃσは、ｎ／|Γ|＝ｃσによって、計算することができる。|Γ|及びｃσを計算する手続きをまとめると、以下に示す手続Ｃのようになる。
【００６３】
[手続きＣ：|Γ|及びｃσの計算方法]
図１１は、ホストｖにおけるビューの種類数|Γ|及び各グループの要素数ｃσを計算する手続Ｃの動作を示すフローチャートである。
（１）  各ホストｖは、手続きＢを用いて、高さ２（ｎ−１）のビューＴσ2(n-1)(ｖ)を構築する。
（２）  ビューＴσ2(n-1)(ｖ)の深さ（ｎ−１）までの節点（ホストｖ）を根とする、深さ（ｎ−１）の部分木で、互いに同型でないものの集合を求め、これをΓn-1とする（ステップＳｃ１）。つまり、Γ＝Γn-1である。
（３）  ｃσ＝ｎ／|Γ|＝ｎ／|Γn-1|を計算する（ステップＳｃ２）。
【００６４】
例えば、図１２のようにホストｖが深さ２（ｎ−１）のビューＴσ2(n-1)(ｖ)を構築したとすると、深さ（ｎ−１）以下の節点（ホストｖ）を根とする深さ（ｎ−１）の木は、ビューＴσ2(n-1)(ｖ)の部分木になっている。よって、深さ（ｎ−１）以下の節点（ホストｖ）を根とする深さ（ｎ−１）の全ての木の内、互いに同型でないものを集めたものがΓであるが、これは、ビューＴσ2(n-1)(ｖ)が得られれば計算することができる。尚、ホストｖが得るビューが、ｎ−１以上の任意のｒに対して、ビューＴσ2r(ｖ)であっても、|Γ|が計算できることは言うまでもない。手続きＣは、ビュー生成手段２５により生成されたビューを用いて、図６におけるアルゴリズム制御手段２６により行われる。
【００６５】
各フェーズにおけるリーダ候補の数をｋとすると、各フェーズを開始するにあたり、ｋキャット状態にある量子ビットを各リーダ候補の間で共有する必要がある。しかし、最初から与えられているのは、全ホストｖ間で共有する、ｎキャット状態にある量子ビットであるので、このｎキャット状態にある量子ビットから、ｋキャット状態にある量子ビットを生成する必要がある。ｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する方法である手続きＤを次に示す。
【００６６】
[手続きＤ：ｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する方法]
図１３は、ホストｖにおいて、ｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する手続きＤの動作を示すフローチャートである。
（１）  リーダ候補ではない、すなわち、flag(ｖ)≠１であるｎ−ｋ個のホストｖが（ステップＳｄ１：ＮＯ）、
【００６７】
【数１６】
2006086765.tif 000018
により、各自が持っている量子ビットを観測する（ステップＳｄ２）。これは、すなわち、量子ビットを
【００６８】
【数１７】
2006086765.tif 000019
として観測することを示す。
【００６９】
（２）  flag(ｖ)≠１である該ｎ−ｋ個のホストｖは、観測した値が、(|0>+|1>)／√２であれば、０を、(|0>-|1>)／√２であれば、１を各ホスト自身のラベルとする（ステップＳｄ３）。また、観測していないｋ個のホストｖ、すなわち、flag(ｖ)＝１のリーダ候補のホストｖは（ステップＳｄ１：ＹＥＳ）、０及び１とは異なる特別な値（例えば２）を各ホスト自身のラベルとする（ステップＳｄ４）。
【００７０】
（３）  各ホストｖは、手続きＢによりビューＴσ2(n-1)(ｖ)を構築する（ステップＳｄ５）。
（４）  flag(ｖ)＝１であるホストｖは、ビューＴσ2(n-1)(ｖ)を基に、１をラベルとして持つホストｖの数を計算する。具体的には、flag(ｖ)＝１であるホストｖは（ステップＳｄ６：ＹＥＳ）、グループの要素数ｃσを手続きＣにより求める（ステップＳｄ７）。そして、ビューＴσ2(n-1)(ｖ)の節点の内、深さ（ｎ−１）以下にありラベル１を持つ各節点（ホストｖ）に対し、該節点（ホストｖ）自身を根とする深さ（ｎ−１）のビューで互いに同型でないビューの集合をΓ(1)とする（ステップＳｄ８）。１をラベルとして持つホスト数は、ｃσ|Γ(1)|である。
【００７１】
（５）  flag(ｖ)＝１であるホストｖは、１をラベルとして持つホストの数が奇数であれば、|0〉→|0〉及び|1〉→ｅiqπ/k|1〉で表されるユニタリ変換を各自の量子ビットに作用させる（ステップＳｄ９、ステップＳｄ１０）。
なお、ステップＳｄ９において、リーダ候補であるｋ個のホストｖの数が奇数であるか否かは、以下による求める。
ｑ＝ｃσ|Γ(1)|（ｍｏｄ２）
ただし、ｍｏｄは、剰余演算子であり、除算の余りを求めることを示す。ｑが０であれば偶数、１であれば奇数である。
【００７２】
（５）の手順は、（２）で、ｎ−ｋ個のホストｖが量子ビットを観測後、残りのｋ個のホストｖが持っている量子ビットの間の相関関係は、(|0...0>＋|1...1>)/√2と(|0...0>−|1...1>)/√2の２種類が考えられることによる。これらの内いずれか決定するには、ｎ−ｋ個のホストｖの内、１を観測したホストの個数が偶数か奇数かを知ることができればよい。すなわち、偶数ならば前者、奇数ならば後者と決定することができる。従って、（３）、（４）により、ｎ−ｋ個のホストの内、１を観測したホストの個数を求め、この結果、ｋ個のホストｖが持っている量子ビットの間の相関関係が(|0...0>−|1...1>)/√2だった場合は、（５）においてｋキャット状態に変換している。
【００７３】
図６を用いて、手続きＤの流れを説明する。上記（１）において、flag(ｖ)≠１のホストｖは、キャット状態量子ビット格納装置１０から、量子ビットを取り出した後、キャット状態調整手段２１、量子ビット付加手段２２、状態変換手段２３を動作させずに、観測手段２４まで通過させ、観測手段２４において、該量子ビットの観測を行う。その結果をもとに、ビュー生成手段２５において、上記（３）を行う。それ以外のflag(ｖ)＝１であるｋ個のホストｖは、ビュー生成手段２５により上記（２）及び（３）を行い、キャット状態調整手段２１により、上記（４）及び（５）を行う。
手続きＡ，Ｂ，Ｃ，Ｄを用いて、リーダを選出するための手続き全体は次のように記述される。
【００７４】
[手続きＥ：リーダを選出するための手続き全体]
図１４は、ホストｖにおけるリーダを選出するための手続全体の動作を示すフローチャートである。
（１）  リーダ候補を全ホストｖとする。すなわち、全てのホストｖに対して、ｋ＝ｎ、flag(ｖ)＝１を設定する（ステップＳｅ１、ステップＳｅ２）。
（２）  手続きＡにより、リーダ候補の絞りこみを行う（ステップＳｅ３）。（手続きＡ終了後、リーダ候補の数ｋは更新されており、また、各ホストｖは、自身がリーダ候補に残っているかどうかを知っている（flag(ｖ)の値は更新されている）ことに注意。）
（３）  ｋ＝１ならば、手続きを終了する（ステップＳｅ４：ＹＥＳ）。ここでflag(ｖ)＝１であるホストｖがリーダとして選出される。
（４）  ｋ≠１ならば（ステップＳｅ４：ＮＯ）、手続きＤにより、全ホスト間で共有されているｎキャット状態の量子ビットから、リーダ候補間でのみ共有されるｋキャット状態の量子ビットを生成する（ステップＳｅ５）。
（５）  ステップＳｅ５の後、（２）へ移る。
【００７５】
以上が、量子通信リンクを用いないリーダ選出方法である。
【００７６】
＜量子通信リンクを用いたアルゴリズムの説明＞
図１５及び図１６は、ホストｖにおける量子通信リンクを用いたアルゴリズムのフローチャートを示す。
アルゴリズムは以下のように記述できる。
Algorithm LEP(ｎ)：各ホストｖは、Ａ(ｖ)、flag(ｖ)、及び、value(ｖ)の３つの変数を持っている。Ａ(ｖ)は、現在のリーダ候補数を表し、flag(ｖ)は、ホストｖがリーダ候補かどうかを示すビットである。また、value(ｖ)は、量子状態を観測して得られる値を格納する。
【００７７】
（１）  各ホストｖに対して、Ａ(ｖ)←ｎ、flag(ｖ)←１、value(ｖ)←０と初期化する（図１５、ステップＳ１１０）。
（２）  ステージ１を実行する（ステップＳ１１５）。
（３）  ステージ１が非対称状態を作ったときは（ステップＳ１２０：ＹＥＳ）、直ちに（４）を実行する。そうでないとき、すなわち、キャット状態を作ったときは（ステップＳ１２０：ＮＯ）、ステージ２を実行の後（ステップＳ１２５）、（４）を実行する。
（４）  各リーダ候補のホストｖは、(|0〉,|1〉)を基底として非対称状態の量子ビットを観測する（ステップＳ１３０）。flag(ｖ)＝１である各リーダ候補のホストｖは（ステップＳ１３５：ＹＥＳ）、観測値をvalue(ｖ)に入れラベルとする（ステップＳ１４０）。残りのflag(ｖ)≠１である、すなわち、リーダ候補ではないホストｖであるホストｖ'は（ステップＳ１３５：ＮＯ）、観測値と区別できる適当な値をvalue(ｖ')に入れる（ステップＳ１４５）。
（５）  各ホストｖは、ビューＴσ2(n-1)(ｖ)を構築し（ステップＳ１５０）、リーダ候補ノードの中で、ビューＴσ(n-1)(ｖ)の２進数表現が最小であるようホストｖだけを、リーダ候補にとどまらせ(flag(ｖ)に１をセット)、残りをリーダ候補から除外する（flag(ｖ)に０をセット)（ステップＳ１５５〜ステップＳ１７５）。また、現在のリーダ候補数Ａ(ｖ)に、更新されたリーダ候補の数をセットする（図１６、ステップＳ１８０）。すなわち、現在のリーダ候補数Ａ(ｖ)に、ステップＳ１６０の手続きＣにより更新されたグループの要素数ｃσ＝ｎ／|Γn-1|を入れる。もし、Ａ(ｖ)＝１ならば（ステップＳ１８５：Ｙｅｓ）、アルゴリズムは終了する。
（６）  Ａ(ｖ)≠１ならば（ステップＳ１８５：Ｎｏ）、（２）にもどる。
【００７８】
（３）において、実行されるステージ２は、
（ｉ）手続きＤを実行
（ii）手続きＡにおける（１）を実行
と表される。上記の手続きＤを先に行うのは、リーダ候補の間だけで、共有されるキャット状態にするためである。
また、（４）（ステップＳ１３５〜Ｓ１４５）及び（５）（ステップＳ１５０〜Ｓ１７５）の手順は、図５に示す手続きＡにおける（２）〜（６）の手順（ステップＳａ６〜Ｓａ１４）と同一である。ただし、本手順においては、flag(v)の値によらず、手続きＣを実行する。
【００７９】
図１７は、ホストｖの詳細な構成例を示す。同図において、図２におけるホストｖのリーダ選出手段５０は、キャット状態調整手段５１、量子ビット付加手段５２、状態変換手段（相関量子ビット生成手段）５３、観測手段（相関量子ビット生成手段）５４、ビュー生成手段（ラベル付与手段、相関量子ビット生成手段）５５、アルゴリズム制御手段５６（相関量子ビット生成手段）、キャット状態生成手段５７、量子ビット交換手段５８、及び、排他的論理和計算手段（相関量子ビット生成手段）５９からなる。キャット状態調整手段５１、量子ビット付加手段５２、状態変換手段５３、観測手段５４、ビュー生成手段５５、アルゴリズム制御手段５６は、それぞれ、量子通信リンクを用いないリーダ選出方法に用いられるホストｖ（図６）のキャット状態調整手段２１、量子ビット付加手段２２、状態変換手段２３、観測手段２４、ビュー生成手段２５、アルゴリズム制御手段２６と同様の機能を少なくとも有する。ステージ１のみで用いられるのは、キャット状態生成手段５７、量子ビット交換手段５８、排他的論理和計算手段５９であり、ステージ２でのみ用いられるのは、キャット状態調整手段５１、量子ビット付加手段５２であり、ステージ１，２、及び、ステージ１，２を呼ぶ最も上位のアルゴリズム（上記のアルゴリズム）共通に用いられるのは、アルゴリズム制御手段５６、観測手段５４、ビュー生成手段５５、状態変換手段５３である。尚、状態変換手段５３は、図が複雑になるのを避けるため、二つ描かれている。
【００８０】
例えば、ステージ１，２をよぶ上記のアルゴリズムにおいて、（１）から（３）及び（６）（ステージ１，２の実行は含まない）は、アルゴリズム制御手段５６で行われる。（４）は、観測手段５４で行い、（５）では、ビューの構築はビュー生成手段５５で行い、ビューを用いた各種計算はアルゴリズム制御手段５６で行う。
【００８１】
２．  ステージ１の第１の実施例
ｄ(ｖ)は、ホストｖにつながっている量子通信リンクの数を表すものとする。ステージ１の概要は、以下の通りである。各ホストｖは、(ｄ(ｖ)＋１）キャット状態を用意する。このキャット状態の量子ビット一つずつを、ｄ(ｖ)の隣接ホストｖと交換する。これにより、(ｄ(ｖ)＋１）量子ビットの内、１量子ビットが、もともとホストｖが作ったキャット状態を構成する量子ビットになっている。この量子ビットに、各ホストｖ内でユニタリ操作と観測を行うことで、ｎホストが待っている量子ビットの状態を、ｎキャット状態または、非対称状態にいずれかに変換する。
【００８２】
次に詳しいアルゴリズムの記述を行うために、用語の定義を行う。各ホストｖは、（ｄ(ｖ)＋１）個の量子ビットを格納するための、（ｄ(ｖ)＋１）個の１量子ビットレジスタ（量子ビット一つが入る箱）Ｒ0，...，Ｒd(v)と、ｄ(ｖ)個の量子ビットを格納できるレジスタＸを用意する。そして、全部の量子ビットを|0〉に初期化しておく。１量子ビットレジスタの系列Ｒ0，...，Ｒd(v)を単にＲとも表す。ステージ１において、各ホストｖは、次のように振る舞う。
【００８３】
図１８は、第１の実施例によるホストｖにおけるステージ１の動作を示すフローチャートである。
（１）  （ｄ(ｖ)＋１）キャット状態をレジスタＲに用意する（ステップＳ２１０）。このとき、システム全体の状態ψは、各ホストｖが用意したキャット状態のテンソル積になっている。
（２）  １量子ビットレジスタＲ1，...，Ｒd(v)に格納されている量子ビットを１つずつ各隣接ホストｖが用意したキャット状態の量子ビットと交換する（ステップＳ２１５）。このとき、システム全体の状態は変化していない。
（３）  
【００８４】
【数１８】
2006086765.tif 000020
を計算し、レジスタＸに格納する（ステップＳ２２０）。ただし、
【００８５】
【数１９】
2006086765.tif 000021
は、Ｒ0とＲtの状態の排他的論理和をとったものを表す。
【００８６】
（４）  (|0〉,|1〉)を基底としてレジスタＸを観測する（ステップＳ２２５）。観測値を、ｘ1ｘ2，…ｘd(v)であらわすことにする。ただし、ｘ1は、
【００８７】
【数２０】
2006086765.tif 000022
の観測値である。観測後のシステム全体の状態は、
【００８８】
【数２１】
2006086765.tif 000023
であらわされる。ただし、
【００８９】
【数２２】
2006086765.tif 000024
（以下、「|ψvJ〉」と記載）は、ホストｖがもっている量子ビット列の状態を表している。このとき|ψvJ〉は、
【００９０】
【数２３】
2006086765.tif 000025
という状態になっている。ただし、
【００９１】
【数２４】
2006086765.tif 000026
は、|ψvJ〉の状態をビットごとに反転してできる状態を表す。
【００９２】
（５）  
【００９３】
【数２５】
2006086765.tif 000027
で表されるユニタリ操作Ｋを１量子ビットレジスタＲに適用する（ステップＳ２３０）。その結果、１量子ビットレジスタＲ1，...，Ｒd(v)は、お互いの間にある相関関係が解消されるので、システムの状態は、各ホストｖが１量子ビットずつ保有している、ｎ量子ビットからなる状態になり、その状態は、
【００９４】
【数２６】
2006086765.tif 000028
と表される。ここで、Ｊi及び
【００９５】
【数２７】
2006086765.tif 000029
は、１量子ビットの状態を表しており、
【００９６】
【数２８】
2006086765.tif 000030
は、Ｊiを反転させたものである。
【００９７】
（６）  全てのホストｖがラベル（Ｊv,flag(ｖ)）を持ったとき、または、全てのホストｖが
【００９８】
【数２９】
2006086765.tif 000031
を持ったときのいずれかに場合に相当するビューであって、深さｎ−１のビューを構築する（ステップＳ２３５）。これを、手続きＢ'とする。以下、前者の場合を仮定する。
【００９９】
（７）  構築したビューから、全てのリーダ候補のホストｖのラベルのうち、第１要素(Ｊvの値）が全て同じかどうか調べる（ステップＳ２４０）。もし同じでなければ（ステップＳ２４０：ＹＥＳ）、リーダ候補のホストｖが自らが持つ量子ビットを観測することで、全てのリーダ候補が同じ値を観測値として得ることはあり得ないことが保証されるから、システムの状態は非対称状態になっている。従って、ステージ１は終了する。そうでなければ（ステップＳ２４０：ＮＯ）、観測すると全てのリーダ候補のホストｖが０を得るかまたは全てのリーダ候補のホストｖが１を得るような状態になっているため、次のステップに進む。
【０１００】
（８）  flag(ｖ)＝０であるホストｖ（つまり、リーダ候補ではないホストｖ）は（ステップＳ２４５：ＹＥＳ）、構築したビューから、自らのラベルの第１要素と、リーダ候補のラベルの第１要素が同じかどうか調べる（ステップＳ２５０）。同じでなければ（ステップＳ２５０：ＮＯ）、自らが持つ量子ビット（１量子ビットレジスタＲ0に格納されている量子ビット）を反転させる（ステップＳ２５５）。この結果、システムの状態は、ｎキャット状態となる。このとき、各ホストｖは、ｎキャット状態を構成するｎ量子ビットのうちの一つを持つ。
【０１０１】
上述するステージ１内の（６）は、図１８では手続きＢ'として示されている。
（１），（２），（３）が正しく動作することは明らかである。（４）で、観測後に
【０１０２】
【数３０】
2006086765.tif 000032
であらわされるような状態になる理由は以下の通りである。
あるホストｖが、レジスタＸを観測することで、
【０１０３】
【数３１】
2006086765.tif 000033
の値が決定する。１量子ビットレジスタＲ1，...，Ｒd(v)は、もともと隣接ホストｖが用意したキャット状態を構成する量子ビットである。これらの量子ビットは０をとる場合と１をとる場合との二つの場合の重ね合わせになっている。この中で、
【０１０４】
【数３２】
2006086765.tif 000034
を満たす場合だけが残り、他の場合は重ね合わせから消滅する。ただし、１量子ビットレジスタＲ1，...，Ｒd(v)は、各隣接ホストｖの用意したキャット状態を構成する量子ビットが０と１のどちらをとるかを表している。全てのホストｖが観測した後、重ね合わせの中に残る状態は、量子力学の公理により、次の（ｉ）及び（ii）を満たしている必要がある：
（ｉ）各ホストｖがもっている１量子ビットレジスタＲは、|０ｘ1…ｘd(v)〉かもしくは、
【０１０５】
【数３３】
2006086765.tif 000035
を満たす。
（ii）もともと同じホストｖで用意されたキャット状態を構成する量子ビットは、全て同じ状態を(|0〉または|1〉)をとっていなければならない。
【０１０６】
仮に、どれか一つの量子ビットを|0〉または|1〉のいずれかに固定すると、上記の２条件により他の量子ビットの状態は一意にきまる。しかも、|0〉に固定したときと、|1〉に固定したときを比べると各量子ビットの状態全て反転の関係にある。従って、観測後に残る状態は、２つであり、それは、
【０１０７】
【数３４】
2006086765.tif 000036
と表すことができる。（５）が、システムの状態を
【０１０８】
【数３５】
2006086765.tif 000037
に、変換するのは明らかである。
【０１０９】
ビューの作り方は後述する方法とほとんど同様である。ただし、各ホストｖは、０と１が、それぞれ、Ｊvと
【０１１０】
【数３６】
2006086765.tif 000038
のどちらに対応するのかわからないので、この点を考慮する必要がある。構築するビューは、実際、全ホストｖが、（Ｊv,flag(ｖ)）かまたは
【０１１１】
【数３７】
2006086765.tif 000039
のいずれかをラベルとしたときのビューとなる。どちらのラベルのものかはわからないが、それは、後の処理に影響しない。なぜなら、これら２種類のビューは、各ホストｖのラベルの第１要素がちょうど反転の関係にあり、後の処理は、同じビュー内でホストｖのラベル（ノードラベル）が一致しているかしていないかが判定できればよいためである。
【０１１２】
ビューの作り方は、以下の通りである。１量子ビットレジスタＲiは、ホストｖの隣接ホストｖiが用意したキャット状態を構成する量子ビットであると仮定する。各ホストｖは、そのホストラベル（ノードラベル）を(0,flag(ｖ))とする。
【０１１３】
【数３８】
2006086765.tif 000040
（以下、「ビューＴσr(ｖi)」と記載）を隣接ホストｖiから受け取ると、それを、ビューＴσr(ｖi)の根の子と取り替える前に、次を行う：もし、ビューＴσr(ｖi)の根のラベルが(ｘｉ,0)または(ｘｉ,1)（以下、「(ｘｉ,0/1)」と記載）ではなかったら、ビューＴσr(ｖi)の全てのホストｖのラベルの第１要素を反転させる。ただし、ｘｉは、レジスタＸの観測値の第ｉ要素である。これを再帰的に繰り返すことにより、全ホストｖが、（Ｊv,flag(ｖ)）かまたは
【０１１４】
【数３９】
2006086765.tif 000041
のいずれかをラベルとしたときのビューとなることは、数学的帰納法により明らかである。
構築したビューの中には、システム内の全てのホストｖに対応する節点が含まれているので、（７）がシステムの状態が非対称かどうかを正しく判定できることがわかる。
【０１１５】
（８）は、システムの状態が、非対称でないとき（観測によりリーダ候補のホストｖが全て同じ値を得てしまうような状態のとき）、|Ｊ0,...,Ｊ(v)〉及び
【０１１６】
【数４０】
2006086765.tif 000042
の状態のいずれにおいても、リーダ候補でないホストｖの状態をリーダ候補の状態に合わせることで、ｎキャット状態にできる。従って、リーダ候補でない各ホストｖ’は、構築したビューを調べ、リーダ候補のホストｖに対応する節点のラベルの第１要素と、ホストｖ’に対応する節点のラベルの第１要素とが、異なるときだけ、みずからの量子ビットを反転させればよい。
【０１１７】
次に図１７の構成図と図１８におけるステージ１の関係を説明する。（１）は、キャット状態生成手段５７で行う。（２）は、量子ビット交換手段５８で行う。（３）は、排他的論理和計算手段５９で行う。（４）は、観測手段５４で行う。（５）は状態変換手段５３で行う。（６）は、ビュー生成手段５５で行う。（７）はアルゴリズム制御手段５６で行う。（８）は、アルゴリズム制御手段５６で判断を行い、１量子ビットレジスタＲ0の反転はその判断に従って、状態変換手段５３で行う。
【０１１８】
（４）と同じ効果を伴う観測の方法は、他にも考えられる。たとえば、レジスタＸを(ｄ(ｖ)＋１）量子ビットのレジスタとし、（３）で、
【０１１９】
【数４１】
2006086765.tif 000043
を計算して、レジスタＸに格納する。この後、（４）で、レジスタＸを
【０１２０】
【数４２】
2006086765.tif 000044
を基底として観測を行う。たとえば、
【０１２１】
【数４３】
2006086765.tif 000045
が観測値ならば、これを、
【０１２２】
【数４４】
2006086765.tif 000046
と読み替えて、上記と同じことを行えばよい。
また、（５）で行う２d(v)+1次元ユニタリ変換の代わりに、各ホストｖが１量子ビットレジスタＲ1，...，Ｒd(v)に格納されている量子ビットをもとのホストｖに戻し、１量子ビットレジスタＲ0を制御ビット、１量子ビットレジスタＲ1，...，Ｒd(v)のそれぞれ標的ビットとして、ＣＮＯＴ操作をｄ(ｖ)回行ってもよい。これにより、１量子ビットレジスタＲ0以外の他の量子ビットは相関関係から解放されるので、（５）と同じことができる。
【０１２３】
図１９は、ホストｖにおける手続きＢ'の動作を示すフローチャートである。
（１）  ｒに１を代入する（ステップＳ３１０）。ｒは現在のラウンドを意味する。なお、ラウンドとは、ネットワークにおいて全ホストｖが一斉に下記の（２）の演算を行い、（３）においてその結果を通信し合うことをいう。
（２）  各ホストｖは、ビューの根を作り、これをビューＴσ0(ｖ)とする。そして、根のラベルを(0,flag(ｖ))とする（ステップＳ３１５）。
（３）  各ホストｖは、ビューＴσr-1(ｖi)のコピーをｄ(ｖ)個作り、全ての量子通信リンクから送信する（ステップＳ３２０）。
（４）  ｒを１増加させる（ステップＳ３２５）。
（５）  各ホストｖは、隣接ホストｖiから受信したビューの根のラベルが(ｘｉ,0/1)ではなかった場合（ステップＳ３３０：Ｎｏ）、隣接ノードｖiから受信したビューの全てのホストｖのラベルの第１要素を反転させる（ステップＳ３３５）。そして、隣接ホストｖiから受信したビューを用いてビューＴσr−１(ｖ)を構築する（ステップＳ３４０）。
（６）  ｒ−１＝ｎならば、終了する（ステップＳ３４５：ＹＥＳ）。ｒ−１＜ｎならば（ステップＳ３４５：ＮＯ）、（３）へ移る。
【０１２４】
３．  ステージ１の第２の実施例
ステージ１の第１の実施例では、キャット状態かまたは非対称状態を確率１で生成した。通信量は増えるが、キャット状態のみを確率１で生成する第２の実施例を以下に示す。
図２０は、第２の実施例によるホストｖにおけるステージ１の動作を示すフローチャートであり、図２１は、このステージ１の動作の（３）から（５）の手順である手続きＢ''の動作を示すフローチャートである。詳細なアルゴリズムは以下の通りである。
（１）  (|0>+|1>)／√２を作って、１量子ビットレジスタＲ0に保存する（図２０、ステップＳ４１０）。
（２）  手続きＢ''を開始する（ステップＳ４１５）。まず、変数ｒに１をセットする（図２１、ステップＳ５１０）。そして、ビューの根を１量子ビットレジスタＲ0で作り、これをビューＴσ0(ｖ)とする（ステップＳ５１５）。ＣＮＯＴ操作により１量子ビットレジスタＲ0のコピーをｄ(ｖ)個作り、このコピーをｄ(ｖ)の隣接ホストｖと一つずつ交換する（ステップＳ５２０）。
（３）  １量子ビットレジスタＲ0を根とし、その子を隣接ホストｖから受け取った量子ビット（隣接ホストｖの１量子ビットレジスタＲ0のコピー）とする、深さ１のビューを構築する。これをビューＴσ1とする。
（４）  現在持っているビューＴσ1のコピーをｄ(ｖ)個作り、隣接ホストｖと交換する。
（５）  各ホストｖは、変数ｒを１増加させる（ステップＳ５２５）。そして、受け取った、ビューのコピーを用いて、深さが１だけ大きいビューを構築する（ステップＳ５３０）。ｒ＜２（ｎ−１）のときは（ステップＳ５３５：ＮＯ）、（３）へ戻る。そうでなければ（ステップＳ５３５：ＹＥＳ）、手続きＢ''を終了する。ｎが奇数の場合は（図２０、ステップＳ４２０：ＹＥＳ）、手続きαを実行し（ステップＳ４２５）、ｎが偶数の場合は（ステップＳ４２０：ＮＯ、手続きβを実行する。手続きαは（６ａ）から、手続きβは（６ｂ）からの手順を実行する。
【０１２５】
図２２は、ホストｖにおける手続きαの動作を示すフローチャートである。
（６ａ）  ビューの根とそれ以外のホストｖの排他的論理和（ＥＸＯＲ）を計算する。ビューのホストｖは全て、量子ビットであるので、この計算は可能である。|Ｔσr|をＴσrのホスト数を表すことにすると、上記の計算結果は、|Ｔσ2(n-1)|−１個の量子ビットとして表される。すなわち、Ｖrootをビューの根である量子ビットとし、Ｖ1，Ｖ2，...，Ｖlastをそれぞれ、根以外のビューのホストｖである量子ビットを表すことにすると、計算の結果、
【０１２６】
【数４５】
2006086765.tif 000047
が得られる（ステップＳ６１０）。
【０１２７】
（７ａ）  上記（３）から（５）までの計算の逆計算を行うことにより、|Ｘ〉およびビューの根となっている量子ビットＲ0を残して、その他の量子ビットを他の量子ビットと相関のない状態に戻す（ステップＳ６１５）。
【０１２８】
（８ａ）  |Ｘ〉を(|0〉,|1〉)を基底として観測する（ステップＳ６２０）。ここで得た観測結果を、ｘ1ｘ2…ｘlastと表すことにする。ただし、ｘiは、
【０１２９】
【数４６】
2006086765.tif 000048
を観測した結果を表す。ステージ１の第１の実施例と同様の理由により、観測後のシステムの状態は、
【０１３０】
【数４７】
2006086765.tif 000049
と表される。ここで、Ｊi及び
【０１３１】
【数４８】
2006086765.tif 000050
は１量子ビットの状態を表しており、
【０１３２】
【数４９】
2006086765.tif 000051
は、Ｊiを反転させたものである。
【０１３３】
（９ａ）  自らが持っている１量子ビットレジスタＲ0の値が、システム内の全てのホストが持つ１量子ビットレジスタＲ0の中で多数派かどうかチェックする（ステップＳ６２５）。
多数派かどうかのチェックは、以下のように行う。
ｘ1ｘ2…ｘlastをもとにビューを再構成し（ビューは根のラベルが０のときと１のときの２種類考えられるがその内の一方でよい）、そのビューのГn-1及びГn-1(1)を計算することにより、ラベルとして１を持つホストｖの数は、|Гn-1(1)|×ｎ／|Гn-1|で求められる。これにより、このビューの中で、１をラベルとして持つホストｖが多数派かどうかがわかり、根（自らが持っている１量子ビットレジスタＲ0の値）が多数派の中に入っているかがわかる。
もし、多数派であれば（ステップＳ６２５：ＹＥＳ）、変数ｍａｊに１をセットし（ステップＳ６３０）、そうでなければ（ステップＳ６２５：ＮＯ）変数ｍａｊに０をセットする（ステップＳ６３５）。ｎは奇数なので、システム内の全てのホストが持つ１量子ビットレジスタＲ0の中で|0〉の数と|1〉の数が等しくなることはない。
【０１３４】
（１０ａ）  １量子ビットレジスタＲ0に
【０１３５】
【数５０】
2006086765.tif 000052
を適用し、停止する（ステップＳ６４０）。
これは、ホストｖがそれぞれ|0〉または|1〉という値をもっているとき、|0〉と|1〉の内の多数派に、少数派が値を合せることによって、皆が同じ値を持つようにする操作を重ねあわせで行っている。すなわち、少数派（ｍａｊ＝０）は、自分の値を反転させ（|0〉→|1〉または|1〉→|0〉)、多数派（ｍａｊ＝１）の場合は、変換が行われないことになる。
【０１３６】
図２３は、ホストｖにおける手続きβの動作を示すフローチャートである。
（６ｂ）  全ホストｖの１量子ビットレジスタＲ0の中の、|1〉の数を計算する（ステップＳ７１０）。これは、ビューＴσ2(n-1)からｃσ・|Γ(1)|（ｍｏｄ２）を計算することで得られる。計算結果を|Ｙ〉とする。
（７ｂ）  上記（３）から（５）までの計算の逆計算を行うことにより、|Ｙ〉及びビューの根となっている、量子ビットＲ0を残して、その他の量子ビットを他の量子ビットと相関のない状態に戻す（ステップＳ７１５）。
（８ｂ）  |Ｙ〉を(|0〉,|1〉)を基底として観測する。観測値をｙで表す（ステップＳ７２０）。観測後のシステムの状態は、ｙ＝１のとき
【０１３７】
【数５１】
2006086765.tif 000053
であり、ｙ＝０のとき
【０１３８】
【数５２】
2006086765.tif 000054
となる。ただし、Ｊodd（Ｊeven）は、２進表記をしたときに値が１であるビットの数が奇数（偶数）であるような数ｊの集合を表す。
【０１３９】
（９ｂ）  システムの状態が
【０１４０】
【数５３】
2006086765.tif 000055
のときは（ステップＳ７２５：ＹＥＳ）、Ｊoddを１量子ビットレジスタＲ0に適用する（ステップＳ７３０）。そうでない場合は（ステップＳ７２５：ＮＯ）、Ｕevenを１量子ビットレジスタＲ0に適用する（ステップＳ７３５）。ただし、
【０１４１】
【数５４】
2006086765.tif 000056
とする。その後、停止する。これは、（８ｂ）までの手順により生成される状態は２つのケースが考えられるためであり、そのケースに応じて、ＵoddまたはＵevenを操作させることにより、キャット状態を生成している。
【０１４２】
アルゴリズム中、量子ビットの状態をコピーするところがあるが、これは具体的にはつぎのような操作を指す。コピー元としてα|0〉＋β|1〉を考える。コピー先として|0〉を用意し、図２４に示す回路により、コピー元を制御ビット、コピー先を標的ビットとするＣＮＯＴ操作を行う。この結果、重ね合わされている状態ごとにコピーが行われ、結果は、α|0〉|0〉＋β|1〉|1〉となる。
【０１４３】
次に図２５に示す第２の実施例におけるホストｖの構成例との対応を説明する。但し、ビュー生成手段５５は、図が複雑になるのを避けるため、二つ描かれている。（１）,（２）は、キャット状態生成手段５７で実行する。ただし、（２）の、隣接ホストｖと量子ビットを交換する部分は、ビュー生成手段５５で行う。（３），（４），（５）は、ビュー生成手段５５で行う。（６ａ）は排他的論理和計算手段５９で行う。（７ａ）は、ビュー生成手段５５で行う。観測手段５４を用いて（８ａ）を行った後、それに基づいて、アルゴリズム制御手段５６で、（９ａ）を行う。（１０ａ）は、状態変換手段５３で行う。
アルゴリズム制御手段で５６で（６ｂ）を行い、その後、（７ｂ）は、ビュー生成手段５５で行う。観測手段２４で、（８ｂ）を行い、状態変換手段５３で（９ｂ）を行う。
【０１４４】
＜非同期型分散システムでの実施例＞
アルゴリズムの中で、全てのホストｖがあるステップを終了してからでないと、どのホストｖも次のステップに進まないように保証しておかなければ、全体としてうまく動作しない箇所がある。同期型分散システムでは、このような同期が保証されているが、同期システムを持たない非同期型分散システムで、同期すべきステップを持つアルゴリズムを実行するためには、そのようなステップで同期をとるようなしくみをアルゴリズムの一部として持たなくてはならない。基本的なアイデアは、同期が必要な各ステップ間で同期させるための仕組（サブルーチン）を挿入することである。
同期させるための仕組（サブルーチン）は以下のよう作ればよい。
例えば、ステップａとステップｂの間で同期させたい場合を考える。すなわち、全てのホストｖがステップａを終えたことを確認できるようにしたい。
ステップａを終えたホストは、ラベルａを用意する。このラベルに基づき、ビューＴσn-1(ｖ)を構築する。構築する方法は、手続きＢと同様である。ステップａを終えていないホストは、ラベルａを用意していないので、ビュー構築には参加できない。
ステップａを終えていないホストがいる場合は、ステップａを終えたホストは、ビュー構築の途中で、必要なビューを受信できないので、ビュー構築の手続きは待たされることになる。逆に、全てのホストがステップａを終えていれば、ビューＴσn-1(ｖ)を構築することができる。
よって、全てのホストｖのラベルがａであるようなビューＴσn-1(ｖ)を構築できたことが確認できれば、全てのホストｖがステップａを終了したことを意味することになる。
【０１４５】
なお、レジスタＸ、１量子ビットレジスタＲは、一つまたは複数量子ビットの集まりであり、一つまたは複数の量子ビットと等価である。また、量子通信リンクは、光子を量子ビットとして用いる方法では、光ファイバーを用いることができる。
また、キャット状態調整手段５１、量子ビット付加手段５２、状態変換手段５３は、量子ビットに演算を加えることにより実現される。これは、例えば、量子ビットとして原子の核スピンを用いた場合、特定の波長のレーザを照射することが想定される。観測手段５４は、例えば、原子の核スピンの方向を測定する装置を用いることにより行う。ビュー生成手段５５、アルゴリズム制御手段５６は、既存の（非量子の、古典の）コンピュータが用いられる。ビュー生成手段５５では、その計算を、ノードのラベルがいろいろな場合について、量子並列性（重ね合せ）を使って並列に行っている。このような、古典の計算を量子並列性を使って並列を行うとき、古典の計算手法をそのまま量子での計算手法に置き換える一般的な置き換え手法がよく知られている。例えば、入力ｘに対して出力f(x)を計算する古典の計算手法があった場合、(x,0)→ (x,f(x))という量子計算手法を機械的に生成することが可能である。量子ビット交換手段５８は、量子ビットそのものを量子通信リンクで通信して送る装置が用いられる。
【０１４６】
キャット状態生成手段５７は、量子ビットを用意し、
（ｉ）|0〉に初期化する
（ii）Hadamard（アダマール）変換（以下の２×２行列）をかける
という操作を行う。
【０１４７】
【数５５】
2006086765.tif 000057
（ii）の操作の結果(|0〉+|1〉)/√2という状態ができる。これは、量子ビット一つのキャット状態に相当する。例えば量子ビット２つのキャット状態を生成するには、|0〉に初期化された新しい量子ビットを用意し、これを標的ビット、さきほど作った状態(|0〉+|1〉)/√2の量子ビットを制御ビットとしてＣＮＯＴ操作を行う。これにより、(|00〉+|11〉)/√2ができる。これが量子ビット２つのキャット状態である。
また、排他的論理和計算手段５９は、R0とR1の排他的論理和を計算してSに入れたい場合（R0,R1,Sは量子ビット)、次の操作を行う。
（ｉ）Sを|0〉に初期化
（ii）Sを標的ビット、R0を制御ビットとしてＣＮＯＴ操作を行う
（iii）Sを標的ビット、R1を制御ビットとしてＣＮＯＴ操作を行う
従って、キャット状態生成手段５７及び排他的論理和計算手段５９は、
（ａ）|0〉への初期化
（ｂ）ユニタリ変換
（ｃ）ＣＮＯＴ操作
を行うための装置により構成する。（ａ）は、原子スピンを用いる場合、スピンの軸を|0〉に相当する方向に変えることを意味するため、特定方向に磁場を与える装置が用いられる。（ｂ）は、任意のユニタリ変換は、スピンの軸を変えることに他ならないため、（ａ）と同じ装置が用いられる。例えば、|0〉→(|0〉＋|1〉)/√2の変換は、スピンの軸を９０度倒すことに相当する。（ｃ）二つの原子を近接させ、そのスピンによって生じる磁場の相互作用を利用する。すなわち、片方（標的ビット）の原子にだけを特定の磁場をかけると、他方（制御ビット）のスピン軸の方向に依存して、前者（標的ビット）の原子のスピン軸が変わる。これを論理レベルで解釈すると、ＣＮＯＴ（制御否定）操作となる。
【０１４８】
なお、上述のホストｖは、内部にコンピュータシステムを有している。そして、上述したキャット状態調整手段５１、量子ビット付加手段５２、状態変換手段５３、観測手段５４、キャット状態生成手段５７、及び、排他的論理和計算手段５９における演算や観測にかかわる制御、量子ビット交換手段５８における量子ビットの送受信に関わる制御、ならびに、ビュー生成手段５５及びアルゴリズム制御手段５６の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウェアを含むものである。
【０１４９】
また、「コンピュータ読み取り可能な記録媒体」とは、ＲＯＭの他に、磁気ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＤＶＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【０１５０】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【０１５１】
参考文献
[1]  N. Norris, Universal covers of graphs: Isomoriphism to depth n-1 implies isomoriphism to a11 depths, Discrete Applied Mathematics, 56(1):61-74, 1995.
【図面の簡単な説明】
【０１５２】
【図１】本発明が適用される分散システムの例を示す図である。
【図２】本発明の第１の実施の形態によるホストの構成例を示すブロック図である。
【図３】分散システムへのラベル付けを説明するための図である。
【図４】図３に示す分散システムにおけるホストのビューを示す図である。
【図５】リーダ候補の絞りこみの手続（手続きＡ）におけるホストの動作を示すフローチャートである。
【図６】ホストの詳細な構成例を示すブロック図である。
【図７】深さｒのビューの構築（手続きＢ）におけるホストの動作を示すフローチャートである。
【図８】手続きＢの１ラウンド目の状況を説明するための図である。
【図９】手続きＢの２ラウンド目の状況を説明するための図である。
【図１０】手続きＢの３ラウンド目の状況を説明するための図である。
【図１１】互いに同型でないビューの種類数|Γ|及び各グループの要素数ｃσの計算（手続きＣ）におけるホストの動作を示すフローチャートである。
【図１２】手続きＣの手順を説明するための図である。
【図１３】ｎキャット状態にある量子ビットからｋキャット状態にある量子ビットを生成する方法（手続きＤ）におけるホストの動作を示すフローチャートである。
【図１４】リーダを選出するための手続き全体におけるホストの動作を示すフローチャートである。
【図１５】本発明の第１の実施の形態によるアルゴリズムにおけるホストの動作を示すフローチャートである。
【図１６】本発明の第１の実施の形態によるアルゴリズムにおけるホストの動作を示すフローチャートである。
【図１７】本発明の第１の実施の形態によるホストの構成例を示すブロック図である。
【図１８】本発明の第１の実施の形態によるステージ１におけるホストの動作を示すフローチャートである。
【図１９】本発明の第１の実施の形態による手続きＢ'におけるホストの動作を示すフローチャートである。
【図２０】本発明の第２の実施の形態によるステージ１におけるホストの動作を示すフローチャートである。
【図２１】本発明の第２の実施の形態による手続きＢ''におけるホストの動作を示すフローチャートである。
【図２２】本発明の第２の実施の形態による手続きαにおけるホストの動作を示すフローチャートである。
【図２３】本発明の第２の実施の形態による手続きβにおけるホストの動作を示すフローチャートである。
【図２４】ＣＮＯＴ操作の回路を示す図である。
【図２５】本発明の第２の実施の形態によるホストの構成例を示すブロック図である。
【符号の説明】
【０１５３】
ｖ、ｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６…ホスト（ノード選択装置）
５０…リーダ選出手段
５１…キャット状態調整手段
５２…量子ビット付加手段
５３…状態変換手段（相関量子ビット生成手段）
５４…観測手段（相関量子ビット生成手段）
５５…ビュー生成手段（ラベル付与手段、相関量子ビット生成手段）
５６…アルゴリズム制御手段（相関量子ビット生成手段）
５７…キャット状態生成手段
５８…量子ビット交換手段
５９…排他的論理和計算手段（相関量子ビット生成手段）
７０…ポート
【図１】
2006086765.tif 000058
【図２】
2006086765.tif 000059
【図３】
2006086765.tif 000060
【図４】
2006086765.tif 000061
【図５】
2006086765.tif 000062
【図６】
2006086765.tif 000063
【図７】
2006086765.tif 000064
【図８】
2006086765.tif 000065
【図９】
2006086765.tif 000066
【図１０】
2006086765.tif 000067
【図１１】
2006086765.tif 000068
【図１２】
2006086765.tif 000069
【図１３】
2006086765.tif 000070
【図１４】
2006086765.tif 000071
【図１５】
2006086765.tif 000072
【図１６】
2006086765.tif 000073
【図１７】
2006086765.tif 000074
【図１８】
2006086765.tif 000075
【図１９】
2006086765.tif 000076
【図２０】
2006086765.tif 000077
【図２１】
2006086765.tif 000078
【図２２】
2006086765.tif 000079
【図２３】
2006086765.tif 000080
【図２４】
2006086765.tif 000081
【図２５】
2006086765.tif 000082