量子ウオークの疑似周期性から抽出されるグラフ構造

点击翻译按钮获取中文摘要

量子ウォークの疑似周期性の問題から量子探索への応用を考える為, 周期性, 量子探索両側面からの研究を行った。量子探索問題については東北大学の吉野聖人氏と共に辺符号グラフ上において符号付けされた辺を探索するアルゴリズムの生成を果たし, 国際ジャーナルへの投稿が叶った。これは2021年に横浜国立大学の瀬川悦生氏と共に行った辺符号グラフ上の符号付きマッチングを探索するアルゴリズムの一般化である。瀬川氏との結果は辺符号グラフにおいて, 符号付けされた部分グラフがマッチングと呼ばれるグラフ構造をしていた場合, 固有値計算などにより, そのマッチング内の任意の辺を高速で見つけるものであったが, 此度の成果は, マッチングに限らず, 符号付き部分グラフが一般のグラフをなしていた場合でもその部分グラフ内の辺を高速で見つけるものである。これが叶った事により, 辺に符号を付けるというある種の摂動により探索問題をうまく働かせる事が出来ると分かった。量子探索はある特定の状態が漸近的に周期的な振る舞いをする事により, 有用性を付加できるため, 一つの疑似周期を与える事が出来た。また周期性に関してはGrover walkと呼ばれるグラフ構造に深く密接している量子ウォークにおいて考えた。特にGrover walkが周期的になる為にはどのようなグラフ構造が抽出されるかという逆問題的な視点から研究に臨み, 此度その周期が奇数になるものを全て列挙出来た。周期が奇数になるものはサイクルと呼ばれる非常にベーシックなもののみであると分かり, このような逆問題の解決にまた一つ近づいた。現在は国際ジャーナルに投稿中で, 校正したものを提出済である。