量子情報：北海道大学大学院情報科学研究科情報エレクトロニクス専攻先端エレクトロニクス講座

　自律分散コンピューティングの世界での基本的な問題として匿名リーダー選挙問題というものがあります．多くの分散アルゴリズムでは処理の方法やデータへのアクセス許可を記述したTokenをあるコンピュータが振り出して，次々にリレーしていきます．一通りの処理が終わるまでは振り出し元は一つでないと不都合が起きるのでどれか決めておかなくてはなりません．振り出し元をリーダーといいますが，リーダーをどうやって決めるかが問題です．もちろんコンピュータに名前がついていれば何の問題もありませんが，どれも対等だと困ります．じゃんけんすればいいわけですが，あいこがでる可能性があります．古典コンピューティングでは有限時間内に確定的に決まらないことが知られています．

一方，量子ではERATO今井量子計算機構プロジェクトで一緒に仕事をしていた谷さんが有限時間内に 確定的に決まるアルゴリズムを見つけました．（S. Tani, H. Kobayashi, and K. Matsumoto, STACS2005; Lecture Notes in Computer Science 3404　(Springer, Berlin, 2005）, p. 581.） アルゴリズムを眺めているうちに，どうも２者の量子リーダー選挙なら実装できそうな気がしてきました． アルゴリズムで必要なCNOTゲートなどを線形光学素子で構成するのですが，面白いことに， 普通なら失敗として捨てなければならない事象もリーダーを決めるのには役立つことがわかりました． これまで線形光学素子を使った量子演算では失敗する確率が必ずあったのですが，このプロトコルでは確定的に実現できるのです！
最初のバージョンは偏光qubitで考えたのでエンタングルした光子対が２つ必要だったのですが，現精華大の王さんのアイディアで光子数qubit（真空が|0>、1光子状態が|1>）を使えばエンタングルしていない光子対１つで実装できることがわかりました．実験は連携大学院で筑波大から来ていた大久保君（現日立)が担当し、装置のセッティングが不完全でエラーが出る場合でも（実験ではこれが当たり前ですが) 通信量の観点から古典アルゴリズムを凌駕することを実証しました．

• Y. Okubo, W.-B. Wang, Y.-K. Jiang, S. Tani, and A. Tomita, Phys. Rev. A77, 032343 (2008). arXiv:0709.4314