(57)【特許請求の範囲】
【請求項１】
量子計算能力を持つ複数のノードが、量子ビットを送受信する量子通信路により接続されている分散システムにおいて、
前記ノードの各々が、自身がリーダ候補である場合に、リーダ候補であること及びリーダ候補ではないことに対応する２値の重ね合わせにより、所定の確率で自身を次のリーダ候補としたときの全ての結果を示す量子ビットを生成するとともに、当該量子ビットを前記量子通信路により他のノードと交換してリーダ候補の数を示す量子ビット列を生成する処理を、リーダ候補が１つだけとなる成功確率が所定以上となる回数繰り返し、
生成した重ね合わせ状態の前記量子ビット及びリーダ候補の数を示す前記量子ビット列に、成功確率が１となるよう量子的に増幅する演算を実行して、前記分散システム内の１つのノードをリーダとして選出する、
ことを特徴とするノード選択方法。
【請求項２】
量子計算能力を持つ複数のノード選択装置が、量子ビットを送受信する量子通信路により接続されている分散システムにおける前記ノード選択装置であって、
自身がリーダ候補である場合に、リーダ候補であること及びリーダ候補ではないことに対応する２値の重ね合わせにより、所定の確率で自身を次のリーダ候補としたときの全ての結果を示す量子ビットを生成するとともに、当該量子ビットを前記量子通信路により他のノード選択装置と交換してリーダ候補の数を示す量子ビット列を生成する処理を、リーダ候補が１つだけとなる成功確率が所定以上となる回数繰り返し、
生成した重ね合わせ状態の前記量子ビット及びリーダ候補の数を示す前記量子ビット列に、成功確率が１となるよう量子的に増幅する演算を実行して、前記分散システム内の１つのノード選択装置をリーダとして選出するリーダ選出手段を有する、
ことを特徴とするノード選択装置。
【請求項３】
請求項２に記載のノード選択装置のリーダ選出手段の制御をコンピュータに実行させることを特徴とするノード選択プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ネットワークのノードの中から１つのノードを選択する技術に関し、特に、量子通信路により接続される分散システムにおいて量子計算を用いて高速にノードを選択するノード選択方法、ノード選択装置及びノード選択プログラムに関する。
【背景技術】
【０００２】
複数のホストがネットワークを通じて接続されている分散システムにおける計算の技術的な困難性は、計算に用いるデータが各ホストに分散して配置されていることにある。このため、ある特定のホスト（リーダ）に全ホストのデータを集めて計算した後、計算結果を他のホストに分配する方法が用いられることが多い。最も単純な方法は、一意に特定できる識別子を各ホストに予め手動で付与しておくことである。識別子の中で最大（または最小）の識別子を持つホストをシステムが自律的に決定する効率的な方法が存在する（例えば、非特許文献１に代表的な手法が紹介されている）ので、この方法を用いて最大（または最小）の識別子を持つホストをリーダとすれば良い。
【０００３】
これに対し、特許文献１に記載の方法は、同期ネットワークでかつホスト数が各ホストに知らされている場合に、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことにより、ネットワークの形状によらず、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定することができる。
上記手法は、通信路として従来の通信路（量子ビットを送ることができない通信路）を仮定しているところに大きな特徴がある。従って、経済的技術的制約により、量子通信路を構築できないときでも、該手法を適用することが可能である。
一方、量子通信路は構築可能であるが、予め相関関係を持つ量子ビットを各ホスト間で共有しておくことは、経済的技術的制約により、困難な場合も想定される。このような場合は、上記手法を適用することはできない。
【０００４】
非特許文献２は、量子ビットを送受信できる量子通信路で接続された分散システムにおいて、ホスト数が各ホストに知らされている場合、ネットワークの形状によらず、ホスト数ｎに対し、高々ｎlogｎに比例する時間内に確率１でリーダを決定することが可能である。
また、古典ビットによる通信路を用いる方法でも、高い確率で、ホスト数ｎに比例する時間内で、リーダを決定することが可能な手法が存在する。それは、例えば非特許文献３に掲載されている。
【特許文献１】特開２００５−１９８２４７号公報
【非特許文献１】Ｎ．Ａ．リンチ（N. A. Lynch），「分散アルゴリズム（Distributed Algorithms）」，アメリカ，モーガン・コーフマン・パブリッシャーズ（Morgan Kaufman Publishers），１９９６年
【非特許文献２】タニ、コバヤシ、マツモト（S.Tani, H.Kobayashi and K.Matsumoto），「リーダ選択問題のための完全量子アルゴリズム（Exact Quantum Algorithms for the Leader Election Problem）」，「コンピュータ・サイエンス・レクチャーノート（Lecture Notes in Computer Science）」, Volume 3404，ＳＴＡＣＳ  ２００５：第２２回コンピュータサイエンスの理論的側面におけるシンポジウム会報、ドイツ、シュトゥットガルト、２００５年２月２４−２６日（STACS 2005: Proceedings of the 22nd Annual Symposium on theoretical Aspects of Computer Science, Stuttgart, Germany, Feburuary 24-26, 2005)，ｐｐ．５８１−５９２，２００５年１月
【非特許文献３】アロン・イタリ、ミカエル・ロデ（Alon Itai and Michael Rodeh），「分散ネットワークにおけるシンメトリー・ブレーキング（Symmetry breaking in distributed networks.）」，インフォメーション・コンピュテーション（Information Computation），88(1):60-87，１９９０年
【発明の開示】
【発明が解決しようとする課題】
【０００５】
上述するように、非特許文献３に記載の方法では、古典ビットによる通信路を用い、高確率でホスト数ｎに比例する時間内でリーダを決定することが可能である。一方、非特許文献２に記載の方法では、量子通信路で接続された分散システムにおいて、確実にリーダを決定するものの、ｎlogｎに比例する時間が必要である。
【０００６】
本発明は、このような事情を考慮してなされたもので、その目的は、量子ビットを送受信できる量子通信路で接続された分散システムにおいて、ホスト数が各ホストに知らされている場合に、ネットワークの形状によらず、また、予め相関関係を持つ量子ビットを各ホスト間で共有することなく、ホスト数ｎに対し、高々ｎに比例する時間内に確率１で高速にリーダを決定することができるノード選択方法、ノード選択装置及びノード選択プログラムを提供することにある。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、本発明は、量子計算能力を持つ複数のノードが、量子ビットを送受信する量子通信路により接続されている分散システムにおいて、前記ノードの各々が、自身がリーダ候補である場合に、リーダ候補であること及びリーダ候補ではないことに対応する２値の重ね合わせにより、所定の確率で自身を次のリーダ候補としたときの全ての結果を示す量子ビットを生成するとともに、当該量子ビットを前記量子通信路により他のノードと交換してリーダ候補の数を示す量子ビット列を生成する処理を、リーダ候補が１つだけとなる成功確率が所定以上となる回数繰り返し、生成した重ね合わせ状態の前記量子ビット及びリーダ候補の数を示す前記量子ビット列に、成功確率が１となるよう量子的に増幅する演算を実行して、前記分散システム内の１つのノードをリーダとして選出する、ことを特徴とするノード選択方法である。
上記によれば、量子計算能力を持つ複数のノードを量子通信路により接続してなる分散システムの各ノードが、自己に接続している量子通信路を区別可能であり、かつ、該分散システムのノード数を知っている場合に、各ノードが量子ビットに演算を行い、該量子ビットを互いに送受信し、該量子ビットを観測することを繰り返して該分散システム内のノードの内の一つをリーダとして選出するノード選択方法において、古典通信路のみを使用するアルゴリズムの成功確率を量子的に増幅することにより、必要な通信ステップ数をほとんど増やすことなく、成功確率を１にしている。
【０００８】
また、本発明は、量子計算能力を持つ複数のノード選択装置が、量子ビットを送受信する量子通信路により接続されている分散システムにおける前記ノード選択装置であって、自身がリーダ候補である場合に、リーダ候補であること及びリーダ候補ではないことに対応する２値の重ね合わせにより、所定の確率で自身を次のリーダ候補としたときの全ての結果を示す量子ビットを生成するとともに、当該量子ビットを前記量子通信路により他のノード選択装置と交換してリーダ候補の数を示す量子ビット列を生成する処理を、リーダ候補が１つだけとなる成功確率が所定以上となる回数繰り返し、生成した重ね合わせ状態の前記量子ビット及びリーダ候補の数を示す前記量子ビット列に、成功確率が１となるよう量子的に増幅する演算を実行して、前記分散システム内の１つのノード選択装置をリーダとして選出するリーダ選出手段を有する、ことを特徴とするノード選択装置である。
【０００９】
また、本発明は、上述するノード選択装置のリーダ選出手段の制御をコンピュータに実行させることを特徴とするノード選択プログラムである。
【発明の効果】
【００１０】
本発明によれば、量子ビットを送受信できる（双方向に通信できる）量子通信路で接続された分散システムにおいて、ホスト数が各ホストに知らされている場合に、ネットワークの形状によらず、また、予め相関関係を持つ量子ビットを各ホスト間で共有することなく、ホスト数ｎに対し、高々ｎに比例する時間内に確率１でリーダを決定することができる。
【発明を実施するための最良の形態】
【００１１】
本発明は、識別子が予め付与されていない同種のｎ個（｛ｎ|ｎ∈自然数、ｎ＞１）のノードを有する任意形状のネットワークにおいて、ｎに比例するステップ数以内のステップ数によって、或る１つのノードを選択する。ここでノードとは、量子計算能力を含む計算能力があり、他のノードと通信能力があるものをいう。なお、ノードとしては、物理的実体を伴うホストや、物理的実体を伴わないプロセスなどがある。
本実施の形態においては、（Ａ）ノード間は量子ビットを送受信できる（双方向に通信できる）量子通信路により接続可能、（Ｂ）予め相関を有する量子ビットをノード間で共有することは不要、（Ｃ）ノード数ｎが既知、（Ｄ）ノードは識別子が予め付与されていない同種ノード、という（Ａ），（Ｂ），（Ｃ），（Ｄ）の４つの制約を満たすネットワークを対象とし、量子アルゴリズムを用いて１つのノードを選択する。
【００１２】
現在広く使われている計算機は、計算の単位として「０」または「１」を値としてとるビットが用いられている。しかし、量子力学の原理である量子重ね合わせ状態を利用すると、「０」及び「１」に加えて、「０」と「１」の重ね合わせを表現できる計算の単位を物理的に実現できることが実験的に確かめられている。この計算の単位を量子ビットと呼び、量子ビットに基づいた演算により計算を行う計算機を量子計算機と呼ぶ。上記の量子計算能力とは、量子計算機が持つ計算能力のことである。この、量子計算機を実現するための種々の基本素子は現在研究開発が行われており、本実施の形態では、これらの素子を用いて量子ビットに基づいた演算を行う量子計算能力を実現する。また、量子ビットとは、通常の計算機におけるビットと同様に、特定の物理実体に依存するものではなく、概念的なものである。しかし、原子の核スピンを量子ビットと見なす方法は、量子ビットの物理的実現方法の代表例である。また、光子を用いた方法や、半導体のエネルギー準位を用いた方法もある。
【００１３】
上述するように、量子ビットは、「０」と「１」とを重ね合わせた状態をとることができ、観測したときに「０」と「１」のどちらであるかが決まる。そして、従来の「０」または「１」の値のみをもつビット（「古典ビット」とよぶ）の「０」を示す量子ビットを|0〉、「１」を示す量子ビットを|1〉と表す。また、「０」または「１」の値をもつ量子ビット|0〉、|1〉を行列で表すと、下記のようになる。
【００１４】
【数１】
0004593482.tif 000002
【００１５】
また、「０」と「１」とを重ね合わせた状態は、以下のように表現される。
α|0〉＋β|1〉
ただし、α,βは複素数、かつ、|α|2+|β|2＝１であり、確率|α|2で「０」が、確率|β|2で「１」が観測されることを示している。また、重ね合わせの状態により「＋」以外に「−」もとりうる。そして、「０」または「１」が観測された場合、重ね合わせ状態は、|0〉または|1〉の状態に収縮する。
【００１６】
また、本明細書中では、便宜上、
【００１７】
【数２】
0004593482.tif 000003
をＸyzと記載する場合がある。
【００１８】
本実施の形態においては、物理的実体を伴うノードの例として、ホストを用いる。分散システムであるネットワークは、ホストｖが量子ビットを送受信できる量子通信路（または量子通信リンクとも言う）によって相互に接続されることにより構成される。図１に分散システムの例を示す。同図においては、６個のホストｖ（これらをｖ１〜ｖ６とする）が量子通信リンクによって相互に接続されている。なお、ノードは、物理実体を伴う必要性はないため、例えば、ホストをプロセスと置き換え、ホスト間の通信をプロセス間の通信と考えても良い。この場合、システムを構成するプロセスの内のいくつかが物理的には同一のホスト内にあり、これらのプロセス同士の通信は、同一ホスト内でのプロセス間通信で行われる。以下では、ホストに限って、実施の形態の説明を行うが、同様の説明がホストをプロセスに置き換えた場合にも成立することは明白である。
【００１９】
図２に各ホストｖの構成例を示す（より詳細な構成は後述）。各ホストｖは、例えば、量子計算機であり、リーダ選出手段１０と、ポート２０とを備える。各ホストｖは、ポート２０によって、該ホストｖに接続する量子通信リンクを識別することができる。これには、例えば、各量子通信リンクに対応するポート２０を自然数により番号付けしておけばよい。ただし、この番号付けは、各ホストｖによって独立に行われていてもよいものとする。
各ホストｖは、識別子等は一切もっていないものとする。この意味で、ホストｖ間の差異は全くない。このようなホストからなる、分散システムを匿名分散システムまたは匿名ネットワークと言う。
【００２０】
匿名ネットワーク上でリーダ選挙問題を解く（リーダを選出する）ためには、ネットワークを構成するホストｖのうちの一つの状態を他のホストｖの状態と異なる状態にする必要がある。
以下に示す実施の形態では、同期ネットワークを仮定する。すなわち、ネットワーク上の全てのメッセージは同時に送信され、同時に受信されるものとする。しかし、下記の実施の形態で示すアルゴリズムでは、各ホストｖは、接続する全ての通信リンクに対して、メッセージを送信する。また、各ノードが、接続する全てのリンクからメッセージを受信して初めて次の処理に移るようにアルゴリズムを改変することにより、非同期ネットワークにおいても動作可能である。
【００２１】
本実施の形態におけるアルゴリズムは、まず、リーダ決定アルゴリズムをシミュレートし、次いで、その成功確率を１にする。最初に実行するリーダ決定アルゴリズムにおいては、Itai及びRodehにより非特許文献３で提案されている、古典通信路のみを用いることを前提としたエラー有りのリーダ決定アルゴリズムを、量子通信路を用いたネットワークで実現可能としている。また、成功確率を１にするアルゴリズムは、Dong Pyo Chi and Jinsoo Kim., Quantum database search by a single query, In Colin P. Williams, editor, Proceedings of the First NASA International Conference Quantum Computing and Quantum Communications, volume 1509 of Lecture Notes in Computer Science, pages 148-151, Palm Springs, California, 1998. Springer（以下、「参考文献１」と記載）の手法を応用する。
【００２２】
［古典通信路を用いたリーダ決定アルゴリズム（非特許文献３）］
ここでは、古典通信路により接続されたｎ個のノードからなる匿名ネットワーク中の１つのノードを選択する確率的アルゴリズムについて説明する。
【００２３】
（１）初めは、全てのノードがリーダ候補である。リーダ候補の数ｋにホスト数ｎをセットする。
（２）リーダ候補のノードは、確率１／ｋで１を、確率１−１／ｋで０を、自らの値とする。
（３）値１を持っているリーダ候補のノード数をかぞえ、これをｃとする。
（４）ｃ＝０ならば、ステップ（２）へ戻る。ｃ＝１ならば、値１をもっているノードをリーダに決定し、アルゴリズムを終了する。ｃ＞１ならば、値０を持っているノードはリーダ候補からはずれ、ｃの値をｋにセットして、ステップ（２）に戻る。
【００２４】
非特許文献３に記述されているように、リーダが決定するまでのステップ（２）から（４）までの平均繰り返し回数は、およそ２．４４回である。従って、４回繰り返して停止すれば、エラー確率（リーダが決定しない確率）は、３／４未満となる。そこで、本実施の形態においては、（２）から（４）までの繰り返し回数を数えておき、４回繰り返したら、強制的に停止するように修正したアルゴリズムを、量子通信路でシミュレートする。
【００２５】
非特許文献３は、片方向リングに関する方法を開示しているが、本実施の形態では、双方向通信できる量子通信路で構成された任意の形状ネットワークを考える。この仮定の変更に伴い、影響をうけるのは、ステップ（３）でｃの値を計算する方法だけであり、他は、全く同様に、問題なく動作する。
【００２６】
また、量子通信路で上記アルゴリズムをシミュレートしただけでは、成功確率は、依然として１未満である。次に示す方法により、成功確率１／４以上の量子アルゴリズムが与えられたときに、機械的に、成功確率を１にすることができる。ただし、成功確率の厳密な値が与えられる必要があるが、上記のアルゴリズムの成功確率を、各ノードが通信を行わずに正確に計算することが可能であるので、問題ない。
【００２７】
［与えられた量子アルゴリズムの成功確率を１にする方法（参考文献１）：一般化グローバーアルゴリズム（Generalized Glover algorithm）］
Αを、途中の観測を含まない量子アルゴリズムであり、論理関数χを真とする変数割り当てを探索する量子アルゴリズムであるとする。すなわち、Αは量子アルゴリズムであるから、ユニタリ変換で表現することができる。簡単のため、このユニタリ変換をΑと同一視する。Αを|0〉に適用してできた状態をΑ|0〉で表現することにすると、定義が意味するところは、「Α|0〉の特定の個所の量子ビットを観測したときに得られる値が、ある正の確率ａ（＞０）で、χを真とする変数割り当てになっている」ということである。特定個所は、Αに依存して決まる。この確率ａをΑの成功確率と呼ぶ。
【００２８】
下記の参考文献１によれば、Αの成功確率が、次に定義するユニタリ変換Ｑ(Α,χ,φ,ψ)に対して、
【００２９】
Ｑ(Α,χ,φ,ψ)Α|0〉    …（式１）
【００３０】
は、χを真とする変数割り当てを確率１で正しく求めるアルゴリズムとなる。すなわち、Ｑ(Α,χ,φ,ψ)Α|0〉を観測すると、χを真とする変数割り当てを確率１で得られる。ψとφ(０≦ψ，φ＜２π）は、ａに依存する値であり、
【００３１】
Ｑ(Α,χ,φ,ψ)＝−ΑＦ0(φ)Α-1Ｆχ(ψ)    …（式２）
【００３２】
であるとする。ここで、ユニタリ変換Ｆχ(ψ)は、χ(ｘ)＝１のとき|x〉をｅiψ|x〉に変換し、χ(ｘ)＝０のときには何も作用しない。また、ユニタリ変換Ｆ0(φ)は、ｘ＝0・・・0のとき|x〉をｅiφ|x〉に変換し、そうでないときには何も作用しない。
【００３３】
［本発明のアルゴリズム］
次に本実施の形態による全体のアルゴリズムを示す。
本アルゴリズムへの入力として、status=“eligible”（“eligible”はリーダであることを、“ineligible”はリーダではないことを示す），量子レジスタＲ0,...,Ｒm,Ｓ0,...,Ｓm,Ｓm+1，ノード数ｎがある。但し、ｍ＝４とする。また、各ホストｖは、隣接ノード数を、接続している通信リンクの数から得られるものとする。
以下に、ホストｖのリーダ選出手段１０が実行するアルゴリズムの詳細を述べる。
【００３４】
【数３】
0004593482.tif 000004
【００３５】
Output：変数status∈{“eligible”,“ineligible”}
【００３６】
（１）各ホストｖは、Ｒ0,...,Ｒm及びＳ0,...,Ｓm+1を|0〉に初期化する。
【００３７】
（２）（式１）における「Α|0〉」を実現するため、次のステップ（２．１）〜（２．２）を実行。
（２．１）各ホストｖは、Ｓ0にｎをセットする。もし、status=“eligible”ならば、Ｒ0に１をセットする。
【００３８】
（２．２）ｉ:=１,...,ｍに対して次のステップ（２．２．１）及び（２．２．２）を繰り返す。
なお、以下において、「Ｒi-1の内容」、「Ｓi-1の内容」とは、それぞれのレジスタに格納されている値（０又は１）を示す。但し、格納されているのは量子ビットであるため、実際は、０と１の重ね合わせになっている場合がある。この場合、重ね合わされている値それぞれに対して、以下のステップ（２．２．１）及び（２．２．２）の処理を行う。例えば、０と１が確率１／２で重ね合わされているとき、０の場合と１の場合のそれぞれについて処理を行い、各々の場合の結果を確率１／２で重ね合わせたものが、最終的な結果となる。
【００３９】
（２．２．１）各ホストｖは、もしＲi-1の内容が１であれば、Ｒiの内容を
【００４０】
【数４】
0004593482.tif 000005
に変換する。ただし、ｓi-1はＳi-1の内容を表す。
【００４１】
（２．２．２）各ホストｖは、全てのホストｖの持つＲiの内容に含まれる１の数を計算し、その値をＳiにセットする。
【００４２】
（３）（式２）における「Ｆχ(ψ)」を実現するために、各ホストｖは、Ｓmの内容ｓmが１であれば、
【００４３】
【数５】
0004593482.tif 000006
をＲ0にかける。ｎ個のホストｖがそれぞれｅi(ψ/n)をかけるため、全体では、ｅiψをかけていることになる。
【００４４】
（４）Α†、すなわち、（式２）における「Ａ-1」を実現するために、各ホストｖは、ステップ（２）の逆計算を行う。なお、Α†とは、作用素Αの随伴作用素のことであり、特に、Αを行列で表現したときは、共役転置行列を示す。Αは、行列で表現した場合、ユニタリ行列と呼ばれる行列になっているため、Α†＝Α-1が成り立つ。
【００４５】
（５）（式２）における「Ｆ0(φ)」を実現するために、次のステップ（５．１）〜（５．３）を実行する。
（５．１）各ホストｖは、Ｒ0,...,ＲmとＳ0,...,Ｓmの内容の論理和を計算し、この値をｓとする。全てのノードのｓの値の論理和を計算し、Ｓm+1にセットする。
【００４６】
（５．２）各ホストｖは、もし、Ｓm+1の内容が０であれば（Ｒ0,...,ＲmとＳ0,...,Ｓmが全て０であれば）、
【００４７】
【数６】
0004593482.tif 000007
をＲ0にかける。ｎ個のホストｖがそれぞれｅi(φ/n)をかけるため、全体では、ｅiφをかけていることになる。
【００４８】
（５．３）各ホストｖは、ステップ（５．１）の逆計算を行う。
【００４９】
（６）各ホストｖは、ステップ（２）における作用Αと同じ作用を実行する。
【００５０】
（７）各ホストｖは、Ｒmを観測する。観測値が０であれば、statusの値を“ineligible”とする。
【００５１】
（８）各ホストｖは、statusの値を出力する。
【００５２】
上記のステップ（２．２）は、前述の「古典通信路を用いたリーダ決定アルゴリズム（非特許文献３）」そのものであり、全ての場合のシミュレート結果を重ね合わせ状態により表している。そのため、ｍ＝４にすれば、Ｒmを観測したときに、リーダが正しく（１つだけ）選ばれる確率は、１／４以上である。上記アルゴリズムは、ステップ（２．２）を、前述の「与えられた量子アルゴリズムの成功確率を１にする方法（参考文献１）」における量子アルゴリズムΑと見て、該方法を適用したものである。従って、成功確率は１となる。以降では、このアルゴリズムがｎに比例するステップ数で動作することの説明を行う。
【００５３】
ステップ（２．２．２）については、非特許文献２の４．１に記載されている、１をラベルとして持つホスト数を数える方法（以下、「手続きｄ」と記載）を用い、１を値として持つノード数の計算をｎに比例するステップ数で行うことができる。手続きｄでは、量子重ね合せを一切使っていない。一方、ステップ（２．２．２）の計算におけるＲiは、０と１の重ね合せになっているが、手続きｄを単に重ね合せで適用すればよく、ｎに比例するステップ数で行うことができる。なお、本願では、ステップ数を、メッセージの送受信回数としている。
【００５４】
ステップ（５．１）についても同じことが言える。ｓにおける計算は、通信を行わずに実行できる。全てのホストｖが持つｓの論理和の計算手法は、さまざまな方法があるが、そのうちの一つは、手続きｄにより、ｓ＝１であるようなノードの数を数え、その値が０であれば、全てのホストｖが持つｓの論理和は０であり、そうでなければ、１ということになる。従って、ステップ（２．２．２）と同様に、ｎに比例するステップ数で行うことができる。
【００５５】
他のステップは、全て各ホストｖ内で行える計算であることから、全体として、アルゴリズムは、ｎに比例するステップ数で動作する。
なお、ステップ（４）においては、ステップ（２）の逆計算、つまり、ステップ（２）における逆方向通信及び逆写像演算を行っており、ステップ（５．３）においては、ステップ（５．１）の逆方向通信及び逆写像演算を行っている。
【００５６】
図３は、上記アルゴリズムを実行するためのホストｖの構成例である。ホストｖのリーダ選出手段１０の構成要素は、古典アルゴリズム模倣手段１１、回転操作実現手段１２、観測手段１３、ノード数計算手段１４、通信手段１５である。
ステップ（２．２）及びステップ（４）における古典アルゴリズムのシミュレーション及びその逆計算を、古典アルゴリズム模倣手段１１で行う。ステップ（２．２．２）における、１の数の計算は、ノード数計算手段１４で行う。この際、通信が生じるが、通信は、通信手段１５を通して行う。ステップ（３）は、回転操作実現手段１２で行う。
ステップ（５）については、ステップ（５．１）をノード数計算手段１４により、全てのノードのｓ中の１の数を計算することで実現する。ステップ（５．２）は、ステップ（３）の同種の操作なので、回転操作実現手段１２で行う。
ステップ（７）における観測は、観測手段１３において行う。
【００５７】
本実施の形態によれば、非特許文献２に記載される従来技術において、本実施の形態と同様の条件（Ａ）ノード間は量子ビットを送受信できる（双方向に通信できる）量子通信路により接続可能、（Ｂ）予め相関を有する量子ビットをノード間で共有することは不要、（Ｃ）ノード数ｎ（｛ｎ|ｎ∈自然数、ｎ＞１）が既知、（Ｄ）ノードは識別子が予め付与されていない同種ノード、という条件下で、１つのノードを選択するためには最大ｎlogｎに比例するステップ数が必要であり、ステップ数が多いという問題を解決している。
【００５８】
すなわち、本実施の形態においては、以下の（１）〜（３）の手順によりリーダを選出する。
（１）古典通信路により接続されたｎ個のノードからなる匿名ネットワーク中の１つのノードを選択する確率的アルゴリズム（非特許文献３）を、量子通信路により接続された匿名ネットワークで実現（この確率的アルゴリズムは、同期ネットワークの場合、平均０(ｎ)のステップ数で１つのノードを選択）。
（２）（１）の確率的アルゴリズムの繰り返し操作（ループ）を所定回数で強制的に停止。
（３）探索問題において解が求まる確率が１／４以上のアルゴリズムが存在した場合、確率１で解が求まるように確率増幅させる一般化グローバーアルゴリズム（Generalized Glover algorithm）（参考文献１）を適用。
これにより、従来と同じ条件下で、高々ｎに比例する時間内に確率１でリーダを決定することができるため、従来よりもステップ数を低減できるという効果がある。
【００５９】
なお、ホストｖのレジスタＲ0,...,Ｒm、Ｓ0,...,Ｓm、Ｓm+1は、一つまたは複数量子ビットの集まりであり、一つまたは複数の量子ビットと等価である。また、量子通信リンクは、光子を量子ビットとして用いる方法では、光ファイバーを用いることができる。
【００６０】
回転操作実現手段１２は、量子ビットを実現する物理的手段に依存するが、例えば量子ビットを原子の核スピンとして実現する場合、特定波長のレーザーを照射することが想定される。観測手段１３は、例えば量子ビットを原子の核スピンとして実現する場合、原子の核スピンの方向を測定する装置を用いることが想定される。
【００６１】
量子ビットを送受信するときは、量子ビットの実現形態として、例えば、光子の偏光を用いることが想定される。回転操作などを行う際に適した量子ビットの物理的実現形態と、通信を行う際の量子ビットの物理的実現形態が異なる場合は、通信手段１５によって、それぞれの物理的実現形態に量子状態を相互にのせかえることが想定される。
【００６２】
古典アルゴリズム模倣手段１１は、古典アルゴリズム中で用いられるランダムビットを１量子ビットに対する操作で置き換える。例えば、確率αで０、確率（１−α）で１がでるようなランダムビットは、
【００６３】
【数７】
0004593482.tif 000008
という操作（この操作も回転操作実現手段１２と同様、量子ビットが原子の核スピンで実現される場合は、特定波長のレーザー照射としての実現が想定される）で置き換える。
古典アルゴリズム中のその他のステップは、機械的に量子計算ステップに置き換える手法が知られている。例えば、入力xに対して、出力f(x)を生成する古典ステップがあった場合、(x,0)→(x,f(x))という量子計算ステップを機械的に生成することが可能である。
ノード数計算手段１４は、古典アルゴリズムを上記と同様に機械的に量子計算アルゴリズムに変換すればよい。
【００６４】
また、ホストｖは、内部にコンピュータシステムを有している。そして、上述したリーダ選出手段１０内の古典アルゴリズム模倣手段１１、回転操作実現手段１２、観測手段１３、及び、ノード数計算手段１４における演算や観測にかかわる制御、通信手段１５における量子ビットの送受信に関わる制御の動作の過程は、プログラムの形式でコンピュータ読み取り可能な記録媒体に記憶されており、このプログラムをコンピュータシステムが読み出して実行することによって、上記処理が行われる。ここでいうコンピュータシステムとは、ＯＳや周辺機器等のハードウェアを含むものである。
【００６５】
また、「コンピュータシステム」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものとする。
また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。さらに「コンピュータ読み取り可能な記録媒体」とは、インターネット等のネットワークや電話回線等の通信回線を介してプログラムを送信する場合の通信線のように、短時間の間、動的にプログラムを保持するもの、その場合のサーバやクライアントとなるコンピュータシステム内部の揮発性メモリのように、一定時間プログラムを保持しているものも含むものとする。また上記プログラムは、前述した機能の一部を実現するためのものであっても良く、さらに前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるものであっても良い。
【００６６】
以下に、量子通信路を用いて、手続ｄ（１をラベルとして持つホストの数を数える従来の方法）について説明する。この方法においては、システム全体をグラフ化し、ビューを生成する手順が含まれるため、まず、ビューの生成について説明する。これは、亀田恒彦、山下雅史，「分散アルゴリズム」，近代科学社，１９９４年、ｐ．１６９−１８０（参考文献２）によく記載されている。
【００６７】
［ビューの生成方法（参考文献２）］
各ホストｖが、必ずしもホスト毎に異なるとは限らないラベルを持っているとする。各ホストｖを節点（すなわち、分散システムにおけるノードに対応）、ホストｖ（節点）間の通信リンクを枝と見なすと、システム全体は、グラフと見なすことが出来る。このグラフをＧとする。以下、グラフＧの節点とホスト、及び、グラフＧの枝と通信リンクを、混乱の無い限り、区別せずに用いる。また、各ホストｖにおいて、通信リンクのポートは、各ホストｖで自然数によって独立に番号付けされているものとする。グラフＧの節点であるホストｖのポート番号付けを表す写像をσ[ｖ]で表すことにする。すなわち、σ[ｖ]は、他のホストｖに接続されているホストｖ内での該通信リンク（枝）に対応するポートの番号を表す。例えば、グラフＧの節点であるホストｖおよびホストｕに対して、枝である通信リンク(ｖ，ｕ)が存在したとき、ホストｖにおける通信リンク(ｖ，ｕ)に対応するポート番号は、σ[ｖ](ｖ，ｕ)で表される。
【００６８】
グラフＧの節点であるホストｖに対して、ホストｖのビューＴσ(ｖ)とは、次のように再帰的に定義される、節点（ホスト）と枝（通信リンク）にラベル付けされた、無限の高さを持つ根付き木である。
・ビューＴσ(ｖ)は、ホストｖに対応する根ｘを持つ。
・ホストｖに隣接するグラフＧの各ホストｖｉに対して、ビューＴσ(ｖ)は、節点ｘｉと、枝(ｘ，ｘｉ)を持つ。ただし、節点ｘｉは、ホストｖｉが持つ値をラベルとして持ち、枝(ｘ，ｘｉ)は、ｌ(ｖ，ｖｉ)をラベルとして持つ。ただし、ｌ(ｖ，ｖｉ)＝(σ[ｖ](ｖ，ｖｉ)，σ[ｖｉ](ｖ，ｖｉ))である。
・ホストｘｉは、ビューＴσ(ｖｉ)の根である。
【００６９】
例えば、図４に示される分散システムを考える。各ホストｖは、１から３までの自然数値でラベル付けされており、各ホストｖを接続する通信リンクの両端には、各ホストｖでのポート番号が記されている。例えば、値１をもつホストｖ１と値２を持つホストｖ２を接続する通信リンクは、値１をもつホストｖ１側ではポート番号１を持ち、値２を持つホストｖ２側では、ポート番号２を持っていることを表している。σを用いて表すと、σ[ｖ１](ｖ１，ｖ２)＝１及びσ[ｖ２](ｖ１，ｖ２)＝２となる。図４に示す分散システムにおいて、値１を持つホストｖ１のビューを、図５に示す。ビューの節点の深さは、根から距離（根から該節点に至るために通るべき枝の数）によって定義される。根は、深さ０とする。ビューの節点の内、深さ３以上の節点は図５では省略されている。ビューの節点に付けられた数値は、該節点に対応するホストｖのラベルを表す。また、ビューの枝の両端に付けられた数値は、図４と同様、両端のホストｖでのポート番号を表している。ビューの枝の両端の数値の内、根に近い数値から順に両端の数値の組をつくることで、枝のラベルを表すことができる。例えば、ｌ(ｖ１，ｖ２)＝(σ[ｖ１](ｖ１，ｖ２)，σ[ｖ２](ｖ１，ｖ２))＝(１，２)となる。ポート番号付けがσであるときの、ホストｖのビューをＴσ(ｖ)で表すものとする。
【００７０】
もし、二つのビューＴσ(ｕ)とビューＴσ(ｖ)が同型（節点と枝のラベルも含めて）ならば、この二つのビューは等しいということにすると(Ｔσ(ｕ)≡Ｔσ(ｖ)と表す)、グラフＧの節点の内、等しいビューを持つ節点同士を一つのグループとすることによグラフＧの節点集合を複数のグループに分割することができる。システム内で互いに同型でないビューの集合をГとする。深さ（ｎ−１）までの部分に、任意のホストｖに対応する節点が存在する。よって、
【００７１】
【数８】
0004593482.tif 000009
（以下、「Ｔσ2(n-1)(ｖ)」と記載）の中に、任意のホストｕに対する、深さ（ｎ−１）のビューが存在する。ただし、ビューＴσ(ｖ)の深さｒまでの部分を
【００７２】
【数９】
0004593482.tif 000010
（以下、「Ｔσr(ｖ)」と記載）
と表す。N. Norris, Universal covers of graphs: Isomoriphism to depth n-1 implies isomoriphism to a11 depths, Discrete Applied Mathematics, 56(1):61-74, 1995（参考文献３）によれば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【００７３】
【数１０】
0004593482.tif 000011
のとき、またそのときに限り成り立つ。よって、ビューＴσ2(n-1)(ｖ)を構築できれば、システム内の全ホストｖの互いに同型でないビューの集合Гの要素数|Γ|＝|Γn-1|を計算することができる。ただし、|Γ|は、Гの要素数を表す。等しいビューを持つ節点同士で作られた各グループの要素数は、互いに等しいから、この要素数ｃσは、ｎ／|Γ|で計算することができる。
【００７４】
[手続きｄ：１をラベルとして持つホスト数を数える方法（非特許文献２）]
（１）  各ホストｖは、後述する手続きＢによりビューＴσ2(n-1)(ｖ)を構築する。なお、本発明のアルゴリズムのステップ（２．２．２）の場合、各ホストｖは、自身の有するＲiの内容を、本発明のアルゴリズムのステップ（５．１）の場合、各ホストｖは、自身の有するｓを、自身のラベルとして用いる。
（２）  各ホストｖは、ビューＴσ2(n-1)(ｖ)を基に、１をラベルとして持つホストｖの数を計算する。具体的には、各ホストｖは、グループの要素数ｃσを後述する手続きＣにより求める。そして、ビューＴσ2(n-1)(ｖ)の節点の内、深さ（ｎ−１）以下にありラベル１を持つ各節点（ホストｖ）に対し、該節点（ホストｖ）自身を根とする深さ（ｎ−１）のビューで互いに同型でないビューの集合をΓ(1)とする。１をラベルとして持つホスト数は、ｃσ|Γ(1)|である。
【００７５】
次に、各ホストｖがビューを構築する手続きＢを説明する。手続きＢでは、隣接ホスト間で通信リンクを用いて、ビューの部分木を送信する必要がある。このとき、送信側では、ビューを２進符号化して、２進数の系列に変換し、受信側では、受信した２進数の系列から、元のビューを構築（復号化）しなければならない。ビューは、節点と枝にラベル付けされた根付き木であるが、この２進表現は、数多く知られている。ここでは、特定の２進表現方法に依存しないので、特に仮定は設けない。
【００７６】
[手続きＢ：深さｒのビューの構築法]
図６は、ホストｖにおける深さｒのビューを構築する手続きＢの動作を示すフローチャートである。
（１）  ｉに１を代入する（ステップＳｂ１）。ｉは現在のラウンドを意味する。なお、ラウンドとは、同期ネットワークにおいて全ホストｖが一斉に下記の（２）の演算を行い、（３）においてその結果を通信し合うことをいう。
（２）  各ホストｖは、ビューの根ｘを作り、これを
【００７７】
【数１１】
0004593482.tif 000012
（以下、「ビューＴσ0(ｖ)」と記載）とする（ステップＳｂ２）。
（３）  各ホストｖは、
【００７８】
【数１２】
0004593482.tif 000013
（以下、「ビューＴσｉ−１(ｖ)」と記載）を２進符号で表したものを、ホストｖに接続する全てのリンクから送信する（ステップＳｂ３）。
（４）  ｉを１増加させる（ステップＳｂ４）。
（５）  各ホストｖは、各リンクから受信したビューをｘの子のホストｖを根とする部分木にして、受信したビューより、深さが１だけ大きい新たなビューＴσｉ−１(ｖ)を構築する（ステップＳｂ５）。
（６）  ｉ−１＝ｒならば、終了する（ステップＳｂ６：ＹＥＳ）。ｉ−１＜ｒならば（ステップＳｂ６：ＮＯ）、（３）へ移る。ただし、ｒは、２（ｎ−１）あるいは（ｎ−１）以上の任意の値である。
【００７９】
３ラウンド目までの手続きＢの動作を、例を使って説明する。図７は、１ラウンド目の状況である。１ラウンド目では、各ホストｖは、ビューの根節点を作り、自己のラベルを、該根節点のラベルとする。図８は２ラウンド目の状況である。各ホストｖは、１ラウンド目で構築した根節点からなるビューを各通信リンクから送信する。各ホストｖは、受信後、１ラウンド目で構築した根節点の子として、受信した隣接ホストｖのビューを挿入する。その結果、深さ１のビューが構築される。同図においては、各ホストｖが構築した深さ１のビューを示している。枝（通信リンク）の両端には、両端のホストｖでのポート番号が記されている。同様に３ラウンド目には、各ホストｖは深さ２のビューを構築することができる。例えば、値１を持つホストｖ１の深さ２のビューは、図９のようになる。ただし、図９では、他のホストｖのビューは略記されている。この例の場合、節点のラベルは１〜３が付けられている。
【００８０】
次に、参考文献３によれば、Ｔσ(ｕ)≡Ｔσ(ｖ)は、
【００８１】
【数１３】
0004593482.tif 000014
のとき、またそのときに限り成り立つ。この性質を用いることにより、各ホストｖは、ビューＴσ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(ｖ)であっても、|Γ|が計算できることは言うまでもない。
【図面の簡単な説明】
【００８４】
【図１】本発明が適用される分散システムの例を示す図である。
【図２】ホストの構成例を示すブロック図である。
【図３】ホストの詳細な構成例を示すブロック図である。
【図４】ビューの生成方法を説明するための図である。
【図５】図３に示す分散システムにおけるホストのビューを示す図である。
【図６】深さｒのビューの構築（手続きＢ）におけるホストの動作を示すフローチャートである。
【図７】手続きＢの１ラウンド目の状況を説明するための図である。
【図８】手続きＢの２ラウンド目の状況を説明するための図である。
【図９】手続きＢの３ラウンド目の状況を説明するための図である。
【図１０】互いに同型でないビューの種類数|Γ|及び各グループの要素数ｃσの計算（手続きＣ）におけるホストの動作を示すフローチャートである。
【図１１】手続きＣの手順を説明するための図である。
【符号の説明】
【００８５】
ｖ、ｖ１、ｖ２、ｖ３、ｖ４、ｖ５、ｖ６…ホスト（ノード選択装置）
１０…リーダ選出手段
１１…古典アルゴリズム模倣手段
１２…回転操作実現手段
１３…観測手段
１４…ノード数計算手段
１５…通信手段
２０…ポート
【図１】
0004593482.tif 000015
【図２】
0004593482.tif 000016
【図３】
0004593482.tif 000017
【図４】
0004593482.tif 000018
【図５】
0004593482.tif 000019
【図６】
0004593482.tif 000020
【図７】
0004593482.tif 000021
【図８】
0004593482.tif 000022
【図９】
0004593482.tif 000023
【図１０】
0004593482.tif 000024
【図１１】
0004593482.tif 000025