ニュース&イベント NEWS & EVENTS

2020.03.05 Thu UP

複雑ネットワーク上の高速空間探索の隠れた法則を発見
-実社会の複雑なネットワークの理解への量子力学的理論の応用-

研究の要旨とポイント
  • ●複雑なネットワーク内をより高速で効率的に探索する量子力学的理論を応用したアルゴリズムの開発に注目が集まっていますが、その根源となる数学的な法則は未だ多くが不明です。
  • ●複雑なネットワークの性質を理解するために、様々なフラクタル格子を用いた量子空間探索について検討した結果、これまで提案されていた数学的仮説が成立することを確認するとともに、新たな数学的仮説も提案することに成功しました。
  • ●数学的な証明による根本的な一般法則の解明は、ネットワークの構造や性質を理解するために欠かせず、新たなアルゴリズムの開発に重要な知見となります。

東京理科大学理学部第一部物理学科の佐藤嶺氏、二国徹郎教授、渡部昌平講師の研究グループは、フラクタル格子上の量子空間探索問題において、これまで一部のフラクタル図形に対してのみ提案されていた「スケーリング仮説」を、広範囲のフラクタル図形について数値計算により検証し、その仮説が成立することを確認するとともに、新たな数学的仮説も提案することに成功しました。

人間同士の関係から、オンラインネットワーク上のコンピュータの関係まで、また、植物や動物がつくるかたちや群れの中にも、実世界のありとあらゆる場所で、複雑なネットワークをみることができます。
これらのネットワークの構造や性質を理解するためには、ネットワーク上で目的とするターゲット(情報や、個別の端末など)に素早くたどり着くための、効率的な探索方法を開発することが重要です。その方法のひとつとして近年注目されているのが、「量子ウォーク」と呼ばれる量子力学的効果を使った量子空間探索です。

実在する複雑なネットワークには、スモールワールド性とフラクタル性というふたつの特徴がみてとれます。スモールワールド性とは、知り合いを数人たどれば世界中の誰とでも繋がれる現象のこと、フラクタル性とは、複雑に見える形状も、同じパターンの小さな図形の集合で表せるという数学的概念のことで、自己相似性ともいいます。
これまでの研究では、無数の小さな三角形からなるシェルピンスキー・ガスケットや、同じく四角形で描かれるシェルピンスキー・カーペットなど、一部のフラクタル格子(フラクタル性を持つ図形)を対象に、探索に役立ついくつかのスケーリング仮説が提案されてきました。スケーリング仮説とは、無数に拡がるフラクタル図形の一部(有限空間)について調べ、得られた情報をフラクタル格子全体(無限空間)に拡張して全体の性質を知ることができるのではないかという仮定のことです。

今回、研究グループは、スケーリング仮説を拡張されたシェルピンスキー・カーペットや、立方体に穴が開けられた形状のメンガーのスポンジなど、さまざまなフラクタル格子に適用して系統的な数値計算を行い、スケーリング仮説が実際に成立することを明らかにしました。
一般法則を示す仮説を広範囲のモデルで数値的に実証できたことにより、複雑なネットワーク上での探索を高速化・効率化するアルゴリズムの開発にも弾みがつくと期待されます。

【研究の背景】

二国教授らの研究グループは、これまでにもフラクタル格子上での量子力学的効果を使った効率的な空間探索の研究を行ってきました。その成果として、波動関数の最大振幅と最適探索時間に関するスケーリング仮説を提案しました。この仮説は、高精度に法則性を表現できるものであり、本研究では同仮説がより広範囲で成り立つかどうかの検証を行いました。

人間をはじめ多くの生物は、その形状や行動パターン、個体同士の関係性などにおいて多くの複雑なネットワークを形成しています。複雑なネットワークはフラクタル性を持つことがあり、その自己相似性のあるパターンの中で量子空間探索を行おうとする際、背後にどんな法則が潜んでいるかを知ることは、探索の効率化・高速化のために非常に重要です。

