組合わせ的離散構造に対する量子ウォークの共鳴現象による逆問題的アプローチ

定常状態に収束する量子ウォーク模型を構築した。特に、Grover walkにおける定常状態の特徴づけや、幾つかの場合における、定常状態に収束する、量子ウォーク版の混合時間の見積もりの証明を与えた。より具体的には、(1) Grover walkの拡張版であるSegedy walkにおいては、一定入力の場合、その定常状態は背後にある可逆ランダムウォークで誘導される電気回路における電流と、そのランダムウォークの定常測度の線形和で書き表されることを証明した。(2)定常状態における外部と内部グラフへの流出入の様子を表す散乱行列を明示的に与え、局所的な時間発展のダイナミクスがそのまま大域的な散乱に反映することを示し、内側のグラフの空間構造に依存せず、外部と接するグラフの表面にのみに依存することを証明した。(3) 一定入力と交代入力の場合、定常状態における内部グラフに蓄積するエネルギー(=量子ウォークの快適度)を提案し、与えられたグラフの量子ウォークで特徴づけられたある共通の性質をもつ部分フラフの属の個数を数え上げることにより、求められることを証明し、量子ウォークから動機づけられるグラフの特徴量を与えることができた。(4) グラフを有限パスに特化した場合の、定常状態の相対確率の極限定理を与えた。(5)定常状態に収束する量子探索アルゴリズムの提案をし、完全グラフの場合の収束速度と、瞬間的最大発見確率になる時刻の見積もりを導出した。(6) 光学偏光素子を用いた、この量子ウォークの実装法のデザインを構築した。

定常状態に収束する量子ウォーク模型を構築した。特に、Grover walkにおける定常状態の特徴づけや、幾つかの場合における、定常状態に収束する、量子ウォーク版の混合時間の見積もりの証明を与えた。より具体的には、(1) Grover walkの拡張版であるSegedy walkにおいては、一定入力の場合、その定常状態は背後にある可逆ランダムウォークで誘導される電気回路における電流と、そのランダムウォークの定常測度の線形和で書き表されることを証明した。(2)定常状態における外部と内部グラフへの流出入の様子を表す散乱行列を明示的に与え、局所的な時間発展のダイナミクスがそのまま大域的な散乱に反映することを示し、内側のグラフの空間構造に依存せず、外部と接するグラフの表面にのみに依存することを証明した。(3) 一定入力と交代入力の場合、定常状態における内部グラフに蓄積するエネルギー(=量子ウォークの快適度)を提案し、与えられたグラフの量子ウォークで特徴づけられたある共通の性質をもつ部分フラフの属の個数を数え上げることにより、求められることを証明し、量子ウォークから動機づけられるグラフの特徴量を与えることができた。(4) グラフを有限パスに特化した場合の、定常状態の相対確率の極限定理を与えた。(5)定常状態に収束する量子探索アルゴリズムの提案をし、完全グラフの場合の収束速度と、瞬間的最大発見確率になる時刻の見積もりを導出した。(6) 光学偏光素子を用いた、この量子ウォークの実装法のデザインを構築した。