今回の研究では、シェルピンスキー・カーペットやメンガー・スポンジなどのフラクタル格子を用いて、量子ウォークを使用した量子空間探索を行いました。量子ウォークは、ランダムな動きを表現するランダムウォークの量子版です。ランダムウォークは物理学や統計学、数学などのほか、証券市場など幅広い分野で、複雑な物事をモデル化したり、検証したりするために使われています。また、量子ウォークは、量子コンピューター開発の基本理論にも寄与しています。

【研究の詳細】

研究グループは最初に、シェルピンスキー・ガスケットなど複数のフラクタル格子に対して先行研究で提唱されていた推定的な法則について、対象とするフラクタル格子の種類を変えて探索効率の検証を行いました。

高効率な空間探索とは、言い換えれば、目的とする答えやターゲットにたどり着くまでに必要な検索の問い合わせをする回数がより少なく済む検索アルゴリズムによる探索です。量子探索では、量子オラクルと呼ばれる量子的な検索を呼び出す回数が少ないほど、効率的な探索であると考えることができます。

先行研究では、フラクタル格子上の量子探索における量子オラクルの呼び出し回数は、フラクタル幾何学を特徴づけるスペクトル次元で表されることがシェルピンスキー・ガスケットなどで推定されていました。また、本研究グループは、昨年度、確率振幅でスケールされた量子オラクルの有効呼び出し回数も、フラクタル幾何学を特徴づけるユークリッド次元、フラクタル次元、スペクトル次元、スケーリング係数の組み合わせで表せるという仮説を提案していました。

今回の研究では、広範囲のフラクタル格子で量子探索を行い、スペクトル次元が2次元であることを境に、量子オラクルの呼び出し回数のスケーリング則が変化することを確認し、特に2次元の近くではスケーリング則に補正が必要であることも確認しました。
また、拡張シェルピンスキー・カーペットについて量子オラクルの有効呼び出し回数を調べたところ、シェルピンスキー・ガスケットやシェルピンスキー・カーペットにおける関係性とよく似ているものの、僅かに異なっていることが確認されました。また、フラクタル格子上の量子空間探索は、フラクタル幾何学を特徴づける有効数の組み合わせによって大きく左右されるらしいことも示唆されました。

多くの事実が確認された一方で、オラクル呼び出しの有効数のスケーリング則が、なぜ次元とスケーリング係数の組み合わせで表せるのかという根本的な問題は未だ解決しておらず、今後、数学的に証明する必要があります。

今回の成果について二国教授は「本研究は、社会現象と関係の深い複雑ネットワーク・物理学における量子力学・数学における自己相似性といった、広範囲の分野にまたがる学際的な研究であると言えます。将来的には量子力学的効果を使って、複雑ネットワーク上を高効率に探索する際の指標となることが期待されます」と述べています。
ネットワーク探索に重要な法則性を見出そうとするこのような理論研究は、複雑なネットワークが日常においてこれまで以上に重要となっている情報化社会において、ネットワークの構造を解明し、効率的な探索アルゴリズムの開発を促進すると期待されています。

※本研究成果は、アメリカ物理学会が発行する英文誌Physical Review Aに 2020年2月10日(米国時間)に掲載されました。また、編集部による注目論文(Editors' Suggestion)にも選ばれました。

※本研究は、日本学術振興会の科学研究費助成事業(JP18K03499、JP16K05504)の助成を受けて実施したものです。

【論文情報】

雑誌名 Physical Review A
論文タイトル Scaling hypothesis of a spatial search on fractal lattices using a quantum walk
著者 Rei Sato, Tetsuro Nikuni, and Shohei Watabe
DOI 10.1103/PhysRevA.101.022312

二国研究室のページ
研究室のページ:https://www.rs.kagu.tus.ac.jp/~nikuni/
二国教授のページ:https://www.tus.ac.jp/fac_grad/p/index.php?3b4d

東京理科大学について
東京理科大学:https://www.tus.ac.jp/
ABOUT:https://www.tus.ac.jp/info/index.html#houjin

当サイトでは、利用者動向の調査及び運用改善に役立てるためにCookieを使用しています。当ウェブサイト利用者は、Cookieの使用に許可を与えたものとみなします。詳細は、「プライバシーポリシー」をご確認ください。